Archived

This topic is now archived and is closed to further replies.

jimywang

algorithm to use for pathfinding

Recommended Posts

im implementing a pathfinder for my game at the moment.so far i have got a idea,how im gonna do it.waypoint pathfinding will be the ideal for my game.my problem is the choice of algorithm for that.A* or Dijkstra?personally,i think dijkstra will be easier to implement,cause i have learnd it on my lecture.however all the books i read told me A* is better at performance.Can anybody give me some suggestion please?thanks in advance.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Do the one that''s easier for you. Performance won''t be that necessary unless we''re talking 10,000+ units or something.

Share this post


Link to post
Share on other sites
In any case, A* is well documented, so I guess you should move to A*. If you already know Dijkstra''s algorithm, it should be pretty easy for you to understand A*

Share this post


Link to post
Share on other sites
Both have their uses. A* is better when you know where you are going (trying to get from point A to point B). Dijstra''s is better when you are looking for a location, but you don''t know where it is (find the closest key to the door and go get it, move to the closest resource gathering area, etc.

There really isn''t much difference between them, code-wise. A* just uses a heuristic whereas Dijkstra''s does not.

Share this post


Link to post
Share on other sites
The particular considerations when choosing between A* or Dijkstra''s are:

1) Dijkstra''s is useful when you want to store the shortest path between every pair of nodes (waypoints).

2) A* is useful when you want to find the shortest path between a single pair of nodes.

3) Dijkstra''s is typically computed offline.

4) A* is typically computed online.

5) The tradeoff for Dijkstra''s is the increased memory requirement of storing the shortest paths information.

6) The tradeoff for A* is the increased computational load during gameplay.

Many game applications employ A* on heirarchical navigational meshes (set of waypoints). A rough path can be found for minimal computational cost on a low resolution mesh, in order to get your agent moving in approximately the right direction. Over the course of several frames, the path can be refined by performing the computation on a higher resolution mesh. The use of navigational meshes is a type of skeletonisation technique for path planning. You might like to look at the literature for other such techniques.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Check out A* tutorial. It's really great and provides code examples.

Also, download this program from Shawn McLean. It shows you interactively how each algorithm works (A*, A* optimized, Dijkstra, etc...): Download PathPlanner. Unfortunately I don't remember where I got this, so I'm temporarily putting this on my website.

[edited by - ghost007 on March 31, 2004 9:29:25 AM]

[edited by - ghost007 on March 31, 2004 9:29:41 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Maybe this could be of interest depending on what kind of game you make:
http://graphics.cs.ucdavis.edu/~okreylos/Private/AlgorithmCorner/PathFinding.html

Share this post


Link to post
Share on other sites