hexgen/maze.py at main · cherryroots/hexgen · 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
import random
from hex import Hex
from graphics import Window, Point
from typing import List
from math import sqrt


class Maze:
    def __init__(
        self,
        x: int,
        y: int,
        num_rows: int,
        num_cols: int,
        cell_size_x: int,
        cell_size_y: int,
        win: Window = None,
        start: Point = None,
        end: Point = None,
        seed=None,
    ):
        self._x_off = x
        self._y_off = y
        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._start = Point(0, 0) if start is None else start
        self._end = (
            Point(self._num_cols - 1, self._num_rows - 1) if end is None else end
        )

        if seed:
            random.seed(seed)

        self._cells: List[List[Hex]] = []

    def _create_cells(self) -> None:
        if self._win:
            self._win.set_tickspeed(4000)  # Set tickspeed for cell creation
        for i in range(self._num_cols):
            column = []
            for j in range(self._num_rows):
                column.append(Hex(i, j, self._win))
            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: int, j: int) -> None:
        if self._win is None:
            return

        horiz = sqrt(3) * self._cell_size_y / 2
        vert = 3 / 2 * self._cell_size_x / 2
        horiz_offset = horiz / 2 if j % 2 == 1 else 0

        top_left_x = self._x_off + i * horiz
        top_left_y = self._y_off + j * vert
        bottom_right_x = top_left_x + self._cell_size_x
        bottom_right_y = top_left_y + self._cell_size_y

        cx = ((top_left_x + bottom_right_x) / 2) + horiz_offset
        cy = (top_left_y + bottom_right_y) / 2

        hex = self._cells[i][j]
        hex.draw(cx, cy, self._cell_size_x, self._cell_size_y)
        self._animate()

    def _animate(self) -> None:
        if self._win is None:
            return
        self._win.redraw()

    def _reset_visited(self) -> None:
        for col in self._cells:
            for hex in col:
                hex.visited = False

    def _break_entrance_and_exit(self) -> None:
        start = self._cells[self._start.x][self._start.y]
        end = self._cells[self._end.x][self._end.y]
        start.break_wall(2)
        self._draw_cells(start._col, start._row)
        end.break_wall(5)
        self._draw_cells(end._col, end._row)

    def _break_walls_r(self, i: int, j: int) -> None:
        if self._win:
            self._win.set_tickspeed(2000)  # Set tickspeed for wall breaking
        current = self._cells[i][j]
        current.visited = True
        while True:
            to_visit: List[Point] = []
            neighbors = current.bounded_neighbors(self._num_cols, self._num_rows)
            for p in neighbors:
                neighbor = self._cells[p.x][p.y]
                if not neighbor.visited:
                    to_visit.append(p)

            if len(to_visit) == 0:
                self._draw_cells(i, j)
                return

            direction = random.randrange(len(to_visit))
            p = to_visit[direction]
            next = self._cells[p.x][p.y]

            current.break_between(next)
            next.break_between(current)
            self._break_walls_r(p.x, p.y)

    def _solve_r(self, i: int, j: int):
        if self._win:
            self._win.set_tickspeed(500)  # Set tickspeed for solving
        self._animate()

        current = self._cells[i][j]
        current.visited = True

        if i == self._end.x and j == self._end.y:
            return True

        neighbors = current.bounded_neighbors(self._num_cols, self._num_rows)

        for p in neighbors:
            neighbor = self._cells[p.x][p.y]
            if neighbor.visited:
                continue
            if current.wall_between(neighbor) or neighbor.wall_between(current):
                continue
            current.draw_move(neighbor)
            if self._solve_r(neighbor._col, neighbor._row):
                return True
            current.draw_move(neighbor, undo=True)

        return False

    def solve(self):
        return self._solve_r(*self._start.xy())

    def generate_and_solve(self):
        self._create_cells()
        self._break_entrance_and_exit()
        self._break_walls_r(*self._start.xy())
        self._reset_visited()

        self.solve()