# Creating a Recursive Maze¶

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