Creating a Depth First Maze

Screen shot of a maze created by depth first
maze_depth_first.py
  1"""
  2Create a maze using a depth-first search maze generation algorithm.
  3For more information on this algorithm see:
  4https://www.algosome.com/articles/maze-generation-depth-first.html
  5...or search up some other examples.
  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_depth_first
 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 = 1000
 21WINDOW_HEIGHT = 700
 22WINDOW_TITLE = "Maze Depth First 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
 35MERGE_SPRITES = True
 36
 37# How many pixels to keep as a minimum margin between the character
 38# and the edge of the screen.
 39VIEWPORT_MARGIN = 200
 40HORIZONTAL_BOUNDARY = WINDOW_WIDTH / 2.0 - VIEWPORT_MARGIN
 41VERTICAL_BOUNDARY = WINDOW_HEIGHT / 2.0 - VIEWPORT_MARGIN
 42# If the player moves further than this boundary away from
 43# he camera we use a constraint to move the camera
 44CAMERA_BOUNDARY = arcade.LRBT(
 45    -HORIZONTAL_BOUNDARY,
 46    HORIZONTAL_BOUNDARY,
 47    -VERTICAL_BOUNDARY,
 48    VERTICAL_BOUNDARY,
 49)
 50
 51def _create_grid_with_cells(width, height):
 52    """ Create a grid with empty cells on odd row/column combinations. """
 53    grid = []
 54    for row in range(height):
 55        grid.append([])
 56        for column in range(width):
 57            if column % 2 == 1 and row % 2 == 1:
 58                grid[row].append(TILE_EMPTY)
 59            elif column == 0 or row == 0 or column == width - 1 or row == height - 1:
 60                grid[row].append(TILE_CRATE)
 61            else:
 62                grid[row].append(TILE_CRATE)
 63    return grid
 64
 65
 66def make_maze_depth_first(maze_width, maze_height):
 67    maze = _create_grid_with_cells(maze_width, maze_height)
 68
 69    w = (len(maze[0]) - 1) // 2
 70    h = (len(maze) - 1) // 2
 71    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
 72
 73    def walk(x: int, y: int):
 74        vis[y][x] = 1
 75
 76        d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
 77        random.shuffle(d)
 78        for (xx, yy) in d:
 79            if vis[yy][xx]:
 80                continue
 81            if xx == x:
 82                maze[max(y, yy) * 2][x * 2 + 1] = TILE_EMPTY
 83            if yy == y:
 84                maze[y * 2 + 1][max(x, xx) * 2] = TILE_EMPTY
 85
 86            walk(xx, yy)
 87
 88    walk(random.randrange(w), random.randrange(h))
 89
 90    return maze
 91
 92
 93class GameView(arcade.View):
 94    """ Main application class. """
 95
 96    def __init__(self):
 97        """
 98        Initializer
 99        """
100        super().__init__()
101
102        # Sprite lists
103        self.player_list = None
104        self.wall_list = None
105
106        # Player info
107        self.score = 0
108        self.player_sprite = None
109
110        # Physics engine
111        self.physics_engine = None
112
113        # Camera for scrolling
114        self.camera = None
115
116        # Time to process
117        self.processing_time = 0
118        self.draw_time = 0
119
120    def setup(self):
121        """ Set up the game and initialize the variables. """
122
123        # Sprite lists
124        self.player_list = arcade.SpriteList()
125        self.wall_list = arcade.SpriteList()
126
127        self.score = 0
128
129        # Create the maze
130        maze = make_maze_depth_first(MAZE_WIDTH, MAZE_HEIGHT)
131
132        # Create sprites based on 2D grid
133        if not MERGE_SPRITES:
134            # This is the simple-to-understand method. Each grid location
135            # is a sprite.
136            for row in range(MAZE_HEIGHT):
137                for column in range(MAZE_WIDTH):
138                    if maze[row][column] == 1:
139                        wall = arcade.Sprite(
140                            ":resources:images/tiles/grassCenter.png",
141                            scale=SPRITE_SCALING,
142                        )
143                        wall.center_x = column * SPRITE_SIZE + SPRITE_SIZE / 2
144                        wall.center_y = row * SPRITE_SIZE + SPRITE_SIZE / 2
145                        self.wall_list.append(wall)
146        else:
147            # This uses new Arcade 1.3.1 features, that allow me to create a
148            # larger sprite with a repeating texture. So if there are multiple
149            # cells in a row with a wall, we merge them into one sprite, with a
150            # repeating texture for each cell. This reduces our sprite count.
151            for row in range(MAZE_HEIGHT):
152                column = 0
153                while column < len(maze):
154                    while column < len(maze) and maze[row][column] == 0:
155                        column += 1
156                    start_column = column
157                    while column < len(maze) and maze[row][column] == 1:
158                        column += 1
159                    end_column = column - 1
160
161                    column_count = end_column - start_column + 1
162                    column_mid = (start_column + end_column) / 2
163
164                    wall = arcade.Sprite(
165                        ":resources:images/tiles/grassCenter.png",
166                        scale=SPRITE_SCALING,
167                    )
168                    wall.center_x = column_mid * SPRITE_SIZE + SPRITE_SIZE / 2
169                    wall.center_y = row * SPRITE_SIZE + SPRITE_SIZE / 2
170                    wall.width = SPRITE_SIZE * column_count
171                    self.wall_list.append(wall)
172
173        # Set up the player
174        self.player_sprite = arcade.Sprite(
175            ":resources:images/animated_characters/female_person/femalePerson_idle.png",
176            scale=SPRITE_SCALING)
177        self.player_list.append(self.player_sprite)
178
179        # Randomly place the player. If we are in a wall, repeat until we aren't.
180        placed = False
181        while not placed:
182
183            # Randomly position
184            self.player_sprite.center_x = random.randrange(MAZE_WIDTH * SPRITE_SIZE)
185            self.player_sprite.center_y = random.randrange(MAZE_HEIGHT * SPRITE_SIZE)
186
187            # Are we in a wall?
188            walls_hit = arcade.check_for_collision_with_list(self.player_sprite, self.wall_list)
189            if len(walls_hit) == 0:
190                # Not in a wall! Success!
191                placed = True
192
193        self.physics_engine = arcade.PhysicsEngineSimple(self.player_sprite, self.wall_list)
194
195        # Set the background color
196        self.background_color = arcade.color.AMAZON
197
198        # Setup Camera
199        self.camera = arcade.camera.Camera2D()
200
201    def on_draw(self):
202        """
203        Render the screen.
204        """
205
206        # This command has to happen before we start drawing
207        self.clear()
208
209        # Start timing how long this takes
210        draw_start_time = timeit.default_timer()
211
212        # Draw all the sprites.
213        self.wall_list.draw()
214        self.player_list.draw()
215
216        # Draw info on the screen
217        sprite_count = len(self.wall_list)
218
219        output = f"Sprite Count: {sprite_count}"
220        left, bottom = self.camera.bottom_left
221        arcade.draw_text(output,
222                         left + 20,
223                         WINDOW_HEIGHT - 20 + bottom,
224                         arcade.color.WHITE, 16)
225
226        output = f"Drawing time: {self.draw_time:.3f}"
227        arcade.draw_text(output,
228                         left + 20,
229                         WINDOW_HEIGHT - 40 + bottom,
230                         arcade.color.WHITE, 16)
231
232        output = f"Processing time: {self.processing_time:.3f}"
233        arcade.draw_text(output,
234                         left + 20,
235                         WINDOW_HEIGHT - 60 + bottom,
236                         arcade.color.WHITE, 16)
237
238        self.draw_time = timeit.default_timer() - draw_start_time
239
240    def on_key_press(self, key, modifiers):
241        """Called whenever a key is pressed. """
242
243        if key == arcade.key.UP:
244            self.player_sprite.change_y = MOVEMENT_SPEED
245        elif key == arcade.key.DOWN:
246            self.player_sprite.change_y = -MOVEMENT_SPEED
247        elif key == arcade.key.LEFT:
248            self.player_sprite.change_x = -MOVEMENT_SPEED
249        elif key == arcade.key.RIGHT:
250            self.player_sprite.change_x = MOVEMENT_SPEED
251
252    def on_key_release(self, key, modifiers):
253        """Called when the user releases a key. """
254
255        if key == arcade.key.UP or key == arcade.key.DOWN:
256            self.player_sprite.change_y = 0
257        elif key == arcade.key.LEFT or key == arcade.key.RIGHT:
258            self.player_sprite.change_x = 0
259
260    def on_update(self, delta_time):
261        """ Movement and game logic """
262
263        start_time = timeit.default_timer()
264
265        # Call update on all sprites (The sprites don't do much in this
266        # example though.)
267        self.physics_engine.update()
268
269        # --- Manage Scrolling ---
270        self.camera.position = arcade.camera.grips.constrain_boundary_xy(
271            self.camera.view_data, CAMERA_BOUNDARY, self.player_sprite.position
272        )
273        self.camera.use()
274
275        # Save the time it took to do this.
276        self.processing_time = timeit.default_timer() - start_time
277
278
279def main():
280    """ Main function """
281    # Create a window class. This is what actually shows up on screen
282    window = arcade.Window(WINDOW_WIDTH, WINDOW_HEIGHT, WINDOW_TITLE)
283
284    # Create and setup the GameView
285    game = GameView()
286    game.setup()
287
288    # Show GameView on screen
289    window.show_view(game)
290
291    # Start the arcade game loop
292    arcade.run()
293
294
295
296if __name__ == "__main__":
297    main()