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?
\$\begingroup\$
\$\endgroup\$
Add a comment
|
6 Answers
\$\begingroup\$
\$\endgroup\$
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.
answered Jul 15, 2010 at 0:25
\$\begingroup\$
\$\endgroup\$
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.
answered Jul 15, 2010 at 1:16
\$\begingroup\$
\$\endgroup\$
3
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.
-
\$\begingroup\$ Good points, but graph theory and game development are not one in the same and my concern is of the latter. \$\endgroup\$ Commented Jul 15, 2010 at 3:31
-
1\$\begingroup\$ 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. \$\endgroup\$ Commented Jul 15, 2010 at 4:30
-
\$\begingroup\$ They may be useful in other parts of the game, but this question was specifically talking about pathfinding. \$\endgroup\$– VeehmotCommented Jul 26, 2011 at 4:34
\$\begingroup\$
\$\endgroup\$
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.
\$\begingroup\$
\$\endgroup\$
1
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*.
-
\$\begingroup\$ What do you mean by 'because of the closed and open lists'? Sans-heuristic, A* == Dijkstra \$\endgroup\$ Commented Jul 15, 2010 at 15:23
\$\begingroup\$
\$\endgroup\$
1
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.
-
\$\begingroup\$ 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. \$\endgroup\$– DMGregory ♦Commented Oct 5, 2014 at 23:00