summaryrefslogtreecommitdiff
path: root/doc/api.texi
diff options
context:
space:
mode:
authorDavid Thompson <dthompson2@worcester.edu>2021-10-01 08:19:52 -0400
committerDavid Thompson <dthompson2@worcester.edu>2021-10-01 08:41:27 -0400
commit1ef0c9b18263ee1354987e8f104aff562a953fe6 (patch)
tree2085b254b3871e08399d33ad6a43fab42d82a9e5 /doc/api.texi
parent602569cd13f8f018194f54f39f4645d36d5b3821 (diff)
Add (chickadee data quadtree) module.
Diffstat (limited to 'doc/api.texi')
-rw-r--r--doc/api.texi111
1 files changed, 111 insertions, 0 deletions
diff --git a/doc/api.texi b/doc/api.texi
index 96803b8..f3b8013 100644
--- a/doc/api.texi
+++ b/doc/api.texi
@@ -5210,10 +5210,121 @@ Clear all messages and scripts awaiting messages in @var{channel}.
@section Data Structures
@menu
+* Quadtrees:: Spatial partitioning with recursive subdivision.
* Grids:: Spatial partitioning with a fixed grid.
* Path Finding:: Generic A* path finding.
@end menu
+@node Quadtrees
+@subsection Quadtrees
+
+The @code{(chickadee data quadtree)} module provides a 2D spatial
+partitioning implementation known as a ``quadtree''. A quadtree
+recursively subdivides the world into rectangular quadrants. This
+data structure is very useful for handling broad-phase collision
+detection because it can quickly determine the objects that may
+possibly be colliding with another, resulting in fewer narrow-phase
+collision tests that are typically much more expensive.
+
+@deffn {Procedure} make-quadtree bounds [#:max-size 5] [#:make-depth 4]
+Return a new quadtree that covers the area @var{bounds}. Each node
+will try to hold at maximum @var{max-size} objects and the tree depth
+will be restricted to @var{max-depth}.
+@end deffn
+
+@deffn {Procedure} quadtree? obj
+Return @code{#t} if @var{obj} is a quadtree.
+@end deffn
+
+@deffn {Procedure} quadtree-clear! quadtree
+Clear all objects from @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-insert! quadtree rect object
+Insert @var{object} with bounding box @var{rect} into @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-delete! quadtree rect object
+Delete @var{object}, who occupies the space @var{rect}, from
+@var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-find rect pred
+Return the first object in @var{quadtree} in the vicinity of
+@var{rect} that satisfies @var{pred}.
+@end deffn
+
+@deffn {Procedure} quadtree-fold quadtree rect init proc
+Apply @var{proc} to all objects in the vicinity of @var{rect} in
+@var{quadtree} to build a result and return that result. @var{init}
+is the initial result. If there are no objects in the vicinity of
+@var{rect}, just @var{init} is returned.
+@end deffn
+
+@deffn {Procedure} quadtree-for-each quadtree rect proc
+Call @var{proc} for all objects in the vicinity of @var{rect} in
+@var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-leaf? quadtree
+Return @code{#t} if @var{quadtree} is a leaf node.
+@end deffn
+
+@deffn {Procedure} quadtree-bounds quadtree
+Return the bounding rectangle of @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-max-depth quadtree
+Return the maximum depth of @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-max-size quadtree
+Return the desired per-node maximum object count of @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-depth quadtree
+Return the depth of the node @var{quadtree}.
+@end deffn
+
+@deffn {Procedure} quadtree-size quadtree
+Return the number of objects stored in the node @var{quadtree}.
+@end deffn
+
+Non-leaf nodes always have four child nodes, which correspond to the
+quadrants of a Cartesian coordinate system:
+
+@verbatim
+*------*------*
+| | |
+| Q2 | Q1 |
+| | |
+*------*------*
+| | |
+| Q3 | Q4 |
+| | |
+*------*------*
+@end verbatim
+
+@deffn {Procedure} quadtree-q1 quadtree
+Return the upper-right child node of @var{quadtree}, or @code{#f} if
+@var{quadtree} is a leaf node.
+@end deffn
+
+@deffn {Procedure} quadtree-q2 quadtree
+Return the upper-left child node of @var{quadtree}, or @code{#f} if
+@var{quadtree} is a leaf node.
+@end deffn
+
+@deffn {Procedure} quadtree-q3 quadtree
+Return the lower-left child node of @var{quadtree}, or @code{#f} if
+@var{quadtree} is a leaf node.
+@end deffn
+
+@deffn {Procedure} quadtree-q4 quadtree
+Return the lower-right child node of @var{quadtree}, or @code{#f} if
+@var{quadtree} is a leaf node.
+@end deffn
+
@node Grids
@subsection Grids