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