A* 尋路算法 C++ 實現詳解：從原理到工程化代碼

項目背景

課程要求開發 C/S 架構小遊戲，涉及地圖自動尋路。經調研選擇 A* 算法，參考經典教程 A* Pathfinding for Beginners 及中文譯文，結合項目需求完成 C++ 實現。

算法核心思想

• Open List：待評估節點，按 F = G + H 排序；
• Close List：已評估節點；
• G：起點到當前節點實際代價；
• H：當前節點到終點估算代價（曼哈頓距離）；
• 每輪取 Open List 中 F 最小節點擴展，直到終點進入 Open List 或 Open List 為空。

數據結構設計

struct Node {
    int x, y;           // 格子坐標
    int g, h;           // 代價值
    Node *parent;       // 父節點指針，構成路徑鏈
};

class AStar {
    int *map;           // 一維化地圖數組，0 可行，1 障礙
    Node *nodes;        // 所有節點池
    list openList, closeList; // 存節點索引
    list result;  // 最終路徑
    // ... 輔助方法：get_g_value, get_h_value, isReachable, testRoad
public:
    AStar(int *mapInfo, int w, int h, int start, int end);
    bool Find();        // 遞歸搜索入口
    void getResultPath(); // 回溯構建 result
};

關鍵邏輯解析

啟發函數

int get_h_value(int pos) {
    // 曼哈頓距離 × 10，避免浮點
    return 10 * (abs(end/Width - pos/Width) + abs(end%Width - pos%Width));
}

鄰居擴展與去重

bool testRoad(int pos, int cur) {
    if (!isReachable(pos)) return false;
    if (pos == end) { nodes[pos].parent = &nodes[cur]; return true; }
    if (map[pos] == 1) return false; // 障礙
    if (find(closeList.begin(), closeList.end(), pos) != closeList.end()) return false;

    auto it = find(openList.begin(), openList.end(), pos);
    if (it == openList.end()) {
        openList.push_back(pos);
        nodes[pos].parent = &nodes[cur];
        nodes[pos].h = get_h_value(pos);
        nodes[pos].g = nodes[cur].g + 10;
    } else if (nodes[cur].g + 10 < nodes[pos].g) {
        nodes[pos].parent = &nodes[cur];
        nodes[pos].g = nodes[cur].g + 10;
    }
    return false;
}

主循環（遞歸寫法）

bool Find() {
    if (openList.empty()) return false;
    // 線性掃描找 F 最小（可優化為優先隊列/二叉堆）
    int minF = -1, cur; list::iterator best;
    for (auto it = openList.begin(); it != openList.end(); ++it) {
        int f = nodes[*it].g + nodes[*it].h;
        if (minF == -1 || f <= minF) { minF = f; best = it; }
    }
    cur = *best; closeList.push_back(cur); openList.erase(best);

    // 四向擴展
    if (testRoad(cur - Width, cur)) return true; // 上
    if (testRoad(cur + Width, cur)) return true; // 下
    if (testRoad(cur - 1, cur)) return true;     // 左
    if (testRoad(cur + 1, cur)) return true;     // 右
    return Find(); // 遞歸下一輪
}

優化方向與彩蛋

原教程指出用 二叉堆 維護 Open List 可提速 2-4 倍，作者計劃後續補充 BFS/DFS/A*/二叉堆 A* 性能對比。文末提到 B* 算法 可能是另一優化方向，留待後續研究。