/traderous

To get this branch, use:
bzr branch http://9ix.org/bzr/traderous
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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
-- Class: Collision
-- This is a utility class that helps with collision detection. It's aware
-- of <Sprite>s and <Group>s and makes sure collisions are resolved in the
-- correct order (most overlap to least). You shouldn't have to use this class
-- directly.
--
-- See Also:
--		<Sprite.collide>, <Group.collide>

Collision = Class:extend
{
	-- Property: gridSize
	-- Default grid size used when checking collisions. Roughly speaking, this
	-- should be two times as big as your most common sprite size, but tweaking
	-- this number can yield better performance.
	gridSize = 25,

	-- Method: check
	-- Checks for collisions between <Sprite>s and <Group>s. If you call
	-- Collision:check(a, b, c), it will check for collisions between a and b,
	-- a and c, but not b and c.
	--
	-- It spatially hashes all objects into a grid, then checks for collisions via
	-- <Sprite.overlap()>. If an overlap is detected, then the collision is recorded.
	-- As a final step, this calls collidedWith() on sprites that collided, but in 
	-- descending order of overlap. (This normally only triggers the onCollide() handler
	-- for the sprite, but <Map>s take advantage of this indirection.)
	-- The sequence of collision resolutions is important, so that displacement occurs
	-- in an order that prevents sprites from getting stuck on walls made of multiple sprites.
	--
	-- Arguments:
	--		a - primary <Sprite> or <Group>
	--		... - any number of <Sprite>s or <Group>s to check for collisions against
	--			  the A sprite or group
	--
	-- Returns:
	--		nothing

	check = function (self, a, ...)
		-- coerce all arguments into a flat list of sprites,
		-- recording where the first argument (or A group) sits in the list

		local args = {...}
		local list = self:solidSprites(a)
		local aLength = #list

		for _, item in pairs(args) do
			self:solidSprites(item, list)
		end

		-- build a spatial hash from the list, recording the grid
		-- cells that each of the sprites fits inside.
		-- we also record which cells each of the sprites in the A group
		-- sits in.

		local grid = {}
		local gridSize = a.gridSize or self.gridSize
		local gridded = {}
		local deferred = {}
		local aHuge = {}
		local aCells = {}

		for i, spr in ipairs(list) do
			if not gridded[spr] then
				local startX = math.floor(spr.x / gridSize)
				local endX = math.floor((spr.x + spr.width) / gridSize)
				local startY = math.floor(spr.y / gridSize)
				local endY = math.floor((spr.y + spr.height) / gridSize)

				-- Special casing of very large sprites (as defined as >= 25 cells in
				-- area). If they are in the A list, we just reserve them
				-- for later and check them against all sprites in the other lists.
				-- If they are not in the A list, we defer them to the very end of the gridding
				-- process, only to cells that have already been gridded by virtue of another
				-- sprite being in them.
				--
				-- The assumption here is that huge sprites are probably big tilemaps, and
				-- thus likely to collide with every sprite anyway.

				if (endX - startX) * (endY - startY) > 25 then
					if i <= aLength then
						table.insert(aHuge, spr)
					else
						table.insert(deferred, { spr = spr, startX = startX, endX = endX, startY = startY, endY = endY })
					end
				else
					if i <= aLength then
						aCells[spr] = {}
					end
				
					for x = startX, endX do
						grid[x] = grid[x] or {}

						for y = startY, endY do
							grid[x][y] = grid[x][y] or {}
							table.insert(grid[x][y], spr)

							if i <= aLength then
								table.insert(aCells[spr], grid[x][y])
							end
						end
					end
				end

				gridded[spr] = true
			end
		end

		-- Grid all huge sprites we just deferred. Unlike above,
		-- we only add them to grid cells that already have sprites in them.

		for _, d in pairs(deferred) do
			for x = d.startX, d.endX do
				if grid[x] then
					for y = d.startY, d.endY do
						if grid[x][y] then
							table.insert(grid[x][y], d.spr)
						end
					end
				end
			end
		end

		-- aCells now is a table whose keys are sprites in this group,
		-- and whose values are a table of grid cells that the sprite is in.
		-- We now build a list of collisions based on that.

		local collisions = {}
		local alreadyCollided = {}

		for aSpr, cells in pairs(aCells) do
			alreadyCollided[aSpr] = alreadyCollided[aSpr] or {}
			
			for _, cell in pairs(cells) do
				for _, bSpr in pairs(cell) do
					if aSpr ~= bSpr and not alreadyCollided[aSpr][bSpr] then
						local xOverlap, yOverlap = bSpr:overlap(aSpr.x, aSpr.y, aSpr.width, aSpr.height)

						if xOverlap ~= 0 or yOverlap ~= 0 then
							table.insert(collisions, { area = xOverlap * yOverlap, x = xOverlap, y = yOverlap, a = aSpr, b = bSpr })
						end

						-- record that we've already checked this collision

						alreadyCollided[bSpr] = alreadyCollided[bSpr] or {}
						alreadyCollided[aSpr][bSpr] = true
						alreadyCollided[bSpr][aSpr] = true
					end
				end
			end
		end

		-- Run through the huge sprites in the A list, if any, adding
		-- collisions to the existing list.

		for _, aSpr in pairs(aHuge) do
			alreadyCollided[aSpr] = alreadyCollided[aSpr] or {}

			for i = aLength + 1, #list do
				local bSpr = list[i]

				if aSpr ~= bSpr and not alreadyCollided[aSpr][bSpr] then
					local xOverlap, yOverlap = bSpr:overlap(aSpr.x, aSpr.y, aSpr.width, aSpr.height)

					if xOverlap ~= 0 or yOverlap ~= 0 then
						table.insert(collisions, { area = xOverlap * yOverlap, x = xOverlap, y = yOverlap, a = aSpr, b = bSpr })
					end

					alreadyCollided[bSpr] = alreadyCollided[bSpr] or {}
					alreadyCollided[aSpr][bSpr] = true
					alreadyCollided[bSpr][aSpr] = true
				end
			end
		end

		-- collisions now is a list, each item containing these properties:
		--		a - sprite colliding
		--		b - second sprite colliding
		--		x - x overlap
		--		y - y overlap
		--	 	area - square area of overlap
		--
		-- we now sort the table and resolve collisions in descending order of overlap area.
		
		table.sort(collisions, self.sortCollisions)

		for _, col in ipairs(collisions) do
			col.a:collidedWith(col.b, col.x, col.y)
			col.b:collidedWith(col.a, col.x, col.y)
		end
	end,

	-- Method: solidSprites
	-- Returns a table of <Sprite>s belonging to an object that
	-- should be collided with others, descending into groups.
	--
	-- Arguments:
	--		source - <Sprite> or <Group>
	--		existing - existing table to add to
	--
	-- Returns:
	--		table of <Sprite>s

	solidSprites = function (self, source, existing)
		local result = existing or {}
		
		if source.solid then
			if source.x and source.y and source.width and source.height then
				table.insert(result, source)
			elseif source.sprites then
				for _, spr in pairs(source.sprites) do
					if spr.sprites then
						result = self:solidSprites(spr, result)
					elseif spr.solid then
						table.insert(result, spr)
					end
				end
			end
		end

		return result
	end,

	-- Method: sortCollisions
	-- This sorts a table of collisions in descending order of overlap,
	-- suitable for use in conjunction with table.sort().
	--
	-- Arguments:
	--		a - one collision table
	--		b - one collision table
	--
	-- Returns:
	--		whether a should be sorted before b

	sortCollisions = function (a, b)
		return a.area > b.area
	end
}