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