/spacey

-- 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
}