finished maze solver

3 files changed, 146 insertions, 7 deletions

diff --git a/cell.py b/cell.py
index c2f763b..9aed822 100644
--- a/cell.py
+++ b/cell.py
@@ -11,6 +11,7 @@ class Cell:
         self.twall = twall
         self.rwall = rwall
         self.bwall = bwall
+        self.visited = False
 
     def draw(self, x1, y1, x2, y2):
         if self._win is None:
@@ -26,8 +27,11 @@ class Cell:
         self._win.draw_line(Line(Point(x1, y2), Point(x2, y2))) if self.bwall else self._win.draw_line(Line(Point(x1, y2), Point(x2, y2)), "white")
 
     def draw_move(self, to_cell, undo=False):
-        center_start = Point((self._x1+self._x2)>>1, (self._y1+self._y2)>>1)
-        center_end = Point((to_cell._x1+to_cell._x2)>>1, (to_cell._y1+to_cell._y2)>>1)
+        half_length_start = abs(self._x2 - self._x1) // 2
+        center_start = Point(self._x1 + half_length_start, self._y1 + half_length_start)
+
+        half_length_end = abs(to_cell._x2 - to_cell._x1) // 2
+        center_end = Point(to_cell._x1 + half_length_end, to_cell._y1 + half_length_end)
         fill_color = "red"
         if undo:
             fill_color = "gray"
diff --git a/main.py b/main.py
index 56f0817..8c88d7e 100755
--- a/main.py
+++ b/main.py
@@ -3,6 +3,8 @@
 from graphics import Window
 from maze import Maze
 
+import sys
+
 def main():
     num_rows = 12
     num_cols = 16
@@ -11,9 +13,17 @@ def main():
     screen_y = 600
     cell_size_x = (screen_x - 2 * margin) / num_cols
     cell_size_y = (screen_y - 2 * margin) / num_rows
+
+    sys.setrecursionlimit(10000)
     win = Window(screen_x, screen_y)
 
     maze = Maze(margin, margin, num_rows, num_cols, cell_size_x, cell_size_y, win)
+    print("maze created")
+    is_solvable = maze.solve()
+    if not is_solvable:
+        print("cannot solve maze")
+    else:
+        print("maze solved")
 
     win.wait_for_close()
 
diff --git a/maze.py b/maze.py
index 71086cb..ac7d1b8 100644
--- a/maze.py
+++ b/maze.py
@@ -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)