bzr branch
/bzr/spacey
1
by Josh C
zoetrope 1.4 |
1 |
-- Class: Collision
|
2 |
-- This is a utility class that helps with collision detection. It's aware
|
|
3 |
-- of <Sprite>s and <Group>s and makes sure collisions are resolved in the
|
|
4 |
-- correct order (most overlap to least). You shouldn't have to use this class
|
|
5 |
-- directly.
|
|
6 |
--
|
|
7 |
-- See Also:
|
|
8 |
-- <Sprite.collide>, <Group.collide>
|
|
9 |
||
10 |
Collision = Class:extend |
|
11 |
{
|
|
12 |
-- Property: gridSize
|
|
13 |
-- Default grid size used when checking collisions. Roughly speaking, this
|
|
14 |
-- should be two times as big as your most common sprite size, but tweaking
|
|
15 |
-- this number can yield better performance.
|
|
16 |
gridSize = 25, |
|
17 |
||
18 |
-- Method: check
|
|
19 |
-- Checks for collisions between <Sprite>s and <Group>s. If you call
|
|
20 |
-- Collision:check(a, b, c), it will check for collisions between a and b,
|
|
21 |
-- a and c, but not b and c.
|
|
22 |
--
|
|
23 |
-- It spatially hashes all objects into a grid, then checks for collisions via
|
|
24 |
-- <Sprite.overlap()>. If an overlap is detected, then the collision is recorded.
|
|
25 |
-- As a final step, this calls collidedWith() on sprites that collided, but in
|
|
26 |
-- descending order of overlap. (This normally only triggers the onCollide() handler
|
|
27 |
-- for the sprite, but <Map>s take advantage of this indirection.)
|
|
28 |
-- The sequence of collision resolutions is important, so that displacement occurs
|
|
29 |
-- in an order that prevents sprites from getting stuck on walls made of multiple sprites.
|
|
30 |
--
|
|
31 |
-- Arguments:
|
|
32 |
-- a - primary <Sprite> or <Group>
|
|
33 |
-- ... - any number of <Sprite>s or <Group>s to check for collisions against
|
|
34 |
-- the A sprite or group
|
|
35 |
--
|
|
36 |
-- Returns:
|
|
37 |
-- nothing
|
|
38 |
||
39 |
check = function (self, a, ...) |
|
40 |
-- coerce all arguments into a flat list of sprites,
|
|
41 |
-- recording where the first argument (or A group) sits in the list
|
|
42 |
||
43 |
local args = {...} |
|
44 |
local list = self:solidSprites(a) |
|
45 |
local aLength = #list |
|
46 |
||
47 |
for _, item in pairs(args) do |
|
48 |
self:solidSprites(item, list) |
|
49 |
end
|
|
50 |
||
51 |
-- build a spatial hash from the list, recording the grid
|
|
52 |
-- cells that each of the sprites fits inside.
|
|
53 |
-- we also record which cells each of the sprites in the A group
|
|
54 |
-- sits in.
|
|
55 |
||
56 |
local grid = {} |
|
57 |
local gridSize = a.gridSize or self.gridSize |
|
58 |
local gridded = {} |
|
59 |
local deferred = {} |
|
60 |
local aHuge = {} |
|
61 |
local aCells = {} |
|
62 |
||
63 |
for i, spr in ipairs(list) do |
|
64 |
if not gridded[spr] then |
|
65 |
local startX = math.floor(spr.x / gridSize) |
|
66 |
local endX = math.floor((spr.x + spr.width) / gridSize) |
|
67 |
local startY = math.floor(spr.y / gridSize) |
|
68 |
local endY = math.floor((spr.y + spr.height) / gridSize) |
|
69 |
||
70 |
-- Special casing of very large sprites (as defined as >= 25 cells in
|
|
71 |
-- area). If they are in the A list, we just reserve them
|
|
72 |
-- for later and check them against all sprites in the other lists.
|
|
73 |
-- If they are not in the A list, we defer them to the very end of the gridding
|
|
74 |
-- process, only to cells that have already been gridded by virtue of another
|
|
75 |
-- sprite being in them.
|
|
76 |
--
|
|
77 |
-- The assumption here is that huge sprites are probably big tilemaps, and
|
|
78 |
-- thus likely to collide with every sprite anyway.
|
|
79 |
||
80 |
if (endX - startX) * (endY - startY) > 25 then |
|
81 |
if i <= aLength then |
|
82 |
table.insert(aHuge, spr) |
|
83 |
else
|
|
84 |
table.insert(deferred, { spr = spr, startX = startX, endX = endX, startY = startY, endY = endY }) |
|
85 |
end
|
|
86 |
else
|
|
87 |
if i <= aLength then |
|
88 |
aCells[spr] = {} |
|
89 |
end
|
|
90 |
||
91 |
for x = startX, endX do |
|
92 |
grid[x] = grid[x] or {} |
|
93 |
||
94 |
for y = startY, endY do |
|
95 |
grid[x][y] = grid[x][y] or {} |
|
96 |
table.insert(grid[x][y], spr) |
|
97 |
||
98 |
if i <= aLength then |
|
99 |
table.insert(aCells[spr], grid[x][y]) |
|
100 |
end
|
|
101 |
end
|
|
102 |
end
|
|
103 |
end
|
|
104 |
||
105 |
gridded[spr] = true |
|
106 |
end
|
|
107 |
end
|
|
108 |
||
109 |
-- Grid all huge sprites we just deferred. Unlike above,
|
|
110 |
-- we only add them to grid cells that already have sprites in them.
|
|
111 |
||
112 |
for _, d in pairs(deferred) do |
|
113 |
for x = d.startX, d.endX do |
|
114 |
if grid[x] then |
|
115 |
for y = d.startY, d.endY do |
|
116 |
if grid[x][y] then |
|
117 |
table.insert(grid[x][y], d.spr) |
|
118 |
end
|
|
119 |
end
|
|
120 |
end
|
|
121 |
end
|
|
122 |
end
|
|
123 |
||
124 |
-- aCells now is a table whose keys are sprites in this group,
|
|
125 |
-- and whose values are a table of grid cells that the sprite is in.
|
|
126 |
-- We now build a list of collisions based on that.
|
|
127 |
||
128 |
local collisions = {} |
|
129 |
local alreadyCollided = {} |
|
130 |
||
131 |
for aSpr, cells in pairs(aCells) do |
|
132 |
alreadyCollided[aSpr] = alreadyCollided[aSpr] or {} |
|
133 |
||
134 |
for _, cell in pairs(cells) do |
|
135 |
for _, bSpr in pairs(cell) do |
|
136 |
if aSpr ~= bSpr and not alreadyCollided[aSpr][bSpr] then |
|
137 |
local xOverlap, yOverlap = bSpr:overlap(aSpr.x, aSpr.y, aSpr.width, aSpr.height) |
|
138 |
||
139 |
if xOverlap ~= 0 or yOverlap ~= 0 then |
|
140 |
table.insert(collisions, { area = xOverlap * yOverlap, x = xOverlap, y = yOverlap, a = aSpr, b = bSpr }) |
|
141 |
end
|
|
142 |
||
143 |
-- record that we've already checked this collision
|
|
144 |
||
145 |
alreadyCollided[bSpr] = alreadyCollided[bSpr] or {} |
|
146 |
alreadyCollided[aSpr][bSpr] = true |
|
147 |
alreadyCollided[bSpr][aSpr] = true |
|
148 |
end
|
|
149 |
end
|
|
150 |
end
|
|
151 |
end
|
|
152 |
||
153 |
-- Run through the huge sprites in the A list, if any, adding
|
|
154 |
-- collisions to the existing list.
|
|
155 |
||
156 |
for _, aSpr in pairs(aHuge) do |
|
157 |
alreadyCollided[aSpr] = alreadyCollided[aSpr] or {} |
|
158 |
||
159 |
for i = aLength + 1, #list do |
|
160 |
local bSpr = list[i] |
|
161 |
||
162 |
if aSpr ~= bSpr and not alreadyCollided[aSpr][bSpr] then |
|
163 |
local xOverlap, yOverlap = bSpr:overlap(aSpr.x, aSpr.y, aSpr.width, aSpr.height) |
|
164 |
||
165 |
if xOverlap ~= 0 or yOverlap ~= 0 then |
|
166 |
table.insert(collisions, { area = xOverlap * yOverlap, x = xOverlap, y = yOverlap, a = aSpr, b = bSpr }) |
|
167 |
end
|
|
168 |
||
169 |
alreadyCollided[bSpr] = alreadyCollided[bSpr] or {} |
|
170 |
alreadyCollided[aSpr][bSpr] = true |
|
171 |
alreadyCollided[bSpr][aSpr] = true |
|
172 |
end
|
|
173 |
end
|
|
174 |
end
|
|
175 |
||
176 |
-- collisions now is a list, each item containing these properties:
|
|
177 |
-- a - sprite colliding
|
|
178 |
-- b - second sprite colliding
|
|
179 |
-- x - x overlap
|
|
180 |
-- y - y overlap
|
|
181 |
-- area - square area of overlap
|
|
182 |
--
|
|
183 |
-- we now sort the table and resolve collisions in descending order of overlap area.
|
|
184 |
||
185 |
table.sort(collisions, self.sortCollisions) |
|
186 |
||
187 |
for _, col in ipairs(collisions) do |
|
188 |
col.a:collidedWith(col.b, col.x, col.y) |
|
189 |
col.b:collidedWith(col.a, col.x, col.y) |
|
190 |
end
|
|
191 |
end, |
|
192 |
||
193 |
-- Method: solidSprites
|
|
194 |
-- Returns a table of <Sprite>s belonging to an object that
|
|
195 |
-- should be collided with others, descending into groups.
|
|
196 |
--
|
|
197 |
-- Arguments:
|
|
198 |
-- source - <Sprite> or <Group>
|
|
199 |
-- existing - existing table to add to
|
|
200 |
--
|
|
201 |
-- Returns:
|
|
202 |
-- table of <Sprite>s
|
|
203 |
||
204 |
solidSprites = function (self, source, existing) |
|
205 |
local result = existing or {} |
|
206 |
||
207 |
if source.solid then |
|
208 |
if source.x and source.y and source.width and source.height then |
|
209 |
table.insert(result, source) |
|
210 |
elseif source.sprites then |
|
211 |
for _, spr in pairs(source.sprites) do |
|
212 |
if spr.sprites then |
|
213 |
result = self:solidSprites(spr, result) |
|
214 |
elseif spr.solid then |
|
215 |
table.insert(result, spr) |
|
216 |
end
|
|
217 |
end
|
|
218 |
end
|
|
219 |
end
|
|
220 |
||
221 |
return result |
|
222 |
end, |
|
223 |
||
224 |
-- Method: sortCollisions
|
|
225 |
-- This sorts a table of collisions in descending order of overlap,
|
|
226 |
-- suitable for use in conjunction with table.sort().
|
|
227 |
--
|
|
228 |
-- Arguments:
|
|
229 |
-- a - one collision table
|
|
230 |
-- b - one collision table
|
|
231 |
--
|
|
232 |
-- Returns:
|
|
233 |
-- whether a should be sorted before b
|
|
234 |
||
235 |
sortCollisions = function (a, b) |
|
236 |
return a.area > b.area |
|
237 |
end
|
|
238 |
}
|