Maze Runner 迷宫求解器

Wavefront propagation and recursive backtracking algorithms with visualization 带可视化的波前传播和递归回溯算法

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.

Python, 波前算法, 递归回溯, 随机 Prim, PyGame

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

项目描述

实现两种经典迷宫求解算法：波前传播 和 递归回溯，并带有可视化功能。系统生成随机迷宫，并从起点到终点找到最优或可行路径。

波前算法

特点:

完备性: 如果存在路径，保证能找到
最优性: 找到最短路径
方法: 从终点到起点的广度优先传播
步骤:
1. 将终点单元格标记为 0
2. 迭代地将相邻空单元格标记为递增值
3. 当起点单元格被标记时停止
4. 从起点沿着递减梯度到达终点

递归回溯算法