# 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:
11"""
12import random
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
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        # camera for scrolling
159        self.cam = None
160
161        # Time to process
162        self.processing_time = 0
163        self.draw_time = 0
164
165    def setup(self):
166        """ Set up the game and initialize the variables. """
167
168        # Sprite lists
169        self.player_list = arcade.SpriteList()
170        self.wall_list = arcade.SpriteList()
171
172        # Set up the player
173        self.score = 0
174
175        maze = make_maze_recursion(MAZE_WIDTH, MAZE_HEIGHT)
176
178        # Create sprites based on 2D grid
179        if not MERGE_SPRITES:
180            # This is the simple-to-understand method. Each grid location
181            # is a sprite.
182            for row in range(MAZE_HEIGHT):
183                for column in range(MAZE_WIDTH):
184                    if maze[row][column] == 1:
185                        wall = arcade.BasicSprite(texture, scale=SPRITE_SCALING)
186                        wall.center_x = column * SPRITE_SIZE + SPRITE_SIZE / 2
187                        wall.center_y = row * SPRITE_SIZE + SPRITE_SIZE / 2
188                        self.wall_list.append(wall)
189        else:
190            # This uses new Arcade 1.3.1 features, that allow me to create a
191            # larger sprite with a repeating texture. So if there are multiple
192            # cells in a row with a wall, we merge them into one sprite, with a
193            # repeating texture for each cell. This reduces our sprite count.
194            for row in range(MAZE_HEIGHT):
195                column = 0
196                while column < len(maze):
197                    while column < len(maze) and maze[row][column] == 0:
198                        column += 1
199                    start_column = column
200                    while column < len(maze) and maze[row][column] == 1:
201                        column += 1
202                    end_column = column - 1
203
204                    column_count = end_column - start_column + 1
205                    column_mid = (start_column + end_column) / 2
206
207                    wall = arcade.Sprite(":resources:images/tiles/grassCenter.png", scale=SPRITE_SCALING)
208                    wall.center_x = column_mid * SPRITE_SIZE + SPRITE_SIZE / 2
209                    wall.center_y = row * SPRITE_SIZE + SPRITE_SIZE / 2
210                    wall.width = SPRITE_SIZE * column_count
211                    self.wall_list.append(wall)
212
213        # Set up the player
214        self.player_sprite = arcade.Sprite(
215            ":resources:images/animated_characters/female_person/femalePerson_idle.png",
216            scale=SPRITE_SCALING)
217        self.player_list.append(self.player_sprite)
218
219        # Randomly place the player. If we are in a wall, repeat until we aren't.
220        placed = False
221        while not placed:
222
223            # Randomly position
224            self.player_sprite.center_x = random.randrange(MAZE_WIDTH * SPRITE_SIZE)
225            self.player_sprite.center_y = random.randrange(MAZE_HEIGHT * SPRITE_SIZE)
226
227            # Are we in a wall?
228            walls_hit = arcade.check_for_collision_with_list(self.player_sprite, self.wall_list)
229            if len(walls_hit) == 0:
230                # Not in a wall! Success!
231                placed = True
232
233        self.physics_engine = arcade.PhysicsEngineSimple(self.player_sprite, self.wall_list)
234
235        # Set the background color
236        self.background_color = arcade.color.AMAZON
237
238        # setup camera
239        self.cam = arcade.camera.Camera2D()
240
241    def on_draw(self):
242        """ Render the screen. """
243
244        # This command has to happen before we start drawing
245        self.clear()
246
247        # Start timing how long this takes
248        draw_start_time = timeit.default_timer()
249
250        # Draw all the sprites.
251        self.wall_list.draw(pixelated=True)
252        self.player_list.draw()
253
254        # Draw info on the screen
255        sprite_count = len(self.wall_list)
256
257        output = f"Sprite Count: {sprite_count}"
258        left, bottom = self.cam.bottom_left
260                         left + 20,
261                         SCREEN_HEIGHT - 20 + bottom,
263
264        output = f"Drawing time: {self.draw_time:.3f}"
266                         left + 20,
267                         SCREEN_HEIGHT - 40 + bottom,
269
270        output = f"Processing time: {self.processing_time:.3f}"
272                         left + 20,
273                         SCREEN_HEIGHT - 60 + bottom,
275
276        self.draw_time = timeit.default_timer() - draw_start_time
277
278    def on_key_press(self, key, modifiers):
279        """Called whenever a key is pressed. """
280
281        if key == arcade.key.UP:
282            self.player_sprite.change_y = MOVEMENT_SPEED
283        elif key == arcade.key.DOWN:
284            self.player_sprite.change_y = -MOVEMENT_SPEED
285        elif key == arcade.key.LEFT:
286            self.player_sprite.change_x = -MOVEMENT_SPEED
287        elif key == arcade.key.RIGHT:
288            self.player_sprite.change_x = MOVEMENT_SPEED
289
290    def on_key_release(self, key, modifiers):
291        """Called when the user releases a key. """
292
293        if key == arcade.key.UP or key == arcade.key.DOWN:
294            self.player_sprite.change_y = 0
295        elif key == arcade.key.LEFT or key == arcade.key.RIGHT:
296            self.player_sprite.change_x = 0
297
298    def on_update(self, delta_time):
299        """ Movement and game logic """
300
301        start_time = timeit.default_timer()
302
303        # Call update on all sprites (The sprites don't do much in this
304        # example though.)
305        self.physics_engine.update()
306
307        # --- Manage Scrolling ---
308
309        # Keep track of if we changed the boundary. We don't want to
310        # update the camera if we don't need to.
311        changed = False
312
313        pos = self.cam.position
314
315        top_left = self.cam.top_left
316        bottom_right = self.cam.bottom_right
317
318        # Scroll left
319        left_boundary = top_left[0] + VIEWPORT_MARGIN
320        if self.player_sprite.left < left_boundary:
321            changed = True
322            pos = pos[0] + (self.player_sprite.left - left_boundary), pos[1]
323
324        # Scroll up
325        top_boundary = top_left[1] - VIEWPORT_MARGIN
326        if self.player_sprite.top > top_boundary:
327            changed = True
328            pos = pos[0], pos[1] + (self.player_sprite.top - top_boundary)
329
330        # Scroll right
331        right_boundary = bottom_right[0] - VIEWPORT_MARGIN
332        if self.player_sprite.right > right_boundary:
333            changed = True
334            pos = pos[0] + (self.player_sprite.right - right_boundary), pos[1]
335
336        # Scroll down
337        bottom_boundary = bottom_right[1] + VIEWPORT_MARGIN
338        if self.player_sprite.bottom < bottom_boundary:
339            changed = True
340            pos = pos[0], pos[1] + (self.player_sprite.bottom - bottom_boundary)
341
342        # If we changed the boundary values, update the view port to match
343        if changed:
344            self.cam.position = pos
345            self.cam.use()
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()