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 HELP: astar
   7 { $description "This tuple must be subclassed and its method " { $link cost } ", "
   8   { $link heuristic } ", and " { $link neighbours } " must be implemented. "
   9   "Alternatively, the " { $link <astar> } " word can be used to build a non-specialized version." } ;
  10
  11 HELP: cost
  12 { $values
  13   { "from" "a node" }
  14   { "to" "a node" }
  15   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
  16   { "n" "a number" }
  17 }
  18 { $description "Return the cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
  19   { $snippet "to" } " is necessarily a neighbour of " { $snippet "from" } "."
  20 } ;
  21
  22 HELP: heuristic
  23 { $values
  24   { "from" "a node" }
  25   { "to" "a node" }
  26   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
  27   { "n" "a number" }
  28 }
  29 { $description "Return the estimated (undervalued) cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
  30   { $snippet "from" } " and " { $snippet "to" } " are not necessarily neighbours."
  31 } ;
  32
  33 HELP: neighbours
  34 { $values
  35   { "node" "a node" }
  36   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
  37   { "seq" "a sequence of nodes" }
  38 }
  39 { $description "Return the list of nodes reachable from " { $snippet "node" } "." } ;
  40
  41 HELP: <astar>
  42 { $values
  43   { "neighbours" "a quotation with stack effect ( node -- seq )" }
  44   { "cost" "a quotation with stack effect ( from to -- cost )" }
  45   { "heuristic" "a quotation with stack effect ( pos target -- cost )" }
  46   { "astar" "a astar tuple" }
  47 }
  48 { $description "Build an astar object from the given quotations. The "
  49   { $snippet "neighbours" } " one builds the list of neighbours. The "
  50   { $snippet "cost" } " and " { $snippet "heuristic" } " ones represent "
  51   "respectively the cost for transitioning from a node to one of its neighbour, "
  52   "and the underestimated cost for going from a node to the target. This solution "
  53   "may not be as efficient as subclassing the " { $link astar } " tuple."
  54 } ;
  55
  56 HELP: find-path
  57 { $values
  58   { "start" "a node" }
  59   { "target" "a node" }
  60   { "astar" "a astar tuple" }
  61   { "path/f" "an optimal path from " { $snippet "start" } " to " { $snippet "target" }
  62     ", or f if no such path exists" }
  63 }
  64 { $description "Find a path between " { $snippet "start" } " and " { $snippet "target" }
  65   " using the A* algorithm."
  66 } ;
  67
  68 HELP: considered
  69 { $values
  70   { "astar" "a astar tuple" }
  71   { "considered" "a sequence" }
  72 }
  73 { $description "When called after a call to " { $link find-path } ", return a list of nodes "
  74   "which have been examined during the A* exploration."
  75 } ;
  76
  77 ARTICLE: "astar" "A* algorithm"
  78 "The " { $vocab-link "path-finding" } " vocabulary implements a graph search algorithm for finding the least-cost path from one node to another." $nl
  79 "The " { $link astar } " tuple may be derived from and its " { $link cost } ", " { $link heuristic } ", and " { $link neighbours } " methods overwritten, or the " { $link <astar> } " word can be used to build such an object from quotations." $nl
  80 "Make an A* object:"
  81 { $subsections <astar> }
  82 "Find a path between nodes:"
  83 { $subsections find-path } ;
  84
  85 ABOUT: "astar"