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

embedded/2024/12/22 21:21:37/

戴克斯特拉算法(英语: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/embedded/147911.html

相关文章

使用Python实现天文数据分析:探索宇宙的奥秘

天文学是一门通过观测和分析天体来研究宇宙结构和演化规律的科学。随着观测技术的进步&#xff0c;天文学家们积累了大量的天文数据。通过对这些数据的分析&#xff0c;我们可以揭示宇宙中的诸多奥秘。Python作为一种功能强大且易用的编程语言&#xff0c;为天文数据分析提供了…

指令v-on 调用传参

在Vue.js中&#xff0c;可以使用指令v-on来给元素绑定事件。v-on指令可以接收一个事件名称作为参数&#xff0c;还可以传递额外的参数给事件处理函数。以下是对v-on指令调用传参的详细解析与代码实例。 当使用v-on指令调用事件处理函数时&#xff0c;可以使用冒号&#xff08;…

PDF无法打印!怎么办?

打开PDF文件之后&#xff0c;发现文件不能打印&#xff1f;这是什么原因&#xff1f;首先我们需要先查看一下自己的打印机是否能够正常运行&#xff0c;如果打印机是正常的&#xff0c;我们再查看一下&#xff0c;文件中的打印功能按钮是否是灰色的状态。 如果PDF中的大多数功…

【C++读写.xlsx文件】OpenXLSX开源库在 Ubuntu 18.04 的编译、交叉编译与使用教程

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a; 2024-12-17 …

harmony UI组件学习(1)

Image 图片组件 string格式&#xff0c;通常用来加载网络图片&#xff0c;需要申请网络访问权限:ohos.permission.INTERNET Image(https://xxx.png) PixelMap格式&#xff0c;可以加载像素图&#xff0c;常用在图片编辑中 Image(pixelMapobject) Resource格式&#xff0c;加…

深度学习环境安装

在此之前请一定要检查一下自己的云服务器里有没有python&#xff0c;一定要&#xff01;&#xff01;&#xff01;&#xff01;因为我就是安装完之后发现自己云服务器中有Python 云服务器的Linux环境下的Python的安装&#xff1a; 第一步&#xff1a;直接安装依赖包 //复制以…

HTML基本标签详解

HTML基本标签详解 HTML&#xff08;超文本标记语言&#xff09;是构建网页的基础&#xff0c;以下是一些常用的 HTML 基本标签及其详细说明&#xff1a; <html> 定义&#xff1a;整个 HTML 文档的根元素。示例&#xff1a;<html lang"zh"><head> …

day04

1.if(表达式) 表达式的最终值为什么类型&#xff1f; 布尔类型 2.多重if用来处理什么样的情况&#xff1f; 通常用于处理某个值处于连续的区间的情况 3.多重if中的else必须写吗 不是必须写 根据需求是否书写 4.Scanner类接收整数&#xff0c;浮点数&#xff0c;字符串分别使用哪…