Maze-Solver/maze.py at main · SandeshNarayan/Maze-Solver · GitHub

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
from cell import Cell
import time, random

class Maze:
    def __init__(self, x1, y1, num_rows, num_cols, cell_size_x, cell_size_y, win=None, seed = None):
        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
        self.seed = seed
        if not self.seed:
            random.seed(self.seed)

        self._cells =[]
        self._create_cells()
        self._break_entrance_and_exit()
        self._break_walls_r(0,0)
        self._reset_cells_visited()


    def _create_cells(self):
        for _ in range(self.num_cols):
            column = []
            for _ in range(self.num_rows):
                cell = Cell(self.win)
                column.append(cell)
            self._cells.append(column)

        for i in range(len(self._cells)):
            for j in range(len(self._cells[i])):
                self._draw_cells(i,j)

    def _draw_cells(self, i, j):
        if not self.win:
            return
        cell = self._cells[i][j]
        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
        cell.draw(x1,y1,x2,y2)
        self._animate()

    def _animate(self):
        if not self.win:
            return
        self.win.redraw()
        time.sleep(0.05)


    def _break_entrance_and_exit(self):
        top_left_cell = self._cells[0][0]
        bottom_left_cell = self._cells[self.num_cols-1][self.num_rows-1]

        top_left_cell.has_top_wall = False
        self._draw_cells(0, 0)
        bottom_left_cell.has_bottom_wall = False
        self._draw_cells(self.num_cols-1, self.num_rows-1)


    def _break_walls_r(self, i, j):
        if i < 0 or i >= self.num_cols or j < 0 or j >= self.num_rows:
            return
        cell = self._cells[i][j]
        if cell.visited:
            return
        cell.visited = True

        while True:
            possible_directions = []

            if i>0 and not self._cells[i-1][j].visited:
                possible_directions.append(("left", i-1, j))

            if i<self.num_cols-1 and not self._cells[i+1][j].visited:
                possible_directions.append(("right", i+1, j))

            if j>0 and not self._cells[i][j-1].visited:
                possible_directions.append(("top", i, j-1))

            if j<self.num_rows-1 and not self._cells[i][j+1].visited:
                possible_directions.append(("bottom", i, j+1))

            if not possible_directions:
                self._draw_cells(i,j)
                return

            direction, next_i, next_j = random.choice(possible_directions)


            if direction == "left":
                self._cells[i][j].has_left_wall = False
                self._cells[next_i][next_j].has_right_wall = False

            elif direction == "right":
                self._cells[i][j].has_right_wall = False
                self._cells[next_i][next_j].has_left_wall = False

            elif direction == "top":
                self._cells[i][j].has_top_wall = False
                self._cells[next_i][next_j].has_bottom_wall = False

            elif direction == "bottom":
                self._cells[i][j].has_bottom_wall = False
                self._cells[next_i][next_j].has_top_wall = False

            self._draw_cells(i,j)
            self._break_walls_r(next_i,next_j)

    def _reset_cells_visited(self):
        for i in range(len(self._cells)):
            for j in range(len(self._cells[i])):
                cell = self._cells[i][j]
                cell.visited = False

    def _solve_r(self, i,j):

        self._animate()
        cell = self._cells[i][j]
        cell.visited = True
        if i == self.num_cols-1 and j == self.num_rows-1:
            return True
        possible_directions = []


        if i>0 and not cell.has_left_wall and not self._cells[i-1][j].visited:
            possible_directions.append(("left", i-1, j))

        if i<self.num_cols-1 and not cell.has_right_wall and not self._cells[i+1][j].visited:
            possible_directions.append(("right", i+1, j))

        if j>0 and not cell.has_top_wall and not self._cells[i][j-1].visited:
            possible_directions.append(("top", i, j-1))

        if j<self.num_rows-1 and not cell.has_bottom_wall and not self._cells[i][j+1].visited:
            possible_directions.append(("bottom", i, j+1))

        for _, next_i, next_j in possible_directions:

            cell.draw_move(self._cells[next_i][next_j])
            if self._solve_r(next_i, next_j):
                return True
            else:
                cell.draw_move(self._cells[next_i][next_j], undo=True)

        return False

    def solve(self):
        return self._solve_r(0,0)