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

server/2024/12/23 16:21:58/

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

相关文章

JavaScript事件循环案例深入理解

事件循环的主要步骤&#xff1a; 执行栈&#xff08;Call Stack&#xff09;&#xff1a; 同步代码直接进入栈中依次执行。 任务队列&#xff08;Task Queue&#xff09;&#xff1a; 异步任务&#xff08;如 setTimeout、DOM 事件、Ajax 回调&#xff09;完成后将其回调函数放…

VSCode 插件开发实战(三):插件配置项自定义设置

前言 作为一名前端开发者&#xff0c;您可能已经在 VSCode 中体验过各种强大的插件。那么&#xff0c;如果您希望创建一个属于自己的插件&#xff0c;并且希望用户能够通过自定义配置进行灵活调整&#xff0c;该如何实现呢&#xff1f;本文将详细介绍如何在 VSCode 插件中实现…

jmeter怎么调用python

jmeter中使用python脚本 在jmeter中使用python脚本&#xff0c;搜了下&#xff0c;找到三种方式&#xff1a; 1、使用Jython包 下载 Download Jython 2.7.0 - Standalone Jar 包&#xff0c;放到jmeter/lib/目录下&#xff0c;重启jmeter&#xff0c;就能在sampler中找到JSR…

【SH】在Ubuntu Server 24中基于Python Web应用的Flask Web开发(实现POST请求)学习笔记

文章目录 Flask开发环境搭建保持Flask运行Debug调试 路由和视图可变路由 请求和响应获取请求信息Request属性响应状态码常见状态码CookieSession 表单GET请求POST请求 Flask 在用户使用浏览器访问网页的过程中&#xff0c;浏览器首先会发送一个请求到服务器&#xff0c;服务器…

第十四届蓝桥杯Scratch国赛真题—转动的车轮

转动的车轮 编程实现&#xff1a; 转动的车轮&#xff08;车轮使用画笔绘制&#xff0c;画面中不能出现其他角色&#xff0c;否则0分&#xff09;。 注&#xff1a;角色、背景非源素材。 具体要求&#xff1a; 1). 点击绿旗&#xff0c;背景如图所示&#xff1b; 2). 等待1…

【系统架构设计师】真题论文: 论软件设计方法及其应用(包括解题思路和素材)

更多内容请见: 备考系统架构设计师-专栏介绍和目录 文章目录 真题题目(2019年 试题1)解题思路论文素材参考软件设计方法概述和使用场景项目案例-结构化设计方法真题题目(2019年 试题1) 软件设计(Software Design,SD)根据软件需求规格说明书设计软件系统的整体结构、划…

电脑连接不上手机热点 找不到到服务器的ip地址

手机热点连接不上 找不到到服务器的ip地址 emmm希望不会有人不会吧 解决方法&#xff1a; 1.点击右上角图标进入设置 2.点击更改所有wifi网络的DNS设置 3.查看自己的IP分配和DNS分配是不是DHCP自动分配&#xff0c;不是的话就不对了&#xff0c;需要点击编辑手动改一下 4.改完…

第二十六周机器学习笔记:PINN求正反解求PDE文献阅读——正问题

第二十六周周报 摘要Abstract文献阅读《Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations》1. 引言2. 问题的设置3.偏微分方程的数据驱动解3.1 连续时间模型3.1.1 …