Creating a Recursive Maze¶
maze_recursive.py¶
1"""
2Create a maze using a recursive division method.
3
4For more information on the algorithm, see "Recursive Division Method"
5at https://en.wikipedia.org/wiki/Maze_generation_algorithm
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_recursive
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 Recursive 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
36
37# How many pixels to keep as a minimum margin between the character
38# and the edge of the screen.
39VIEWPORT_MARGIN = 200
40
41MERGE_SPRITES = True
42
43
44def create_empty_grid(width, height, default_value=TILE_EMPTY):
45 """ Create an empty grid. """
46 grid = []
47 for row in range(height):
48 grid.append([])
49 for column in range(width):
50 grid[row].append(default_value)
51 return grid
52
53
54def create_outside_walls(maze):
55 """ Create outside border walls."""
56
57 # Create left and right walls
58 for row in range(len(maze)):
59 maze[row][0] = TILE_CRATE
60 maze[row][len(maze[row])-1] = TILE_CRATE
61
62 # Create top and bottom walls
63 for column in range(1, len(maze[0]) - 1):
64 maze[0][column] = TILE_CRATE
65 maze[len(maze) - 1][column] = TILE_CRATE
66
67
68def make_maze_recursive_call(maze, top, bottom, left, right):
69 """
70 Recursive function to divide up the maze in four sections
71 and create three gaps.
72 Walls can only go on even numbered rows/columns.
73 Gaps can only go on odd numbered rows/columns.
74 Maze must have an ODD number of rows and columns.
75 """
76
77 # Figure out where to divide horizontally
78 start_range = bottom + 2
79 end_range = top - 1
80 y = random.randrange(start_range, end_range, 2)
81
82 # Do the division
83 for column in range(left + 1, right):
84 maze[y][column] = TILE_CRATE
85
86 # Figure out where to divide vertically
87 start_range = left + 2
88 end_range = right - 1
89 x = random.randrange(start_range, end_range, 2)
90
91 # Do the division
92 for row in range(bottom + 1, top):
93 maze[row][x] = TILE_CRATE
94
95 # Now we'll make a gap on 3 of the 4 walls.
96 # Figure out which wall does NOT get a gap.
97 wall = random.randrange(4)
98 if wall != 0:
99 gap = random.randrange(left + 1, x, 2)
100 maze[y][gap] = TILE_EMPTY
101
102 if wall != 1:
103 gap = random.randrange(x + 1, right, 2)
104 maze[y][gap] = TILE_EMPTY
105
106 if wall != 2:
107 gap = random.randrange(bottom + 1, y, 2)
108 maze[gap][x] = TILE_EMPTY
109
110 if wall != 3:
111 gap = random.randrange(y + 1, top, 2)
112 maze[gap][x] = TILE_EMPTY
113
114 # If there's enough space, to a recursive call.
115 if top > y + 3 and x > left + 3:
116 make_maze_recursive_call(maze, top, y, left, x)
117
118 if top > y + 3 and x + 3 < right:
119 make_maze_recursive_call(maze, top, y, x, right)
120
121 if bottom + 3 < y and x + 3 < right:
122 make_maze_recursive_call(maze, y, bottom, x, right)
123
124 if bottom + 3 < y and x > left + 3:
125 make_maze_recursive_call(maze, y, bottom, left, x)
126
127
128def make_maze_recursion(maze_width, maze_height):
129 """ Make the maze by recursively splitting it into four rooms. """
130 maze = create_empty_grid(maze_width, maze_height)
131 # Fill in the outside walls
132 create_outside_walls(maze)
133
134 # Start the recursive process
135 make_maze_recursive_call(maze, maze_height - 1, 0, 0, maze_width - 1)
136 return maze
137
138
139class MyGame(arcade.Window):
140 """ Main application class. """
141
142 def __init__(self, width, height, title):
143 """
144 Initializer
145 """
146 super().__init__(width, height, title)
147
148 # Set the working directory (where we expect to find files) to the same
149 # directory this .py file is in. You can leave this out of your own
150 # code, but it is needed to easily run the examples using "python -m"
151 # as mentioned at the top of this program.
152 file_path = os.path.dirname(os.path.abspath(__file__))
153 os.chdir(file_path)
154
155 # Sprite lists
156 self.player_list = None
157 self.wall_list = None
158
159 # Player info
160 self.score = 0
161 self.player_sprite = None
162
163 # Physics engine
164 self.physics_engine = None
165
166 # Used to scroll
167 self.view_bottom = 0
168 self.view_left = 0
169
170 # Time to process
171 self.processing_time = 0
172 self.draw_time = 0
173
174 def setup(self):
175 """ Set up the game and initialize the variables. """
176
177 # Sprite lists
178 self.player_list = arcade.SpriteList()
179 self.wall_list = arcade.SpriteList()
180
181 # Set up the player
182 self.score = 0
183
184 maze = make_maze_recursion(MAZE_WIDTH, MAZE_HEIGHT)
185
186 # Create sprites based on 2D grid
187 if not MERGE_SPRITES:
188 # This is the simple-to-understand method. Each grid location
189 # is a sprite.
190 for row in range(MAZE_HEIGHT):
191 for column in range(MAZE_WIDTH):
192 if maze[row][column] == 1:
193 wall = arcade.Sprite(":resources:images/tiles/grassCenter.png", SPRITE_SCALING)
194 wall.center_x = column * SPRITE_SIZE + SPRITE_SIZE / 2
195 wall.center_y = row * SPRITE_SIZE + SPRITE_SIZE / 2
196 self.wall_list.append(wall)
197 else:
198 # This uses new Arcade 1.3.1 features, that allow me to create a
199 # larger sprite with a repeating texture. So if there are multiple
200 # cells in a row with a wall, we merge them into one sprite, with a
201 # repeating texture for each cell. This reduces our sprite count.
202 for row in range(MAZE_HEIGHT):
203 column = 0
204 while column < len(maze):
205 while column < len(maze) and maze[row][column] == 0:
206 column += 1
207 start_column = column
208 while column < len(maze) and maze[row][column] == 1:
209 column += 1
210 end_column = column - 1
211
212 column_count = end_column - start_column + 1
213 column_mid = (start_column + end_column) / 2
214
215 wall = arcade.Sprite(":resources:images/tiles/grassCenter.png", SPRITE_SCALING,
216 repeat_count_x=column_count)
217 wall.center_x = column_mid * SPRITE_SIZE + SPRITE_SIZE / 2
218 wall.center_y = row * SPRITE_SIZE + SPRITE_SIZE / 2
219 wall.width = SPRITE_SIZE * column_count
220 self.wall_list.append(wall)
221
222 # Set up the player
223 self.player_sprite = arcade.Sprite(":resources:images/animated_characters/female_person/femalePerson_idle.png", SPRITE_SCALING)
224 self.player_list.append(self.player_sprite)
225
226 # Randomly place the player. If we are in a wall, repeat until we aren't.
227 placed = False
228 while not placed:
229
230 # Randomly position
231 self.player_sprite.center_x = random.randrange(MAZE_WIDTH * SPRITE_SIZE)
232 self.player_sprite.center_y = random.randrange(MAZE_HEIGHT * SPRITE_SIZE)
233
234 # Are we in a wall?
235 walls_hit = arcade.check_for_collision_with_list(self.player_sprite, self.wall_list)
236 if len(walls_hit) == 0:
237 # Not in a wall! Success!
238 placed = True
239
240 self.physics_engine = arcade.PhysicsEngineSimple(self.player_sprite, self.wall_list)
241
242 # Set the background color
243 arcade.set_background_color(arcade.color.AMAZON)
244
245 # Set the viewport boundaries
246 # These numbers set where we have 'scrolled' to.
247 self.view_left = 0
248 self.view_bottom = 0
249 print(f"Total wall blocks: {len(self.wall_list)}")
250
251 def on_draw(self):
252 """
253 Render the screen.
254 """
255
256 # This command has to happen before we start drawing
257 arcade.start_render()
258
259 # Start timing how long this takes
260 draw_start_time = timeit.default_timer()
261
262 # Draw all the sprites.
263 self.wall_list.draw()
264 self.player_list.draw()
265
266 # Draw info on the screen
267 sprite_count = len(self.wall_list)
268
269 output = f"Sprite Count: {sprite_count}"
270 arcade.draw_text(output,
271 self.view_left + 20,
272 SCREEN_HEIGHT - 20 + self.view_bottom,
273 arcade.color.WHITE, 16)
274
275 output = f"Drawing time: {self.draw_time:.3f}"
276 arcade.draw_text(output,
277 self.view_left + 20,
278 SCREEN_HEIGHT - 40 + self.view_bottom,
279 arcade.color.WHITE, 16)
280
281 output = f"Processing time: {self.processing_time:.3f}"
282 arcade.draw_text(output,
283 self.view_left + 20,
284 SCREEN_HEIGHT - 60 + self.view_bottom,
285 arcade.color.WHITE, 16)
286
287 self.draw_time = timeit.default_timer() - draw_start_time
288
289 def on_key_press(self, key, modifiers):
290 """Called whenever a key is pressed. """
291
292 if key == arcade.key.UP:
293 self.player_sprite.change_y = MOVEMENT_SPEED
294 elif key == arcade.key.DOWN:
295 self.player_sprite.change_y = -MOVEMENT_SPEED
296 elif key == arcade.key.LEFT:
297 self.player_sprite.change_x = -MOVEMENT_SPEED
298 elif key == arcade.key.RIGHT:
299 self.player_sprite.change_x = MOVEMENT_SPEED
300
301 def on_key_release(self, key, modifiers):
302 """Called when the user releases a key. """
303
304 if key == arcade.key.UP or key == arcade.key.DOWN:
305 self.player_sprite.change_y = 0
306 elif key == arcade.key.LEFT or key == arcade.key.RIGHT:
307 self.player_sprite.change_x = 0
308
309 def on_update(self, delta_time):
310 """ Movement and game logic """
311
312 start_time = timeit.default_timer()
313
314 # Call update on all sprites (The sprites don't do much in this
315 # example though.)
316 self.physics_engine.update()
317
318 # --- Manage Scrolling ---
319
320 # Track if we need to change the viewport
321
322 changed = False
323
324 # Scroll left
325 left_bndry = self.view_left + VIEWPORT_MARGIN
326 if self.player_sprite.left < left_bndry:
327 self.view_left -= left_bndry - self.player_sprite.left
328 changed = True
329
330 # Scroll right
331 right_bndry = self.view_left + SCREEN_WIDTH - VIEWPORT_MARGIN
332 if self.player_sprite.right > right_bndry:
333 self.view_left += self.player_sprite.right - right_bndry
334 changed = True
335
336 # Scroll up
337 top_bndry = self.view_bottom + SCREEN_HEIGHT - VIEWPORT_MARGIN
338 if self.player_sprite.top > top_bndry:
339 self.view_bottom += self.player_sprite.top - top_bndry
340 changed = True
341
342 # Scroll down
343 bottom_bndry = self.view_bottom + VIEWPORT_MARGIN
344 if self.player_sprite.bottom < bottom_bndry:
345 self.view_bottom -= bottom_bndry - self.player_sprite.bottom
346 changed = True
347
348 if changed:
349 arcade.set_viewport(self.view_left,
350 SCREEN_WIDTH + self.view_left,
351 self.view_bottom,
352 SCREEN_HEIGHT + self.view_bottom)
353
354 # Save the time it took to do this.
355 self.processing_time = timeit.default_timer() - start_time
356
357
358def main():
359 """ Main method """
360 window = MyGame(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_TITLE)
361 window.setup()
362 arcade.run()
363
364
365if __name__ == "__main__":
366 main()