Difference between revisions of "LavishNav:Pathfinders"
| Line 9: | Line 9: | ||
== Dijkstra's == | == Dijkstra's == | ||
| − | [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Dijkstra's] is the pathfinder of choice when there are overlaps in the coordinate system, or when looking for the shortest path (or distance) to many different locations. | + | [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Dijkstra's] is the pathfinder of choice when there are multiple coordinate systems (overlaps in the coordinate system), or when looking for the shortest path (or distance) to many different locations. |
This pathfinder is optimized such that subsequent searches with the same starting location can use the same information without recalculating for regions that have already been processed, and therefore it is highly efficient to continue to use the same starting location. | This pathfinder is optimized such that subsequent searches with the same starting location can use the same information without recalculating for regions that have already been processed, and therefore it is highly efficient to continue to use the same starting location. | ||
Latest revision as of 17:12, 24 October 2006
Introduction
What is a Pathfinder?
A pathfinder is a system of finding the shortest path from one location to another. LavishNav currently provides two systems that are useful in different circumstances.
A*
A* is generally the pathfinder of choice when there are no overlapping coordinate systems. In other words, if there is more than one 0,0,0 (or some other location) in the possible path, A* is not going to be preferable. This is because A* uses the distance from the goal in its estimation of the shortest path in order to find the shortest directed path to the goal.
Unlike Dijkstra's, this pathfinder is only optimized such that subsequent searches are not optimized unless both the start and destination locations remain the same. This is because the stored information is based on a path directed toward the previous destination.
Dijkstra's
Dijkstra's is the pathfinder of choice when there are multiple coordinate systems (overlaps in the coordinate system), or when looking for the shortest path (or distance) to many different locations.
This pathfinder is optimized such that subsequent searches with the same starting location can use the same information without recalculating for regions that have already been processed, and therefore it is highly efficient to continue to use the same starting location.
