summaryrefslogtreecommitdiff
path: root/doc
diff options
context:
space:
mode:
Diffstat (limited to 'doc')
-rw-r--r--doc/api.texi76
1 files changed, 75 insertions, 1 deletions
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