Maze Game with 🐍

This is a story of me building a simple maze game using Python and Pygame. I want to present my story as a guide for fellow developer if they want to build a simple project to me.

Check it out:

Maze Game

The code for the game is available on Github.

GitHub - Avashist1998/maze_game: Maze Game written in Pygame

Project Components

• Maze Generation
• Maze Visualization
• Maze Game and Keyboard Events
• Maze options screen
• Maze Game Application Design

In this story I will only cover the maze generation logic, since each of the components will require a seperate story of their own. Maze sure to clap the story if you want to see the remaining component stories.

Maze Generation

I used the Randomized Prim’s algorithm for generating the maze, which is a popular choice for maze generation. I followed Orestis Zekai’s article on maze generation using Python, which was helpful for the basic setup. However, I had some difficulty following the final parts of the article, so I implemented my own version. You can find the final version of my implementation in this file on Github.

Maze board State Object

Before we can start implementing the maze generation, we need to define a enum for different maze game objects. The MazeGameObject enum improves the readability of the code and creates a layer of abstraction between the values on the game board and the maze generation code.

from enum import Enum
class MazeGameObject(Enum):
  PATH = 0
  WALL = 1
  GOAL = 2
  EMPTY = -1
  PLAYER_TILE = 7
  VISITED_TILE = 3

Helper Functions

• Initialize the maze with Empty object values (Exactly same as Zekai)

def init_maze(height, width):
    maze = []
    for _ in range(height):
        maze_row = [MazeGameObject.EMPTY.value for _ in range(width)]
        maze.append(maze_row)
    return maze

• Pick a start position by randomly selecting a location in the maze that does not lie on the edge. (Exactly same as Zekai)

from random import random
def get_start_pos(row, col):
    start_row = int(random() * (row-2))+1 
    start_col = int(random() * (col-2))+1
    return start_row, start_col

• Function fills the empty cells with wall value (Exactly same as Zekai)

def fill_walls(maze)
    for i, _ in enumerate(maze):
        for j in range(len(maze[0])):
            if maze[i][j] == MazeGameObject.EMPTY.value:
                maze[i][j] = MazeGameObject.WALL.value

• To determine the number of paths surrounding a given cell in the maze, we examine the adjacent cells using `if` statements. If the cells are within the grid’s boundaries and have the same value as the path, the `s_cell_count` is incremented.

def get_surrounding_cell_count(cell, maze):
    s_cell_count = 0
    if (cell[0] > 0 and 
        maze[cell[0] - 1][cell[1]] ==  MazeGameObject.PATH.value):
        s_cell_count += 1
    if (cell[0] < len(maze) - 1 and 
        maze[cell[0] + 1][cell[1]] ==  MazeGameObject.PATH.value):
        s_cell_count += 1
    if (cell[1] > 0 and 
        maze[cell[0]][cell[1] - 1] ==  MazeGameObject.PATH.value):
        s_cell_count += 1
    if (cell[1] < len(maze[0]) - 1 and 
        maze[cell[0]][cell[1] + 1] ==  MazeGameObject.PATH.value):
        s_cell_count += 1
    return s_cell_count

• To create entry and exit points for the maze after it’s generated, we break the top and bottom walls of the maze into paths that are adjacent to existing paths. This creates a long and winding path that leads from the entrance to the exit of the maze. This step is important because it ensures that there is a clear path from the entrance to the exit, and that the maze is solvable.

def create_entry_exit(maze):
    row, col = len(maze), len(maze[0])
    start_point, exit_point = (0, 0), (row - 1, col - 1)
    # Set entrance and exit
    for i in range(col):
        if maze[1][i] == MazeGameObject.PATH.value:
            maze[0][i] = MazeGameObject.PLAYER_TILE.value
            start_point = (0, i)
            break

    for i in range(col - 1, 0, -1):
        if maze[row - 2][i] == MazeGameObject.PATH.value:
            maze[row - 1][i] = MazeGameObject.GOAL.value
            exit_point = (row - 1, i)
            break
    return start_point, exit_point, maze

Generation the maze

• The first step in generating the maze is to initialize the board using the `init_maze` function.
• We need to determine the starting position of the maze, which we achieve using the get_start_pos function. This function ensures that the starting position is always a path cell and returns its coordinates. We then set the start_pos variable to these coordinates.
• We assign the surrounding cells to the `start_pos` to the value of a `WALL`. Then we add the defined walls the our queue, in my case a set named `wall_list`

from random import choices
def generate_maze(n_row, n_col):
  wall_list = set()
  maze = init_maze(n_row, n_col)
  start_pos = get_start_pos(maze)
  maze[start_pos[0]][start_pos[1]] = MazeGameObject.PATH.value

  for val in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
      wall_list.add((start_pos[0] + val[0], start_pos[1] + val[1]))
      maze[start_pos[0] + val[0]][start_pos[1] + val[1]] = MazeGameObject.WALL.value

  while wall_list:
      rand_wall = choices(list(wall_list), k=1)[0]
      s_cell_count = get_surrounding_cell_count(rand_wall, maze)

After the initialization steps, the maze generation algorithm repeats the following steps until all the walls in the maze have been processed:

• Pick a random wall from the `wall_list`.
• Count the number of surrounding cells of the wall that are paths using the `get_surrounding_cell_count` function.
• If the count is greater than 1, remove the wall from the `wall_list` since it has been processed.
• If the count is 1, we process the wall and remove the wall from the `wall_list`.
• We continue this process until the `wall_list` is empty.
• After all the cells are processed, we fill the remaining cells with walls using the fill_walls function.
• Finally, we create an entry and exit in the maze using the `create_entry_exit` function.

  while wall_list:
      rand_wall = choices(list(wall_list), k=1)[0]
      s_cell_count = get_surrounding_cell_count(rand_wall, maze)
      if s_cell_count < 2:
          ### Wall Processing block
      wall_list.remove(rand_wall)
  fill_walls(maze)
  entry_point, exit_point, maze = create_entry_exit(maze)
  return entry_point, exit_point, maze

The “Row case” and “Col case” refer to the two possibilities for which direction the wall being processed is oriented: either horizontally (a “row”) or vertically (a “column”).

• For each of these cases, there are two sub-cases, based on whether the wall is at the edge of the grid or not.
• If the wall being processed is not at the edge of the grid, the code checks the cells on either side of the wall to see if one of them is a path and the other empty (i.e. possible connected). If so, the wall is removed from the wall list, meaning it is no longer available to be broken down.
• If the wall being processed is at the edge of the grid, the code only checks the cells on the side that is not at the edge. This is because the cells on the other side are already known to be walls, since they lie outside the bounds of the grid.

Row Cases:
    Case 1:         Case 2:
        Path               Empty
        |                  |
        Wall               Wall
        |                  |
        Empty              Path   

Col Cases:
    Case 1: Path - Wall - Empty

    Case 2: Empty - Wall - Path

    if (rand_wall[0] > 0 and rand_wall[0] + 1 < n_row):
        # row case
        if (maze[rand_wall[0] - 1][rand_wall[1]] == MazeGameObject.WALL.value 
            and maze[rand_wall[0] + 1][rand_wall[1]] == MazeGameObject.PATH.value):
            # Case 2
            maze[rand_wall[0]][rand_wall[1]] = MazeGameObject.PATH.value

            maze[rand_wall[0] - 1][rand_wall[1]] = MazeGameObject.WALL.value
            maze[rand_wall[0]][rand_wall[1] - 1] = MazeGameObject.WALL.value
            maze[rand_wall[0]][rand_wall[1] + 1] = MazeGameObject.WALL.value

            wall_list.add((rand_wall[0] - 1, rand_wall[1]))
            wall_list.add((rand_wall[0], rand_wall[1] + 1))
            wall_list.add((rand_wall[0], rand_wall[1] - 1))
        if (maze[rand_wall[0] + 1][rand_wall[1]] == MazeGameObject.WALL.value 
            and maze[rand_wall[0] + 1][rand_wall[1]] == MazeGameObject.PATH.value):
            # Case 1
                # Similar logic as case 2 block
    if (rand_wall[1] > 0 and rand_wall[1] + 1 < n_col):
        ### similar logic as above row cases

Final Function

def generate_prim_maze(n_row, n_col):
  wall_list = set()
  maze = init_maze(n_row, n_col)
  start_pos = get_start_pos(maze)
  maze[start_pos[0]][start_pos[1]] = MazeGameObject.PATH.value

  for val in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
      wall_list.add((start_pos[0] + val[0], start_pos[1] + val[1]))
      maze[start_pos[0] + val[0]][start_pos[1] + val[1]] = MazeGameObject.WALL.value

  while wall_list:
      rand_wall = choices(list(wall_list), k=1)[0]
      s_cell_count = get_surrounding_cell_count(rand_wall, maze)

      if s_cell_count < 2:
          if (rand_wall[0] > 0 and rand_wall[0] + 1 < n_row):

              if (maze[rand_wall[0] - 1][rand_wall[1]] == MazeGameObject.EMPTY.value
                      and maze[rand_wall[0] + 1][rand_wall[1]] == MazeGameObject.PATH.value):
                  maze[rand_wall[0]][rand_wall[1]] = MazeGameObject.PATH.value

                  maze[rand_wall[0] - 1][rand_wall[1]] = MazeGameObject.WALL.value
                  maze[rand_wall[0]][rand_wall[1] - 1] = MazeGameObject.WALL.value
                  maze[rand_wall[0]][rand_wall[1] + 1] = MazeGameObject.WALL.value

                  wall_list.add((rand_wall[0] - 1, rand_wall[1]))
                  wall_list.add((rand_wall[0], rand_wall[1] + 1))
                  wall_list.add((rand_wall[0], rand_wall[1] - 1))

              if (maze[rand_wall[0] + 1][rand_wall[1]] == MazeGameObject.EMPTY.value
                      and maze[rand_wall[0] - 1][rand_wall[1]] == MazeGameObject.PATH.value):
                  maze[rand_wall[0]][rand_wall[1]] = MazeGameObject.PATH.value

                  maze[rand_wall[0] + 1][rand_wall[1]] = MazeGameObject.WALL.value
                  maze[rand_wall[0]][rand_wall[1] - 1] = MazeGameObject.WALL.value
                  maze[rand_wall[0]][rand_wall[1] + 1] = MazeGameObject.WALL.value

                  wall_list.add((rand_wall[0] + 1, rand_wall[1]))
                  wall_list.add((rand_wall[0], rand_wall[1] + 1))
                  wall_list.add((rand_wall[0], rand_wall[1] - 1))

          if (rand_wall[1] > 0 and rand_wall[1] + 1 < n_col):
              if (maze[rand_wall[0]][rand_wall[1] - 1] == MazeGameObject.EMPTY.value
                      and maze[rand_wall[0]][rand_wall[1] + 1] == MazeGameObject.PATH.value):
                  maze[rand_wall[0]][rand_wall[1]] = MazeGameObject.PATH.value

                  maze[rand_wall[0]][rand_wall[1] - 1] = MazeGameObject.WALL.value
                  maze[rand_wall[0] - 1][rand_wall[1]] = MazeGameObject.WALL.value
                  maze[rand_wall[0] + 1][rand_wall[1]] = MazeGameObject.WALL.value

                  wall_list.add((rand_wall[0], rand_wall[1] - 1))
                  wall_list.add((rand_wall[0] + 1, rand_wall[1]))
                  wall_list.add((rand_wall[0] - 1, rand_wall[1]))

              if (maze[rand_wall[0]][rand_wall[1] + 1] == MazeGameObject.EMPTY.value
                      and maze[rand_wall[0]][rand_wall[1] - 1] == MazeGameObject.PATH.value):
                  maze[rand_wall[0]][rand_wall[1]] = MazeGameObject.PATH.value

                  maze[rand_wall[0]][rand_wall[1] + 1] = MazeGameObject.WALL.value
                  maze[rand_wall[0] - 1][rand_wall[1]] = MazeGameObject.WALL.value
                  maze[rand_wall[0] + 1][rand_wall[1]] = MazeGameObject.WALL.value

                  wall_list.add((rand_wall[0], rand_wall[1] + 1))
                  wall_list.add((rand_wall[0] - 1, rand_wall[1]))
                  wall_list.add((rand_wall[0] + 1, rand_wall[1]))
      wall_list.remove(rand_wall)
  fill_walls(maze)
  entry_point, exit_point, maze = create_entry_exit(maze)
  return entry_point, exit_point, maze