-- Finds the complete set of blocks that must move together for one grid step.
-- A block joins the set when it is in another block's destination (ordinary
-- pushing), is softly grabbed by a sticky block, or is rigidly welded to a
-- gluey block.
local Movement = {}

local adjacentDirections = {
	{x = 1, y = 0},
	{x = -1, y = 0},
	{x = 0, y = 1},
	{x = 0, y = -1},
}

local function isSticky(entity)
	return entity.isSticky and entity:isSticky()
end

local function isPassable(entity)
	return entity.canPassOver and entity:canPassOver()
end

local function isGluey(entity)
	return entity.isGluey and entity:isGluey()
end

-- Build one rigid component: ordinary pushes are required, and gluey blocks weld
-- along every edge. `alreadyMoving` contains cells that will be vacated during
-- this same step, so a later pulled component may move into them.
local function findRigidGroup(startCells, direction, entityAt, isInBounds, alreadyMoving)
	local entities = {}
	local pendingCells = {}
	for _, cell in ipairs(startCells) do
		table.insert(pendingCells, cell)
	end

	local nextCell = 1
	while nextCell <= #pendingCells do
		local cell = pendingCells[nextCell]
		nextCell = nextCell + 1

		if not isInBounds(cell) then
			return false, entities
		end

		local entity = entityAt(cell)
		if entity and not isPassable(entity) and not entities[entity] and
			not (alreadyMoving and alreadyMoving[entity]) then
			if not entity:canMove() then
				return false, entities
		end

			entities[entity] = entity

			-- Anything occupying this block's destination must be pushed too.
			for _, projectedCell in ipairs(entity:getOccupiedCells(direction)) do
				table.insert(pendingCells, projectedCell)
			end

			-- Gluey blocks make every edge contact part of this rigid component.
			for _, occupiedCell in ipairs(entity:getOccupiedCells()) do
				for _, adjacentDirection in ipairs(adjacentDirections) do
					local adjacentCell = {
						x = occupiedCell.x + adjacentDirection.x,
						y = occupiedCell.y + adjacentDirection.y,
					}
					if isInBounds(adjacentCell) then
						local adjacentEntity = entityAt(adjacentCell)
						local attached = adjacentEntity and (
							isGluey(entity) or isGluey(adjacentEntity)
						)
						if attached and adjacentEntity ~= entity and adjacentEntity:canMove() and
							not (alreadyMoving and alreadyMoving[adjacentEntity]) then
							table.insert(pendingCells, adjacentCell)
						end
					end
				end
			end
		end
	end

	return true, entities
end

function Movement.findMovableGroup(startCells, direction, entityAt, isInBounds)
	local possible, entities = findRigidGroup(
		startCells, direction, entityAt, isInBounds
	)
	if not possible then return false, entities end

	local movingQueue = {}
	for entity in pairs(entities) do table.insert(movingQueue, entity) end
	local attemptedPulls = {}
	local nextMover = 1

	while nextMover <= #movingQueue do
		local entity = movingQueue[nextMover]
		nextMover = nextMover + 1

		-- Sticky contact is soft on every face: it tries to drag each neighbour
		-- along, but simply releases a blocked rigid component without cancelling
		-- this entity or another independently pulled branch.
		for _, occupiedCell in ipairs(entity:getOccupiedCells()) do
			for _, adjacentDirection in ipairs(adjacentDirections) do
				local adjacentCell = {
					x = occupiedCell.x + adjacentDirection.x,
					y = occupiedCell.y + adjacentDirection.y,
				}
				if isInBounds(adjacentCell) then
					local adjacentEntity = entityAt(adjacentCell)
					local softContact = adjacentEntity and (
						isSticky(entity) or isSticky(adjacentEntity)
					)
					if softContact and adjacentEntity ~= entity and
						not entities[adjacentEntity] and not attemptedPulls[adjacentEntity] and
						adjacentEntity:canMove() then
						attemptedPulls[adjacentEntity] = true
						local canPull, pulled = findRigidGroup(
							{adjacentCell}, direction, entityAt, isInBounds, entities
						)
						if canPull then
							for pulledEntity in pairs(pulled) do
								if not entities[pulledEntity] then
									entities[pulledEntity] = pulledEntity
									table.insert(movingQueue, pulledEntity)
								end
							end
						end
					end
				end
			end
		end
	end

	return true, entities
end

return Movement