To get this branch, use:
bzr branch
http://9ix.org/bzr/ld27
« back to all changes in this revision
Viewing changes to zoetrope/core/collision.lua
- browse files at revision 1
- compare with another revision
- compare with revision 29
- download diff
- download tarball
- view history from revision 1
- Committer: Josh C
- Date: 2013-08-24 03:11:38 UTC
- Revision ID: josh@9ix.org-20130824031138-j4ta4ome0upsxcv5
zoetrope 1.4
- files added:
- zoetrope
- zoetrope/core
- zoetrope/input
- zoetrope/sprites
- zoetrope/ui
- zoetrope/utils
added
removed
zoetrope/core/collision.lua
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
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1