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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
from cell import Cell
import time
import random
class Maze:
def __init__(
self,
x1,
y1,
num_rows,
num_cols,
cell_size_x,
cell_size_y,
win=None,
seed=None
):
self._cells = []
self._x1 = x1
self._y1 = y1
self._num_rows = num_rows
self._num_cols = num_cols
self._cell_size_x = cell_size_x
self._cell_size_y = cell_size_y
self._win = win
if seed:
random.seed(seed)
self._create_cells()
self._break_entrance_and_exit()
self._rec_break_walls(0, 0)
self._reset_cells_visited()
def _create_cells(self):
self._cells = [[Cell(self._win) for i in range(self._num_rows)] for j in range(self._num_cols)]
# for i in range(self._num_cols):
# col_cells = []
# for j in range(self._num_rows):
# col_cells.append(Cell(self._win))
# self._cells.append(col_cells)
[[self._draw_cell(i, j) for j in range(self._num_rows)] for i in range(self._num_cols)]
# for i in range(self._num_cols):
# for j in range(self._num_rows):
# self._draw_cell(i, j)
def _draw_cell(self, i, j):
if self._win is None:
return
x1 = self._x1 + i * self._cell_size_x
y1 = self._y1 + j * self._cell_size_y
x2 = x1 + self._cell_size_x
y2 = y1 + self._cell_size_x
self._cells[i][j].draw(x1, y1, x2, y2)
self._animate()
def _animate(self):
self._win.redraw()
time.sleep(0.01)
def _break_entrance_and_exit(self):
self._cells[0][0].twall = False
self._draw_cell(0, 0)
self._cells[-1][-1].bwall = False
self._draw_cell(self._num_cols-1, self._num_rows-1)
def _rec_break_walls(self, i, j):
self._cells[i][j].visited = True
while True:
next_index = []
# look for next cell to visit
# left
if i > 0 and not self._cells[i - 1][j].visited:
next_index.append((i - 1, j))
# up
if j > 0 and not self._cells[i][j - 1].visited:
next_index.append((i, j - 1))
# right
if i < self._num_cols - 1 and not self._cells[i + 1][j].visited:
next_index.append((i + 1, j))
# down
if j < self._num_rows - 1 and not self._cells[i][j + 1].visited:
next_index.append((i, j + 1))
# if no further cell to go, then draw and return
if len(next_index) == 0:
self._draw_cell(i, j)
return
# choose next direction to go in
direction_index = random.randrange(len(next_index))
next = next_index[direction_index]
# break walls between this and next cell
# left
if next[0] == i - 1:
self._cells[i][j].lwall = False
self._cells[i - 1][j].rwall = False
# up
if next[1] == j - 1:
self._cells[i][j].twall = False
self._cells[i][j - 1].bwall = False
# right
if next[0] == i + 1:
self._cells[i][j].rwall = False
self._cells[i + 1][j].lwall = False
# down
if next[1] == j + 1:
self._cells[i][j].bwall = False
self._cells[i][j + 1].twall = False
self._rec_break_walls(next[0], next[1])
def _reset_cells_visited(self):
for col in self._cells:
for cell in col:
cell.visited = False
def _rec_solve(self, i, j):
self._animate()
self._cells[i][j].visited = True
if i == self._num_cols - 1 and j == self._num_rows - 1:
return True
# try moving left
if (
i > 0
and not self._cells[i][j].lwall
and not self._cells[i - 1][j].visited
):
self._cells[i][j].draw_move(self._cells[i - 1][j])
if self._rec_solve(i - 1, j):
return True
else:
self._cells[i][j].draw_move(self._cells[i - 1][j], True)
# try moving up
if (
j > 0
and not self._cells[i][j].twall
and not self._cells[i][j - 1].visited
):
self._cells[i][j].draw_move(self._cells[i][j - 1])
if self._rec_solve(i, j - 1):
return True
else:
self._cells[i][j].draw_move(self._cells[i][j - 1], True)
# try moving right
if (
i < self._num_cols - 1
and not self._cells[i][j].rwall
and not self._cells[i + 1][j].visited
):
self._cells[i][j].draw_move(self._cells[i + 1][j])
if self._rec_solve(i + 1, j):
return True
else:
self._cells[i][j].draw_move(self._cells[i + 1][j], True)
# try moving down
if (
j < self._num_rows - 1
and not self._cells[i][j].bwall
and not self._cells[i][j + 1].visited
):
self._cells[i][j].draw_move(self._cells[i][j + 1])
if self._rec_solve(i, j + 1):
return True
else:
self._cells[i][j].draw_move(self._cells[i][j + 1], True)
# went wrong way -> backtrack
return False
def solve(self):
return self._rec_solve(0, 0)
|
