游戏AI实现-寻路算法(Dijkstra)

devtools/2024/12/23 1:14:02/

戴克斯特拉算法(英语:Dijkstra's algorithm),又称迪杰斯特拉算法、Dijkstra算法,是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法。

算法过程:

1.首先设置开始节点的成本值为0,并将开始节点放入检测列表中。

2.将检测列表中的所有点按到目标点所需的成本值排序,选择成本最小的节点作为当前节点,并将其移出检测列表。

3.将当前点周围的点中不包含在检测列表中的点加入到检测列表,将周围点加入到已检测列表中。

4.更新检测列表中的节点到当前节点的成本值。

5.重复2,3,4直到找到目标点。

代码实现:

public class Dijkstra : FindPathAlgorithm
{public Dijkstra(int[,] mapData, int xCount, int zCount) : base(mapData, xCount, zCount){}public override List<Vector2Int> FindPath(Vector2Int startPos, Vector2Int goalPos){DataNode dataNode = this.DijkstraFind(startPos, goalPos);if (dataNode == null){Debug.LogError("寻路有误,请检查参数是否正确");return null;}return Utils.GetPath(dataNode);}DataNode DijkstraFind(Vector2Int startPos, Vector2Int goalPos){//存储要检测的点List<DataNode> frontier = new List<DataNode>();//存储已经检测的点List<Vector2Int> reached = new List<Vector2Int>();DataNode startNode = new DataNode(startPos, null);startNode.gCost = 0;frontier.Add(startNode);reached.Add(startPos);while (frontier.Count > 0){DataNode currentNode = GetLowestgCostNode(frontier);frontier.Remove(currentNode);if (currentNode.pos == goalPos){Debug.Log("完成!!!");return new DataNode(goalPos, currentNode.parent);}List<DataNode> neighbors = GetNeighbors(currentNode.pos, reached);foreach (DataNode neighbourNode in neighbors){if (!frontier.Contains(neighbourNode)){neighbourNode.parent = currentNode;frontier.Add(neighbourNode);}reached.Add(neighbourNode.pos);}this.UpdateCost(frontier, currentNode);}return null;}//更新成本值void UpdateCost(List<DataNode> nodes, DataNode currentNode){for (int i = 0; i < nodes.Count; i++){int newCost = currentNode.gCost + CalculateDistanceCost(nodes[i].pos, currentNode.pos);if (nodes[i].gCost > newCost){nodes[i].gCost = newCost;}}}List<DataNode> GetNeighbors(Vector2Int current, List<Vector2Int> reached){List<DataNode> neighbors = new List<DataNode>();for (int i = 0; i < Utils.pointDir.Count; i++){Vector2Int neighbor = current + Utils.pointDir[i];if (this.IsCanAdd(neighbor, reached)){neighbors.Add(new DataNode(neighbor, null));}}return neighbors;}bool IsCanAdd(Vector2Int current, List<Vector2Int> reached){if (reached.Contains(current))return false;if (current.x >= 0 && current.y >= 0 && current.x < MapData.m_MapData.GetLength(1) && current.y < MapData.m_MapData.GetLength(0)){//如果是障碍物,则不能被Addif (MapData.m_MapData[current.y, current.x] == 1){return false;}return true;}return false;}private int CalculateDistanceCost(Vector2Int a, Vector2Int b){return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);}private DataNode GetLowestgCostNode(List<DataNode> pathNodeList){DataNode lowestFCostNode = pathNodeList[0];for (int i = 1; i < pathNodeList.Count; i++){if (pathNodeList[i].gCost < lowestFCostNode.gCost){lowestFCostNode = pathNodeList[i];}}return lowestFCostNode;}
}

结果:

参考链接:

Pathfinding in Unity - Part3: Dijkstra Algorithm Theory (youtube.com)

Pathfinding in Unity - Part4: Dijkstra Algorithm Implementation (youtube.com)

How Dijkstra's Algorithm Works (youtube.com)

戴克斯特拉算法 - 维基百科,自由的百科全书 (wikipedia.org)


http://www.ppmy.cn/devtools/144537.html

相关文章

熟悉u8g2图形库C语言函数

前言&#xff1a; 前面我们已经成功移植了U8g2的图形库&#xff08;0.96寸OLED&#xff09;&#xff1a;手把手移植U8g2图形库&#xff0c;这个文章主要熟悉u8g2图形库的常用C语言函数&#xff01;需要移植的资料的可以关注一波评论区评论&#xff0c;我看到了就会给你发哦&am…

bestphp‘s revenge

bestphp’s revenge 知识点 php session反序列化 解题 <?php highlight_file(__FILE__); $b implode; call_user_func($_GET[f], $_POST); //参数二的位置固定为 $_POST 数组&#xff0c;我们很容易便想到利用 extract 函数进行变量覆盖&#xff0c;以便配合后续利用…

远程连接的功能以及种类(sshd)

1.ssh简介 ssh通过创建安全隧道来实现ssh客户端与服务器之间的连接&#xff0c; 它的主要用途是连接远程服务器然后在上面执行指令。 远程连接服务器&#xff1a;分享主机的运算能力 种类&#xff1a;明文传输&#xff1a;Telent RSH等 目前非常少用 加密传输&#xff1a;S…

解决 Ubuntu 20.04 上编译 OpenCV 3.2 时的类型不匹配错误

解决 Ubuntu 20.04 上编译 OpenCV 3.2 时的类型不匹配错误 make[2]: *** [modules/python3/CMakeFiles/opencv_python3.dir/build.make:329&#xff1a;modules/python3/CMakeFiles/opencv_python3.dir/__/src2/cv2.cpp.o] 错误 1 make[1]: *** [CMakeFiles/Makefile2:11856&a…

在M系列芯片的Mac上使用Uniapp开发的依赖安装指南

在M系列芯片的Mac上使用Uniapp开发的依赖安装指南 在基于M系列芯片&#xff08;例如M3、M4&#xff09;的Mac上进行Uniapp开发时&#xff0c;使用esbuild和rollup等依赖包时需要注意处理不同架构的支持。具体问题出现在darwin-arm64&#xff08;ARM架构&#xff09;和darwin-x…

[react]suspend 组件搭配路由组件时fallback不生效

用key即可解决, 为什么,因为suspend只会在首次加载时执行一次fallback <Suspense> – React 中文文档

中阳科技:从量化交易到智能金融的创新实践

量化交易的出现改变了传统金融市场的游戏规则&#xff0c;它通过算法驱动和数据分析实现了自动化、智能化的交易流程。作为这一领域的佼佼者&#xff0c;中阳科技专注于探索量化模型的创新&#xff0c;助力投资者在复杂的市场中获取竞争优势。 量化交易的优势剖析 量化交易依赖…

深入浅出支持向量机(SVM)

1. 引言 支持向量机&#xff08;SVM, Support Vector Machine&#xff09;是一种常见的监督学习算法&#xff0c;广泛应用于分类、回归和异常检测等任务。自1990年代初期由Vapnik等人提出以来&#xff0c;SVM已成为机器学习领域的核心方法之一&#xff0c;尤其在模式识别、文本…