Creating a Recursive Maze

Screen shot of a maze created by recursion
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()