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