首页 > 编程语言 >游戏AI-寻路-A*寻路算法

游戏AI-寻路-A*寻路算法

时间:2023-07-07 15:11:33浏览次数:43  
标签:Node AI 节点 int 算法 Cost Path 寻路 CurNode

算法介绍:

作用:在一个图中,提供一个起点A与一个终点B,给你找出一条估算出来较短的路

时间复杂度:n * log(m) ,n表示图中的节点数,m表示总边的数量

时间复杂度分析:

  1. 一般游戏中的图是一个二维矩阵,所以每个点的方向也就上下左右这么几个,所以每个点枚举方向的时间为常数
  2. 虽然复杂度为:n * log(m),但A*是启发式算法,其中大量的点可能都没被枚举到,真正的时间消耗远小于:n * log(m)

算法解析:

A*算法可以理解成是从BFS经历了两次优化,第一次优化成了Dijkstra算法,再从Dijkstra算法优化成了A*算法。

A*的算法流程:
  1. 初始化一个启发数组,array[p] = 点p到终点的距离(array的值要看程序员设计了,设计的好估算出来的较短路就越优秀)
  2. 准备一个优先队列,以期望费用值从小到大排列
  3. 将起点加入队列
  4. 取出队头
    1. 若节点为终点:结束
    2. 若节点已经过:跳过节点
    3. 若节点未经过:标记节点已经过,并记录费用
  5. 枚举队头节点的8个方向
  6. 将可达的新节点加入队列
    1. 节点的费用设置为:当前点的费用 + 当前点到新节点的费用
    2. 期望费用设置为:当前点的费用 + 当前点到新节点的费用 + 启发数组[新节点]
  7. 回到第4步循环
A*部分内容说明:
  1. 启发函数的作用:
    1. 这就是从Dijkstra到A*的优化,具体作用就是用启发函数去影响找点的优先级
    2. Dijkstra的逻辑:每次都能找到一个费用最低的点再用这个费用最低的点去维护出其他的费用最低的点出来,是一种贪心的思路,并且也可以证明以这种方式找出来的路一定是最短路
    3. A*的逻辑:我不仅要考虑我下一个检查的点是不是费用小的,我还要考虑它是不是离终点近,然后对点到终点的距离加权并影响检查的点的顺序。这种方式找最短路,离终点近的点其实并不一定费用会小,但很可能更快抵达终点
  2. 为什么用优先队列:
    1. 主要就是利用二叉堆加速查找期望费用最小的点是哪个
  3. 如何减小A*跑出来的最短路的误差:
    1. 降低期望数组的权重
    2. 设计更合理期望数组

算法实现:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int N = 25;
const int M = 100;

class Node {
public:
	int X;
	int Y;
	int Cost;
	int ExpectCost;
	Node* FatherNode;
	static int ExpectArray[N][M];
	Node();
	Node(int x, int y, Node* fatherNode) :X(x), Y(y), FatherNode(fatherNode)
	{
		if (fatherNode == nullptr)
		{
			Cost = 0;
			ExpectCost = ExpectArray[x][y];
			return;
		}
		Cost = fatherNode->Cost + 1;
		ExpectCost = Cost + ExpectArray[x][y];
	}
};

int Node::ExpectArray[N][M];
char MapInfo[N][M];
const int S_X = 0;
const int S_Y = 0;
const int E_X = N - 1;
const int E_Y = M - 1;
void CreateMap()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (i == S_X && j == S_Y || i == E_X && j == E_Y)
			{
				MapInfo[i][j] = ' ';
			}
			else if (rand() % 5 == 0)
			{
				MapInfo[i][j] = '#';
			}
			else
			{
				MapInfo[i][j] = ' ';
			}
		}
	}
}

void PrintMap()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << MapInfo[i][j];
		}
		cout << endl;
	}
}

void InitExpectArray()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			Node::ExpectArray[i][j] = abs(i - E_X) + abs(j - E_Y);
		}
	}
}

class Compare_Node_Pointer
{
public:
	bool operator () (Node*& a, Node*& b) const
	{
		return a->Cost > b->Cost;
	}
};

priority_queue<Node*, vector<Node*>, Compare_Node_Pointer>Queue;

void InitQueue()
{
	while (!Queue.empty())
	{
		Queue.pop();
	}
}

int DirectionX[4] = { 0,0,1,-1 };
int DirectionY[4] = { 1,-1,0,0 };
bool Flag[N][M];

void FindPath()
{
	memset(Flag, false, sizeof(Flag));
	vector<Node*>Path;
	InitExpectArray();
	InitQueue();
	Node* StartNode = new Node(S_X, S_Y, nullptr);
	Queue.push(StartNode);
	while (!Queue.empty())
	{
		Node* CurNode = Queue.top();
		Queue.pop();
		if (CurNode->X == E_X && CurNode->Y == E_Y)
		{
			Path.push_back(CurNode);
			break;
		}
		if (Flag[CurNode->X][CurNode->Y])
		{
			continue;
		}
		Flag[CurNode->X][CurNode->Y] = true;
		for (int i = 0; i < 4; i++)
		{
			int NextX = CurNode->X + DirectionX[i];
			int NextY = CurNode->Y + DirectionY[i];
			if(0 <= NextX && NextX < N && 0 <= NextY && NextY < M && MapInfo[NextX][NextY] != '#')
			{
				
				Node* NextNode = new Node(NextX, NextY, CurNode);
				Queue.push(NextNode);
				if (NextX == CurNode->X && NextY == CurNode->Y)
				{
					printf("%d = %d + %d\n", NextX, CurNode->X, DirectionX[i]);
					printf("%d = %d + %d\n", NextY, CurNode->Y, DirectionY[i]);
					printf("\n");
				}
			}
		}
	}

	if (Path.size() == 1)
	{
		Node* Node = Path[0];
		while (true)
		{
			if (Node->FatherNode != nullptr)
			{
				printf("%d %d", Node->FatherNode->X, Node->FatherNode->Y);
				Path.push_back(Node->FatherNode);
				Node = Node->FatherNode;
			}
			else
			{
				break;
			}
		}
	}
	reverse(Path.begin(), Path.end());
	for (int i = 0; i < Path.size(); i++)
	{
		printf("X = %d, Y = %d, Cost = %d\n", Path[i]->X, Path[i]->Y, Path[i]->Cost);
		MapInfo[Path[i]->X][Path[i]->Y] = 'o';
	}
}

int main()
{
	CreateMap();
	FindPath();
	PrintMap();
	system("pause");
	return 0;
}

标签:Node,AI,节点,int,算法,Cost,Path,寻路,CurNode
From: https://www.cnblogs.com/whitelily/p/17535022.html

相关文章

  • 数据结构与算法(一)
    需要点Java编程基础常见的数据结构栈(Stack):栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作。队列(Queue):队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。数组(Array):数组是一种聚合数据......
  • C/C++数据结构与算法课程设计[2023-07-06]
    C/C++数据结构与算法课程设计[2023-07-06]数据结构与算法课程设计一、课程设计的目的、要求和任务 本课程设计是为了配合《数据结构与算法》课程的开设,通过设计完整的程序,使学生掌握数据结构的应用、算法的编写等基本方法。1.课程的目的(1)使学生进一步理解和掌握课堂上所学......
  • 万能欧几里得算法学习笔记
    万能欧几里得算法万能欧几里得算法用于解决一类与\(\left\lfloor\frac{p\cdotx+r}{q}\right\rfloor\)有关的和式求解问题,例如类欧几里得算法中提到的和式就属于此类问题。但万能欧几里得算法从几何意义出发能处理更广泛的和式类型。例如\(\sum_{x=0}^{l}A^xB^{\left\lfloor\f......
  • 使用vscode的devcontainer以及docker初体验
    想尝试0xffff提供的devcontainer来搭建开发环境。在后面发现搭建失败,都显示连接失败。后面查看nginx的log日志发现,nginx服务是正常启动的,可以看到404。查看phperrorlog发现,是未找到autoload.php。顺着找下去我发现,可能是因为composer包没有安装完全。flarum-lang/chinese-simp......
  • Failed to instantiate [org.apache.tomcat.jdbc.pool.DataSource]
    问题:项目中没有使用db相关的东西,但是在应用启动时报错:Failedtoinstantiate[org.apache.tomcat.jdbc.pool.DataSource]原因:  pom.xml中配置了和数据库相关的,SpringBoot启动默认会加载org.springframework.boot.autoconfigure.jdbc.DataSourceAutoConfiguration类,DataSo......
  • 解决“Host key verification failed”远程连接linux服务器 could not establish conn
    在使用vscode远程连接linux服务器时,遇到了个报错:couldnotestablishconnectionto我用的服务器是腾讯云轻应用。查了半天看到阿里云文档里有类似的解决方法,最后得到解决。发现是本地缓存的问题?使用SSH远程连接Linux系统的ECS实例时,提示“Hostkeyverificationfailed”错误怎......
  • 常用算法记录
    二叉树遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/递归解法前序遍历publicstaticvoidpreOrderRecur(TreeNodehead){if(head==null){return;}......
  • 几个经典算法的概念
    动态规划(DynamicProgramming) 一、动态规划的基本思想:   动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题......
  • 数据结构(算法)【7月6日】
    一、算法的基本概念:1、算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。2、算法的特性:(1)有穷性:一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成;【算法是有穷的,程序是无穷的】(2)确定性:算法中每条指令必须有确切的含义,......
  • Docker CLI docker container kill 常用命令
    Docker是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中,然后发布到任何流行的Linux或Windows操作系统的机器上,也可以实现虚拟化。Docker是内核虚拟化,不使用Hypervisor是不完全虚拟化,依赖内核的特性实现资源隔离。本文主要介绍DockerCLI中d......