Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Solution for pathfinding on a dynamic world. Preferably free.

Discussion in 'Scripting' started by AlanGameDev, Nov 24, 2015.

  1. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    Hello there.

    I need to implement pathfinding on a dynamic world. I can't simply use avoidance because the 'floors' aren't static, I'm thinking about some kind of configurable waypoint system, but I didn't find any that works with dynamic points so far.

    Is there a solution out there or should I just implement my own?

    I don't think something like UnitySteer would work in my case.

    Thanks in advance.

    P.S.: I'm totally broke atm, so no pricey stuff for me. Libre is preferred.
     
  2. jister

    jister

    Joined:
    Oct 9, 2009
    Posts:
    1,749
    unity's NavMesh? otherwise i like Astar as a pathfinding algorithm.
     
  3. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    lordofduct likes this.
  4. CaoMengde777

    CaoMengde777

    Joined:
    Nov 5, 2013
    Posts:
    813
    RAIN , it can generate navmeshes at runtime ,its a thing lol
    http://rivaltheory.com/rain/

    oooh nevermind lol, yeah it doesnt have dynamic object avoidance ...
    i was thinking about like procedurally created levels, works for that ... sorta, kinda slow generating the navmeshes seems itd make a long loading time.. but i was having a large level so
     
  5. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    Great project, I use it myself.

    Only downside is that the runtime updating (Graph Updates in this comparison) is a pro only feature:
    http://arongranberg.com/astar/freevspro

    Definitely worth its price tag though. I really like the project a lot.
     
  6. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    Ok, thanks guys, I really appreciate your help, but that's totally not what I'm asking for...

    Perhaps I didn't express myself clearly, but I need some kinda pf in point-based graph system that allows the points to be fully 'dynamic', for example, the waypoints could be components attached to GameObjects that can be moved (including by physics engine). Navmesh is somewhat out of question here.

    Preferably, for obvious performance reasons, the system should support two types of points: static and dynamic. Dynamic would be fully 'movable' around at runtime, while static can only be enabled/disabled and aren't dependent on unity objects.

    Only if you could bake the built-in navmesh at runtime, I could use it for the 'static' parts and connect it to a dynamic point-based system which is easy enough to roll out.
     
  7. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
  8. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    I never asked which algorithm to use. The problem is achieving a 'dynamic' graph.
    And btw, a* search, besides being by far the most popular algorithm, sucks badly :p.
     
  9. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    So you wanted a already created solution.

    Which we shared.

    If you mean that you wanted an already created project that has dynamic graph generation at runtime that does NOT use A*. Well, specify that.

    I'd love to also hear your reasons for why A* "sucks badly :p".
     
  10. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    I'm not discussing algorithms at all... did I even mention something about that?

    I clearly stated that I need a "solution for pathfinding on a dynamic world", and also I asked about "configurable waypoint system" and "dynamic points". None of the answers so far addressed any of those requirements.

    The built-in navmesh doesn't even work on runtime, and the Aron asset, although being very good AAA-quality stuff, doesn't have what I need.

    RAIN would work for a few navmesh updates I think, but I'm talking about fully dynamic stuff, so I need a point-based system that uses the actual positions of the dynamic points for calculation instead of using static 'baked' data.
     
  11. hippocoder

    hippocoder

    Digital Ape

    Joined:
    Apr 11, 2010
    Posts:
    29,723
    No, it doesn't :)

    And yes, try http://arongranberg.com/astar/freevspro

    Seems to me you have this idea how things should work and want people to keep suggesting until the inevitable conclusion: you using A*
     
  12. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    That's because you didn't see those new (not really) algorithms that takes line of sight into account (any angle pf) :p. Then you'll inevitably agree that plain a* sucks terribly :p.

    Nope, Aron's library will surely not work for me. Sure you can update the graph on-the-fly but certainly not at 10hz or something.

    By the way, I've decided to go with a flat world so I can use the built-in navmesh system and carving objects for procedural stuff, and for the dynamic parts I'm rolling out my own solution. The hard part is going to be somehow connecting the static navmesh to my waypoint-based solution, I'll have to create special nodes to 'link' both navigation systems.
     
  13. Ryiah

    Ryiah

    Joined:
    Oct 11, 2012
    Posts:
    20,943
    How will you know if you don't actually verify it?
     
  14. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    I've used the Aaron's A* library and it's not intended for dynamic nodes. His solution, along with all the other I've tried/read about, are only intended for 'static' of "mostly-static" nodes.
    Imagine a 'net' where the knots are always moving around, changing their distances all the time.
     
  15. Ryiah

    Ryiah

    Joined:
    Oct 11, 2012
    Posts:
    20,943
    Okay. I don't know any others you've tried, but glancing over the store there is an asset that used to be paid but went free when the developer got busy with other things. I don't know how out of date it is but it mentions dynamic updates.

    https://www.assetstore.unity3d.com/en/#!/content/6385
     
  16. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    Thank you! I know about that asset but never tried it. I think the 'dynamic updates' features is not exactly what I want though, I need the pathfinder to 'get' the distances on-the-fly (pretty much by calling Vector3.Distance), and I'm pretty sure that pf solution simply 're-caches' all the distances on a given API call, so not exactly the same thing, but thanks for the recommendation, really appreciated!
     
  17. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    Well this thread turned weird. A* is a graph search algorithm. And for most standard graph searches, it's best in class. It's mathematically proven that any other solution to the graph search problem sucks at least as much as A*.

    The question you are asking is how to build the graph that's modifiable at runtime. There are several ways to approach this.

    The simplest is simply to use GameObjects for nodes and raycast between them on a regular basis to check for passibility. It's crude and expensive, but it will work for simple games. As the number of nodes goes up you will want an intelligent data structure that reduces the number of passability checks.

    Another approach would be to build a traditional navigation mesh in pieces. As objects move about you can add and remove pieces from the mesh. Or you can do this with links between pieces.

    You can also generate the graph each time you need to use it. I've seen point cloud methods that do this.
     
    nra and AlanGameDev like this.
  18. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    Finally someone who understands me! :D Yay!

    Of course a* is the best in class (well, not in all cases) IF (and that's a huge IF) you're talking about finding the shortest path without deviating from the links you provide it. For all your non-robotic pathfinding needs these 'any angle view-enhanced pathfinders' are your new best friend! :) lol!

    Also, in my case I don't need to raycast too much, probably only at the beginning since it's not possible to make new passable connections between other nodes in the game I'm doing.

    Thank you.
     
  19. jister

    jister

    Joined:
    Oct 9, 2009
    Posts:
    1,749
    or I'm still not getting how dynamic your world is, or you are not getting how easily A* could be used dynamically just by updating your list of accessible nodes? i use it in a dynamic world where you can build and destroy much about anything. i just update my list every time something changes in the world (or chunk)
     
    Kiwasi likes this.
  20. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    It's a crazy moving world where crazy minions go about. Lol! :D

    In all seriousness, I'm sorry for my totally lacking communication skills, I'm not talking about a destructible world. For that I'd just use a navmesh/grid-based solution. Think about constantly moving nodes.

    Say you have a,b,c,d, and a-b-c-d-a links, say you're at a and want the path to c, at a given moment the best path is a-d-c, then stuff moved and you calc again, so now the best path is a-b-c, because b moved closer to a and c than d, so now you're going the other way around, and let's say b and d keep moving so on the next calc the path is always the other, and they keep like that so you can't reach c from a because the shortest path keep changing so you keep turning around and going the other way only to realize the other way is shorter now :p.
     
  21. jister

    jister

    Joined:
    Oct 9, 2009
    Posts:
    1,749
    ok i see thanks for explaining.
    still a good sorting of open and closed lists with a nice algorithm would also get you there in the end i think... maybe :p
    anyway if you're still looking and are up for some experimentation, have a look at neural networks or genetic algorithms,
    sound like something they could handle, and they are fun working with.
     
    AlanGameDev likes this.
  22. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    Then its just A* with nodes that can calculate their own neighbours each time they are queried. A simple method would be to use a GameObject with a trigger collider for each node. Each time another node enters the trigger area then its added to the neighbours list. Each time it leaves its removed. A* will automatically calculate a best path.

    If you need a time based solution this can also be achieved with A* (I'm not sure the heuristic I'm proposing is admissible, Dijkstra's might end up being the better algorithm). Its a bit more complex, each node will need to be able to predict its own position in the future, as well as which nodes will be its neighbours in the future. Then you need to ensure each node also has itself as a neighbour, thus allowing your graph search to perform a 'wait' action.

    I would suggest using time to reach the node as your g cost and the time to cross the straight line distance to the end node as your h cost. Doing things this way means that you can calculate the neighbours at the time of g cost, you don't need to have a separate variable to measure travel time.
     
    AlanGameDev likes this.
  23. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    Yes, precisely! I'm not talking algorithms though. Imho, basically they're just the piece of code returning the path/nodes_list. It hardly matter which one you're using... A* (basis for most other advanced algorithms) is just Dijkstra with heuristics, and Dijkstra is basically brute-force first-result search, so, it gets confusing. Lol :D.

    That trigger solution no me gusta :p... Linking the nodes is not going to be a problem though. I'm surely going to use GameObjects for the moving nodes though. That's surely going to be easy enough, but if there was a ready-to-use solution I would rather use it. It seems there isn't... I mean, there are the usual suspects out there, but none of them works with moving objects, so I'd have to keep updating the nodes manually what surely isn't efficient nor straightforward.

    Thank you guys for your help. Really appreciate it. Even though the first replies weren't very helpful I'm sure they were full of good intentions so thank you very much guys!
     
    Last edited: Nov 27, 2015
  24. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    You've seen all of the prebuilt systems out there in this thread. What you are asking for is pretty specific, and will have to be custom built for your game.

    And without real details of your game we can't provide any more specific advice.

    Best of luck with this.
     
  25. AlanGameDev

    AlanGameDev

    Joined:
    Jun 30, 2012
    Posts:
    437
    Thank you. I've managed to put something together. I'm having trouble linking it with the built-in navmesh thingy, but I'm sure I can go on by myself from now on. Perhaps I'm going to use my solution for everything... in any case, it's kinda solved. Thanks everyone.