概 述

在游戲開發(fā)中，經(jīng)常會使用A*算法來實現(xiàn)尋路。本文主要介紹使用C++來簡單實現(xiàn)A*算法，便于理解。

算法原理

網(wǎng)上有關A*算法原理的講解很多，這里就不闡述了。貼一個個人認為講解比較好的鏈接：初學者的 A* 尋路。鏈接文章用圖文的方式，講解了算法原理、流程以及尋路算法相關的注意點和優(yōu)化。

算法實現(xiàn)

根據(jù)算法原理，詳細的實現(xiàn)步驟如下：

1. 將起點添加到open表中；
2. 從open表中取成本最低的結點，即F(G + H)值的最小結點；
3. 判斷此結點是否是終點，若是則結束尋路；
4. 將此結點從open表中移除，添加到close表；
5. 依次判斷當前結點各個方位的結點(下面稱為搜索結點)：
   5.1 若搜索結點超出世界范圍或不可達到，則跳過；
   5.2 判斷搜索結點是否已存在于open表中，若不存在，添加到open表中；反之，若G值更小，更新結點；
6. 循環(huán)處理open表中的結點，直到open表為空，則不存在路徑。
7. 根據(jù)終點反推起點，生成最終路徑

實現(xiàn)代碼如下：

// AStar.h
#include <vector>

struct Vec2
{
    int x;
    int y;
    bool operator == (const Vec2 &rhs)
    {
        return (x == rhs.x && y == rhs.y);
    };

};

struct Node
{
    Vec2 coordinate_; //坐標
    int G; //起點到該位置的成本
    int H; //該位置到終點的成本，啟發(fā)式
    Node *parent_; //父結點

    Node(Vec2 coordinate, Node *parent = nullptr)
    {
        coordinate_ = coordinate;
        G = 0;
        H = 0;
        parent_ = parent;
    };

    int GetCost() { return G + H; } //獲取總成本
};

using CoordinateList = std::vector<Vec2>;
using NodeArr = std::vector<Node *>;

class AStar
{
public:
    AStar();

    void SetWorldSize(Vec2 size); //設置地圖大小
    void SetWalls(CoordinateList walls); //設置墻體
    CoordinateList FindPath(Vec2 source, Vec2 target); //A*尋路

private:
    bool IfCollision(Vec2 coordinate); //判斷是否碰撞
    Node* FindNodeInArr(NodeArr &arr, Vec2 coordinate);
    int Manhattan(Vec2 source, Vec2 target); //曼哈頓距離
    void ReleaseNodes(NodeArr& arr);

private:
    Vec2 worldSize_; //地圖大小
    int direction_; //搜索方位(4或8)
    CoordinateList directions_; //方向
    CoordinateList walls_; //墻
};

// AStar.cpp
#include "AStar.h"

Vec2 operator + (const Vec2 &lhs, const Vec2 &rhs)
{
    return { lhs.x + rhs.x, lhs.y + rhs.y };
}

AStar::AStar()
{
    worldSize_ = { 0, 0 };
    direction_ = 8;
    directions_ = {
        { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 },
        { -1, -1 }, { 1, 1 }, { -1, 1 }, { 1, -1 }
    };
    walls_ = {};
}

void AStar::SetWorldSize(Vec2 size)
{
    worldSize_ = size;
}

void AStar::SetWalls(CoordinateList walls)
{
    walls_ = walls;
}

CoordinateList AStar::FindPath(Vec2 source, Vec2 target)
{
    NodeArr openSet; //open表
    NodeArr closedSet; //close表
    Node* nodePtr = nullptr;

    // 添加起點
    openSet.emplace_back(new Node(source));

    while (!openSet.empty()) {
        // 獲取open表中總成本最小的結點
        auto node = openSet.begin();
        nodePtr = *node;
        for (auto item = openSet.begin(); item != openSet.end(); ++item) {
            if ((*item)->GetCost() < (*node)->GetCost()) {
                node = item;
                nodePtr = *item;
            }
        }

        // 判斷是否到達目標
        if (nodePtr->coordinate_ == target) {
            break;
        }

        // 添加到close表中，從open表中移除
        closedSet.emplace_back(nodePtr);
        openSet.erase(node);

        // 依次判斷當前結點的各個方位
        for (int i = 0; i < direction_; ++i) {
            Vec2 findCoordinate(nodePtr->coordinate_ + directions_[i]);

            // 判讀是否超出世界范圍 是否不可達到(結點位置是墻體)
            if (IfCollision(findCoordinate) || FindNodeInArr(closedSet, findCoordinate)) {
                continue;
            }

            // 判斷搜索結點是否已存在于open表中
            int gCost = nodePtr->G + ((i < 4) ? 10 : 14);
            Node* findNode = FindNodeInArr(openSet, findCoordinate);
            if (nullptr == findNode) { //不存在，添加添加新的結點
                findNode = new Node(findCoordinate, nodePtr);
                findNode->G = gCost;
                findNode->H = Manhattan(findNode->coordinate_, target);
                openSet.emplace_back(findNode);
            } else { //存在，判斷是否需要更新
                if (gCost < findNode->G) {
                    findNode->parent_ = nodePtr;
                    findNode->G = gCost;
                }
            }
        }
    }

    // 生成最終路徑
    CoordinateList path;
    while (nodePtr != nullptr) {
        path.emplace_back(nodePtr->coordinate_);
        nodePtr = nodePtr->parent_;
    }

    // 釋放尋路結點
    ReleaseNodes(openSet);
    ReleaseNodes(closedSet);

    return path;
}

bool AStar::IfCollision(Vec2 coordinate)
{
    if (coordinate.x < 0 || coordinate.x >= worldSize_.x ||
        coordinate.y < 0 || coordinate.y >= worldSize_.y ||
        std::find(walls_.begin(), walls_.end(), coordinate) != walls_.end()) {
        return true;
    }
    return false;
}

Node* AStar::FindNodeInArr(NodeArr& arr, Vec2 coordinate)
{
    for (auto node : arr) {
        if (node->coordinate_ == coordinate) {
            return node;
        }
    }
    return nullptr;
}

int AStar::Manhattan(Vec2 source, Vec2 target)
{ 
    return 10 * (abs(source.x - target.x) + abs(source.y - target.y));
}

void AStar::ReleaseNodes(NodeArr& arr)
{
    for (auto i = arr.begin(); i != arr.end();) {
        delete *i;
        i = arr.erase(i);
    }
}

注：代碼中H值的計算，即啟發(fā)式，使用的是曼哈頓距離。當然，啟發(fā)式函數(shù)可以使用很多不同的計算方式，這里不一一展示。

用法示例

#include <iostream>
#include "source/AStar.h"

using namespace std;

int main()
{
    AStar aStar;
    aStar.SetWorldSize({ 7, 7 }); //設置世界大小
    std::vector<Vec2> walls = { { 2, 3 }, { 3, 3 }, { 4, 3 } };
    aStar.SetWalls(walls); //設置墻體
    auto path = aStar.FindPath({ 3, 1 }, { 3, 5 }); //尋路

    for (auto &i : path) {
        std::cout << i.x << " " << i.y << "\n";
    }
}

GitHub地址：A-Star