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

6 Answers 6

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

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

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

If you're working with a uniform-weighted grid and don't need to worry about dynamic pathing, Jump-Point Search is an extremely efficient pathfinding algorithm. It's extremely fast, usually ten-to-thirty times as speedy as A*. It achieves this through symmetry reduction, which is a method by which empty spaces are ignored.

share|improve this answer

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

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
    
There's another interesting sense in which A* alternatives might be better for zombies. A* is great when you want one path from one start point to the nearest goal. But what if you have a whole horde of zombies all pathing toward the player? In some such situations, it may be more efficient to compute an exhaustive single-source shortest path tree for the area (pathfinding for all zombies at once), rather than re-computing branches of it repeatedly for each zombie tracing a similar route. –  DMGregory Oct 5 at 23:00

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.