/ld26-basecode

To get this branch, use:
bzr branch http://9ix.org/bzr/ld26-basecode
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
}