Stack Overflow 1024 on recursively selecting neighbors in my Minesweeper clone

Question

I am building a minesweeper clone. The cells are instantiations of a custom "Tile" scene, they are laid out on a GridContainer.

Upon selection of a cell, I call a function to check the neighbor cells to see if they're a mine cell. If not, then I mark the current cell as clear and call that same function on all the neighboring cells

Everything works perfectly until I increase the grid size. I am attempting to play with a 30 X 30 grid, and when I click on a blank cell, the recursion needed to check all the cells for mines throws a Stack Overflow (Stack Size: 1024) error. How would I fix this?

Select function on the Tile scene:

func select():
    if not flagged and not selected:
        selected = true

        if mine:
            Game.lose()

        else:
            var mines = check_neighbors() # Returns number of mines, int 0-8
            match mines:
                0:
                    set_texture(clear_blocked)
                    select_neighbors() # Runs select() on all neighbor cells
                1: set_texture(number_block_1)
                2: set_texture(number_block_2)
                3: set_texture(number_block_3)
                4: set_texture(number_block_4)
                5: set_texture(number_block_5)
                6: set_texture(number_block_6)
                7: set_texture(number_block_7)
                8: set_texture(number_block_8)

Comments

This issue is occurring is because you are creating to many items so your passing the limit.

You have two options, change the limit of nodes or use less nodes to do the same work.

The first option can be done, by looking thorugh the settings and finding where hte node limit is. The second option is a more efficient way of drawing the tiles. Use the tilemap. Map a 2d array or a Vector2 Dictionary to a tilemap so that it draws the tiles you want in a way that doesn't hit the node limit. You can also just draw to the canvas directly was well.

---

Here is an example of what I am talking about.
https://github.com/codelyok13/Rosetta-Code/blob/master/Garbahe%20Minesweeper.7z

https://tmpfiles.org/244040/garbaheminesweeper.7z
Two Hours from now to check.

---

Thank you! This makes plenty of sense! I appreciate your time and input!

---

I recommend reading Inces answer because most likely he is correct as usually using to many slows you down not cause crashes. It was probably due to a rouge recursive function making to many calls.

Answer 1

To be honest I don't think stack overflow happens because of some arbitrary node limit. Stack overflow is not an optimisation issue, it happens when code endlessly runs in circles within loops or functions stacks.

I assume your select_neighbors()function is not adapted to changable grid size and somehow it runs selectendlessly by always matching 0 mines. Show the code of this function. The same propably goes to check_neighbours()

Comments

I agree. Especially not with less than 1000 tiles, and the problem occuring during runtime, and not when adding the tiles. Doing a flood fill (and that's what it is, basically) recursively is extremely inefficient for larger areas. I'd recommend switching to an iterative approach instead:

https://en.wikipedia.org/wiki/Flood_fill#Moving_the_recursion_into_a_data_structure

Also, (re-)checking the neighbors with every select adds to the inefficiency: Calculating the neighboring mines once in the beginning should be enough.

---

Now that I think about it more, I agree with you. It is probably a rouge recursive function making to many calls.

---

This makes sense, thank you!

When I create the tiles and add them to the grid, I assign each tile an ID with an x and y coordinate. EX: the tile in the top left will have id = [1, 1], the next tile to the right will have [2, 1]. I all the cells are stored in a 1d array on the GridContainer, and I have a function on the GridContainer object called get_cell that returns the specified cell object based on the id.

func get_cell(id):
    if id[0] < 1 or id[1] < 1:
        return null
    if id[0] > Game.parameters.cols or id[1] > Game.parameters.rows:
        return null
    return tiles[((id[1] - 1) * Game.parameters.cols) + (id[0] - 1)]

Here is my check neighbors and select neighbors functions:

func check_neighbors():
    var mines = 0
    for cell_id in get_neighbor_ids():
        if not get_parent().get_cell(cell_id) == null:
            if get_parent().get_cell(cell_id).mine:
                mines += 1
    return mines


func select_neighbors():
    for cell_id in get_neighbor_ids():
        if not get_parent().get_cell(cell_id) == null:
            get_parent().get_cell(cell_id).select()

I'm gonna do some more looking and testing myself, but is there anything you can see that would result in infinite recursion?

---

Interestingly enough, if I add a timer on the select function, to slow the spread of the recursion, it seems to work just fine... Is this telling of anything?

func select():
    yield(get_tree().create_timer(0.1), "timeout")
    if not flagged and not selected:
        selected = true

        if mine:
            set_texture(mine_block)

        else:
            var mines = check_neighbors()
            match mines:
                0:
                    set_texture(clear_blocked)
                    select_neighbors()
                1: set_texture(number_block_1)
                2: set_texture(number_block_2)
                3: set_texture(number_block_3)
                4: set_texture(number_block_4)
                5: set_texture(number_block_5)
                6: set_texture(number_block_6)
                7: set_texture(number_block_7)
                8: set_texture(number_block_8)

---

Perhaps resizing grid makes program to check some neighbouring tiles few times in the same frame before flagged/selected becomes true. If You want to know mechanism behind it, show the code of check_neighbours() and select_neighbours()

---

I showed the code for those two functions in my earlier comment. I left two comments back to back.

---

I am sorry, I totally missed this comment up there

Wow, I never thought of such simple calculation to create 1d array, that is neat :)
Took me a while to make sure it is really working in large sized grids :)

Even now this is still suspicious to me, it is a good place for stack overflow to happen, calling unexpected tiles instead of neighbours. Are You sure parameter.cols are updated after changing grid size to 30 ?

Another thing that came to my mind, is could it be you have setget for selected boolean ?

I noticed, that aside from adding timer, You also removed game.lose line. Did You make sure it is not the only condition for stack overflow ?

Other than that I can't find anything risky in this code. I am sure You didn't mess getneighborid(). Your code is very clean and sharp. Maybe I could at least give You a tip to improve that further :) :

set_texture("number_block_" +str(mines))