Tads-3 Path Finders 1.0 Steve Breslin, 2004 steve.breslin@gmail.com ==**== This archive should contain the following 9 files: BreadthFirst.t (standard breadth-first search) DoubleBreadth.t (bi-directional breadth-first search) Floyd.t (standard Floyd-Warshall algorithm) Dijkstra.t (also includes the A* algorithm) BinaryHeap.t (implements Dijkstra/A*'s priority queue) RmPthFnd.t (supports path finding between rooms in normal game) pf_test.t (tests & demonstrates the use of these algorithms) pf_test.t3m (the Tads-3 makefile for pf_test.t) readme.txt (this file) The two "breadth" searches and Floyd are "uninformed" search algorithms, meaning that they do not use heuristics to direct their searches. Dijkstra can be easily modified into an informed search; because the necessary heuristic is graph-specific, we simply provide the standard Dijkstra algorithm by default, but we make it easy for you to add your own heuristics. The BinaryHeap file is for use with Dijkstra.t -- it provides the proiority queue. To learn how to use these algorithms in your project, take a look at RmPthFnd.t and pf_test.t -- they demonstrate everything you'll need to know. There are a number of other search algorithms, but the above tend to be the most useful. If you would like to see another algorithm here, please let me know. ==**== Terminology: node: a point or location on the graph. If you are looking for a shortest path between rooms, the nodes of the graph represent rooms. edge: a connection between nodes. In a "room graph," the edges are the travel connections between rooms. (un)weighted: a graph is weighted if the edges do not have the same traversal cost. If the edges all have the same traversal cost, the graph is unweighted. (un)directed: a graph is undirected if the edges always point both ways. But if for example you have one-way travel connectors, the "room graph" is directed. ==**== Comparison: Either Breadth-First or Double-Breadth is best in most Tads-3 applications. - If your graph is undirected, Double-Breadth is best. - If the graph is directed, Breadth-First is best. - If you have a weighted graph, you should use either Floyd or Dijkstra. Floyd is best for precalculating information about the graph -- and this can also be useful when your graph is unweighted. If the graph is large and changes frequently, Floyd's recalculations will slow things down; in this case, either of the Breadth searches will serve you well, or if the graph is weighted and changes frequently, Dijkstra is best. If your graph is conducive to a heuristic for estimating the distance between nodes, A* is ideal. ==**== Breadth-First ============= Breadth-First is a very fast and very simple algorithm for finding the shortest path between two points in an *unweighted* graph: it finds the path between two points with the least number of nodes between. It does this by visiting all the nodes connected to the start node, then all the nodes connected to those nodes, and so on, until the target node has been reached. The shortest path is then built backwards along the path it took to find the target node. If your graph is unweighted, Breadth-First is somewhat faster than Dijkstra. If your graph is also undirected, Double-Breadth is an even better option. The time complexity is linear in the size of the graph or tree searched: i.e., O(b^d) where b is the branching factor and d is the depth of the shallowest solution. Double-Breadth ============== By far the fastest uninformed search algorithm for unweighted and undirected graphs. Altough the algorithm is more complicated than the straightforward Breadth-Search, the computation time is much faster on average. It performs a Breadth-Search from both the starting node and the target node. Every time a node is added, it checks if the two searches have yet intersected; if so, a shortest path has been found: this is built by tracking from the intersection node backward to the start-node and forward to the target-node. The purpose of this complication is that the shortest-path is normally discovered with fewer nodes visited: two smaller search patterns are normally better than one larger search pattern. It is of course possible to make a graph for which a single-breadth search visits fewer nodes, but it is fairly clear that double-breadth should visit fewer nodes in most cases. Please note that the calculation time per node is very slightly higher, compared with Breadth-First. The time complexity is much smaller than breadth-first: O(b^(d/2)). Floyd ===== The Floyd-Warshall algorithm finds the shortest distance between all nodes and all other nodes on a graph, whether or not the graph is weighted or directed. Optionally, Floyd can also find the shortest paths between all nodes. Because it works on weighted graphs, it doesn't calculate the path that passes through the fewest nodes, but instead one that passes along the shortest combined edge-distance. (If the graph is unweighted, this amounts to the same thing.) The Floyd algorithm is much simpler in design than Dijkstra, and because it can easily store at compile-time all shortest paths and distances in matrix-like lookup tables (for easy extraction), the runtime cost of calculating shortest paths and shortest distances is comparatively negligible. However, changes in the graph (e.g., certain changes in "game state") necessitate a recalculation. Depending on how frequently this happens relative to how frequently you need to calculate shortest-paths, you may consider using Dijkstra or a combination of Floyd and Dijkstra. Alternatively, if the graph is unweighted, you might be better served by Breadth-First, or if the graph is undirected, Double-Breadth. As a rule of thumb, if it is useful to cache shortest-paths, Floyd is probably the best choice. (Floyd is a great heuristic for use with A*!) The algorithm: - Begin with a matrix (or matrix-like lookup-table) such that the value of matrix[i,j] is the distance between node i and node j. (This "distance table," the dTable below, only initializes with directly-connected nodes; unconnected or indirectly-connected nodes are at infinite distance at this stage.) For pathfinding in addition to distance finding, populate a similar "path table" (the pTable below). - Expand the matrix to account for indirectly-connected nodes, by doing: for (local k = 1; k <= nodeCount ; k++) { for (local i = 1; i <= nodeCount ; i++) { for (local j = 1; j <= nodeCount; j++) { if (dTable[[i, k]] + dTable[[k, j]] < dTable[[i, j]]) { dTable[[i, j]] = dTable[[i, k]] + dTable[[k, j]]; pTable[[i, j]] = pTable[[k, j]]; } } } } The time complexity is O(n^3) where n is the number of nodes. Towards 100 nodes this becomes pretty steep (on a modern PC). A* (Dijkstra) ============= Like Floyd, the A*/Dijkstra algorithm finds the shortest path between a start-node to a target node on a directed, weighted graph. Unlike Floyd, A*/Dijkstra only calculates for a single pair of nodes, the start-node and end-node, whereas Floyd calculates for all pairs of nodes. The algorithm: - Each node has: 1) a distance from the start node, 2) A pointer to its parent or predecessor node, 3) A state: open or closed. - Begin with the start-node, and add the nodes directly connected to the open vector. - Search the open vector to find the node with the shortest distance to the start node plus the estimated distance to the target node<1>. Mark it as closed, and add the nodes directly connected to the open vector. Repeat until the target node is found. - (When the target node is reached, the total cost of the path is the cost value in the cost value field in the target node.) - To find the route taken to achieve this shortest path, we simply work back from the pointers in the nodes, starting with the target node. The complexity of A* depends on the heuristic, which is graph-specific. The time complexity of Dikjstra depends on the details of a given implementation, but it is normally of the order of O(e + n log n), where n=nodes and e=edges. (Or O(n^2) in the worst case.) Should we repeat this process to find the path between all nodes to all other nodes on the graph (which is what Floyd accomplishes), we would have a time complexity of O(n^3) -- the same as Floyd, though in this case Dijkstra is much less direct than Floyd. <1> In the case of Dijkstra, we simply choose the node with the shortest distance from the start node, without trying to determine the distance from that node to the target node. ==**== For more information about Tads-3, visit: http://www.tads.org