Having problems writing a recursive function in Lua - looking for help & suggestions!

SDK Get Help
1

I'm on a Mac, using Nova for development, but I don't think it's relevant to this issue.

Basically, I’m trying to create a recursive function in Lua… and one of my tables doesn’t seem to be working correctly the second time through the recursion loop. First time everything works right, but the second time the variable’s count is always 0 (using the #variable method of getting the count).

Apologies in advance for this relatively long code block. I'm not sure if there's a better way to post this.

So the relevant bits are the very last function (which I’m calling from main.lua), and the loop in indexesOfFirstMatchingGroup …which calls matchingAdjacentIndexes (the recursive bit).

import 'CoreLibs/object'

class('Game').extends()


--Game = {}
--Game.__index = Game

-- Note that values > 99 are reserved for non-game states
-- and will generally be ignored by most of these functions.

local grid = {}
local w
local h

local valueDefault = 1
local valueEmpty = -1
local valueMaxForRandom = 6

Directions = {UP = "1", DOWN = "2", LEFT = "3", RIGHT = "4"}

function Game:init(width, height)
	Game.super.init(self)
	w = width
	h = height
	self:resetGrid()
end

function Game:indexForXY(x, y)
	if x < 1 or y < 1 or x > w or y > h then return 1 end
	return ((y-1) * w) + x
end

function Game:valueForXY(x, y)
	if x < 1 or y < 1 or x > w or y > h then return valueEmpty end
	return grid[self:indexForXY(x, y)]
end

function Game:inBounds(x, y)
	if x < 1 or y < 1 or x > w or y > h then
		return false
	else
		return true
	end
end

function Game:setValueForXY(newValue, x, y)
	if x < 1 or y < 1 or x > w or y > h then return end
	grid[self:indexForXY(x, y)] = newValue
end

function Game:printGrid()
	local rows = "grid (w:" .. w .. ",h:" .. h .. ") \n"
	for y = 1, h do
		local row = " [ "
		for x = 1, w do
			row = row .. grid[self:indexForXY(x, y)] .. ", "
		end
		row = row .. "]\n"
		rows = rows .. row
	end
	print(rows)
end

function Game:randomizeGrid()
	for x = 1, w do
		for y = 1, h do
			grid[self:indexForXY(x, y)] = math.random(1,valueMaxForRandom)
		end
	end
end

function Game:resetGrid()
	for x = 1, w do
		for y = 1, h do
			grid[self:indexForXY(x, y)] = valueDefault
		end
	end
end

function Game:setGrid(gridTable)
	-- this seems like the safest way to do this
	local index
	for x = 1, w do
		for y = 1, h do
			index = self:indexForXY(x, y)
			grid[index] = gridTable[index] or valueDefault
		end
	end
end

function Game:swapGridValues(x1, y1, x2, y2)
	local value1 = self:valueForXY(x1, y1)
	grid[self:indexForXY(x1, y1)] = self:valueForXY(x2, y2)
	grid[self:indexForXY(x2, y2)] = value1
end

function Game:valueInDirection(direction, fromX, fromY)
	if direction == Directions.UP then
		return self:valueForXY(fromX, fromY-1)
	elseif direction == Directions.DOWN then
		return self:valueForXY(fromX, fromY+1)
	elseif direction == Directions.LEFT then
		return self:valueForXY(fromX-1, fromY)
	elseif direction == Directions.RIGHT then
		return self:valueForXY(fromX+1, fromY)
	else
		return valueEmpty
	end
end

-- functions past this point are really pretty specific to this game

function Game:indexesOfFirstMatchingGroup()
	local currentValue
	for x = 1, w do
		for y = 1, h do
			currentValue = self:valueForXY(x, y)
			-- don't try to match values of defaultValue or > 99
			if currentValue > 1 and currentValue < 100 then
				local checkedIndexes = {}
				local matchingIndexes = {}
				checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(currentValue, x, y, checkedIndexes, matchingIndexes)
				if #matchingIndexes > 1 then
					return matchingIndexes
				end
			end
		end
	end
	-- no matches found
	return {}
end

function Game:matchingAdjacentIndexes(value, x, y, checkedIndexes, matchingIndexes)
	print("in matchingAdjacentIndexes for x,y: " .. x .. "," .. y)
	if not self:inBounds(x, y) then
		print("  returning OOB")
		return checkedIndexes, matchingIndexes
	end
	local currentIndex = self:indexForXY(x, y)
	if checkedIndexes[currentIndex] == true then
		print("  returning already checked")
		return checkedIndexes, matchingIndexes
	end
	checkedIndexes[currentIndex] = true
	if grid[currentIndex] ~= value then
		print("  returning values (" .. value .. "," .. grid[currentIndex] .. ") do not match")
		return checkedIndexes, matchingIndexes
	end
	matchingIndexes[currentIndex] = true
	print("  found match, matchingIndex count: " .. #matchingIndexes)
	-- add up
	checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(value, x, y-1, checkedIndexes, matchingIndexes)
	-- add down
	checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(value, x, y+1, checkedIndexes, matchingIndexes)
	-- add left
	checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(value, x-1, y, checkedIndexes, matchingIndexes)
	-- add right
	checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(value, x+1, y, checkedIndexes, matchingIndexes)
	print("  checked all directions (" .. x .. "," .. y .. "), matchingIndex count: " .. #matchingIndexes)
	return checkedIndexes, matchingIndexes
end

function Game:removeMatchingTiles()
	-- note, only values between 2 and 99 will be checked and
	-- if they have any neighbors that match, they will be
	-- replaced with 1, (the default value)
	-- this function returns the number of tiles removed
	local matchesFound = 0
	local currentIndex
	local currentValue
	local indexHasMatch = {}
	for x = 1, w do
		for y = 1, h do
			currentIndex = self:indexForXY(x, y)
			currentValue = grid[currentIndex]
			if (currentValue > 1 and currentValue < 99) and (
				(currentValue == grid[self:indexForXY(x+1, y)]) or
				(currentValue == grid[self:indexForXY(x-1, y)]) or
				(currentValue == grid[self:indexForXY(x, y+1)]) or
				(currentValue == grid[self:indexForXY(x, y-1)])) then
					indexHasMatch[currentIndex] = true
					matchesFound += 1
			end
		end
	end
	if matchesFound > 0 then
		for x = 1, w do
			for y = 1, h do
				currentIndex = self:indexForXY(x, y)
				if indexHasMatch[currentIndex] then
					grid[currentIndex] = 1
				end
			end
		end
	end
	return matchesFound
end

function Game:addRandomNonDefaultValue()
	local defaults = self:defaultIndexes()
	if #defaults == 0 then return end
	local key = defaults[math.random(1,#defaults)]
	grid[key] = math.random(2,valueMaxForRandom)
end

-- returns a table of grid indexes with default values
function Game:defaultIndexes()
	local defaultKeys = {}
	for key, value in ipairs(grid) do
		if value == valueDefault then
			table.insert(defaultKeys, key)
		end
	end
	return defaultKeys
end

function Game:allValuesAreDefault()
	local currentValue
	for x = 1, w do
		for y = 1, h do
			currentValue = self:valueForXY(x, y)
			if currentValue < 99 and currentValue ~= valueDefault then
				return false
			end
		end
	end
	return true
end

function Game:allTilesContainAdjacentMatchingValues()
	local foundOne = false
	local checkedIndexes = { }
	local currentIndex = 1
	local checkIndex = 1
	for x = 1, w do
		for y = 1, h do
			currentIndex = self:indexForXY(x, y)
			-- need to exclude cursor values
			if grid[currentIndex] > 99 then
				checkedIndexes[currentIndex] = true
			end
			-- only need to check this index if we haven't checked it already
			if checkedIndexes[currentIndex] ~= true then
				foundOne = false
				-- down
				checkIndex = self:indexForXY(x, y+1)
				if grid[currentIndex] == grid[checkIndex] then
					foundOne = true
					checkedIndexes[currentIndex] = true
					checkedIndexes[checkIndex] = true
				end
				-- right
				if foundOne == false then
					checkIndex = self:indexForXY(x+1, y)
					if grid[currentIndex] == grid[checkIndex] then
						foundOne = true
						checkedIndexes[currentIndex] = true
						checkedIndexes[checkIndex] = true
					end
				end
				-- up
				if foundOne == false then
					checkIndex = self:indexForXY(x, y-1)
					if grid[currentIndex] == grid[checkIndex] then
						foundOne = true
						checkedIndexes[currentIndex] = true
						checkedIndexes[checkIndex] = true
					end
				end
				-- left
				if foundOne == false then
					checkIndex = self:indexForXY(x-1, y)
					if grid[currentIndex] == grid[checkIndex] then
						foundOne = true
						checkedIndexes[currentIndex] = true
						checkedIndexes[checkIndex] = true
					end
				end
				if foundOne == false then
					return false
				end
			end
		end
	end
	return true
end

function Game:testIndexesOfMatchingGroups()
	local game = Game(5, 6)
	local tempGrid = {
		2, 1, 2, 1, 5,
		1, 1, 1, 1, 1,
		1, 1, 100, 1, 1,
		1, 1, 1, 4, 1,
		1, 1, 4, 4, 1,
		3, 3, 1, 1, 4,
	}
	game:setGrid(tempGrid)
	local matchingIndexes = game:indexesOfFirstMatchingGroup()
	print("number of matching indexes is: " .. #matchingIndexes)
--	assert(#matchingIndexes == 3, "no matching indexes found")
end

So all the print statements in matchingAdjacentIndexes are to try and fix this problem. (I can see it “working” first time by replacing a 1 next to the initial 2 in my grid with another 2, which correctly returns a matchingIndexes table with 2 or 3 elements in it.)

As is, it outputs the following:

in matchingAdjacentIndexes for x,y: 1,1
  found match, matchingIndex count: 1
in matchingAdjacentIndexes for x,y: 1,0
  returning OOB
in matchingAdjacentIndexes for x,y: 1,2
  returning values (2,1) do not match
in matchingAdjacentIndexes for x,y: 0,1
  returning OOB
in matchingAdjacentIndexes for x,y: 2,1
  returning values (2,1) do not match
  checked all directions (1,1), matchingIndex count: 1
in matchingAdjacentIndexes for x,y: 1,6
  found match, matchingIndex count: 0
in matchingAdjacentIndexes for x,y: 1,5
  returning values (3,1) do not match
in matchingAdjacentIndexes for x,y: 1,7
  returning OOB
in matchingAdjacentIndexes for x,y: 0,6
  returning OOB
in matchingAdjacentIndexes for x,y: 2,6
  found match, matchingIndex count: 0
in matchingAdjacentIndexes for x,y: 2,5
  returning values (3,1) do not match
in matchingAdjacentIndexes for x,y: 2,7
  returning OOB
in matchingAdjacentIndexes for x,y: 1,6
  returning already checked
in matchingAdjacentIndexes for x,y: 3,6
  returning values (3,1) do not match
  checked all directions (2,6), matchingIndex count: 0
  checked all directions (1,6), matchingIndex count: 0
<snipped the rest>

Plus a bunch more that I deleted. Anyway, I’d expect the lines that say “found match, …” and the ones that say “checked all directions…” to end with values of 1 or higher. But you can see after the first time through they’re always zero.

If you’ve read this far… you’re already my hero. :heart:

2

A little more on what this code is trying to do: This is a relatively "generic" model for a grid-based game. The indexesOfFirstMatchingGroup function should return a table whose indexes correspond to the indexes of the grid that contain adjacent "groups" of matching values. (Doesn't matter what the values are, as long as they're >1 and <99.)

Incidentally, when I'm confident this code is working pretty well, I'll probably release it in some form somewhere. I'm happy to let anyone use it. (This is the umpteenth time I've written almost this exact class in various languages/environments.)

3

The problem is actually not the recursive code, it's in my lack of understanding how the #table count works. (And how it wouldn't work in my case.)

I found the solution essentially by reading the comments here: How to get number of entries in a Lua table? - Stack Overflow

1 Like