迷宫寻路算法：DFS、BFS 与 A* 的实现与可视化

迷宫生成：递归回溯法

完美迷宫的定义是：任意两点之间有且仅有一条路径。递归回溯法（Recursive Backtracking）是生成这种迷宫的经典算法：

1. 从起点开始，标记当前单元格为已访问
2. 随机选择一个未访问的邻接单元格
3. 打通当前单元格与选中单元格之间的墙
4. 递归对新单元格重复上述过程
5. 若无未访问邻接单元格，回溯到上一个单元格

void MazeGenerator::generate(int x, int y) {
    visited[x][y] = true;
    auto neighbors = getUnvisitedNeighbors(x, y);
    shuffle(neighbors);
    
    for (auto [nx, ny] : neighbors) {
        if (!visited[nx][ny]) {
            removeWall(x, y, nx, ny);
            generate(nx, ny);  // 递归
        }
    }
}

这个算法天然使用了栈（递归调用栈），与 DFS 寻路形成了有趣的对应关系。

DFS 寻路：栈的应用

DFS（深度优先搜索）在迷宫中的实现使用显式栈或递归：

bool dfs(int x, int y) {
    if (x == endX && y == endY) return true;
    visited[x][y] = true;
    
    for (auto [dx, dy] : directions) {
        int nx = x + dx, ny = y + dy;
        if (canMove(nx, ny) && !visited[nx][ny]) {
            if (dfs(nx, ny)) {
                path.push_back({nx, ny});  // 记录路径
                return true;
            }
        }
    }
    return false;
}

DFS 的特点是一条路走到底，遇到死胡同才回溯。这使得它在迷宫中往往会走出一条曲折冗长的路径，而不是最短路径。

BFS 寻路：队列的应用

BFS（广度优先搜索）使用队列实现：

bool bfs() {
    queue<pair<int, int>> q;
    q.push({startX, startY});
    visited[startX][startY] = true;
    
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == endX && y == endY) return true;
        
        for (auto [dx, dy] : directions) {
            int nx = x + dx, ny = y + dy;
            if (canMove(nx, ny) && !visited[nx][ny]) {
                visited[nx][ny] = true;
                parent[nx][ny] = {x, y};  // 记录前驱节点
                q.push({nx, ny});
            }
        }
    }
    return false;
}

BFS 的层序遍历特性保证了找到的一定是最短路径（以步数计算）。代价是需要更多的内存来存储队列中的节点。

A* 算法：启发式搜索

A* 是 DFS 和 BFS 的折中，使用优先队列（最小堆）来选择下一步：

bool astar() {
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({startX, startY, 0, heuristic(startX, startY)});
    
    while (!pq.empty()) {
        auto [x, y, g, f] = pq.top(); pq.pop();
        if (x == endX && y == endY) return true;
        
        for (auto [dx, dy] : directions) {
            int nx = x + dx, ny = y + dy;
            if (canMove(nx, ny) && g + 1 < cost[nx][ny]) {
                cost[nx][ny] = g + 1;
                int h = heuristic(nx, ny);  // 启发函数
                pq.push({nx, ny, g + 1, g + 1 + h});
            }
        }
    }
    return false;
}

启发函数的选择至关重要。在迷宫问题中，曼哈顿距离是常用选择：

h(n) = |x - endX| + |y - endY|

可视化中的动画同步

Qt 可视化最大的挑战是算法执行与 UI 更新的同步。直接方案是使用 QTimer 分步执行：

void MazeWidget::stepAlgorithm() {
    if (!algorithmSteps.empty()) {
        auto step = algorithmSteps.front();
        algorithmSteps.pop();
        applyStep(step);  // 更新网格状态
        update();         // 触发重绘
    }
}

每个算法步骤被记录为”访问节点”、“回溯”、“找到路径”等事件，定时器按固定间隔回放这些事件，形成流畅的动画效果。

算法决策流程对比

flowchart LR
  subgraph DFS["DFS — 深度优先"]
      D1[起点] --> D2[选择一条路径]
      D2 --> D3[走到底]
      D3 --> D4{死胡同?}
      D4 -->|是| D5[回溯]
      D5 --> D2
      D4 -->|否| D6[终点]
  end

  subgraph BFS["BFS — 广度优先"]
      B1[起点] --> B2[入队]
      B2 --> B3[逐层扩展]
      B3 --> B4{找到终点?}
      B4 -->|否| B3
      B4 -->|是| B5[最短路径]
  end

  subgraph ASTAR["A* — 启发式搜索"]
      A1[起点] --> A2[计算 f=g+h]
      A2 --> A3[选择最小f节点]
      A3 --> A4{终点?}
      A4 -->|否| A2
      A4 -->|是| A5[最优路径]
  end

  style DFS fill:#667eea20,stroke:#667eea
  style BFS fill:#f093fb20,stroke:#f093fb
  style ASTAR fill:#4facfe20,stroke:#4facfe

三种算法对比