0
0

AI自动寻路AStar算法【图示讲解原理】

文章目录

AI自动寻路AStar算法

背景

AI自动寻路的算法可以分为以下几种：

1、A算法：A算法是一种

启发式搜索算法

，它利用启发函数（heuristic function）来评估节点的估价函数（estimated cost function），从而寻找最短路径。A*算法综合考虑了

节点的实际代价

和

到目标节点的预计代价

，因此能够快速而准确地寻找最短路径【不一定最短，A*算法并不一定能够找到最短路径，但它通常可以找到

接近最短路径

的解决方案。】

2、Dijkstra算法：Dijkstra算法是一种

贪心算法

，它从起点开始，每次选择当前代价最小的节点作为下一个节点。通过不断

更新节点的代价

，最终可以找到起点到终点的最短路径。

3、Bellman-Ford算法：Bellman-Ford算法是一种

动态规划算法

，它通过

不断更新节点的代价

，直到收敛到最短路径。相比于Dijkstra算法，Bellman-Ford算法能够

处理负权边

的情况。

4、Floyd-Warshall算法：Floyd-Warshall算法是一种

动态规划算法

，它能够计算出图中任意两点之间的最短路径。Floyd-Warshall算法通过

不断更新节点之间的代价

，直到

收敛到最短路径

。

这些算法都可以用于AI自动寻路，具体选择哪种算法需要根据具体的应用场景和性能要求进行选择。

随着 3D 游戏的日趋流行,在复杂的 3D 游戏环境中如何能使非玩家控制角色准确实现自动寻路功能成为了 3D 游戏开
发技术中一大研究热点。其中 A算法得到了大量的运用，A算法较之传统的路径规划算法,实时性更高、灵活性更强,寻路
结果更加接近人工选择的路径结果. A寻路算法并不是找到最优路径，只是找到相对近的路径，因为找最优要把所有可行
路径都找出来进行对比，消耗性能太大，寻路效果只要相对近路径就行了。
所以对于自动寻路，A算法是一个很不错的选择！！！
在这里插入图片描述

AStar算法原理

我们假设在推箱子游戏中人要从站里的地方移动到右侧的箱子目的地，但是这两点之间被一堵墙隔开。
在这里插入图片描述

我们下一步要做的便是查找最短路径。既然是 AI 算法， A* 算法和人寻找路径的做法十分类似，当我们离目标较远时，我
们的目标方向是朝向目的点直线移动，但是在近距离上因为各种障碍需要绕行（走弯路）！而且已走过的地方就无须再次
尝试。
为了简化问题，我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域，就像推箱子游戏一样。
这样就把我们的

搜索区域简化为了 2 维数组

。数组的每一项代表一个格子，它的状态就是可走 (walkalbe) 和不可走
(unwalkable) 。通过计算出从起点到终点需要走过哪些方格，就找到了路径。一旦路径找到了，人物便从一个方格的中心
移动到另一个方格的中心，直至到达目的地。

简化搜索区域以后，如何定义小人当前走要走的格子离终点是近是远呢？我们需要两个指标来表示：
1、 G 表示从

起点

移动到网格上

指定方格

的移动距离 (暂时不考虑沿斜向移动，只考虑上下左右移动)。
2、 H 表示从

指定的方格

移动到

终点

的

预计移动距离

，只计算直线距离 (H 有很多计算方法, 这里我们设定只可以上
下左右移动，即该点与终点的直线距离)。
在这里插入图片描述
令 F = G + H ，F 即表示从起点经过此点预计到终点的总移动距离

AStar寻路步骤

1、从起点开始, 把它作为待处理的方格存入一个预测可达的节点列表，简称 openList, 即把起点放入“预测可达节点列表”，可达节点列表 

openList 就是一个等待检查方格的列表

。

2、

寻找 openList 中 F 值最小的点 min（一开始只有起点）周围可以到达的方格

（可到达的意思是其不是障碍物，也不存在关闭列表中的方格,即不是已走过的方格）。计算 min 周围可到达的方格的 F 值。将还没在 openList 中点放入其中, 并设置它们的"父方格"为点 min,表示他们的上一步是经过 min 到达的。如果 min 下一步某个可到达的方格已经在 openList列表那么并且经 min 点它的 F 值更优,则修改 F 值并把其"父方格"设为点 min。

3、

把 2 中的点 min 从"开启列表"中删除并存入"关闭列表"closeList 中

【当自己对四周扩散时，将自己放入到closeList中】, closeList 中存放的都是

不需要再次检查的方格

。如果 2 中点 min 不是终点并且开启列表的数量大于零，那么继续从第 2 步开始。如果是终点执行第 4 步，如果 openList 列表数量为零，那么就是找不到有效路径。

4、如果第 3 步中 min 是终点，则结束查找，

直接追溯父节点到起点的路径即为所选路径

。

AStar具体寻路过程

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
最后通过

父子关系

将一条起点到终点的路径完整的描述出来

AStar代码实现

Astar.h

#pragmaonce#include<list>//链表#include<vector>constint k_Cost1 =10;//走一格消耗10constint k_Cost2 =14;//斜移走一个消耗14typedefstruct_Point{int x, y;//x为行，y为列int F, G, H;//F=G+H;struct_Point* parent;//父节点的坐标}Point;//分配一个节点
Point*AllocPoint(int x,int y);//初始化地图，地图，行，列voidInitAstarMaze(int* _maze,int _line,int _colums);//通过A*算法寻找路径
std::list<Point*>GetPath(const Point* startPoint,const Point* endPoint);//查找路径的小方法,返回一个终点，根据终点可以回溯到起点static Point*findPath(const Point* startPoint,const Point* endPoint);//用static是为了只能在函数内部调用而不能单独的使用//返回开放列表中F的最小值的点static Point*getLeastFPoint();//获取周围的节点static std::vector<Point*>getSurroundPoint(const Point* point);//某个点是否可达staticboolisCanreach(const Point* point,const Point* target);//是否存在某个list中，这里用作是否存在closeList/openList中static Point*isInList(const std::list<Point*>& list,const Point* point);//获取G，H，FstaticintcaloG(const Point* temp_start,const Point* point);staticintcaloH(const Point* point,const Point* end);staticintcaloF(const Point* point);//清理资源voidclearAstarMaze();

Astar.cpp

#include"Astar.h"#include<cmath>#include<iostream>#include<vector>//extern int k_Cost1;//extern int k_Cost2;staticint* maze;//初始化迷宫staticint cols;//二维数组对应的列staticint lines;//二维数组对应的行static std::list<Point*>openList;//开放列表static std::list<Point*>closeList;//关闭列表/*初始化地图*/voidInitAstarMaze(int* _maze,int _line,int colums){//一级指针保存二维数组
    maze = _maze;
    lines = _line;
    cols = colums;}/*分配节点*/
Point*AllocPoint(int x,int y){
    Point* temp =new Point;memset(temp,0,sizeof(Point));//清理养成好习惯

    temp->x = x;
    temp->y = y;return temp;}/*通过A*算法寻找路径*/
std::list<Point*>GetPath(const Point* startPoint,const Point* endPoint){
    Point *result =findPath(startPoint, endPoint);
    std::list<Point*>path;//返回路径while(result){
        path.push_front(result);//这样起点就是在这个链表的最前面了
        result = result->parent;}return path;}/*查找路径的小方法,返回一个终点，根据终点可以回溯到起点*/static Point*findPath(const Point* startPoint,const Point* endPoint){
    openList.push_back(AllocPoint(startPoint->x, startPoint->y));//重新分配更加的安全，置入起点while(!openList.empty()){//1、获取开放表中最小的F值
        Point* curPoint =getLeastFPoint();//2、把当前节点放到closeList中
        openList.remove(curPoint);
        closeList.push_back(curPoint);//3、找到当前节点周围可到达的节点并计算F值
        std::vector<Point*> surroundPoints =getSurroundPoint(curPoint);

        std::vector<Point*>::const_iterator iter;for(iter = surroundPoints.begin(); iter != surroundPoints.end(); iter++){
            Point* target =*iter;//如果没在开放列表中就加入到开放列表，设置当前节点为父节点
            Point* exist =isInList(openList, target);if(!exist){

                target->parent = curPoint;
                target->G =caloG(curPoint, target);//父节点的G加上某个数就好（自己设计的）
                target->H =caloH(target, endPoint);
                target->F =caloF(target);

                openList.push_back(target);}else{//如果已存在就重新计算G值看要不要替代int tempG =caloG(curPoint, target);if(tempG < target->G){//更新
                    exist->parent = curPoint;
                    exist->G = tempG;
                    exist->F =caloF(target);}delete*iter;}}//end for循环

        surroundPoints.clear();
        Point* resPoint =isInList(openList, endPoint);//终点是否在openList上if(resPoint){return resPoint;}}returnNULL;}//返回开放列表中F的最小值的点static Point*getLeastFPoint(){//遍历if(!openList.empty()){
        Point* resPoint = openList.front();

        std::list<Point*>::const_iterator itor;//定义迭代器，用于遍历链表//迭代器遍历，C++特性,直接理解成平时我们用的forfor(itor = openList.begin(); itor != openList.end(); itor++){
            Point* p =*itor;//把元素拿出来if(p->F < resPoint->F){
                resPoint = p;}}return resPoint;}returnNULL;}/*获取周围的节点*/static std::vector<Point*>getSurroundPoint(const Point* point){
    std::vector<Point*>surroundPoints;//周围九个点都会进行检测for(int x = point->x -1; x <= point->x +1; x++){for(int y = point->y -1; y <= point->y +1; y++){
            Point* temp =AllocPoint(x, y);if(isCanreach(point, temp)){
                surroundPoints.push_back(temp);}else{delete temp;}}}return surroundPoints;}/*某个点是否可达*/staticboolisCanreach(const Point* point,const Point* target){if(target->x<0|| target->x>(lines -1)|| target->y<0|| target->y>(cols -1)||(maze[target->x * cols + target->y]==1)//找到对应的二维数组中的位置-》障碍物||(maze[target->x * cols + target->y]==2)||(target->x == point->x && target->y == point->y)||isInList(closeList, target)){returnfalse;}if(abs(point->x - target->x)+abs(point->y - target->y)==1){//我们现在只考虑上下左右4个点returntrue;}else{returnfalse;}}/*是否存在某个list中，这里用作是否存在closeList/openList中*/static Point*isInList(const std::list<Point*>& list,const Point* point){
    std::list<Point*>::const_iterator itor;for(itor = list.begin(); itor != list.end(); itor++){if((*itor)->x == point->x &&(*itor)->y == point->y){return*itor;//存在返回该节点}}returnNULL;}staticintcaloG(const Point* temp_start,const Point* point){int extraG =(abs(point->x - temp_start->x)+abs(point->y - temp_start->y))==1? k_Cost1 : k_Cost2;//周围的点与扩散点的差值,是否为斜边int parentG =(point->parent ==NULL?NULL: point->parent->G);//如果是初始值为null，其他的点是父类的G值return parentG + extraG;//返回两个量相加}staticintcaloH(const Point* point,const Point* end){//欧几里得求斜边return(int)sqrt((double)(end->x - point->x)*(double)(end->x - point->x))+(double)(end->y - point->y)*(double)(end->y - point->y)* k_Cost1;}staticintcaloF(const Point* point){return point->G + point->H;}/*清理资源*/voidclearAstarMaze(){
    maze =NULL;
    lines =0;
    cols =0;
    std::list<Point*>::iterator itor;for(itor = openList.begin(); itor != openList.end();){delete* itor;
        itor = openList.erase(itor);//获取到下一个节点}for(itor = closeList.begin(); itor != closeList.end();){delete* itor;
        itor = closeList.erase(itor);//获取到下一个节点}}

main.cpp

#include<iostream>#include<stdlib.h>#include<stdio.h>#include<string.h>#include<windows.h>#include"Astar.h"usingnamespace std;int map[13][13]={{0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,0,1,0,1,0,1,0,1,0,1,0},{0,1,0,1,0,1,0,1,0,1,0,1,0},{0,1,0,1,0,1,2,1,0,1,0,1,0},{0,1,0,1,0,1,0,1,0,1,0,1,0},{0,1,0,1,0,0,0,1,0,1,0,1,0},{0,0,0,0,0,1,0,1,0,0,0,0,0},{2,0,1,1,0,0,0,1,0,1,0,0,2},{0,0,0,0,0,1,1,1,0,0,0,0,0},{0,1,0,1,0,1,0,1,0,1,0,1,0},{0,1,0,1,0,1,0,1,0,1,0,1,0},{0,1,0,1,0,0,0,0,0,1,0,1,0},{0,0,0,0,0,1,3,1,0,0,0,0,0}};voidastarTest(){InitAstarMaze(&map[0][0],13,13);//设置
    Point* start =AllocPoint(12,4);
    Point* end =AllocPoint(0,12);//寻找路径
    list<Point*>path =GetPath(start, end);//设置迭代器遍历
    list<Point*>::const_iterator iter;//迭代器

    cout <<"("<< start->x <<","<< start->y <<")"<<"------>("<< end->x <<","<< end->y <<")"<< endl;
    cout <<"****************** 寻路结果 ********************************"<< endl;for(iter = path.begin(); iter != path.end();){
        Point* cur =*iter;
        cout <<'('<< cur->x <<","<< cur->y <<')'<< endl;//delete cur;//不用再进行释放了因为在openList和closeList链表中我们最后都有清理，如果再清理就会报错
        iter = path.erase(iter);Sleep(800);//休眠}clearAstarMaze();}intmain(){astarTest();system("pause");return0;}

运行结果

在这里插入图片描述

标签： 算法 人工智能 数据结构
本文转载自: https://blog.csdn.net/Jacksqh/article/details/130021686
版权归原作者 CAccept 所有， 如有侵权，请联系我们删除。
登录后发布评论

“AI自动寻路AStar算法【图示讲解原理】”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

信息系统与互联网中的安全、隐私及伦理问题

3分钟解决Ubuntu22.04没有声音输出设备

Docker下载途径

Vue3 与 D3.js 集成：实现数据可视化和动态图表的交互效果

【Kafka】Kafka源码解析之producer过程解读

设备的双按钮安全启动控制，你知道吗？

打造网页版Ubuntu环境：群晖NAS部署docker-webtop与远程访问指南

文章导航