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

这篇具有很好参考价值的文章主要介绍了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*算法是一个很不错的选择!!!
AI自动寻路AStar算法【图示讲解原理】


AStar算法原理

我们假设在推箱子游戏中人要从站里的地方移动到右侧的箱子目的地,但是这两点之间被一堵墙隔开。
AI自动寻路AStar算法【图示讲解原理】

我们下一步要做的便是查找最短路径。既然是 AI 算法, A* 算法和人寻找路径的做法十分类似,当我们离目标较远时,我
们的目标方向是朝向目的点直线移动,但是在近距离上因为各种障碍需要绕行(走弯路)!而且已走过的地方就无须再次
尝试。
为了简化问题,我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步,简化搜索区域,就像推箱子游戏一样。
这样就把我们的搜索区域简化为了 2 维数组。数组的每一项代表一个格子,它的状态就是可走 (walkalbe) 和不可走
(unwalkable) 。通过计算出从起点到终点需要走过哪些方格,就找到了路径。一旦路径找到了,人物便从一个方格的中心
移动到另一个方格的中心,直至到达目的地。

简化搜索区域以后,如何定义小人当前走要走的格子离终点是近是远呢?我们需要两个指标来表示:
1、 G 表示从起点移动到网格上指定方格的移动距离 (暂时不考虑沿斜向移动,只考虑上下左右移动)。
2、 H 表示从指定的方格移动到终点预计移动距离,只计算直线距离 (H 有很多计算方法, 这里我们设定只可以上
下左右移动,即该点与终点的直线距离)。
AI自动寻路AStar算法【图示讲解原理】
令 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具体寻路过程

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


AI自动寻路AStar算法【图示讲解原理】
最后通过父子关系将一条起点到终点的路径完整的描述出来


AStar代码实现

Astar.h

#pragma once
#include<list>//链表
#include<vector>
const int k_Cost1 = 10;//走一格消耗10
const int k_Cost2 = 14;//斜移走一个消耗14

typedef struct _Point {
	int x, y;  //x为行,y为列
	int F, G, H;  //F=G+H;
	struct _Point* parent;  //父节点的坐标
}Point;

//分配一个节点
Point* AllocPoint(int x, int y);


//初始化地图,地图,行,列
void InitAstarMaze(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);

//某个点是否可达
static bool isCanreach(const Point* point, const Point* target);

//是否存在某个list中,这里用作是否存在closeList/openList中
static Point* isInList(const std::list<Point*>& list, const Point* point);

//获取G,H,F
static int caloG(const Point* temp_start, const Point* point);
static int caloH(const Point* point, const Point* end);
static int caloF(const Point* point);

//清理资源
void clearAstarMaze();

Astar.cpp

#include"Astar.h"
#include<cmath>
#include<iostream>
#include<vector>
//extern int k_Cost1;
//extern int k_Cost2;

static int* maze;//初始化迷宫
static int cols;//二维数组对应的列
static int lines;//二维数组对应的行

static std::list<Point*>openList;  //开放列表
static std::list<Point*>closeList; //关闭列表


/*初始化地图*/
void InitAstarMaze(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;
		}


	}


	return NULL;
}

//返回开放列表中F的最小值的点
static Point* getLeastFPoint() {
	//遍历
	if (!openList.empty()) {
		Point* resPoint = openList.front();

		std::list<Point*>::const_iterator itor;//定义迭代器,用于遍历链表

		//迭代器遍历,C++特性,直接理解成平时我们用的for
		for (itor = openList.begin(); itor != openList.end(); itor++) {
			Point* p = *itor;//把元素拿出来
			if (p->F < resPoint->F) {
				resPoint = p;
			}
		}
		return resPoint;
	}
	return NULL;
}

/*获取周围的节点*/
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;
}


/*某个点是否可达*/
static bool isCanreach(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)) {
		return false;

	}

	if (abs(point->x - target->x) + abs(point->y - target->y) == 1) {//我们现在只考虑上下左右4个点
		return true;
	}
	else {
		return false;
	}
}


/*是否存在某个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;  //存在返回该节点
		}
	}
	return NULL;
}

static int caloG(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;//返回两个量相加
}

static int caloH(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;

}

static int caloF(const Point* point) {
	return point->G + point->H;
}

/*清理资源*/
void clearAstarMaze() {
	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"
using namespace 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}
};
void astarTest() {

	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();
}
int main() {
	astarTest();
	system("pause");
	return 0;
}

运行结果

AI自动寻路AStar算法【图示讲解原理】文章来源地址https://www.toymoban.com/news/detail-418453.html

到了这里,关于AI自动寻路AStar算法【图示讲解原理】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 自动驾驶路径规划——A*(Astar)算法

         最佳优先搜索(BFS) ,又称A算法,是一种启发式搜索算法(Heuristic Algorithm)。[不是广度优先搜索算法( Breadth First Search , BFS )]     BFS算法在广度优先搜索的基础上, 用启发估价函数对将要被遍历到的点进行估价 ,然后选择代价小的进行遍历,直到找到目标节点

    2024年02月01日
    浏览(52)
  • Unity 中 A*寻路(AStar,A星)的优化,二叉堆,双向队列,哈希表

    前篇:A星寻路的简单实现 A星寻路,在2D地图下使用频率较高 本篇基于上一篇文章实现的A星寻路进一步优化。利用二叉堆代替了原先openList的数据结构, 改进了path返回时的操作,以及在搜索时的性能开销。 c#中的Sort函数,在实现方面采用的是快速排序。 在日常的使用上,好

    2024年02月03日
    浏览(41)
  • Unity AI Navigation自动寻路

    Unity是一款强大的游戏开发引擎,而人工智能(AI)导航是游戏中至关重要的一部分。通过Unity的AI Navigation系统,开发者可以轻松地为游戏中的角色实现自动导航功能。本文将介绍Unity中AI Navigation的基础内容,帮助开发者快速入门。 Unity中的AI Navigation是一套用于游戏开发的导

    2024年04月16日
    浏览(40)
  • unity的AI自动寻路navigation基本用法

     1.场景中的地面和障碍物都设置成静态的,  2.给需要寻路的AI物体添加Nav Mesh Agent 组件, 3在window下面找到navigation,打开选all,调好参数后点击bake 4.运行时用代码实现鼠标点击屏幕一点,AI就自动避让障碍物到达(代码在下面)      

    2024年02月11日
    浏览(48)
  • unity有限状态机和模糊状态机(怪物AI、自动寻路)

    自动寻路步骤: 1、把场景中不同的物体勾选static 2、烘培寻路网格 3、添加NavMeshAgent组件 4、给需要寻路的物体添加脚本 游戏中有限状态机的体现:小怪的巡逻和追逐功能 模糊状态机的体现:当玩家离小怪比较近时,小怪会追逐玩家,当玩家离小怪比较远时小怪会停止追逐玩

    2024年02月04日
    浏览(54)
  • 【Unity】一篇文章搞定AStar(A*)算法

    AStar(A*)算法,是一种在静态网格中求解最短路径直接有效的搜索方法。在游戏开发中,A*算法常应用于部分RPG游戏和策略战棋类游戏。对于Unity开发者来说,掌握A*算法也是十分有必要的。不过在了解A*算法之前,有必要先回顾一下深度优先算法(DFS)、广度优先算法(BFS)

    2024年02月02日
    浏览(59)
  • 【ROS-Navigation】—— Astar路径规划算法解析

        最近在学习ROS的navigation部分,写些东西作为笔记,方便理解与日后查看。本文从Astar算法入手,对navigation源码进行解析。 PS:ros navigation源码版本https://gitcode.net/mirrors/ros-planning/navigation/-/tree/noetic-devel     对于Astar算法,想必大家都非常熟悉了。具体算法原理就不

    2024年01月18日
    浏览(49)
  • 【Unity】Unity寻路系统讲解及Navigation实际应用

    Unity常用的寻路方式主要有以下几种: 路点寻路(WayPoint) 单元格寻路(Grid) 导航系统(Navigation) 路点寻路就是在地图上指定一些路点,让角色在路点之间移动。常用于一些固定路线的敌人或物体。 优点:路点寻路的优点是实现起来比较简单,且占用资源少、计算开销低

    2024年02月01日
    浏览(99)
  • 【Unity自动寻路】使用Navigation系统实现物体自动寻路绕开障碍物

    知识点流程图 我们在游戏场景中经常会有一些障碍物、墙壁、树木等等,如果我想要让角色或者怪物去墙的另一边,我直接在墙另一边点击左键,我希望角色自动跑过去,但是他不能直接穿透墙,他需要“智能”的绕开障碍物,自动找到可以走的路,自己过去!这就是Unity

    2024年02月03日
    浏览(52)
  • 遗传算法原理详细讲解(算法+Python源码)

    博主介绍:✌专研于前后端领域优质创作者、本质互联网精神开源贡献答疑解惑、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战,深受全网粉丝喜爱与支持✌有需要可以联系作者我哦! 🍅文末获取源码联系🍅 👇🏻 精彩专栏

    2024年01月25日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包