I have recently challenged myself to write the Depth First Search algorithm for maze generation and am on the home stretch of completing it but I have been battling a specific error for most of the final half of the project.
I use binary for notating the connections between two neighboring nodes on the tree (learn network theory if you haven't already, it's absolutely wonderful and a very relevant field to programming) which goes as follows: 0:no directions,1:left,2:right,4:up,8:down, and any of these added together with produce their directions, ie: 3:left-right, 12:up-down, 7:left-right-up...
The following function is the primary function and theoretically works for any size 2d list (not considering Python cutting me off because of too many iterations >:^<).
def DepthFirstSearch(map,inX,inY,priorPoses,iteration,seed,mapSize):
if len(priorPoses) == mapSize:
print(F"Finished in {iteration} iterations")
print(map)
return map
x = inX
y = inY
mapHold = map
history = priorPoses
random.seed(seed + iteration)
if CheckNeighbors(map, x, y) == []:
CheckPriorPositions(map,priorPoses)
print(F"Check prior positions, {CheckNeighbors(map,x,y)}")
return DepthFirstSearch(mapHold,CheckPriorPositions(map,priorPoses)[0],CheckPriorPositions(map,priorPoses)[1],
priorPoses,iteration+1,seed,mapSize)
else:
move = CheckNeighbors(map, x, y)
move = random.choice(move)
if move == 1:
mapHold[inY][inX] += move
x -= 1
mapHold[y][x] += 2
else:
if move == 2:
mapHold[inY][inX] += move
x += 1
mapHold[y][x] += 1
else:
if move == 4:
mapHold[inY][inX] += move
y += 1
mapHold[y][x] += 8
else:
if move == 8:
mapHold[inY][inX] += move
y -= 1
mapHold[y][x] += 4
history.append([x,y])
return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
The CheckNeighbors function works perfectly fine but the CheckPriorPositions function has been cause for concern but I can't find a problem, I'll include it anyway though. If you have any tips on it then please give a tip, I somewhat feel like I'm missing something that would completeley trivialize this CheckPriorPositions function.
def CheckPriorPositions(map,priorPoses):
posesToSearch = priorPoses
posesToSearch.reverse()
for poses in range(0,len(posesToSearch)):
if CheckNeighbors(map,posesToSearch[poses][0],posesToSearch[poses][1]) != []:
return posesToSearch[poses]
The particular error I keep getting thrown is as follows:
Traceback (most recent call last):
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 87, in <module>
DepthFirstSearch(testMapD,0,0,testHistoryD,0,5,4)
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 46, in DepthFirstSearch
return DepthFirstSearch(mapHold,CheckPriorPositions(map,priorPoses)[0],CheckPriorPositions(map,priorPoses)[1],
TypeError: 'NoneType' object is not subscriptable
I don't really know where to start, but I do have some test data to give.
The following scenarios are simplified versions of real scenarios meant to test the functions:
testMapA = [[0,0],[0,0],[0,0]]
testHistoryA = []
DepthFirstSearch(testMapA,0,0,testHistoryA,0,5,6)
testMapB = [[4,0],[10,5],[2,9]]
testHistoryB = [[0,0],[0,1],[1,1],[1,2],[0,2]]
DepthFirstSearch(testMapB,0,2,testHistoryB,5,5,6)
testMapC = [[4,0],[14,5],[8,8]]
testHistoryC = [[0,0],[0,1],[0,2],[1,1],[1,2]]
DepthFirstSearch(testMapC,1,2,testHistoryC,5,5,6)
testMapD = [[0,0],[0,0]]
testHistoryD = []
DepthFirstSearch(testMapD,0,0,testHistoryD,0,5,4)
testMapE = [[0,0]]
testHistoryE = []
DepthFirstSearch(testMapE,0,0,testHistoryE,0,5,2)
There are several issues:
With a depth-first traversal you shouldn't recur deeper when backtracking. Backtracking involves getting out of recursion. That also means you don't need an explicit stack like you have priorPoses, ...etc. The callstack serves for that purpose.
For the reason in the previous point, you wouldn't need CheckPriorPositions, but it is also the cause of the runtime error: it can return None when the if condition is never true. And you have code that tries to take the first index of the returned value, so that raises an exception when it happens to be None.
Your code suggests that you think that an assignment like history = priorPoses makes a copy of the list. This is not true. Both names will reference the same list, so that mutations you do to that list using history will be reflected in what you see with priorPoses and vice versa. For instance, the call of priorPoses.reverse() is such a mutation.
I didn't find code that checks whether a cell was already visited. It looks like your approach would eventually "break all walls". You'd need to mark cells as already visited to avoid that you make multiple routes to the same cell. So I would suggest introducing a matrix with booleans to hold that "visited" information.
Calling the maze map shadows the native Python function with the same name. You don't want to do that. Call it maze or grid or board... but not map.
You can also reduce much of your code by avoiding repetition of similar code. The bit configuration allows for using bit operators, like ^ to get an opposite direction.
Not a problem, but I would not use function names that start with a capital. That is commonly done for class names. I prefer snake_case for function names:
import random
LEFT = 1
RIGHT = 2
UP = 4
DOWN = 8
SIDES = ((0, -1), (0, 1), (-1, 0), (1, 0))
def get_moves_to_nonvisited(visited, y, x):
height = len(visited)
width = len(visited[0])
return [
(side, y + dy, x + dx)
for side, (dy, dx) in enumerate(SIDES)
if 0 <= y + dy < height and 0 <= x + dx < width and not visited[y + dy][x + dx]
]
def depth_first_search(maze):
row = [False] * len(maze[0])
visited = [row[:] for _ in maze]
def recur(y, x):
visited[y][x] = True
while True:
moves = get_moves_to_nonvisited(visited, y, x)
if not moves:
return # just backtrack!
move, y2, x2 = random.choice(moves)
maze[y][x] |= 1 << move # Formula to convert 0,1,2,3 to 1,2,4,8
maze[y2][x2] |= 1 << (move ^ 1) # Formula for opposite direction
recur(y2, x2)
recur(0, 0)
I used this helper function to visualise the maze:
CROSSES = " ╴╶─╵┘└┴╷┐┌┬│┤├┼"
def stringify(maze):
row = [0] * (len(maze[0])*2+1)
spots = [row[:] for _ in range(len(maze)*2+1)]
for y, row in enumerate(maze):
y *= 2
for x, cell in enumerate(row):
x *= 2
for x2 in range(x, x+4, 2):
if (cell & 1) == 0:
spots[y ][x2] |= DOWN
spots[y+1][x2] |= UP | DOWN
spots[y+2][x2] |= UP
cell >>= 1
for y2 in range(y, y+4, 2):
if (cell & 1) == 0:
spots[y2][x ] |= RIGHT
spots[y2][x+1] |= RIGHT | LEFT
spots[y2][x+2] |= LEFT
cell >>= 1
return "\n".join(
"".join(CROSSES[spot] * (1 + (x % 2)*2) for x, spot in enumerate(row))
for y, row in enumerate(spots)
)
An example run:
width = height = 8
maze = [[0] * width for _ in range(height)]
depth_first_search(maze)
print(stringify(maze))
...outputs something like this:
┌───────────┬───────────────────┐
│ │ │
├───────┐ └───┐ ╷ ╶───┐ │
│ │ │ │ │ │
│ ╷ ├───┐ └───┴───┐ │ │
│ │ │ │ │ │ │
│ │ ╵ ├───────╴ │ └───┤
│ │ │ │ │
│ ├───╴ │ ┌───────┴───╴ │
│ │ │ │ │
│ └───────┤ └───┐ ╶───────┤
│ │ │ │
│ ╶───┐ └───┐ ├───────╴ │
│ │ │ │ │
├───╴ └───┐ ╵ ╵ ┌───╴ │
│ │ │ │
└───────────┴───────────┴───────┘
Using recursion is elegant, but as here a recursive call is made for every visit, the recursion depth could get equal to the total number of cells. For a 100x100 maze this would be 10000, which will exceed the (default) maximum recursion depth that Python allows.
To avoid that, you could work with an iterative solution that uses an explicit stack:
def depth_first_search(maze):
row = [False] * len(maze[0])
visited = [row[:] for _ in maze]
stack = [(0, 0)]
visited[0][0] = True
while stack:
y, x = stack[-1]
moves = get_moves_to_nonvisited(visited, y, x)
if not moves:
stack.pop()
else:
move, y2, x2 = random.choice(moves)
maze[y][x] |= 1 << move
maze[y2][x2] |= 1 << (move ^ 1)
stack.append((y2, x2))
visited[y2][x2] = True