Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am familiar with how the common ones technically work (BFS, DFS, Dijkstra, A*) but as far as their realistic benefits I don't quite see the need for them. Considering that, given the right heuristics, A* is more performant then why bother with any others?

share|improve this question
add comment

5 Answers

up vote 5 down vote accepted

I'm not very familiar with many of them but I have seen the usage of Dijkstra's algorithm not for pathfinding but for finding the nearest X to you. For example, what powerup is closest to you or what enemy is closest to you out of a group of enemies. So a "target nearest enemy" function often uses that.

share|improve this answer
add comment

I'm not an expert, but I can see Floyd-Warshall being better in some situations where you can afford to just precalculate all best paths up front and then reuse them.

share|improve this answer
add comment

What you are really listing are, rather, graph search algorithms, which are a part of Graph Theory. A* happens to be one which is optimized for "pathfinding" applications.

Why bother? Those algorithms are good for much, much more than simple pathfinding. In fact, there is an entire branch of mathematics devoted to studying graph theory and its properties.

BFS and DFS, in particular, are one of the most basic and powerful tools of graph theory application.

EDIT

It is of use to note that A* is rather weak when the shape and nature of the obstacles to be navigated around is dynamic and changing. In this case, it is usually a good bet to look into other pathfinding algorithms.

share|improve this answer
    
Good points, but graph theory and game development are not one in the same and my concern is of the latter. –  SnOrfus Jul 15 '10 at 3:31
1  
Graph Theory and game development are inherently tied. Most AI logics and decisions/choice algorithms are best modeled with graph theory; Physics engines optimize with graph theory, Procedural Generation has a lot intertwined with it, as well as many other aspects of game design that I have not even come to realize. The other algorithms might not be useful for pathfinding, but they will come up in other parts of your game. –  Justin L. Jul 15 '10 at 4:30
    
They may be useful in other parts of the game, but this question was specifically talking about pathfinding. –  Veehmot Jul 26 '11 at 4:34
add comment

A*, because of the closed and open lists, can be more memory intensive than a well-implemented Dijkstra. However both are probably processor-bound anyway so you might as well go for the flexibility of A*.

share|improve this answer
    
What do you mean by 'because of the closed and open lists'? Sans-heuristic, A* == Dijkstra –  SnOrfus Jul 15 '10 at 15:23
add comment

Zombies!!

Sometimes your AI shouldn't be so "I". For certain classes of MOBs (see above), the "Face where you want to go and Advance" algorithm is all you need.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.