diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/api.texi | 76 |
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 |