167 lines
5.1 KiB
Python
167 lines
5.1 KiB
Python
from Cell import Cell
|
|
import random
|
|
import time
|
|
from Window import Window
|
|
from typing import List
|
|
|
|
|
|
class Maze:
|
|
def __init__(
|
|
self,
|
|
x1:int,
|
|
y1:int,
|
|
num_rows:int,
|
|
num_cols:int,
|
|
cell_size_x:int,
|
|
cell_size_y:int,
|
|
win:Window|None=None,
|
|
seed:int|None=None,
|
|
):
|
|
self.cells:List[List[Cell]] = []
|
|
self.x1:int = x1
|
|
self.y1:int = y1
|
|
self.num_rows:int = num_rows
|
|
self.num_cols:int = num_cols
|
|
self.cell_size_x:int = cell_size_x
|
|
self.cell_size_y:int = cell_size_y
|
|
self.win:Window|None = win
|
|
|
|
if seed:
|
|
random.seed(seed)
|
|
|
|
self.create_cells()
|
|
self.break_entrance_and_exit()
|
|
self.break_walls_r(0, 0)
|
|
self.reset_cells_visited()
|
|
|
|
def create_cells(self) -> None:
|
|
for i in range(self.num_cols):
|
|
self.cells.append([])
|
|
for j in range(self.num_rows):
|
|
self.cells[i].append(Cell(self.win))
|
|
|
|
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) -> None:
|
|
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_y
|
|
self.cells[i][j].draw(x1, y1, x2, y2)
|
|
self.animate()
|
|
|
|
def animate(self) -> None:
|
|
if self.win is None:
|
|
return
|
|
self.win.redraw()
|
|
time.sleep(0.01)
|
|
|
|
def reset_cells_visited(self) -> None:
|
|
for i in range(self.num_cols):
|
|
for j in range(self.num_rows):
|
|
self.cells[i][j].visited = False
|
|
|
|
def break_entrance_and_exit(self) -> None:
|
|
self.cells[0][0].has_top_wall = False
|
|
self.draw_cell(0, 0)
|
|
self.cells[self.num_cols - 1][self.num_rows - 1].has_bottom_wall = False
|
|
self.draw_cell(self.num_cols - 1, self.num_rows - 1)
|
|
|
|
def break_walls_r(self, i:int, j:int) -> None:
|
|
self.cells[i][j].visited = True
|
|
while True:
|
|
last_index = []
|
|
|
|
if i > 0 and not self.cells[i - 1][j].visited:
|
|
last_index.append((i - 1, j))
|
|
if i < self.num_cols - 1 and not self.cells[i + 1][j].visited:
|
|
last_index.append((i + 1, j))
|
|
if j > 0 and not self.cells[i][j - 1].visited:
|
|
last_index.append((i, j - 1))
|
|
if j < self.num_rows - 1 and not self.cells[i][j + 1].visited:
|
|
last_index.append((i, j + 1))
|
|
|
|
if len(last_index) == 0:
|
|
self.draw_cell(i, j)
|
|
return
|
|
|
|
direction = random.randrange(len(last_index))
|
|
next_index = last_index[direction]
|
|
|
|
if next_index[0] == i + 1:
|
|
self.cells[i][j].has_right_wall = False
|
|
self.cells[i + 1][j].has_left_wall = False
|
|
if next_index[0] == i - 1:
|
|
self.cells[i][j].has_left_wall = False
|
|
self.cells[i - 1][j].has_right_wall = False
|
|
if next_index[1] == j + 1:
|
|
self.cells[i][j].has_bottom_wall = False
|
|
self.cells[i][j + 1].has_top_wall = False
|
|
if next_index[1] == j - 1:
|
|
self.cells[i][j].has_top_wall = False
|
|
self.cells[i][j - 1].has_bottom_wall = False
|
|
|
|
self.break_walls_r(next_index[0], next_index[1])
|
|
|
|
|
|
def solve_r(self, i:int, j:int) -> bool:
|
|
self.animate()
|
|
|
|
self.cells[i][j].visited = True
|
|
|
|
if i == self.num_cols - 1 and j == self.num_rows - 1:
|
|
return True
|
|
|
|
if (
|
|
i > 0
|
|
and not self.cells[i][j].has_left_wall
|
|
and not self.cells[i - 1][j].visited
|
|
):
|
|
self.cells[i][j].draw_move(self.cells[i - 1][j])
|
|
if self.solve_r(i - 1, j):
|
|
return True
|
|
else:
|
|
self.cells[i][j].draw_move(self.cells[i - 1][j], True)
|
|
|
|
if (
|
|
i < self.num_cols - 1
|
|
and not self.cells[i][j].has_right_wall
|
|
and not self.cells[i + 1][j].visited
|
|
):
|
|
self.cells[i][j].draw_move(self.cells[i + 1][j])
|
|
if self.solve_r(i + 1, j):
|
|
return True
|
|
else:
|
|
self.cells[i][j].draw_move(self.cells[i + 1][j], True)
|
|
|
|
if (
|
|
j > 0
|
|
and not self.cells[i][j].has_top_wall
|
|
and not self.cells[i][j - 1].visited
|
|
):
|
|
self.cells[i][j].draw_move(self.cells[i][j - 1])
|
|
if self.solve_r(i, j - 1):
|
|
return True
|
|
else:
|
|
self.cells[i][j].draw_move(self.cells[i][j - 1], True)
|
|
|
|
if (
|
|
j < self.num_rows - 1
|
|
and not self.cells[i][j].has_bottom_wall
|
|
and not self.cells[i][j + 1].visited
|
|
):
|
|
self.cells[i][j].draw_move(self.cells[i][j + 1])
|
|
if self.solve_r(i, j + 1):
|
|
return True
|
|
else:
|
|
self.cells[i][j].draw_move(self.cells[i][j + 1], True)
|
|
|
|
return False
|
|
|
|
def solve(self) -> bool:
|
|
return self.solve_r(0, 0)
|