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