extra/path-finding/path-finding-docs.factor

   1 ! Copyright (C) 2010 Samuel Tardieu.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: help.markup help.syntax ;
   4 IN: path-finding
   5
   6 { <astar> <bfs> <dijkstra> } related-words
   7
   8 HELP: astar
   9 { $description "This tuple must be subclassed and its method " { $link cost } ", "
  10   { $link heuristic } ", and " { $link neighbours } " must be implemented. "
  11   "Alternatively, the " { $link <astar> } " word can be used to build a non-specialized version." } ;
  12
  13 HELP: cost
  14 { $values
  15   { "from" "a node" }
  16   { "to" "a node" }
  17   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
  18   { "n" "a number" }
  19 }
  20 { $description "Return the cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
  21   { $snippet "to" } " is necessarily a neighbour of " { $snippet "from" } "."
  22 } ;
  23
  24 HELP: heuristic
  25 { $values
  26   { "from" "a node" }
  27   { "to" "a node" }
  28   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
  29   { "n" "a number" }
  30 }
  31 { $description "Return the estimated (undervalued) cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
  32   { $snippet "from" } " and " { $snippet "to" } " are not necessarily neighbours."
  33 } ;
  34
  35 HELP: neighbours
  36 { $values
  37   { "node" "a node" }
  38   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
  39   { "seq" "a sequence of nodes" }
  40 }
  41 { $description "Return the list of nodes reachable from " { $snippet "node" } "." } ;
  42
  43 HELP: <astar>
  44 { $values
  45   { "neighbours" "a quotation with stack effect ( node -- seq )" }
  46   { "cost" "a quotation with stack effect ( from to -- cost )" }
  47   { "heuristic" "a quotation with stack effect ( pos target -- cost )" }
  48   { "astar" "a astar tuple" }
  49 }
  50 { $description "Build an astar object from the given quotations. The "
  51   { $snippet "neighbours" } " one builds the list of neighbours. The "
  52   { $snippet "cost" } " and " { $snippet "heuristic" } " ones represent "
  53   "respectively the cost for transitioning from a node to one of its neighbour, "
  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."
  56 } ;
  57
  58 HELP: <bfs>
  59 { $values
  60   { "neighbours" "an assoc" }
  61   { "astar" "a astar tuple" }
  62 }
  63 { $description "Build an astar object from the " { $snippet "neighbours" } " 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."
  66 } ;
  67
  68 HELP: <dijkstra>
  69 { $values
  70   { "costs" "an assoc" }
  71 }
  72 { $description "Build an astar object from the " { $snippet "costs" } " assoc. "
  73   "The assoc keys are edges of the graph, while the corresponding values are assocs whose keys are "
  74   "the edges that can be reached and whose values are the costs to reach those edges. When used with "
  75   { $link find-path } ", this astar tuple will use the Dijkstra path finding algorithm which is "
  76   "a particular case of the general A* algorithm."
  77 } ;
  78
  79 HELP: find-path
  80 { $values
  81   { "start" "a node" }
  82   { "target" "a node" }
  83   { "astar" "a astar tuple" }
  84   { "path/f" "an optimal path from " { $snippet "start" } " to " { $snippet "target" }
  85     ", or f if no such path exists" }
  86 }
  87 { $description "Find a path between " { $snippet "start" } " and " { $snippet "target" }
  88   " using the A* algorithm."
  89 } ;
  90
  91 HELP: considered
  92 { $values
  93   { "astar" "a astar tuple" }
  94   { "considered" "a sequence" }
  95 }
  96 { $description "When called after a call to " { $link find-path } ", return a list of nodes "
  97   "which have been examined during the A* exploration."
  98 } ;
  99
 100 ARTICLE: "path-finding" "Path finding using the A* algorithm"
 101 "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
 102 "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
 103 "Make an A* object:"
 104 { $subsections <astar> <bfs> }
 105 "Find a path between nodes:"
 106 { $subsections find-path } ;
 107
 108 ABOUT: "path-finding"