-
Notifications
You must be signed in to change notification settings - Fork 1
/
growing_tree.py
43 lines (40 loc) · 1.35 KB
/
growing_tree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import random
from grid import Grid
def create_maze(screen, mode, num_rows, num_cols, render):
''' Growing tree algorithm.
Can behave like "recursive backtracking" or almost like "Prim's"
with little change.
'''
maze = Grid(screen, num_rows, num_cols)
# Define the start of the maze
maze.set_start(maze.grid[0][0])
current = maze.grid[random.randrange(num_rows)][random.randrange(num_cols)]
current.visited = True
# Define maze goal
maze.set_goal(maze.grid[num_rows - 1][num_cols - 1])
# Stack of visited cells
stack = []
while True:
# Find unvisited neighbors
neighbors = maze.unvisited_neighbors(current)
if neighbors:
if len(neighbors) > 1:
stack.append(current)
# Select a random neighbor
r_neighbor = random.choice(neighbors)
# Remove wall between neighbor and current
maze.remove_wall(current, r_neighbor)
# Move to it
current = r_neighbor
current.visited = True
elif stack:
if mode == 'prim':
current = stack.pop(random.randrange(len(stack)))
elif mode == 'backtracker':
current = stack.pop()
# Else maze is done
else:
break
if render:
maze.draw(current)
return maze