#### Archived

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

# algorithm to use for pathfinding

This topic is 5224 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
Do the one that''s easier for you. Performance won''t be that necessary unless we''re talking 10,000+ units or something.

##### 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 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 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 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 on other sites
Maybe this could be of interest depending on what kind of game you make:
http://graphics.cs.ucdavis.edu/~okreylos/Private/AlgorithmCorner/PathFinding.html

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
19
5. 5

• 14
• 26
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631771
• Total Posts
3002253
×