check validation for input for perfect maze

Question

I'm working on a project to build a perfect maze. I have a class Maze and a class Cell which represents each square in a maze. In my Cell class, I have four Boolean variable(north, south, east, west) to represent whether there is a wall at north or south.. of cell. There is also a boolean variable named visit to check if the cell has been visited. Here is my code for the init() for Cell class.

def __init__(self):
    self.north = True
    self.south = True
    self.east = True
    self.west = True
    self.visit = False

And for the Maze class, I have self.maze(a bunch of Cell) and the self.size = N(build a N*N maze). Here is the init() for class Maze:

def __init__(self, N):

    self.size = N
    self.maze = [[i for i in range(N + 2)] for i in range(N + 2)]

    for r in range(self.size + 2):
        for c in range(self.size + 2):
            self.maze[r][c] = Cell()

While I'm updating the index of maze, I wrote two function to check whether the newX and newY is in the range of 1 <= x <= self.size and 1 <= y <= self.size, also whether the cell has been visited. Here is the code:

def in_range(self, x, y):

    if 1 <= x <= self.size and 1 <= y <= self.size:
        return True
    else:
        return False

def is_valid(self, x, y):

    if not self.maze[x][y].getVisit() and self.in_range(x,y):
        return True
    else:
        return False

After all this, I wrote the main structure:

def walk(self, s, x, y):

    neighbor = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]


    if s.size() == self.size**2: return

    else:

        while True:
            new = choice(neighbor)#choice() is import from random
            #print(self.is_valid(new[0], new[1]))
            if self.is_valid(new[0], new[1]):break
            else:
                if len(neighbor) != 0:
                    neighbor.remove(new)
                    new = choice(neighbor)
                else:
                    temp = s.pop(s)
                    self.walk(s, temp[0], temp[1])

                break
    print(new)

However, running my code stills give me index that is not between 1 and self.size. I couldn't figure out why, I think my checking algorithm works fine. Here is what I got:

>>> ================================ RESTART 

================================
>>> 
>>> a = Maze(5)
>>> a.search()
1 2
(1, 3)
(2, 3)
(2, 4)
(1, 4)
(2, 4)
(2, 5)
(3, 5)
(4, 5)
(4, 4)
(4, 3)
(3, 3)
(3, 2)
(2, 2)
(2, 1)
(1, 1)
(0, 1)
(-1, 1)
(0, 1)
(1, 1)
(0, 1)
(-1, 1)
(-1, 2)
(-1, 1)
(0, 1)

Can someone help me out? plz, really appreciate!

Answer 1

In Python range starts with 0 if you don't specify another start position. Thus, when you initialize your maze, you have cells in (0, *) and (*, 0):

for r in range(self.size + 2):
    for c in range(self.size + 2):
        self.maze[r][c] = Cell()

When you compute your neighbors you don't check that you don't get out:

neighbor = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]

And it's only after having assigned new to such a coordinates that you check it is valid. But then, if it is not valid and there is no neighbors, you're calling walk again. You should try to check for in_range independently of visit.

Also your loop can only run once because either new is valid and you break out of the loop or it is not valid and you break out of the loop.

Finally, you forgot to give us the search function and what s is (and s.pop(s) looks funny as usually the argument of pop is an index, not the sequence again).

Answer 2

You could have found this by looking closely at walk(), or splattering it with print statements to trace things. Things are going wrong at the extremities of your grid (when either x or y == 0 or N-1). Unless you're allowing wraparound, I assume your grid initialization puts walls on the north of the grid(y==0), south, east and west. By the way, your grid has two unnecessary rows and columns: if you want N cells, numbered O..(N-1), then use range(N), not range(N+2), Or else use range(1,N+1). (Do you pad any unneeded cells with valid==False?)

Anyway, walk() first picks a random neighbor cell and breaks out of the while-loop if it is a valid cell. But if it isn't, it cheerfully picks any remaining neighbor cell (regardless whether valid) and soldiers on. That's your bug. Always test validity. If it has run out of valid neighbor cells, it backtracks by doing s.pop(s). s.pop(s) also looks like a bug. Why not s.pop()? Btw, call the variable path instead of s.

Also, this is only checking the coords for validity; you never actually check if you've visited that cell before, so there's no end condition to your recursive backtracking; you could very easily go in loops.

You could help yourself a lot if you refactored walk() into using a separate generator get_random_valid_neighbor() which returns randomly-chosen neighbors already tested as valid (and None when you run out of neighbors).

def walk(self, s, x, y):

...
      while True:
            new = choice(neighbor)
            if self.is_valid(new[0], new[1]):break # tested for validity
            else:
                if len(neighbor) != 0:
                    neighbor.remove(new)
                    new = choice(neighbor) # BUG: never tested for validity
                ...