diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/api.texi | 365 |
1 files changed, 186 insertions, 179 deletions
diff --git a/doc/api.texi b/doc/api.texi index 6a1361d..96803b8 100644 --- a/doc/api.texi +++ b/doc/api.texi @@ -4,6 +4,7 @@ * Graphics:: 2D and 3D rendering. * Audio:: Make some noise. * Scripting:: Bringing the game world to life. +* Data Structures:: Spatial partitioning and more. @end menu @node Kernel @@ -531,8 +532,6 @@ 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. -* Grid:: Spatial partitioning for bounding boxes. @end menu @node Basics @@ -1377,183 +1376,6 @@ 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? obj -Return @code{#t} if @var{obj} is a path finder. -@end deffn - -@deffn {Procedure} a* path-finder start goal neighbors cost 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 Grid -@subsection Grid - -The @code{(chickadee math grid)} module provides a simple spatial -partitioning system for axis-aligned bounding boxes -(@pxref{Rectangles}) in 2D space. The grid divides the world into -tiles and keeps track of which rectangles occupy which tiles. When -there are lots of moving objects in the game world that need collision -detection, the grid greatly speeds up the process. Instead of -checking collisions of each object against every other object (an -O(n^2) operation), the grid quickly narrows down which objects could -possibly be colliding and only performs collision testing against a -small set of objects. - -In addition to checking for collisions, the grid also handles the -resolution of collisions. Exactly how each collision is resolved is -user-defined. A player bumping into a wall may slide against it. An -enemy colliding with a projectile shot by the player may get pushed -back in the opposite direction. Two players colliding may not need -resolution at all and will just pass through each other. The way this -works is that each time an object (A) is moved within the grid, the -grid looks for an object (B) that may possibly be colliding with A. A -user-defined procedure known as a ``filter'' is then called with both -A and B. If the filter returns @code{#f}, it means that even if A and -B are colliding, no collision resolution is needed. In this case the -grid won't waste time checking if they really do collide because it -doesn't matter. If A and B are collidable, then the filter returns a -procedure that implements the resolution technique. The grid will -then perform a collision test. If A and B are colliding, the resolver -procedure is called. It's the resolvers job to adjust the objects -such that they are no longer colliding. The grid module comes with a -very simple resolution procedure, @code{slide}, that adjusts object A -by the smallest amount so that it no longer overlaps with B. By using -this filtering technique, a game can resolve collisions between -different objects in different ways. - -@deffn {Procedure} make-grid [cell-size 64] -Return a new grid partitioned into @var{cell-size} tiles. -@end deffn - -@deffn {Procedure} grid? obj -Return @code{#t} if @var{obj} is a grid. -@end deffn - -@deffn {Procedure} cell? obj -Return @code{#t} if @var{obj} is a grid cell. -@end deffn - -@deffn {Procedure} cell-count cell -Return the number of items in @var{cell}. -@end deffn - -@deffn {Procedure} grid-cell-size grid -Return the cell size of @var{grid}. -@end deffn - -@deffn {Procedure} grid-cell-count grid -Return the number of cells currently in @var{grid}. -@end deffn - -@deffn {Procedure} grid-item-count grid -Return the number of items in @var{grid}. -@end deffn - -@deffn {Procedure} grid-add grid item x y @ - width height - -Add @var{item} to @var{grid} represented by the axis-aligned bounding -box whose lower-left corner is at (@var{x}, @var{y}) and is -@var{width} x @var{height} in size. -@end deffn - -@deffn {Procedure} grid-remove grid item -Return @var{item} from @var{grid}. -@end deffn - -@deffn {Procedure} grid-clear grid -Remove all items from @var{grid}. -@end deffn - -@deffn {Procedure} grid-move grid item position filter -Attempt to move @var{item} in @var{grid} to @var{position} (a 2D -vector) and check for collisions. For each collision, @var{filter} -will be called with two arguments: @var{item} and the item it collided -with. If a collision occurs, @var{position} may be modified to -resolve the colliding objects. -@end deffn - -@deffn {Procedure} for-each-cell proc grid [rect] -Call @var{proc} with each cell in @var{grid} that intersects -@var{rect}, or every cell if @var{rect} is @code{#f}. -@end deffn - -@deffn {Procedure} for-each-item proc grid -Call @var{proc} for each item in @var{grid}. -@end deffn - -@deffn {Procedure} slide item item-rect other other-rect goal - -Resolve the collision that occurs between @var{item} and @var{other} -when moving @var{item-rect} to @var{goal} by sliding @var{item-rect} -the minimum amount needed to make it no longer overlap -@var{other-rect}. -@end deffn - @node Graphics @section Graphics @@ -5383,3 +5205,188 @@ after it has been received. @deffn {Procedure} channel-clear! channel Clear all messages and scripts awaiting messages in @var{channel}. @end deffn + +@node Data Structures +@section Data Structures + +@menu +* Grids:: Spatial partitioning with a fixed grid. +* Path Finding:: Generic A* path finding. +@end menu + +@node Grids +@subsection Grids + +The @code{(chickadee data grid)} module provides a simple spatial +partitioning system for axis-aligned bounding boxes +(@pxref{Rectangles}) in 2D space. The grid divides the world into +tiles and keeps track of which rectangles occupy which tiles. When +there are lots of moving objects in the game world that need collision +detection, the grid greatly speeds up the process. Instead of +checking collisions of each object against every other object (an +O(n^2) operation), the grid quickly narrows down which objects could +possibly be colliding and only performs collision testing against a +small set of objects. + +In addition to checking for collisions, the grid also handles the +resolution of collisions. Exactly how each collision is resolved is +user-defined. A player bumping into a wall may slide against it. An +enemy colliding with a projectile shot by the player may get pushed +back in the opposite direction. Two players colliding may not need +resolution at all and will just pass through each other. The way this +works is that each time an object (A) is moved within the grid, the +grid looks for an object (B) that may possibly be colliding with A. A +user-defined procedure known as a ``filter'' is then called with both +A and B. If the filter returns @code{#f}, it means that even if A and +B are colliding, no collision resolution is needed. In this case the +grid won't waste time checking if they really do collide because it +doesn't matter. If A and B are collidable, then the filter returns a +procedure that implements the resolution technique. The grid will +then perform a collision test. If A and B are colliding, the resolver +procedure is called. It's the resolvers job to adjust the objects +such that they are no longer colliding. The grid module comes with a +very simple resolution procedure, @code{slide}, that adjusts object A +by the smallest amount so that it no longer overlaps with B. By using +this filtering technique, a game can resolve collisions between +different objects in different ways. + +@deffn {Procedure} make-grid [cell-size 64] +Return a new grid partitioned into @var{cell-size} tiles. +@end deffn + +@deffn {Procedure} grid? obj +Return @code{#t} if @var{obj} is a grid. +@end deffn + +@deffn {Procedure} cell? obj +Return @code{#t} if @var{obj} is a grid cell. +@end deffn + +@deffn {Procedure} cell-count cell +Return the number of items in @var{cell}. +@end deffn + +@deffn {Procedure} grid-cell-size grid +Return the cell size of @var{grid}. +@end deffn + +@deffn {Procedure} grid-cell-count grid +Return the number of cells currently in @var{grid}. +@end deffn + +@deffn {Procedure} grid-item-count grid +Return the number of items in @var{grid}. +@end deffn + +@deffn {Procedure} grid-add grid item x y @ + width height + +Add @var{item} to @var{grid} represented by the axis-aligned bounding +box whose lower-left corner is at (@var{x}, @var{y}) and is +@var{width} x @var{height} in size. +@end deffn + +@deffn {Procedure} grid-remove grid item +Return @var{item} from @var{grid}. +@end deffn + +@deffn {Procedure} grid-clear grid +Remove all items from @var{grid}. +@end deffn + +@deffn {Procedure} grid-move grid item position filter +Attempt to move @var{item} in @var{grid} to @var{position} (a 2D +vector) and check for collisions. For each collision, @var{filter} +will be called with two arguments: @var{item} and the item it collided +with. If a collision occurs, @var{position} may be modified to +resolve the colliding objects. +@end deffn + +@deffn {Procedure} for-each-cell proc grid [rect] +Call @var{proc} with each cell in @var{grid} that intersects +@var{rect}, or every cell if @var{rect} is @code{#f}. +@end deffn + +@deffn {Procedure} for-each-item proc grid +Call @var{proc} for each item in @var{grid}. +@end deffn + +@deffn {Procedure} slide item item-rect other other-rect goal + +Resolve the collision that occurs between @var{item} and @var{other} +when moving @var{item-rect} to @var{goal} by sliding @var{item-rect} +the minimum amount needed to make it no longer overlap +@var{other-rect}. +@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 data 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? obj +Return @code{#t} if @var{obj} is a path finder. +@end deffn + +@deffn {Procedure} a* path-finder start goal neighbors cost 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 |