I made a program that ask the user a size and generate a perfect maze of size n^2 using the recursive backtarcking algorithm. I've run into this error and saw that i could simply use :
sys.setrecursionlimit(8000)
It worked well at the begining but when i increased the size of the maze my python program simply exited without saying anything...
Here is the dictionary i use to check directions :
_dic = {
"N": (-1, 0),
"S": (1, 0),
"E": (0, 1),
"W": (0, -1),
}
I store the maze inside a numpy array of str, i only store the part of the maze that is going to be modified and add the rest for display when i convert it into a string. For instance a maze of size 3 (3x3) will look like this in display :
.######
..#.#.#
#######
#.#.#.#
#######
#.#.#..
######.
But in my array i'll only have the middle part :
.#.#.
#####
.#.#.
#####
.#.#.
This is just to try to optimize a bit...
Here is the actual backtracking function :
# Recursive backtracking function that takes a posx and posy as position of the cell to visit
def _backtrack(self, posx, posy):
self._map[posx][posy] = 'V' # Mark the cell as visited
while True:
# hasNeighbors returns a empty list if no valid neighbors ar found
# but returns a list of cardinal directions corresponding to valid neighbors if found such as ["N", "E"]
# if there si a valid neighbor on the right and beneath.
dir = self._hasNeighbors(posx, posy)
lenght = len(dir)
# If there is no valid neighbors this is a dead end then return to backtrack
if lenght == 0:
return
# select a random direction to move to and remove it from the list
toBreak = dir.pop(dir.index(random.choice(dir)))
# Replace '#' by '.'
self._map[posx + self._dic[toBreak][0]][posy + self._dic[toBreak][1]] = '.'
# If there is only one valid neightbor break the wall and update posx and posy
# It uses the while loop to keep visiting cells without recursion as long as there is only one choice
if lenght == 1:
posx += self._dic[toBreak][0] * 2
posy += self._dic[toBreak][1] * 2
self._map[posx][posy] = 'V'
#recursive call of the backtrack function with the position of the cell we want to visit
else:
self._backtrack(posx + self._dic[toBreak][0] * 2, posy + self._dic[toBreak][1] * 2)
And here is the hasNeighbors one :
def _hasNeighbors(self, posx, posy):
result = []
# Checking neighbors in each direction
for dir in self._dic.keys():
# If the indexes doesn't exceed the size of the maze
if 0 <= posx + self._dic[dir][0] < self._size * 2 - 1 and 0 <= posy + self._dic[dir][1] < self._size * 2 - 1:
# If the neighbor hasn't been visited
if self._map[posx + self._dic[dir][0] * 2][posy + self._dic[dir][1] * 2] == '.':
#Append this direction to the list of valid neighbors
result.append(dir)
return result
It works like a charm for small sizes like 5, 20, 50... but when i start to go a bit bigger i either have the maximum recursion depth error if i don't increase the limit and if i do increase it the program simply exit without saying anything like this :
PS C:\Users\pierr\Travail\Code\Amazing-Maze> python -m amazingmaze
Please entre the size of the maze : 100
PS C:\Users\pierr\Travail\Code\Amazing-Maze>
I really don't know how to solve this. I don't understand why it blocks at such small sizes i mean i should be able to generate bigger size without breaking a sweat... Is it my recursive backtracking implementation that is the issue have i missed something ? My teacher told me that it was because my stopping condition wasn't working and i was probably visiting cells that i already visited but i kinda disagree, there is obviously something wrong but i really don't think it's that. You can find the complete code at https://github.com/lebair-pierre-alexis/Amazing-Maze
Your recursive function _backtrack is suitable for Tail Call Optimization. Tail call optimization allows unlimited recursion (when applicable). But, Python does not have this out of the box for reasons explained here by Guido van Rossum, the developer of Python.
Code
# Tail recursion decorator (could place in file tail_recursion.py)
class Recurse(Exception):
def __init__(self, *args, **kwargs):
self.args = args
self.kwargs = kwargs
def recurse(*args, **kwargs):
raise Recurse(*args, **kwargs)
def tail_recursive(f):
def decorated(*args, **kwargs):
while True:
try:
return f(*args, **kwargs)
except Recurse as r:
args = r.args
kwargs = r.kwargs
continue
return decorated
# Recursive backtracking function that takes a posx and posy as position of the cell to visit
@tail_recursive # add recursive decorator
def _backtrack(self, posx, posy):
self._map[posx][posy] = 'V' # Mark the cell as visited
while True:
# hasNeighbors returns a empty list if no valid neighbors ar found
# but returns a list of cardinal dir_ections corresponding to valid neighbors if found such as ["N", "E"]
# if there is a valid neighbor on the right and beneath.
dir_ = self._hasNeighbors(posx, posy) # refactor dir to dir_ to avoid overwriting builtin function
lenght = len(dir_)
# If there is no valid neighbors this is a dead end then return to backtrack
if lenght == 0:
return
# select a random direction to move to and remove it from the list
toBreak = dir_.pop(dir_.index(random.choice(dir_)))
# Replace '#' by '.'
self._map[posx + self._dic[toBreak][0]][posy + self._dic[toBreak][1]] = '.'
# If there is only one valid neightbor break the wall and update posx and posy
# It uses the while loop to keep visiting cells without recursion as long as there is only one choice
if lenght == 1:
posx += self._dic[toBreak][0] * 2
posy += self._dic[toBreak][1] * 2
self._map[posx][posy] = 'V'
#recursive call of the backtrack function with the position of the cell we want to visit
else:
# Replace call with tail recursive call
# self._backtrack(posx + self._dic[toBreak][0] * 2, posy + self._dic[toBreak][1] * 2)
recurse(self, posx + self._dic[toBreak][0] * 2, posy + self._dic[toBreak][1] * 2)