1 ! Copyright (C) 2010 Samuel Tardieu.
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: assocs help.markup help.syntax math sequences ;
6 { <astar> <bfs> <dijkstra> } related-words
9 { $description "This tuple must be subclassed and its method " { $link cost } ", "
10 { $link heuristic } ", and " { $link neighbors } " must be implemented. "
11 "Alternatively, the " { $link <astar> } " word can be used to build a non-specialized version." } ;
17 { "astar" "an instance of a subclassed " { $link astar } " tuple" }
20 { $description "Return the cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
21 { $snippet "to" } " is necessarily a neighbor of " { $snippet "from" } "."
28 { "astar" "an instance of a subclassed " { $link astar } " tuple" }
31 { $description "Return the estimated (undervalued) cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
32 { $snippet "from" } " and " { $snippet "to" } " are not necessarily neighbors."
38 { "astar" "an instance of a subclassed " { $link astar } " tuple" }
39 { "seq" "a sequence of nodes" }
41 { $description "Return the list of nodes reachable from " { $snippet "node" } "." } ;
45 { "neighbors" { $quotation ( node -- seq ) } }
46 { "cost" { $quotation ( from to -- cost ) } }
47 { "heuristic" { $quotation ( pos target -- cost ) } }
50 { $description "Build an astar object from the given quotations. The "
51 { $snippet "neighbors" } " one builds the list of neighbors. The "
52 { $snippet "cost" } " and " { $snippet "heuristic" } " ones represent "
53 "respectively the cost for transitioning from a node to one of its neighbor, "
54 "and the underestimated cost for going from a node to the target. This solution "
55 "may not be as efficient as subclassing the " { $link astar } " tuple."
63 { $description "Build an astar object from the " { $snippet "neighbors" } " assoc. "
64 "When used with " { $link find-path } ", this astar tuple will use the breadth-first search (BFS) "
65 "path finding algorithm which is a particular case of the general A* algorithm."
73 { $description "Build an astar object from the " { $snippet "costs" } " assoc. "
74 "The assoc keys are edges of the graph, while the corresponding values are assocs whose keys are "
75 "the edges that can be reached and whose values are the costs to reach those edges. When used with "
76 { $link find-path } ", this astar tuple will use the Dijkstra path finding algorithm which is "
77 "a particular case of the general A* algorithm."
85 { "path/f" "an optimal path from " { $snippet "start" } " to " { $snippet "target" }
86 ", or f if no such path exists" }
88 { $description "Find a path between " { $snippet "start" } " and " { $snippet "target" }
89 " using the A* algorithm."
95 { "considered" sequence }
97 { $description "When called after a call to " { $link find-path } ", return a list of nodes "
98 "which have been examined during the A* exploration."
101 ARTICLE: "path-finding" "Path finding using the A* algorithm"
102 "The " { $vocab-link "path-finding" } " vocabulary implements a graph search algorithm for finding the least-cost path from one node to another using the A* algorithm." $nl
103 "The " { $link astar } " tuple may be derived from and its " { $link cost } ", " { $link heuristic } ", and " { $link neighbors } " methods overwritten, or the " { $link <astar> } " or " { $link <bfs> } " words can be used to build a new tuple." $nl
105 { $subsections <astar> <bfs> }
106 "Find a path between nodes:"
107 { $subsections find-path } ;
109 ABOUT: "path-finding"