diff options
Diffstat (limited to 'maze.py')
| -rw-r--r-- | maze.py | 135 |
1 files changed, 130 insertions, 5 deletions
@@ -1,5 +1,6 @@ from cell import Cell import time +import random class Maze: def __init__( @@ -10,7 +11,8 @@ class Maze: num_cols, cell_size_x, cell_size_y, - win=None + win=None, + seed=None ): self._cells = [] self._x1 = x1 @@ -20,15 +22,26 @@ class Maze: 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)]*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) + 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: @@ -49,3 +62,115 @@ class Maze: 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) |