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