BFS pathfinding algorithm

[Hampfh]

--[[
	This is a breath first search implementation
]]
MAP_SIZE = 9

-- By specifying a current tile and a previous adjacent tile
-- this function returns should move to get back to the previous tile
local function getDirection(fromX, fromY, toX, toY)
	if fromX == toX then
		-- Down
		if fromY == toY + 1 then
			return 2
		else -- Up
			return 0
		end
	else
		-- Right
		if fromX == toX + 1 then
			return 1
		else -- Left
			return 3
		end
	end
end

local function coordinateFromDirection(x, y, direction)
	if direction == 0 then
		return { x = x, y = y - 1 }
	elseif direction == 1 then
		return { x = x + 1, y = y }
	elseif direction == 2 then
		return { x = x, y = y + 1 }
	else
		return { x = x - 1, y = y }
	end
end

local function getIndex(coordinate)
	return coordinate.y * MAP_SIZE + coordinate.x + 1
end

local function bfs(x, y, context)
	local queue = { { x = x, y = y } }
	local lastMoveQueue = { { x = x, y = y } }
	local prevTile = { x = x, y = y }
	local goal = nil
	-- Construct empty visisted map
	local visited = {}
	for i = 1, MAP_SIZE * MAP_SIZE, 1 do
		table.insert(visited, -1)
	end

	local counter = 0

	-- Continue searching until either all tiles have been visited
	-- or the top of the map has been reached
	while next(queue) ~= nil do
		counter = counter + 1
		local current = table.remove(queue, 1)
		local prevTile = table.remove(lastMoveQueue, 1)
		-- Here we mark how to get back to the previous tile
		-- from our current position
		visited[getIndex(current)] = getDirection(prevTile.x, prevTile.y, current.x, current.y)
		if current.y == 0 then
			goal = { x = current.x, y = current.y }
			break
		end

		-- Check all adjacent tiles
		for i = 0, 3, 1 do
			-- Create a new table to avoid modifying the current coordinate
			local new_coordinate = { x = current.x, y = current.y }
			if i == 0 then
				new_coordinate.y = new_coordinate.y - 1
			elseif i == 1 then
				new_coordinate.x = new_coordinate.x + 1
			elseif i == 2 then
				new_coordinate.y = new_coordinate.y + 1
			else
				new_coordinate.x = new_coordinate.x - 1
			end

			-- Check if coordinate is within bounds
			if new_coordinate.x >= 0 and new_coordinate.x < MAP_SIZE and new_coordinate.y >= 0 and new_coordinate.y < MAP_SIZE then
				local tile = context.board[getIndex(new_coordinate)]

				-- Pathing algorithm is allowed to path through empty tiles, player 1 and player 2
				if tile < 3 and visited[getIndex(new_coordinate)] == -1 then
					--[[ return "#debug inside " .. tostring(new_coordinate.x) .. " " .. tostring(new_coordinate.y) .. "\n" ]]
					table.insert(lastMoveQueue, current)
					table.insert(queue, new_coordinate)
				end
			end
		end
	end

	local current = { x = goal.x, y = goal.y }
	local prev = { x = goal.x, y = goal.y }
	while true do
		-- Continue until we have found our starting position
		if current.x == x and current.y == y then
			-- Invert direction
			return tostring((getDirection(current.x, current.y, prev.x, prev.y) + 2) % 4);
		end
		prev = { x = current.x, y = current.y }

		if current.x < 0 or current.x >= MAP_SIZE or current.y < 0 or current.y >= MAP_SIZE then
			return "#debug 4 " .. tostring(current.x) .. " " .. tostring(current.y)
		end

		current = coordinateFromDirection(current.x, current.y, visited[getIndex(current)])
	end
end


function onTurn(context)
	return bfs(context.player.x, context.player.y, context)
end

function onJump(context)
	return "0"
end

[Hampfh]

[THIS MESSAGE IS AUTOMATIC]
User: Hampfh
Script-id: fe128b4c-b947-4420-990a-7658f8c2dc48
Thanks for submitting!
Your code is being processed...

[Hampfh]

[THIS MESSAGE IS AUTOMATIC]
[SUCCESS] Opponent: 2b04c102-556f-4522-b0b4-77f531c2f46d
Match
[WIN] Opponent: 661deec5-1967-4f0c-82de-69b3b01e47a1 | Match
[WIN] Opponent: c0412c19-887b-4762-9fa9-d93aab383d83 | Match
[LOSS] Opponent: 1da0638b-0912-4672-8237-4f5bf502c6b4 | Match
[LOSS] Opponent: adbd08b3-8504-4b72-83ae-23b843313692 | Match
[LOSS] Opponent: 16754832-98d7-4d61-9c5c-b29eabd5e3ec | Match
[WIN] Opponent: e62c6a3e-3123-4041-ab24-05382f85f23c | Match
[WIN] Opponent: f4e7e93d-fc25-4b64-9068-39506c1d7e9e | Match
[LOSS] Opponent: 367e1c4b-ff88-40a8-a054-9718470fb7fd | Match
[WIN] Opponent: 0f152710-dcbb-49df-8566-d82afaa2fd67 | Match

[Hampfh]

[THIS MESSAGE IS AUTOMATIC]
This submission has already been submitted before

[Hampfh]

[THIS MESSAGE IS AUTOMATIC]
[LOSS] Opponent: e25da2fb-8bc8-4b19-b6af-69c5a64c6af9 | Match