Log In  

Hello all!

I have been trying to make a minesweeper clone in order to practice grid based games. Everything was going well, until I tried to make the mechanic where adjacent 0 tiles are revealed. I made a recursive function, but when set to all eight directions, it would run out of memory almost instantly. Any tips on how to either optimize the function or replace it? Any help would be awesome, I'm not the best programmer, thanks!

Recursive function:

function tile_reveal(x,y)
    if y > 0
    and y <= #board.board
    and x > 0
    and x <= #board.board[1] then
        if board.overlay[y][x] == 11 then
            if board.board[y][x] != 9 then
                for d=1,#dirs do
                    if y+dirs[d][2] > 0
                    and y+dirs[d][2] <= #board.board
                    and x+dirs[d][1] > 0
                    and x+dirs[d][1] <= #board.board[1]
                    and board.overlay[y+dirs[d][2]][x+dirs[d][1]] == 11 then
                        board:change_overlay(x+dirs[d][1],y+dirs[d][2],0)
                    end
                end
            end
            board:change_overlay(x,y,0)
        end
    end
end

Cart #tyofagzi-0 | 2020-07-02 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

P#78805 2020-07-02 22:00 ( Edited 2020-07-02 22:01)

Without context of what all these variables do through comments in your code, it isn't exactly feasible for outside people to give in-depth advice tailored to your situation. Like for example, what do the numbers 9 and 11 that you're checking for in the if-statements mean? Also, what is inside your change_overlay() function?

I can offer some general thoughts, though. The first thing I think of when there is trouble with recursive functions: do you have a local variable in the function for each grid cell that remembers whether it has been visited during the overarching recursive call? If you don't have a variable like this, or don't properly set it during a check, then the same grid cell will be checked again and again by every surrounding grid cell as those are checked, while it in turn checks all its surrounding cells again, leading to a never-ending and explosivley-expanding cascade of calls which might very well get you out of memory.

P#78807 2020-07-02 22:48 ( Edited 2020-07-02 22:55)

I apologize, I never really tend to share code. I don't really want an answer tailored to my code, I was just showing it. Instead, I would like to know if anyone has an optimized way of recursively checking adjacent tiles in a game like minsweeper.

P#78810 2020-07-03 00:17

This is not really readable.

But if it's any help - any time I've run into that kind of problem is because I accidentally created an infinite recursion loop.

Draw debug information, and use a flip() in your loop to track how the recursion plays out and make sure you aren't doing something over and over again.

P#78827 2020-07-03 06:29
2

So, I read through your code, and I'm guessing these are the major bugs:

  • board.overlay is what gets displayed on-screen, and board.board is the actual mines (9) and numbers (0-8). Since unrevealed tiles are 11s, you should always update the overlay from 11s before any recursion, so it doesn't think that old spaces are still unrevealed. This creates infinite loops.

  • The change_overlay calls just seem to set any revealed tile to the value 0, when they should set them to what the current value is in board.board at that position.

  • tile_reveal() isn't recursive, because it doesn't call tile_reveal() again inside of itself.

With this in mind, here's a rewrite of your tile_reveal function:

function tile_reveal(x,y)
 local w,h = #board.board[1],#board.board      --save the width and height in local variables
 local r = 0                                   --return what was revealed, as a number
 if y > 0 and y <= h and x > 0 and x <= w then
  if board.overlay[y][x] == 11 then            --if unrevealed space
   r = board.board[y][x]                       --then return what was clicked
   board:change_overlay(x,y,r)                 --and reveal board's value in overlay
   if r == 0 then                              --ONLY if zero nearby mines, recursively reveal neighbors
    for d=1,#dirs do
     tile_reveal(x+dirs[d][1], y+dirs[d][2])   --this is the recursion, it's like you clicked every neighboring square
    end
   end
  end
 end
 return r                                      --use this number to check if the player revealed a mine!
end

Note that the if statements at the top of the function already check to make sure the x y position is valid and unrevealed in the overlay, so you don't have to check them again before calling tile_reveal recursively. The big change is that r == 0 check before doing the for loop, otherwise it would always create 8 more function calls recursively. That is how you run out of memory with recursion, so you basically have to make sure that the only times you call the function again are when you're supposed to do that. Also note that I put change_overlay() above the for loop, so tiles will be revealed first, and then your next tile_reveal() call knows not to go backwards to the same space over and over again.

I haven't tested this code with everything else, and I think there are probably more bugs in your code that could prevent this from working properly, but hopefully the code and advice helps you head in the right direction. Good luck!

P#78854 2020-07-03 20:47

Thank you all for responding! What a great community we have here! I'll try and use all of your information to help fix this program. Again, thank you so much!!

P#78904 2020-07-04 19:55

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2024-03-29 07:43:16 | 0.011s | Q:19