Creating a Depth First Maze#
maze_depth_first.py#
1"""
2Create a maze using a depth-first search maze generation algorithm.
3For more information on this algorithm see:
4https://www.algosome.com/articles/maze-generation-depth-first.html
5...or search up some other examples.
6
7Artwork from https://kenney.nl
8
9If Python and Arcade are installed, this example can be run from the command line with:
10python -m arcade.examples.maze_depth_first
11"""
12from __future__ import annotations
13
14import random
15import arcade
16import timeit
17
18NATIVE_SPRITE_SIZE = 128
19SPRITE_SCALING = 0.25
20SPRITE_SIZE = int(NATIVE_SPRITE_SIZE * SPRITE_SCALING)
21
22SCREEN_WIDTH = 1000
23SCREEN_HEIGHT = 700
24SCREEN_TITLE = "Maze Depth First Example"
25
26MOVEMENT_SPEED = 8
27
28TILE_EMPTY = 0
29TILE_CRATE = 1
30
31# Maze must have an ODD number of rows and columns.
32# Walls go on EVEN rows/columns.
33# Openings go on ODD rows/columns
34MAZE_HEIGHT = 51
35MAZE_WIDTH = 51
36
37MERGE_SPRITES = True
38
39# How many pixels to keep as a minimum margin between the character
40# and the edge of the screen.
41VIEWPORT_MARGIN = 200
42
43
44def _create_grid_with_cells(width, height):
45 """ Create a grid with empty cells on odd row/column combinations. """
46 grid = []
47 for row in range(height):
48 grid.append([])
49 for column in range(width):
50 if column % 2 == 1 and row % 2 == 1:
51 grid[row].append(TILE_EMPTY)
52 elif column == 0 or row == 0 or column == width - 1 or row == height - 1:
53 grid[row].append(TILE_CRATE)
54 else:
55 grid[row].append(TILE_CRATE)
56 return grid
57
58
59def make_maze_depth_first(maze_width, maze_height):
60 maze = _create_grid_with_cells(maze_width, maze_height)
61
62 w = (len(maze[0]) - 1) // 2
63 h = (len(maze) - 1) // 2
64 vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
65
66 def walk(x: int, y: int):
67 vis[y][x] = 1
68
69 d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
70 random.shuffle(d)
71 for (xx, yy) in d:
72 if vis[yy][xx]:
73 continue
74 if xx == x:
75 maze[max(y, yy) * 2][x * 2 + 1] = TILE_EMPTY
76 if yy == y:
77 maze[y * 2 + 1][max(x, xx) * 2] = TILE_EMPTY
78
79 walk(xx, yy)
80
81 walk(random.randrange(w), random.randrange(h))
82
83 return maze
84
85
86class MyGame(arcade.Window):
87 """ Main application class. """
88
89 def __init__(self, width, height, title):
90 """
91 Initializer
92 """
93 super().__init__(width, height, title)
94
95 # Sprite lists
96 self.player_list = None
97 self.wall_list = None
98
99 # Player info
100 self.score = 0
101 self.player_sprite = None
102
103 # Physics engine
104 self.physics_engine = None
105
106 # Used to scroll
107 self.view_bottom = 0
108 self.view_left = 0
109
110 # Time to process
111 self.processing_time = 0
112 self.draw_time = 0
113
114 def setup(self):
115 """ Set up the game and initialize the variables. """
116
117 # Sprite lists
118 self.player_list = arcade.SpriteList()
119 self.wall_list = arcade.SpriteList()
120
121 self.score = 0
122
123 # Create the maze
124 maze = make_maze_depth_first(MAZE_WIDTH, MAZE_HEIGHT)
125
126 # Create sprites based on 2D grid
127 if not MERGE_SPRITES:
128 # This is the simple-to-understand method. Each grid location
129 # is a sprite.
130 for row in range(MAZE_HEIGHT):
131 for column in range(MAZE_WIDTH):
132 if maze[row][column] == 1:
133 wall = arcade.Sprite(":resources:images/tiles/grassCenter.png", scale=SPRITE_SCALING)
134 wall.center_x = column * SPRITE_SIZE + SPRITE_SIZE / 2
135 wall.center_y = row * SPRITE_SIZE + SPRITE_SIZE / 2
136 self.wall_list.append(wall)
137 else:
138 # This uses new Arcade 1.3.1 features, that allow me to create a
139 # larger sprite with a repeating texture. So if there are multiple
140 # cells in a row with a wall, we merge them into one sprite, with a
141 # repeating texture for each cell. This reduces our sprite count.
142 for row in range(MAZE_HEIGHT):
143 column = 0
144 while column < len(maze):
145 while column < len(maze) and maze[row][column] == 0:
146 column += 1
147 start_column = column
148 while column < len(maze) and maze[row][column] == 1:
149 column += 1
150 end_column = column - 1
151
152 column_count = end_column - start_column + 1
153 column_mid = (start_column + end_column) / 2
154
155 wall = arcade.Sprite(":resources:images/tiles/grassCenter.png", scale=SPRITE_SCALING)
156 wall.center_x = column_mid * SPRITE_SIZE + SPRITE_SIZE / 2
157 wall.center_y = row * SPRITE_SIZE + SPRITE_SIZE / 2
158 wall.width = SPRITE_SIZE * column_count
159 self.wall_list.append(wall)
160
161 # Set up the player
162 self.player_sprite = arcade.Sprite(
163 ":resources:images/animated_characters/female_person/femalePerson_idle.png",
164 scale=SPRITE_SCALING)
165 self.player_list.append(self.player_sprite)
166
167 # Randomly place the player. If we are in a wall, repeat until we aren't.
168 placed = False
169 while not placed:
170
171 # Randomly position
172 self.player_sprite.center_x = random.randrange(MAZE_WIDTH * SPRITE_SIZE)
173 self.player_sprite.center_y = random.randrange(MAZE_HEIGHT * SPRITE_SIZE)
174
175 # Are we in a wall?
176 walls_hit = arcade.check_for_collision_with_list(self.player_sprite, self.wall_list)
177 if len(walls_hit) == 0:
178 # Not in a wall! Success!
179 placed = True
180
181 self.physics_engine = arcade.PhysicsEngineSimple(self.player_sprite, self.wall_list)
182
183 # Set the background color
184 self.background_color = arcade.color.AMAZON
185
186 # Set the viewport boundaries
187 # These numbers set where we have 'scrolled' to.
188 self.view_left = 0
189 self.view_bottom = 0
190
191 def on_draw(self):
192 """
193 Render the screen.
194 """
195
196 # This command has to happen before we start drawing
197 self.clear()
198
199 # Start timing how long this takes
200 draw_start_time = timeit.default_timer()
201
202 # Draw all the sprites.
203 self.wall_list.draw()
204 self.player_list.draw()
205
206 # Draw info on the screen
207 sprite_count = len(self.wall_list)
208
209 output = f"Sprite Count: {sprite_count}"
210 arcade.draw_text(output,
211 self.view_left + 20,
212 SCREEN_HEIGHT - 20 + self.view_bottom,
213 arcade.color.WHITE, 16)
214
215 output = f"Drawing time: {self.draw_time:.3f}"
216 arcade.draw_text(output,
217 self.view_left + 20,
218 SCREEN_HEIGHT - 40 + self.view_bottom,
219 arcade.color.WHITE, 16)
220
221 output = f"Processing time: {self.processing_time:.3f}"
222 arcade.draw_text(output,
223 self.view_left + 20,
224 SCREEN_HEIGHT - 60 + self.view_bottom,
225 arcade.color.WHITE, 16)
226
227 self.draw_time = timeit.default_timer() - draw_start_time
228
229 def on_key_press(self, key, modifiers):
230 """Called whenever a key is pressed. """
231
232 if key == arcade.key.UP:
233 self.player_sprite.change_y = MOVEMENT_SPEED
234 elif key == arcade.key.DOWN:
235 self.player_sprite.change_y = -MOVEMENT_SPEED
236 elif key == arcade.key.LEFT:
237 self.player_sprite.change_x = -MOVEMENT_SPEED
238 elif key == arcade.key.RIGHT:
239 self.player_sprite.change_x = MOVEMENT_SPEED
240
241 def on_key_release(self, key, modifiers):
242 """Called when the user releases a key. """
243
244 if key == arcade.key.UP or key == arcade.key.DOWN:
245 self.player_sprite.change_y = 0
246 elif key == arcade.key.LEFT or key == arcade.key.RIGHT:
247 self.player_sprite.change_x = 0
248
249 def on_update(self, delta_time):
250 """ Movement and game logic """
251
252 start_time = timeit.default_timer()
253
254 # Call update on all sprites (The sprites don't do much in this
255 # example though.)
256 self.physics_engine.update()
257
258 # --- Manage Scrolling ---
259
260 # Track if we need to change the viewport
261
262 changed = False
263
264 # Scroll left
265 left_bndry = self.view_left + VIEWPORT_MARGIN
266 if self.player_sprite.left < left_bndry:
267 self.view_left -= left_bndry - self.player_sprite.left
268 changed = True
269
270 # Scroll right
271 right_bndry = self.view_left + SCREEN_WIDTH - VIEWPORT_MARGIN
272 if self.player_sprite.right > right_bndry:
273 self.view_left += self.player_sprite.right - right_bndry
274 changed = True
275
276 # Scroll up
277 top_bndry = self.view_bottom + SCREEN_HEIGHT - VIEWPORT_MARGIN
278 if self.player_sprite.top > top_bndry:
279 self.view_bottom += self.player_sprite.top - top_bndry
280 changed = True
281
282 # Scroll down
283 bottom_bndry = self.view_bottom + VIEWPORT_MARGIN
284 if self.player_sprite.bottom < bottom_bndry:
285 self.view_bottom -= bottom_bndry - self.player_sprite.bottom
286 changed = True
287
288 if changed:
289 arcade.set_viewport(self.view_left,
290 SCREEN_WIDTH + self.view_left,
291 self.view_bottom,
292 SCREEN_HEIGHT + self.view_bottom)
293
294 # Save the time it took to do this.
295 self.processing_time = timeit.default_timer() - start_time
296
297
298def main():
299 """ Main function """
300 window = MyGame(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_TITLE)
301 window.setup()
302 arcade.run()
303
304
305if __name__ == "__main__":
306 main()