Dijkstra's algorithm
From GMpedia.org Wiki
Contents |
[edit] Summary
Dijkstra's algorithm is useful in situations where you wish to find an optimal path without any time constraints. It is also a special case of A*, and is easier to understand and to implement than that algorithm.
[edit] Understanding
We assume, as in most pathfinding algorithms, that we are working in a node graph; nodes may be assigned costs, changing the outcome of the path. (if you have a simple grid design, every node is connected to four or eight others, in the cardinal/diagonal directions, with a cost of 1 each)
Imagine that instead of looking for just one perfect path from start to finish, you split your path each time you encounter a new node. When a path runs out of new places to go, it's discarded. Further, each path knows a certain property of the other paths: how much it cost to reach their final node. Or rather, each node is assigned a working cost based on the shortest path that's reached it.
The final piece of this puzzle is the order in which new nodes are searched: the lowest-cost node goes first. An initial exploration that is inefficient can be usurped by shorter paths.
The result, if shown graphically, is like an organism expanding: The first node explores the ones adjacent to it, and those explore their adjacent nodes likewise.
[edit] Differences between Dijkstra's algorithm and A*
A* adds prioritization of search: The next node to explore is evaluated based on a heuristic, which is usually the straight-line distance. So in addition to the current working cost, each node has their value - for the purposes of search - biased based on whether they're closer to the target or not.
The heuristic adds a tuning element to A*, making it more efficient(fewer nodes searched), but more complex.
[edit] Possibilities for optimization
Most optimizations lead to an implementation of A*. However, you can also cache some results and tell your path-finding objects to go follow the nearest available path, if you only need a few paths and they don't need to be the 100% optimal ones.
