实用高效的寻路算法——A*寻路算法的实现及优化思路

前言：寻路是游戏比较重要的一个组成部分。因为不仅AI还有很多地方(例如RTS游戏里操控人物点到地图某个点，然后人物自动寻路走过去)都需要用到自动寻路的功能。

本文将介绍一个经常被使用且效率理想的寻路方法——A*寻路算法，并且提供额外的优化思路。

图片及信息参考自：https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/

A*算法介绍

寻路，即找到一条从某个起点到某个终点的可通过路径。而因为实际情况中，起点和终点之间的直线方向往往有障碍物，便需要一个搜索的算法来解决。

有一定算法基础的同学可能知道从某个起点到某个终点通常使用深度优先搜索（DFS），DFS搜索的搜索方向一般是8个方向（如果不允许搜索斜向，则有4个），但是并无优先之分。

为了让DFS搜索更加高效，结合贪心思想，我们给搜索方向赋予了优先级，直观上离终点最近的方向（直观上的意思是无视障碍物的情况下）为最优先搜索方向，这就是A*算法。

A*算法步骤解析

（如下图，绿色为起点，红色为终点，蓝色为不可通过的墙。）


从起点开始往四周各个方向搜索。

（这里的搜索方向有8个方向）


为了区分搜索方向的优先级，我们给每个要搜索的点赋予2个值。

G值（耗费值）：指从起点走到该点要耗费的值。

H值（预测值）：指从该点走到终点的预测的值（从该点到终点无视障碍物情况下预测要耗费的值，也可理解成该点到终点的直线距离的值）

在这里，值=要走的距离

（实际上，更复杂的游戏，因为地形不同（例如陷阱，难走的沙地之类的），还会有相应不同的权值：值=要走的距离*地形权值）

我们还定义直着走一格的距离等于10，斜着走一格的距离等于14（因为45°斜方向的长度=sqrt(10^2+10^2)≈14）

F值（优先级值）：F=G+H

这条公式意思：F是从起点经过该点再到达终点的预测总耗费值。通过计算F值，我们可以优先选择F值最小的方向来进行搜索。

（每个点的左上角为F值，左下角为G值，右下角为H值）


计算出每个方向对应点的F,G,H值后，

还需要给这些点赋予当前节点的指针值（用于回溯路径。因为一直搜下去搜到终点后，如果没有前一个点的指针，我们将无从得知要上次经过的是哪个点，只知道走到终点最终耗费的最小值是多少）

然后我们将这些点放入openList(开启列表：用于存放可以搜索的点)。

然后再将当前点放入closeList(关闭列表：用于存放已经搜索过的点，避免重复搜索同一个点)

然后再从openList取出一个F值最小（最优先方向）的点，进行上述同样的搜索。


在搜索过程中，如果搜索方向上的点是障碍物或者关闭列表里的点，则跳过之。

通过递归式的搜索，多次搜索后，最终搜到了终点。


搜到终点后，然后通过前一个点的指针值，我们便能从终点一步步回溯通过的路径点。

（红色标记了便是回溯到的点）


A*算法优化思路

openList使用优先队列（二叉堆）

可以看到openlist(开启列表)，需要实时添加点，还要每次取出最小值的点。

所以我们可以使用优先队列（二叉堆）来作为openList的容器。

优先队列（二叉堆）：插入一个点的复杂度为O（logN），取出一个最值点复杂度为O（logN）

障碍物列表，closeList使用二维表（二维数组）

由于障碍物列表和closeList仅用来检测是否能通过，所以我们可以使用bool二维表来存放。

//假设已经定义Width和Height分别为地图的长和宽bool barrierList[Width][Height];bool closetList[Width][Height];
有某个点(Xa,Yb)，可以通过

if(barrierList[Xa][Yb]&&closeList[Xa][Yb])来判断。

因为二维表用下标访问，效率很高，但是耗空间比较多。（三维地图使用三维表则更耗内存。不过现在计算机一般都不缺内存空间，所以尽量提升运算时间为主）

这是一个典型的牺牲内存空间换取运算时间的例子。


深度限制

有时要搜的路径非常长，利用A*算法搜一次付出的代价很高，造成游戏的卡顿。

那么为了保证每次搜索不会超过一定代价，可以设置深度限制，每搜一次则深度+1，搜到一定深度限制还没搜到终点，则返还失败值。

平均帧运算

有时候，大量物体使用A*寻路时，CPU消耗比较大。

我们可以不必一帧运算一次寻路，而是在N帧内运算一次寻路。（虽然有所缓慢，但是就几帧的东西，一般实际玩家的体验不会有大影响）

所以我们可以通过每帧只搜索一定深度=深度限制/N（N取决于自己定义多少帧内完成一次寻路）。

导航图辅助寻路


我们可以预先通过给每个房子的门口设置一个导航点（图中为黄色点），如果起点或终点在某个房子里，那么必定经过该房子对应的导航点。

那么可以从起点搜到第一个导航点，然后往下搜索到每个导航点，最后一个导航点搜到终点。

相比直接从起点搜索到终点，这种做法，减少了大量不必要开启搜索的点，效率明显的高。

此外，导航图可以以导航路线为基础而不是导航点为基础。

平滑路径


很容易看出来，这种路径太过死板，只能上下左右+斜45度方向走。


一种平滑化路径的作法是利用递归函数来折半建立直线路径，调用入口是起点和终点。

平滑函数（begin,end）：

用射线检测两点begin,end之间有没有障碍物，

-若无则直接建立两点间的直线路径，结束。

-若有则取两点之间的中间点center,执行平滑函数(begin,center)和平滑函数(center,end)。

A*算法实现（C++代码）

#include <iostream>
#include <vector>
#include <queue>

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

struct OpenPoint : public Point {
    int cost;                 // 耗费值
    int pred;                 // 预测值
    OpenPoint* father;        // 父节点
    OpenPoint() = default;
    OpenPoint(const Point & p, const Point& end, int c, OpenPoint* fatherp) oint(p), cost(c), father(fatherp) {
        //相对位移x,y取绝对值
        int relativex = std::abs(end.x - p.x);
        int relativey = std::abs(end.y - p.y);
        //x,y偏移值n
        int n = relativex - relativey;
        //预测值pred = (max–n)*14+n*10+c
        pred = std::max(relativex, relativey) * 14 - std::abs(n) * 4 + c;
    }
};

const int width = 30;
const int height = 100;

//比较器，用以优先队列的指针类型比较
struct OpenPointPtrCompare {
    bool operator()(OpenPoint* a, OpenPoint* b){
        return a->pred > b->pred;
    }
};
//使用最大优先队列
std::priority_queue<OpenPoint*, std::vector<OpenPoint*>, OpenPointPtrCompare> openlist;
//存储OpenPoint的内存空间
std::vector<OpenPoint> pointList = std::vector<OpenPoint>(width*height);
//地图数据
char mapBuffer[width][height];
//是否可以经过
bool closeAndBarrierList[width][height];
//深度
int deepth;

//检查函数 返还成功与否值
inline bool inBarrierAndCloseList(const Point & pos) {
    if (pos.x < 0 || pos.y < 0 || pos.x >= width || pos.y >= height)
        return true;
    return closeAndBarrierList[pos.x][pos.y];
}

//创建一个开启点
inline OpenPoint* createOpenPoint(const Point & p, const Point& end, int c, OpenPoint* fatherp) {
    pointList.emplace_back(p, end, c, fatherp);
    return &pointList.back();
}

//四方的位置
Point direction[4] ={ Point{1,0},Point{0,1},Point{-1,0}, Point{0,-1} };
//四角的位置
Point corners[4] ={ Point{1,1}, Point{ -1,1 }, Point{ -1,-1 }, Point{ 1,-1 } };

// 开启检查，检查父节点
void open(OpenPoint& pointToOpen, const Point & end) {
    //每检查一次，深度+1
    deepth++;
    //将父节点从openlist移除
    openlist.pop();
    Point toCreate;
    //检查p点四方的点
    for (int i = 0; i < 4; ++i)
    {
        toCreate = Point{pointToOpen.x + direction.x, pointToOpen.y + direction.y};
        if (!inBarrierAndCloseList(toCreate)) {
            openlist.push(createOpenPoint(toCreate, end, pointToOpen.cost + 10, &pointToOpen));
            closeAndBarrierList[toCreate.x][toCreate.y] = true;

        }
    }
    //检查p点四角的点
    for (int i = 0; i < 4; ++i) {
        toCreate = Point{pointToOpen.x + corners.x, pointToOpen.y + corners.y};
        if (!inBarrierAndCloseList(toCreate)) {
            openlist.push(createOpenPoint(toCreate, end, pointToOpen.cost + 14, &pointToOpen));
            closeAndBarrierList[toCreate.x][toCreate.y] = true;
        }
    }
}

//开始搜索路径
OpenPoint* findway(const Point& start, const Point& end) {
    deepth = 0;
    // 创建并开启一个父节点
    openlist.push(createOpenPoint(start, end, 0, nullptr));
    closeAndBarrierList[start.x][start.y] = false;
    // 重复寻找预测和花费之和最小节点开启检查
    while (!openlist.empty())
    {
        auto toOpen = openlist.top();
        // 找到终点后返还end点
        if (*toOpen == end)
            return toOpen->father;
        //若超出一定深度(1000深度)，则失败
        else if (deepth >= 1000)
            return nullptr;
        open(*toOpen, end);
    }
    return nullptr;
}

//创建地图
void createMap() {
    for (int i = 0; i < width; ++i)
        for (int j = 0; j < height; ++j){
            //五分之一概率生成障碍物，不可走
            if (rand() % 5 == 0) {
                mapBuffer[j] = '*';
                closeAndBarrierList[j] = true;
            }
            else {
                mapBuffer[j] = ' ';
                closeAndBarrierList[j] = false;
            }
        }
}

//打印地图
void printMap() {
    for (int i = 0; i < width; ++i) {
        for (int j = 0; j < height; ++j)
            std::cout << mapBuffer[j];
        std::cout << std::endl;
    }
    std::cout << std::endl << std::endl << std::endl;
}

int main() {
    //起点
    Point begin = {0,0};
    //终点
    Point end = {29,99};
    //创建地图
    createMap();
    //打印初始化的地图
    printMap();
    //保证起点和终点都不是障碍物
    mapBuffer[begin.x][begin.y] = mapBuffer[end.x][end.y] = ' ';
    closeAndBarrierList[begin.x][begin.y] = closeAndBarrierList[end.x][end.y] = false;
    //根据搜索得到的终点openpoint，一直延路径回溯
    //并将回溯经过的点标记为'O'
    for (auto rs = findway(Point{ begin.x,begin.y }, Point{ end.x,end.y }); rs != nullptr; rs = rs->father) {
        mapBuffer[rs->x][rs->y] = 'O';
    }
    //打印走过路后的地图
    printMap();
    system("pause");
    return 0;
}

示例效果：

博客地址：https://www.cnblogs.com/KillerAery/p/9231511.html