Maze Generator and Solver

This Python program demonstrates various maze generation and solving algorithms using the Pygame library. The implementation includes binary tree maze generation, Prim's algorithm, left wall follower maze solver, Dijkstra's algorithm, and depth-first search (DFS) maze solver.

Maze Generation Algorithms:

1. Binary Tree Maze Generation:

• Initialization: The algorithm starts with a grid of cells, each representing a part of the maze. A stack is used to keep track of the current cell being processed.

• Choose Random Starting Cell: The algorithm starts with a random cell in the grid.

• Carve Passages: For each cell in the grid, the algorithm chooses a random direction (North, East, South, or West). If moving in that direction is valid (within the grid boundaries and not visited), a passage is carved between the current cell and the neighboring cell in that direction. This creates passages in the maze.

• Backtracking: After carving a passage, the neighboring cell becomes the current cell, and the process repeats. If a cell has no valid neighbors, the algorithm backtracks to the previous cell in the stack.

• carving of passage and backtracking is repeated until all cells are visited, resulting in a fully connected maze.

Data Structures:

• Grid: A 2D array of cells, where each cell has information about its carved paths (N, E, S, W) and whether it has been visited.

class Cell:
    def __init__(self):
        self.N = 0
        self.W = 0
        self.E = 0
        self.S = 0
        self.visited = False

grid = [[Cell() for i in range(width)] for i in range(height)]

• Stack: An array based stack to process cells in a particular order.

2. Prim's Algorithm for Maze Generation:

• Initialization: Start with a grid of cells, each representing a part of the maze. Create a set to keep track of visited cells and a list for processing cells.

• Choose Random Starting Cell: Select a random cell as the starting point.

• Add Neighboring Walls to Cell: Add the neighboring walls of the current cell to the cell list.

• Select Random Cell: Choose a random wall from the list.

• Carve Path: Carve a passage through the wall to the neighboring cell. Add the neighboring walls of the new cell to the list if they are not visited.

• Repeat steps 4-5 until the list is empty. The maze is fully connected, and passages are carved in a way that avoids loops.

Data Structures:

• Grid: A 2D array of cells, similar to the one used in the Binary Tree algorithm.

  class Cell:
      def __init__(self):
          self.N = 0
          self.W = 0
          self.E = 0
          self.S = 0
          self.visited = False
  
  grid = [[Cell() for i in range(width)] for i in range(height)]

• Cells: A list to store walls that are candidates for carving.

• Visited Set: A set to keep track of visited cells during the maze generation process.

Maze Solving Algorithms:

3. Left Wall Follower Maze Solver:

• Initialization: The algorithm is used to solve a maze generated using the Binary Tree or Prim's algorithm. It employs the "left wall following" strategy to navigate through the maze.

• Choose Starting Point: The solver starts at the entrance of the maze, usually the top-left corner.

• Left Wall Following: The solver follows the left wall of the maze, always keeping the left side of the wall to its left. It makes decisions based on the presence of walls to its left, front, and right.

• Decision Making:

  • If there is an open path to the left, the solver turns left.
  • If there is no open path to the left, but an open path in front, the solver moves forward.
  • If there is no open path to the left or front, the solver turns right.
  • If there is no open path to the left, front, or right, the solver turns around.

• Reach the Exit: The solver continues following the left wall until it reaches the exit of the maze.

• Draw Path: The algorithm visualizes the path taken by drawing it on the maze.

Data Structures:

• Directions: A dictionary to keep track of the current orientation (forward, left, back, right).

    directions = {'forward': 'N', 'left': 'W', 'back': 'S', 'right': 'E'}

4. Dijkstra's Algorithm Maze Solver:

• Initialization: This algorithm is used to find the shortest path in a maze generated by Binary Tree or Prim's algorithm. It employs Dijkstra's algorithm for pathfinding.

• Create a Grid: A grid is created to represent the maze, with each cell having information about carved paths (N, E, S, W).

• Borders: If the maze has borders, they are taken into account during the pathfinding process.

• Dijkstra's Algorithm: Starting from the entrance, the algorithm explores the maze by visiting neighboring cells and updating the minimum distance to each cell.

• Backtracking: Once the exit is reached, the algorithm backtracks from the exit to the entrance to find the shortest path.

• Draw Path: The shortest path is visualized by drawing it on the maze.

Data Structures:

• Priority Queue (Unvisited): A priority queue implemented using a dictionary to store distances.

    unvisited = {}

• Path Reconstruction: A dictionary to reconstruct the path from the exit to the entrance.

    reverse_path = {}

  A list to store the final path from the exit to the entrance by traversing the parent child relationship in the reverse_path dictionary.

    reverse_list = []

• Visited Set: A set to keep track of visited cells.

    visited = []

5. Depth-First Search (DFS) Maze Solver:

• Initialization: The algorithm is used to solve a maze generated by Binary Tree or Prim's algorithm. It employs the Depth-First Search strategy to navigate through the maze.

• Stack: The algorithm uses a stack to keep track of the current cell and backtracks when necessary.

• Get Unvisited Neighbors: At each step, the algorithm identifies unvisited neighboring cells.

• Backtracking: If there are no unvisited neighbors, the algorithm backtracks to the previous cell.

• Reach the Exit: The solver continues navigating through the maze until it reaches the exit.

• Draw Path: The algorithm visualizes the path taken by drawing it on the maze.

Data Structures:

• Visited Set: A set to keep track of visited cells.
• Stack: An array based stack to process cells in a particular order.

6. Dead End Filler Maze Solver:

Overview

This Python code for, dead_end_filler, is designed to solve mazes represented by a grid of cells. The maze-solving algorithm focuses on filling dead-end cells to optimize the path from the start point (0, 0) to the end point (width - 1, height - 1). It traverses the grid again again until no more dead ends are left in the grid.

Components

step(x, y)

• Function to determine the next step in the maze-solving process based on the current position (x, y) and the surrounding cells' connectivity.

Maze Solving Loop

• The script iterates through the maze cells, identifying and filling dead-end cells until no more dead-end cells remain. Note that more dead ends will be produced after each iteration of the algorithm, which will be consequently filled again.

Maze Traversal

• After dead-end filling, the script visually traces the optimal path from the start

---

Requirements:

• Python 3
• Pygame library ()

How to Run:

1. Install the required dependencies.
2. Run the script using a Python interpreter.

python maze_generator.py

3. Follow the on-screen instructions to generate a maze using Prim's algorithm.

Maze Generation and Solving Controls

Maze Generation Algorithms:

• Binary Tree: binary_tree()
• Prim's Algorithm: prims_algorithm()

Maze Solving Algorithms:

• Left Wall Follower: left_wall_follower()
• Dijkstra's Algorithm: dikshtra()
• Depth-First Search (DFS): dfs()

Grid Size Controls:

• 5x5 Grid: initialize_grid(5, 5)
• 10x10 Grid: initialize_grid(10, 10)
• 20x20 Grid: initialize_grid(20, 20)

Reset Grid:

• Reset: initialize_grid(width, height)