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