Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

So I'm attempting to learn Python by way of Minesweeper. I've got experience with SDL, so I figured playing around with PyGame sounded like a fun way to learn the syntax of the language.

Anywho, I'm having an issue in uncovering adjacent open squares as you would in a normal game of Minesweeper. I click on a cell with 0 neighboring mines, and attempt to scan the top, left, right, and bottom to see if those also have 0 neighboring mines, and I do this recursively.

Here is the error that I receive:

RuntimeError: maximum recursion depth exceeded in cmp

And here is my algorithm:

#open up blank mines
def open_blank_cells(mines, cr, cc):
  #top
  if (cr > 0):
    t_mine = mines[cr-1][cc]
    t_mine.switch_state(3)
    if (t_mine.neighbor_mines == 0):
      open_blank_cells(mines, cr-1, cc)

  #right
  if (cc < 9):
    r_mine = mines[cr][cc+1]
    r_mine.switch_state(3)
    if (r_mine.neighbor_mines == 0):
      open_blank_cells(mines, cr, cc+1)

  #bottom
  if (cr < 9):
    r_mine = mines[cr+1][cc]
    r_mine.switch_state(3)
    if (r_mine.neighbor_mines == 0):
      open_blank_cells(mines, cr+1, cc)

  #left
  if (cc > 0):
    l_mine = mines[cr][cc-1]
    l_mine.switch_state(3)
    if (l_mine.neighbor_mines == 0):
      open_blank_cells(mines, cr, cc-1)

  return

where mines is my 2D array of cells, cr is the index of the current row (first array index), and cc is the index of the current column (second array index).

I thought that my algorithm was decently solid (but please tell me if I'm wrong there!!!), so I turned to the Internet and found that the default Python recursion limit of 1000 could be to blame. However, when I bump it higher with the call to sys.setrecursionlimit the game either exhibits the same behavior, or simply crashes as the system kills it.

When I comment out 2 of the 4 recursive checks in the function, it will open up blank cells without any problem. 3 or more however breaks the algorithm.


Edit

As requested....

Calculation of neighbor_mines

# if not a mine, figure out how many surround it
  for i in xrange(10):
    for j in xrange(10):
      if (mines[i][j].is_mine == False):
        #check top 3
        if (i > 0):
          if (j > 0):
            if (mines[i-1][j-1].is_mine == True):
              mines[i][j].neighbor_mines += 1


          if (mines[i-1][j].is_mine == True):
            mines[i][j].neighbor_mines += 1

          if (j < 9):
            if (mines[i-1][j+1].is_mine == True):
              mines[i][j].neighbor_mines += 1

        #check left and right
        if (j > 0):
          if (mines[i][j-1].is_mine == True):
            mines[i][j].neighbor_mines += 1

        if (j < 9):
          if (mines[i][j+1].is_mine == True):
            mines[i][j].neighbor_mines += 1

        #check bottom 3
        if (i < 9):
          if (j > 0):
            if (mines[i+1][j-1].is_mine == True):
              mines[i][j].neighbor_mines += 1

          if (mines[i+1][j].is_mine == True):
            mines[i][j].neighbor_mines += 1

          if (j < 9):
            if (mines[i+1][j+1].is_mine == True):
              mines[i][j].neighbor_mines += 1

Switch_state

 def switch_state(self, newstate):
    self.state = newstate

    #marked as mine
    if (newstate == 1):
      nf = "sq_mine_marked.png"
    elif (newstate == 2):
      nf = "sq_mine_question.png"
    elif (newstate == 3):
      nf = "sq_mine_open.png"
    elif (newstate == 4):
      nf = "sq_mine_mine.png"
    else:
      nf = "sq_mine.png"

    oldrect = self.rect #save old rect as load_image overwrites it
    self.image, self.rect = load_image(nf, (255,0,255))
    self.rect = oldrect
share|improve this question
    
Could you show code for neighbor_mines and switch_state? –  CiscoIPPhone Aug 12 '11 at 12:58
    
sure, no problem –  espais Aug 12 '11 at 13:01
    
It seems you want to create a flood fill ... without actually flooding the matrix (say, with "revealed" status instead of "hidden"). –  Martin Sojka Aug 12 '11 at 14:00
add comment

1 Answer

up vote 10 down vote accepted

Imagine the following setup:

1 1 1 1 1 1 
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

As a side note, I refer to squares in the matrix like this: (row, column). I've represented mines with "1" and empty spaces with "0". Assume the user clicks on the empty space at (2, 2) (the corner at the top-left is (0, 0)).

This is what would happen:

  • the square at (2, 3) is empty and has no adjacent mines. Let's call our function for those coordinates
  • in the new function call we notice that (3, 3) is empty and has no adjacent mines, let's call the function for that space as well
  • (3, 2) is a valid place too, let's call again
  • in the fourth call we'll notice that (2, 2) is empty and has no nearby mines, so we're back at square one, thus creating an endless loop

Any adjacent squares that each do not have adjacent mines will create an endless loop once your recursive function is called for either of them. Simply putting in a condition to not call the function again for the square you just came from wouldn't have been enough, as can be seen in the example above.

One solution is to create another matrix that can show what squares have already been visited. If the current square has already been visited, return from the function immediately. Otherwise, mark is as a visited square and carry on with your usual code.

share|improve this answer
    
ohhhhhhhhh crap...that makes a lot more sense now. thanks! –  espais Aug 12 '11 at 13:30
    
+1 Excellent answer. –  Jonathan Hobbs Aug 12 '11 at 14:06
    
As TokPhobia said, you should somehow save and get info about what cells are already processed. Another way to save this info is dictionary. Python has them. It would be of the same perfomance, as to have "another matrix". –  Nakilon Aug 12 '11 at 15:38
1  
i just added a boolean flag to my Mine class...then reset that flag once all the recursive calls are complete –  espais Aug 12 '11 at 18:24
1  
@espais For something as light as minesweeper that will probably do the job just fine. –  Jonathan Hobbs Aug 12 '11 at 23:58
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.