From 0e699be281c8dea53e589e08a5831837e0eae7ea Mon Sep 17 00:00:00 2001 From: David Thompson Date: Thu, 7 Oct 2021 20:17:50 -0400 Subject: Updates for Chickadee 0.8.0 and Guile-SDL2 0.7.0. --- manuals/chickadee/Quadtrees.html | 222 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 222 insertions(+) create mode 100644 manuals/chickadee/Quadtrees.html (limited to 'manuals/chickadee/Quadtrees.html') diff --git a/manuals/chickadee/Quadtrees.html b/manuals/chickadee/Quadtrees.html new file mode 100644 index 0000000..e6962a4 --- /dev/null +++ b/manuals/chickadee/Quadtrees.html @@ -0,0 +1,222 @@ + + + + + + +Quadtrees (The Chickadee Game Toolkit) + + + + + + + + + + + + + + + + + + + +
+

+Next: , Previous: , Up: Data Structures   [Contents][Index]

+
+
+

5.6.4 Quadtrees

+ +

The (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. +

+
+
Procedure: make-quadtree bounds [#:max-size 5] [#:max-depth 4]
+

Return a new quadtree that covers the area bounds. Each node +will try to hold at maximum max-size objects and the tree depth +will be restricted to max-depth. +

+ +
+
Procedure: quadtree? obj
+

Return #t if obj is a quadtree. +

+ +
+
Procedure: quadtree-clear! quadtree
+

Clear all objects from quadtree. +

+ +
+
Procedure: quadtree-insert! quadtree rect object
+

Insert object with bounding box rect into quadtree. +

+ +
+
Procedure: quadtree-delete! quadtree rect object
+

Delete object, who occupies the space rect, from +quadtree. +

+ +
+
Procedure: quadtree-find rect pred
+

Return the first object in quadtree in the vicinity of +rect that satisfies pred. +

+ +
+
Procedure: quadtree-fold quadtree rect init proc
+

Apply proc to all objects in the vicinity of rect in +quadtree to build a result and return that result. init +is the initial result. If there are no objects in the vicinity of +rect, just init is returned. +

+ +
+
Procedure: quadtree-for-each quadtree rect proc
+

Call proc for all objects in the vicinity of rect in +quadtree. +

+ +
+
Procedure: quadtree-leaf? quadtree
+

Return #t if quadtree is a leaf node. +

+ +
+
Procedure: quadtree-bounds quadtree
+

Return the bounding rectangle of quadtree. +

+ +
+
Procedure: quadtree-max-depth quadtree
+

Return the maximum depth of quadtree. +

+ +
+
Procedure: quadtree-max-size quadtree
+

Return the desired per-node maximum object count of quadtree. +

+ +
+
Procedure: quadtree-depth quadtree
+

Return the depth of the node quadtree. +

+ +
+
Procedure: quadtree-size quadtree
+

Return the number of objects stored in the node quadtree. +

+ +

Non-leaf nodes always have four child nodes, which correspond to the +quadrants of a Cartesian coordinate system: +

+
*------*------*
+|      |      |
+|  Q2  |  Q1  |
+|      |      |
+*------*------*
+|      |      |
+|  Q3  |  Q4  |
+|      |      |
+*------*------*
+
+
+
Procedure: quadtree-q1 quadtree
+

Return the upper-right child node of quadtree, or #f if +quadtree is a leaf node. +

+ +
+
Procedure: quadtree-q2 quadtree
+

Return the upper-left child node of quadtree, or #f if +quadtree is a leaf node. +

+ +
+
Procedure: quadtree-q3 quadtree
+

Return the lower-left child node of quadtree, or #f if +quadtree is a leaf node. +

+ +
+
Procedure: quadtree-q4 quadtree
+

Return the lower-right child node of quadtree, or #f if +quadtree is a leaf node. +

+ +
+
+

+Next: , Previous: , Up: Data Structures   [Contents][Index]

+
+ + + + + -- cgit v1.2.3