Simple Recursive Tactical RPG Movement Range Issue

[LudvickToba]

So I'm working on a simple Fire Emblem like game. But the movement range that it calculates is a bit buggy when the movement range is 3. I'm using a recursive function that will check if a space can be reached by a unit, if it can't it jumps out of the recursion, if it does then it is added to an array of valid spaces and is marked true, then it checks left, right, up and down of that space. However, if the max number of spaces to move is three, it will think the top and bottom two spaces are not accessible when they should be. I provided the code in the main.lua added and a pic to illustrate the goal. Any suggestions would be most helpful! If you need a better explanation please ask!

Code: Select all

function ValidSpaces(x, y, movement, moveMax)
	--BASE CASE
-- if movement is greater than max, or the new space is out of map bounds
	if (movement > moveMax) or (x > mapW) or (x < 0) or (y < 0) or (y > mapH) then
		return false
	end
-- if that space has not been checked
	if validMove[tostring(x..':'..y)] == nil then
		validMove[tostring(x..':'..y)] = true 
		return 
			ValidSpaces(x+1, y, movement + 1, moveMax), -- Check right
			ValidSpaces(x-1, y, movement + 1, moveMax), -- check left
			ValidSpaces(x, y+1, movement + 1, moveMax), -- check down
			ValidSpaces(x, y-1, movement + 1, moveMax)  -- check up
	end
end

[Nelvin]

Your problem is that you recursively only check if the position is reachable and if so, mark it as true and never evaluate the position again. But to reach all the possible destinations you need to also check for the length of the path so far and not skip the recursion if you reached a tile in less moves than before.
Here's the fixed code.

Code: Select all

function love.load()

	tileSize = 16 -- FOR NOW JUST SPACEING FOR MAP
	validMove = {} -- TABLE TO STORE POSSIBLE VALID SPACES TO MOVE TO
	--MAP DATA
	map1 = {
		{1, 1, 1, 1, 1, 1, 1},
		{1, 0, 0, 0, 0, 0, 1},
		{1, 0, 0, 0, 0, 0, 1},
		{1, 0, 0, 1, 1, 1, 1},
		{1, 0, 0, 0, 0, 0, 1},
		{1, 0, 0, 0, 0, 0, 1},
		{1, 0, 0, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1, 1}
	}
	mapW = #map1[1]
	mapH = #map1
	--UNIT DATA
	unit = {
		x = 4,
		y = 5,
		move = 3 -- play around with this
	}

-- The problem
	ValidSpaces(unit.x, unit.y, 0, unit.move)
end

function love.update(dt)
end

function love.draw()
	drawMap()
	drawUnit()
end

function drawMap()
	for y=1, mapH do
		for x=1, mapW do
			if validMove[tostring(x .. ":" .. y)] ~= nil then
				love.graphics.setColor(155,155,255)
				love.graphics.print(map1[y][x], x * tileSize, y * tileSize)
				love.graphics.setColor(255, 255, 255)
			else
				love.graphics.print(map1[y][x], x * tileSize, y * tileSize)
			end
		end
	end
end

function drawUnit()
	love.graphics.rectangle("fill", unit.x*tileSize, unit.y*tileSize, tileSize, tileSize)
end

function resetValidMove()
	validMove = {}
end

--[[
Calculate the range based on given pramiters
x - x coord of current space
y - y coord of current space
movement - how many spaces taken to get to current space. base always 0
moveMax - The maximum spaces the range can go
--]]
function ValidSpaces(x, y, movement, moveMax)
	--BASE CASE
-- if movement is greater than max, or the new space is out of map bounds
	if (movement > moveMax) or (x > mapW) or (x < 0) or (y < 0) or (y > mapH) then
		return false
	end
-- if that space has not been checked
    local key = tostring(x..':'..y)
    if validMove[key] == nil or validMove[key] > movement then
		validMove[key] = movement
		return
			ValidSpaces(x+1, y, movement + 1, moveMax), -- Check right
			ValidSpaces(x-1, y, movement + 1, moveMax), -- check left
			ValidSpaces(x, y+1, movement + 1, moveMax), -- check down
			ValidSpaces(x, y-1, movement + 1, moveMax)  -- check up
	end
end

[LudvickToba]

Thank you!