From f86e465ae364b119a400d868661ad51815a61df1 Mon Sep 17 00:00:00 2001 From: David Thompson Date: Sat, 5 Dec 2020 16:42:27 -0500 Subject: doc: Move grid subsection to end of math section. --- doc/api.texi | 219 ++++++++++++++++++++++++++++++----------------------------- 1 file changed, 112 insertions(+), 107 deletions(-) (limited to 'doc') diff --git a/doc/api.texi b/doc/api.texi index 67ed524..974a7f8 100644 --- a/doc/api.texi +++ b/doc/api.texi @@ -543,12 +543,12 @@ 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. * 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 @@ -1007,111 +1007,6 @@ 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 [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 Matrices @subsection Matrices @@ -1127,7 +1022,12 @@ garbage generated and improve matrix multiplication performance, there are many procedures that perform in-place modifications of matrix objects. -@subsubsection Matrix Operations +@subsubsection 3x3 Matrices + +@deffn {Procedure} make-matrix3 +@end deffn + +@subsubsection 4x4 Matrices @deffn {Procedure} make-matrix4 aa ab ac ad @ ba bb bc bd @ @@ -1481,6 +1381,111 @@ 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 -- cgit v1.2.3