Python, Wavefront, Recursive Backtracking, Randomized Prim, PyGame

Authors: Allen Liu, Anuj Natray, Henry Brown, Ishani Narwankar, Leo Li

Project Description

Implementation of two classical maze-solving algorithms: Wavefront Propagation and Recursive Backtracking with visualization. The system generates random mazes and finds optimal or feasible paths from start to goal.

Algorithm Comparison

graph TB
    subgraph Wavefront["Wavefront Algorithm<br/>(Optimal, BFS-based)"]
        W_START[Start at Goal<br/>Label = 0]
        W_PROP[Propagate Wavefront<br/>Label = n+1]
        W_PATH[Follow Gradient<br/>to Goal]
    end

    subgraph Backtrack["Recursive Backtracking<br/>(Depth-First Search)"]
        B_START[Start at Start Position]
        B_EXPLORE[Try Directions:<br/>E → N → W → S]
        B_BACK[Backtrack if Stuck]
    end

    W_START --> W_PROP
    W_PROP --> W_PATH

    B_START --> B_EXPLORE
    B_EXPLORE --> B_BACK
    B_BACK --> B_EXPLORE

    style W_PATH fill:#d4edda
    style B_EXPLORE fill:#fff4e1

Wavefront Algorithm

flowchart TD
    START([Initialize]) --> MARK_GOAL[Label Goal Cell = 0]
    MARK_GOAL --> ITER[n = 0]

    ITER --> FIND_N[Find All Cells<br/>Labeled n]
    FIND_N --> EXPAND[Label Empty Neighbors<br/>n+1]

    EXPAND --> CHECK{Start<br/>Labeled?}
    CHECK -->|No| INCREMENT[n = n+1]
    INCREMENT --> ITER

    CHECK -->|Yes| BACKTRACK_START[Start at Start Cell]
    BACKTRACK_START --> FOLLOW[Move to Neighbor with<br/>Label = current - 1]
    FOLLOW --> AT_GOAL{At Goal?}

    AT_GOAL -->|No| FOLLOW
    AT_GOAL -->|Yes| END([Path Complete])

    style MARK_GOAL fill:#e1f5ff
    style FOLLOW fill:#fff4e1
    style END fill:#d4edda

Characteristics:

• Completeness: Guaranteed to find a path if one exists
• Optimality: Finds the shortest path
• Method: Breadth-first propagation from goal to start
• Steps:
  1. Label goal cell as 0
  2. Iteratively label empty neighbors with incrementing values
  3. Stop when start cell is labeled
  4. Follow decreasing gradient from start to goal

Recursive Backtracking Algorithm

stateDiagram-v2
    [*] --> Start
    Start --> TryEast: Try directions in order
    TryEast --> TryNorth: Blocked/Visited
    TryNorth --> TryWest: Blocked/Visited
    TryWest --> TrySouth: Blocked/Visited
    TrySouth --> Backtrack: All blocked

    TryEast --> MoveEast: Valid
    TryNorth --> MoveNorth: Valid
    TryWest --> MoveWest: Valid
    TrySouth --> MoveSouth: Valid

    MoveEast --> CheckGoal
    MoveNorth --> CheckGoal
    MoveWest --> CheckGoal
    MoveSouth --> CheckGoal

    CheckGoal --> [*]: At Goal
    CheckGoal --> TryEast: Not at Goal

    Backtrack --> PreviousCell
    PreviousCell --> TryEast: Continue from previous

Characteristics:

• Completeness: Guaranteed to find a path (may not be optimal)
• Priority: East → North → West → South
• Method: Depth-first exploration with backtracking
• Steps:
  1. From current position, try directions in priority order
  2. If direction is valid (not wall, not visited), move there
  3. If all directions blocked, backtrack to previous cell
  4. Repeat until goal is reached

Amination

Challenges

• Solver algorithm: When first implementing the algorithm for two solvers, it was difficult for us to understand the concept for the solver so we spent most of time drawing the process on a paper to visualize it. After we had a clear concept about what it was it was a smooth process for all of us.