2010-03-06 02:48:39 -05:00
! Copyright (C) 2010 Samuel Tardieu.
! See http://factorcode.org/license.txt for BSD license.
2014-05-24 20:16:26 -04:00
USING: assocs help.markup help.syntax math sequences ;
2010-03-23 04:52:51 -04:00
IN: path-finding
2010-03-06 02:48:39 -05:00
2010-11-11 04:59:05 -05:00
{ <astar> <bfs> <dijkstra> } related-words
2010-03-23 05:24:01 -04:00
2010-03-08 14:26:36 -05:00
HELP: astar
{ $description "This tuple must be subclassed and its method " { $link cost } ", "
{ $link heuristic } ", and " { $link neighbours } " must be implemented. "
"Alternatively, the " { $link <astar> } " word can be used to build a non-specialized version." } ;
HELP: cost
{ $values
{ "from" "a node" }
{ "to" "a node" }
{ "astar" "an instance of a subclassed " { $link astar } " tuple" }
2014-05-24 20:16:26 -04:00
{ "n" number }
2010-03-08 14:26:36 -05:00
}
{ $description "Return the cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
{ $snippet "to" } " is necessarily a neighbour of " { $snippet "from" } "."
} ;
HELP: heuristic
{ $values
{ "from" "a node" }
{ "to" "a node" }
{ "astar" "an instance of a subclassed " { $link astar } " tuple" }
2014-05-24 20:16:26 -04:00
{ "n" number }
2010-03-08 14:26:36 -05:00
}
{ $description "Return the estimated (undervalued) cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
{ $snippet "from" } " and " { $snippet "to" } " are not necessarily neighbours."
} ;
HELP: neighbours
{ $values
{ "node" "a node" }
{ "astar" "an instance of a subclassed " { $link astar } " tuple" }
{ "seq" "a sequence of nodes" }
}
{ $description "Return the list of nodes reachable from " { $snippet "node" } "." } ;
2010-03-06 02:48:39 -05:00
HELP: <astar>
{ $values
2014-05-18 23:09:10 -04:00
{ "neighbours" { $quotation ( node -- seq ) } }
{ "cost" { $quotation ( from to -- cost ) } }
{ "heuristic" { $quotation ( pos target -- cost ) } }
2010-11-14 22:29:37 -05:00
{ "astar" astar }
2010-03-06 02:48:39 -05:00
}
{ $description "Build an astar object from the given quotations. The "
{ $snippet "neighbours" } " one builds the list of neighbours. The "
{ $snippet "cost" } " and " { $snippet "heuristic" } " ones represent "
"respectively the cost for transitioning from a node to one of its neighbour, "
2010-03-08 14:26:36 -05:00
"and the underestimated cost for going from a node to the target. This solution "
"may not be as efficient as subclassing the " { $link astar } " tuple."
2010-03-06 02:48:39 -05:00
} ;
2010-03-23 05:24:01 -04:00
HELP: <bfs>
{ $values
2010-11-14 22:29:37 -05:00
{ "neighbours" assoc }
{ "astar" astar }
2010-03-23 05:24:01 -04:00
}
{ $description "Build an astar object from the " { $snippet "neighbours" } " assoc. "
"When used with " { $link find-path } ", this astar tuple will use the breadth-first search (BFS) "
"path finding algorithm which is a particular case of the general A* algorithm."
} ;
2010-11-11 04:59:05 -05:00
HELP: <dijkstra>
{ $values
2010-11-14 22:29:37 -05:00
{ "costs" assoc }
{ "astar" astar }
2010-11-11 04:59:05 -05:00
}
{ $description "Build an astar object from the " { $snippet "costs" } " assoc. "
"The assoc keys are edges of the graph, while the corresponding values are assocs whose keys are "
"the edges that can be reached and whose values are the costs to reach those edges. When used with "
{ $link find-path } ", this astar tuple will use the Dijkstra path finding algorithm which is "
"a particular case of the general A* algorithm."
} ;
2010-03-06 02:48:39 -05:00
HELP: find-path
{ $values
{ "start" "a node" }
{ "target" "a node" }
2010-11-14 22:29:37 -05:00
{ "astar" astar }
2010-03-06 02:48:39 -05:00
{ "path/f" "an optimal path from " { $snippet "start" } " to " { $snippet "target" }
", or f if no such path exists" }
}
{ $description "Find a path between " { $snippet "start" } " and " { $snippet "target" }
2010-03-23 04:30:48 -04:00
" using the A* algorithm."
2010-03-06 02:48:39 -05:00
} ;
HELP: considered
{ $values
2010-11-14 22:29:37 -05:00
{ "astar" astar }
2014-05-24 20:16:26 -04:00
{ "considered" sequence }
2010-03-06 02:48:39 -05:00
}
{ $description "When called after a call to " { $link find-path } ", return a list of nodes "
"which have been examined during the A* exploration."
} ;
2010-03-12 05:36:43 -05:00
2010-03-23 05:24:01 -04:00
ARTICLE: "path-finding" "Path finding using the A* algorithm"
"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
"The " { $link astar } " tuple may be derived from and its " { $link cost } ", " { $link heuristic } ", and " { $link neighbours } " methods overwritten, or the " { $link <astar> } " or " { $link <bfs> } " words can be used to build a new tuple." $nl
2010-03-12 05:36:43 -05:00
"Make an A* object:"
2010-03-23 05:24:01 -04:00
{ $subsections <astar> <bfs> }
2010-03-12 05:36:43 -05:00
"Find a path between nodes:"
{ $subsections find-path } ;
2010-03-23 05:24:01 -04:00
ABOUT: "path-finding"