Love 2d - match 3, I get a stack overflow

Question

main.lua:147: stack overflow

Traceback

[love "callbacks.lua"]:228: in function 'handler'
main.lua:94: in function 'matches'
main.lua:80: in function 'checkforNil'
main.lua:89: in function 'removeMatches'
main.lua:148: in function 'matches'
main.lua:80: in function 'checkforNil'
main.lua:89: in function 'removeMatches'
main.lua:148: in function 'matches'
main.lua:80: in function 'checkforNil'
main.lua:89: in function 'removeMatches'
...
main.lua:89: in function 'removeMatches'
main.lua:148: in function 'matches'
main.lua:80: in function 'checkforNil'
main.lua:89: in function 'removeMatches'
main.lua:148: in function 'matches'
main.lua:161: in function 'swap'
main.lua:183: in function <main.lua:175>
[love "callbacks.lua"]:154: in function <[love "callbacks.lua"]:144>
[C]: in function 'xpcall'

I'm was working a tile matching game using Love2D. The game involves a grid of colored tiles that players can swap to form matches of three or more. When matches are formed, the tiles are removed, and new tiles drop down to fill the empty spaces. However, I'm encountering a "stack overflow" error, and I'm not sure how to resolve it. Here is my code: How can I resolve this stack overflow error? It seems to occur in the matches and removeMatches functions, causing an infinite loop or recursion issue.

updated to provide error and minimal case of working.

local game = {}

-- Table to store the grid elements
gridTable = {}
local selectedTile = nil

-- Function to initialize the gridTable with colors
function game:initializeGrid()
    for i = 1, 64 do
        gridTable[i] = {
            x = ((i - 1) % 8) * 65,
            y = (math.floor((i - 1) / 8) * 65),
            color = love.math.random(7)
        }
    end
end

-- Function to draw the grid elements
function game:drawGrid()
    for i, cell in ipairs(gridTable) do
        if cell.color then
            love.graphics.setColor(self:getColor(cell.color))
            love.graphics.rectangle("fill", cell.x, cell.y, 50, 50)
        end
    end
    if selectedTile then
        love.graphics.setColor(1, 1, 1)
        love.graphics.rectangle("line", gridTable[selectedTile].x, gridTable[selectedTile].y, 50, 50)
    end
end

-- Helper function to get color by index
function game:getColor(index)
    local colors = {
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 1},
        {1, 1, 0},
        {0, 1, 1},
        {1, 0, 1},
        {0.5, 0.5, 0.5}
    }
    return colors[index]
end

function game:checkforNil() -- looks for nil values in the table
    for i = 64, 56, -1 do --grid is 8x8 so 64 items
      local counter = 8 -- looks through each row
      for j = i, 1, -8 do
        local tempY, tempColor = 0, 0

        if gridTable[j].y == nil then -- if value at j is nil we swap the nil value with what's about it and repeats until all values are filled
          for test = j, 1, -8 do
            if gridTable[test].y ~= nil then
              tempY = gridTable[test].y
                tempColor = gridTable[test].color

                gridTable[j].y = ((counter) * 50) + (((counter) - 1) * 15)
                gridTable[j].color = tempColor

                gridTable[test].y = nil
                gridTable[test].color = nil
                break
                end
                end
            end

            for k = 1, 8 do -- loops through the top and assigns random colours
                if gridTable[k].y == nil then
                    gridTable[k].y = 50
                    gridTable[k].color = love.math.random(7)
                end
            end

            counter = counter - 1
        end
    end
    self:matches(gridTable)
end

function game:removeMatches(grid)
    for _, v in ipairs(listofMatches) do --lists of matches contain where in the table there are 3 or more colours of the same 
        grid[v].y = nil --and removes them
        grid[v].color = nil
    end
    listofMatches = {} --resets the list 
    self:checkforNil() -- calls the function that pushes bricks down
end

function game:matches(grid) --searches everytime we swap for a match
    matchTest = false --if we find at least one match we'll set this to true
    listofMatches = {}
    local matches = 0 

    for i = 1, 63 do --loops through the table of which there are 64 items
      for _, y in ipairs(listofMatches) do
        if i == y then
          goto continue --if i and i+1 are a match we skip to i+2 to see if that matches too
        end
      end
      ::continue::
      for j = i + 1, 64 do --in this loop we are looking for horizontal matches
        local currentColor = grid[i].color --sets the current colour we are searching for
          if currentColor ~= grid[j].color then --we break out of searching for the same colour and if the
            if matches > 1 then --matches are 3+ we set match test to tru and insert into list of matches
              matchTest = true
              for k = i, j - 1 do
                table.insert(listofMatches, k)
              end
            end
            matches = 0
            break
          else
          matches = matches + 1
          end
        end
    end

    for num = 1, 8 do --looking for vertical
      for vertical = num, 48, 8 do
        for _, y in ipairs(listofMatches) do
          if vertical == y then
            goto continue
            end
          end
          ::continue::
          for down = vertical + 8, 64, 8 do
            local currentColor = grid[vertical].color
            if currentColor ~= grid[down].color then
            if matches > 1 then
              matchTest = true
              for k = vertical, down - 8, 8 do
                table.insert(listofMatches, k)
              end
              end
              matches = 0
              break
            else
              matches = matches + 1
            end
          end
        end
    end

    if matchTest then --if there is a match test we want to remove matches so call the function and add points
        self:removeMatches(grid)
        game.points = (game.points or 0) + 500
        matchTest = false
    end
end

function game:swap(swap1, swap2) --swapping blocks and then checking if there's a match
    local temp1 = gridTable[swap1].color
    local temp2 = gridTable[swap2].color

    gridTable[swap1].color = temp2
    gridTable[swap2].color = temp1

    self:matches(gridTable)
end

-- Love2D callback functions
function love.load()
    game:initializeGrid()
end

function love.draw()
    game:drawGrid()
    love.graphics.setColor(1, 1, 1)
    love.graphics.print("Points: " .. (game.points or 0), 10, 10)
end

function love.mousepressed(x, y, button)
    if button == 1 then
        local tileIndex = game:getTileIndex(x, y)
        if tileIndex then
            if not selectedTile then
                selectedTile = tileIndex
            else
                if selectedTile ~= tileIndex then
                    game:swap(selectedTile, tileIndex)
                    selectedTile = nil
                else
                    selectedTile = nil
                end
            end
        end
    end
end

function game:getTileIndex(x, y)
    for i, cell in ipairs(gridTable) do
        if x > cell.x and x < cell.x + 50 and y > cell.y and y < cell.y + 50 then
            return i
        end
    end
    return nil
end

Answer 1

In addition to the stack overflow error in certain circumstances, the grid falls apart very quickly after a move or two.

There are fundamental design issues here which I'd resolve before fighting bugs. In fact, following these principles will likely automatically resolve the bugs, because they're likely caused by subtle math errors that leave the grid in a bad state.

1. Avoid magic values.

   The abundant magic values like 63, 64, 8, 65 scattered throughout the code are difficult to understand and make it challenging to keep the grid in non-corrupt state as you perform complex manipulations. It's best to assign these one time as constants and derive all other values from the base values using simple mathematical operations.

2. Keep the UI and game logic separate.

   Convert to and from real-world coordinates immediately after receiving a mouse click and when rendering the grid to the UI. This will also help reduce the need for confusing magic numbers.

3. Model a 2d grid with a 2d table, rather than a 1d table.

   A 2d table corresponds better to what the actual grid looks like. With a 2d grid that doesn't care about UI coordinates (63, 64, 65 and so forth), all row and column values are implicit in the cell's 2d table position. You only need to track the colors of each cell.

4. Avoid recursion, which is generally harder to reason about and debug than loops.

Applying these principles (getting rid of magic values, decoupling the UI and game logic and using a 2d grid, avoiding recursion) cleans things up considerably:

local grid = {}
local gridSize = 8
local gapSize = 15
local squareSize = 50
local squareSizeWithGap = gapSize + squareSize
local selectedTile = nil
local colors = {
    {1, 0, 0},
    {0, 1, 0},
    {0, 0, 1},
    {1, 1, 0},
    {0, 1, 1},
    {1, 0, 1},
    {0.5, 0.5, 0.5},
}

function initializeGrid()
    for row = 1, gridSize do
        grid[row] = {}
    end
    fillGrid()
    resolveMatches()
end

function drawGrid()
    for row = 1, gridSize do
        for col = 1, gridSize do
            love.graphics.setColor(colors[grid[row][col]])
            love.graphics.rectangle(
                "fill",
                (col - 1) * squareSizeWithGap,
                (row - 1) * squareSizeWithGap,
                squareSize,
                squareSize
            )
        end
    end

    if selectedTile then
        love.graphics.setColor(1, 1, 1)
        love.graphics.rectangle(
            "line",
            (selectedTile.col - 1) * squareSizeWithGap,
            (selectedTile.row - 1) * squareSizeWithGap,
            squareSize,
            squareSize
        )
    end
end

function resolveMatches()
    while removeHorizontalMatch() or removeVerticalMatch() do
        shiftTilesDown()
        fillGrid()
    end
end

function removeHorizontalMatch()
    for row = 1, gridSize do
        for col = 1, gridSize - 2 do
            local color = grid[row][col]
            if color == grid[row][col + 1] and color == grid[row][col + 2] then
                grid[row][col] = nil
                grid[row][col + 1] = nil
                grid[row][col + 2] = nil
                return true
            end
        end
    end
end

function removeVerticalMatch()
    for col = 1, gridSize do
        for row = 1, gridSize - 2 do
            local color = grid[row][col]
            if color == grid[row + 1][col] and color == grid[row + 2][col] then
                grid[row][col] = nil
                grid[row + 1][col] = nil
                grid[row + 2][col] = nil
                return true
            end
        end
    end
end

function fillGrid()
    for col = 1, gridSize do
        for row = 1, gridSize do
            if not grid[row][col] then
                grid[row][col] = love.math.random(#colors)
            end
        end
    end
end

function shiftTilesDown()
    for col = 1, gridSize do
        for row = gridSize, 1, -1 do
            if not grid[row][col] then
                -- Find the next non-nil tile above to move down
                for aboveRow = row - 1, 1, -1 do
                    if grid[aboveRow][col] then
                        grid[row][col] = grid[aboveRow][col]
                        grid[aboveRow][col] = nil
                        break
                    end
                end
            end
        end
    end
end

function handleMove(row, col)
    if row <= gridSize and col <= gridSize then
        if selectedTile then
            local s = selectedTile
            grid[row][col], grid[s.row][s.col] = grid[s.row][s.col], grid[row][col]
            resolveMatches()
            selectedTile = nil
        else
            selectedTile = { row = row, col = col }
        end
    end
end

function love.load()
    initializeGrid()
end

function love.draw()
    drawGrid()
end

function love.mousepressed(x, y, button)
    if button == 1 then
        local col = math.floor(x / squareSizeWithGap) + 1
        local row = math.floor(y / squareSizeWithGap) + 1
        handleMove(row, col)
    end
end