1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 2017-2023 David Thompson dthompson2@worcester.edu
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3
or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
A copy of the license is included in the section entitled "GNU
Free Documentation License".
A copy of the license is also available from the Free Software
Foundation Web site at http://www.gnu.org/licenses/fdl.html.
* Chickadee: (chickadee). Game programming toolkit for Guile.
The document was typeset with
http://www.texinfo.org/ (GNU Texinfo).
-->
<!-- Created by GNU Texinfo 6.7, http://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Grids (The Chickadee Game Toolkit)</title>
<meta name="description" content="Grids (The Chickadee Game Toolkit)" />
<meta name="keywords" content="Grids (The Chickadee Game Toolkit)" />
<meta name="resource-type" content="document" />
<meta name="distribution" content="global" />
<meta name="Generator" content="makeinfo" />
<link href="index.html" rel="start" title="Top" />
<link href="Index.html" rel="index" title="Index" />
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Data-Structures.html" rel="up" title="Data Structures" />
<link href="Path-Finding.html" rel="next" title="Path Finding" />
<link href="Quadtrees.html" rel="prev" title="Quadtrees" />
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.indentedblock {margin-right: 0em}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
kbd {font-style: oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
span.nolinebreak {white-space: nowrap}
span.roman {font-family: initial; font-weight: normal}
span.sansserif {font-family: sans-serif; font-weight: normal}
ul.no-bullet {list-style: none}
@media (min-width: 1140px) {
body {
margin-left: 14rem;
margin-right: 4rem;
max-width: 52rem;
}
}
@media (min-width: 800px) and (max-width: 1140px) {
body {
margin-left: 6rem;
margin-right: 4rem;
max-width: 52rem;
}
}
@media (max-width: 800px) {
body {
margin: 1rem;
}
}
-->
</style>
<link rel="stylesheet" type="text/css" href="https://dthompson.us/css/dthompson.css" />
</head>
<body lang="en">
<span id="Grids"></span><div class="header">
<p>
Next: <a href="Path-Finding.html" accesskey="n" rel="next">Path Finding</a>, Previous: <a href="Quadtrees.html" accesskey="p" rel="prev">Quadtrees</a>, Up: <a href="Data-Structures.html" accesskey="u" rel="up">Data Structures</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index.html" title="Index" rel="index">Index</a>]</p>
</div>
<hr />
<span id="Grids-1"></span><h4 class="subsection">5.6.5 Grids</h4>
<p>The <code>(chickadee data grid)</code> module provides a simple spatial
partitioning system for axis-aligned bounding boxes
(see <a href="Rectangles.html">Rectangles</a>) 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.
</p>
<p>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</code>, 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</code>, 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.
</p>
<dl>
<dt id="index-make_002dgrid">Procedure: <strong>make-grid</strong> <em>[cell-size 64]</em></dt>
<dd><p>Return a new grid partitioned into <var>cell-size</var> tiles.
</p></dd></dl>
<dl>
<dt id="index-grid_003f">Procedure: <strong>grid?</strong> <em>obj</em></dt>
<dd><p>Return <code>#t</code> if <var>obj</var> is a grid.
</p></dd></dl>
<dl>
<dt id="index-cell_003f">Procedure: <strong>cell?</strong> <em>obj</em></dt>
<dd><p>Return <code>#t</code> if <var>obj</var> is a grid cell.
</p></dd></dl>
<dl>
<dt id="index-cell_002dcount">Procedure: <strong>cell-count</strong> <em>cell</em></dt>
<dd><p>Return the number of items in <var>cell</var>.
</p></dd></dl>
<dl>
<dt id="index-grid_002dcell_002dsize">Procedure: <strong>grid-cell-size</strong> <em>grid</em></dt>
<dd><p>Return the cell size of <var>grid</var>.
</p></dd></dl>
<dl>
<dt id="index-grid_002dcell_002dcount">Procedure: <strong>grid-cell-count</strong> <em>grid</em></dt>
<dd><p>Return the number of cells currently in <var>grid</var>.
</p></dd></dl>
<dl>
<dt id="index-grid_002ditem_002dcount">Procedure: <strong>grid-item-count</strong> <em>grid</em></dt>
<dd><p>Return the number of items in <var>grid</var>.
</p></dd></dl>
<dl>
<dt id="index-grid_002dadd">Procedure: <strong>grid-add</strong> <em>grid item x y width height</em></dt>
<dd>
<p>Add <var>item</var> to <var>grid</var> represented by the axis-aligned bounding
box whose lower-left corner is at (<var>x</var>, <var>y</var>) and is
<var>width</var> x <var>height</var> in size.
</p></dd></dl>
<dl>
<dt id="index-grid_002dremove">Procedure: <strong>grid-remove</strong> <em>grid item</em></dt>
<dd><p>Return <var>item</var> from <var>grid</var>.
</p></dd></dl>
<dl>
<dt id="index-grid_002dclear">Procedure: <strong>grid-clear</strong> <em>grid</em></dt>
<dd><p>Remove all items from <var>grid</var>.
</p></dd></dl>
<dl>
<dt id="index-grid_002dmove">Procedure: <strong>grid-move</strong> <em>grid item position filter</em></dt>
<dd><p>Attempt to move <var>item</var> in <var>grid</var> to <var>position</var> (a 2D
vector) and check for collisions. For each collision, <var>filter</var>
will be called with two arguments: <var>item</var> and the item it collided
with. If a collision occurs, <var>position</var> may be modified to
resolve the colliding objects.
</p></dd></dl>
<dl>
<dt id="index-for_002deach_002dcell">Procedure: <strong>for-each-cell</strong> <em>proc grid [rect]</em></dt>
<dd><p>Call <var>proc</var> with each cell in <var>grid</var> that intersects
<var>rect</var>, or every cell if <var>rect</var> is <code>#f</code>.
</p></dd></dl>
<dl>
<dt id="index-for_002deach_002ditem">Procedure: <strong>for-each-item</strong> <em>proc grid</em></dt>
<dd><p>Call <var>proc</var> for each item in <var>grid</var>.
</p></dd></dl>
<dl>
<dt id="index-slide">Procedure: <strong>slide</strong> <em>item item-rect other other-rect goal</em></dt>
<dd>
<p>Resolve the collision that occurs between <var>item</var> and <var>other</var>
when moving <var>item-rect</var> to <var>goal</var> by sliding <var>item-rect</var>
the minimum amount needed to make it no longer overlap
<var>other-rect</var>.
</p></dd></dl>
<hr />
<div class="header">
<p>
Next: <a href="Path-Finding.html" accesskey="n" rel="next">Path Finding</a>, Previous: <a href="Quadtrees.html" accesskey="p" rel="prev">Quadtrees</a>, Up: <a href="Data-Structures.html" accesskey="u" rel="up">Data Structures</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index.html" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
