From e69ff99cd28be0e73c85ae7653a556e4065d0007 Mon Sep 17 00:00:00 2001
From: David Thompson <dthompson2@worcester.edu>
Date: Wed, 3 Oct 2018 07:45:39 -0400
Subject: doc: Document the path finding API.

---
 doc/api.texi | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 75 insertions(+), 1 deletion(-)

(limited to 'doc')

diff --git a/doc/api.texi b/doc/api.texi
index a2e546d..4c34cf4 100644
--- a/doc/api.texi
+++ b/doc/api.texi
@@ -1,6 +1,6 @@
 @menu
 * Kernel::                      The fundamental components.
-* Math::                        Linear algebra and more.
+* Math::                        Linear algebra, spatial partitioning, and more.
 * Graphics::                    Eye candy.
 * Scripting::                   Bringing the game world to life.
 @end menu
@@ -368,6 +368,7 @@ detection.
 * Quaternions::                 Rotations about an arbitrary axis.
 * Easings::                     Easing functions for interesting animations.
 * Bezier Curves::               Cubic Bezier curves and paths in 2D space.
+* Path Finding::                Generic A* path finding.
 @end menu
 
 @node Basics
@@ -1184,6 +1185,79 @@ Modify the 2D vector @var{dest} in-place to contain the coordinates
 for @var{bezier} at @var{t}.
 @end deffn
 
+@node Path Finding
+@subsection Path Finding
+
+Most game worlds have maps.  Often, these games have a need to move
+non-player characters around in an unscripted fashion.  For example,
+in a real-time strategy game, the player may command one of their
+units to attack something in the enemy base.  To do so, the unit must
+calculate the shortest route to get there.  It wouldn't be a very fun
+game if units didn't know how to transport themselves efficiently.
+This is where path finding algorithms come in handy.  The
+@code{(chickadee math path-finding)} module provides a generic
+implementation of the popular A* path finding algorithm.  Just add a
+map implementation!
+
+The example below defines a very simple town map and finds the
+quickest way to get from the town common to the school.
+
+@example
+(define world-map
+  '((town-common . (town-hall library))
+    (town-hall . (town-common school))
+    (library . (town-common cafe))
+    (school . (town-hall cafe))
+    (cafe . (library school))))
+(define (neighbors building)
+  (assq-ref town-map building))
+(define (cost a b) 1)
+(define (distance a b) 1)
+(define pf (make-path-finder))
+(a* pf 'town-common 'school neighbors cost distance)
+@end example
+
+In this case, the @code{a*} procedure will return the list
+@code{(town-common town-hall school)}, which is indeed the shortest
+route.  (The other possible route is @code{(town-common library cafe
+school)}.)
+
+The @code{a*} procedure does not know anything about about any kind of
+map and therefore must be told how to look up neighboring nodes, which
+is what the @code{neighbors} procedure in the example does. To
+simulate different types of terrain, a cost procedure is used.  In
+this example, it is just as easy to move between any two nodes because
+@code{cost} always returns 1.  In a real game, perhaps moving from
+from a field to a rocky hill would cost a lot more than moving from
+one field to another.  Finally, a heuristic is used to calculate an
+approximate distance between two nodes on the map.  In this simple
+association list based graph it is tough to calculate a distance
+between nodes, so the @code{distance} procedure isn't helpful and
+always returns 1.  In a real game with a tile-based map, for example,
+the heuristic could be a quick Manhattan distance calculation based on
+the coordinates of the two map tiles.  Choose an appropriate heuristic
+for optimal path finding!
+
+@deffn {Procedure} make-path-finder
+Return a new path finder object.
+@end deffn
+
+@deffn {Procedure} path-finder? @var{obj}
+Return @code{#t} if @var{obj} is a path finder.
+@end deffn
+
+@deffn {Procedure} a* @var{path-finder} @var{start} @var{goal} @
+                      @var{neighbors} @var{cost} @var{distance}
+
+Return a list of nodes forming a path from @var{start} to @var{goal}
+using @var{path-finder} to hold state.  @var{neighbors} is a procedure
+that accepts a node and returns a list of nodes that neighbor it.
+@var{cost} is a procedure that accepts two neighboring nodes and
+returns the cost of moving from the first to the second as a real
+number.  @var{distance} is a procedure that accepts two nodes and
+returns an approximate distance between them.
+@end deffn
+
 @node Graphics
 @section Graphics
 
-- 
cgit v1.2.3