doc: Document collision grid API.

1 files changed, 107 insertions, 0 deletions

diff --git a/doc/api.texi b/doc/api.texi
index 47e16f5..a2e546d 100644
--- a/doc/api.texi
+++ b/doc/api.texi
@@ -363,6 +363,7 @@ detection.
 * Basics::                      Commonly used, miscellaneous things.
 * Vectors::                     Euclidean vectors.
 * Rectangles::                  Axis-aligned bounding boxes.
+* Grid::                        Spatial partitioning for bounding boxes.
 * Matrices::                    Transformation matrices.
 * Quaternions::                 Rotations about an arbitrary axis.
 * Easings::                     Easing functions for interesting animations.
@@ -781,6 +782,112 @@ Restrict the coordinates of the 2D vector @var{v} so that they are
 within the bounds of @var{rect}.  @var{v} is modified in-place.
 @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 [@var{cell-size} 64]
+Return a new grid partitioned into @var{cell-size} tiles.
+@end deffn
+
+@deffn {Procedure} grid? @var{obj}
+Return @code{#t} if @var{obj} is a grid.
+@end deffn
+
+@deffn {Procedure} cell? @var{obj}
+Return @code{#t} if @var{obj} is a grid cell.
+@end deffn
+
+@deffn {Procedure} cell-count @var{cell}
+Return the number of items in @var{cell}.
+@end deffn
+
+@deffn {Procedure} grid-cell-size @var{grid}
+Return the cell size of @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-cell-count @var{grid}
+Return the number of cells currently in @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-item-count @var{grid}
+Return the number of items in @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-add @var{grid} @var{item} @var{x} @var{y} @
+                            @var{width} @var{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 @var{grid} @var{item}
+Return @var{item} from @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-clear @var{grid}
+Remove all items from @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-move @var{grid} @var{item} @var{position} @var{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 @var{proc} @var{grid} [@var{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 @var{proc} @var{grid}
+Call @var{proc} for each item in @var{grid}.
+@end deffn
+
+@deffn {Procedure} slide @var{item} @var{item-rect} @
+                         @var{other} @var{other-rect} @var{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 Matrices
 @subsection Matrices