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?
Tell me more
×
Game Development Stack Exchange is a question and answer site for
professional and independent game developers. It's 100% free, no registration required.
|
|
|
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. |
|||
|
|
|
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. |
|||||||||
|
|
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. |
|||
|
|
|
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*. |
|||
|
|
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. |
|||
|
|
