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

戴克斯特拉算法(英语: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.rhkb.cn/news/492137.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【第二节】Git 工作流程、概念及仓库创建

目录 一、Git 工作流程 二、Git 基本概念 2.1 工作区 2.2 暂存区 2.3 版本库 2.4 操作流程 三、Git 仓库创建 3.1 初始化仓库 3.2 克隆仓库 一、Git 工作流程 Git 的工作流程通常包括以下几个步骤&#xff1a; 1. **克隆 Git 资源**&#xff1a;将远程 Git 仓库克隆到…

概率论得学习和整理30: 用EXCEL 描述泊松分布 poisson distribution

目录 1 泊松分布的基本内容 1.1 泊松分布的关键点 1.1.1 属于离散分布 1.1.2 泊松分布的特点&#xff1a;每个子区间内概率相等 &#xff0c; λ就是平均概率 1.2 核心参数 1.3 pmf公式 1.4 期望和方差 2 例1&#xff1a;用EXCEL计算泊松分布的概率 3 比较λ不同值时…

【机器学习】【无监督学习——聚类】从零开始掌握聚类分析:探索数据背后的隐藏模式与应用实例

从零开始掌握聚类分析&#xff1a;探索数据背后的隐藏模式与应用实例 基本概念聚类分类聚类算法的评价指标&#xff08;1&#xff09;内部指标轮廓系数&#xff08;Silhouette Coefficient&#xff09;DB指数&#xff08;Davies-Bouldin Index&#xff09;Dunn指数 &#xff08…

灵活接入第三方接口,解析第三方json数据,返回我们想要的json格式

需求&#xff1a;我想接入任意第三方http 接口&#xff08;暂不考虑鉴权问题&#xff09;、接口返回任意json数据。 1、要求返回的json数据通过我的R< T > 返回。 2、我的R< T > 里面包含参数 data&#xff0c;code&#xff0c;msg&#xff0c;success标识。 3、…

Nginx 在不同操作系统下的安装指南

Nginx 在不同操作系统下的安装指南 一、Linux 系统下 Nginx 的安装 &#xff08;一&#xff09;基于 Ubuntu 系统 更新软件包列表 打开终端&#xff0c;首先执行sudo apt-get update命令。这一步是为了确保系统的软件包列表是最新的&#xff0c;能够获取到最新版本的 Nginx 及…

docker redis 详细教程

1. 拉取镜像 docker pull redis 2. 创建数据存储目录 cd /home/ mkdir redis cd redis mkdir data mkdir log mkdir conf 3.创建容器并且运行 docker run \ -p 6379:6379 \ --name redis \ -v /home/redis/data:/data \ -d redis 参考链接 史上最详细Docker安装Redis &am…

学技术学英文:代码中的锁:悲观锁和乐观锁

本文导读&#xff1a; 1. 举例说明加锁的场景&#xff1a; 多线程并发情况下有资源竞争的时候&#xff0c;如果不加锁&#xff0c;会出现数据错误&#xff0c;举例说明&#xff1a; 业务需求&#xff1a;账户余额>取款金额&#xff0c;才能取钱。 时间线 两人共有账户 …

云计算赋能:TSP 问题求解与创新定价机制的全景剖析

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;编程探索专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年12月18日14点02分 神秘男子影, 秘而不宣藏。 泣意深不见, 男子自持重, 子夜独自沉。 论文源地址&#xff1a; Aspiringco…

二、windows环境下vscode使用wsl教程

本篇文件介绍了在windows系统使用vscode如何连接使用wsl&#xff0c;方便wsl在vscode进行开发。 1、插件安装 双击桌面vscode&#xff0c;按快捷键CtrlShiftX打开插件市场&#xff0c;搜索【WSL】点击安装即可。 2、开启WSL的linux子系统 点击左下方图标【Open a Remote Win…

QScreen在Qt5.15与Qt6.8版本下的区别

简述 QScreen主要用于提供与屏幕相关的信息。它可以获取有关显示设备的分辨率、尺寸、DPI&#xff08;每英寸点数&#xff09;等信息。本文主要是介绍Qt5.15与Qt6环境下&#xff0c;QScreen的差异&#xff0c;以及如何判断高DPI设备。 属性说明 logicalDotsPerInch&#xff1…

【已解决】在Visual Studio里将应用与Microsoft Store关联时提示网络异常

发布Windows应用时。在Visual Studio里点击"发布“&#xff0c;将应用与Microsoft Store关联时&#xff0c;一直提示网络错误。 查了一下论坛&#xff0c;发现之前也经常出现&#xff0c;但我是第一次遇到。 不能就这样一直被卡着呀&#xff0c;研究了一下&#xff0c;还…

【从零开始入门unity游戏开发之——C#篇10】循环结构——while、do-while、for、foreach的使用

文章目录 一、while 循环1、语法&#xff1a;2、示例&#xff1a; 二、 do-while 循环1、语法&#xff1a;2、示例&#xff1a; 三、for 循环1、语法&#xff1a;2、示例&#xff1a; 四、foreach 循环1、语法&#xff1a;2、示例&#xff1a; 五、总结对比六、注意事项七、使用…

【数据分析】数据结构数据内容概述

文章目录 表格结构数据特征数据类别结构化数据表格结构数据层级表格结构的数据类型单元格的格式属性 表格结构数据获取方法从企业后台数据库系统获取后台数据库系统获取数据流程前端操作平台获取从企业外部渠道获取数据 表格结构数据使用方法单元格值的引用方法单元格区域值的引…

控制策略和算法:两者的类型、应用领域

目录 控制策略类型&#xff1a; 控制算法类型&#xff1a; 应用领域&#xff1a; 其他学术知识 控制策略类型&#xff1a; 开环控制&#xff1a; 在没有反馈的情况下&#xff0c;控制信号是根据对系统模型的预测或设定目标生成的。适用于系统动态特性已知且外部干扰较小的情…

Nacos 3.0 考虑升级到 Spring Boot 3 + JDK 17 了!

Nacos 由阿里开源&#xff0c;是 Spring Cloud Alibaba 中的一个重要组件&#xff0c;主要用于发现、配置和管理微服务。 由于 Spring Boot 2 的维护已于近期停止&#xff0c;Nacos 团队考虑升级到 Spring Boot 3 JDK 17&#xff0c;目前正在征求意见和建议。 这其实是一件好…

【笔记】RT-Thread Studio+STM32CubeMX联合开发,使用SPI+DMA驱动WS2812B RGB灯条,实现单独操控任意灯珠。

硬件平台&#xff1a;STM32L431RCT6 软件版本&#xff1a;RT-Thread Studio 2.2.8&#xff0c;STM32CubeMX 6.12.0 RT-Thread版本&#xff1a;4.1.0 言&#xff1a;之前写过一篇WS2812B的教程&#xff0c;但是最近扒出来用发现不能单独点亮或者熄灭特定位置的灯珠&#xff0c;只…

Vue 中实现节点对齐

Vue 如何将两个 Dom 节点进行对对齐&#xff0c;在前端页面中如何快速的对两个节点元素进行对齐操作&#xff0c;最简单的方式就是使用 Postion&#xff1a;Relative 加 Absolute 实现两个元素的相对位置。今天使用 dom-align 库实现节点对齐&#xff0c;实现以下效果&#xff…

计算机网络-HTTP协议

HTTP HTTP是一种不保存状态&#xff0c;即无状态的协议。HTTP协议自身不对请求和响应之间的通信进行保存。为了保存状态因此后面也有一些技术产生比如Cookies技术。 HTTP是通过URI定位网上的资源&#xff0c;理论上将URI可以访问互联网上的任意资源。 如果不是访问特定的资源…

端到端自动驾驶大模型:视觉-语言-动作模型 VLA

模型框架定义、模型快速迭代能力是考查智驾团队出活能力的两个核心指标。在展开讨论Vision-Language-Action Models(VLA)之前&#xff0c;咱们先来讨论端到端自动驾驶大模型设计。 目录 1. 端到端自动驾驶大模型设计 1.1 模型输入设计 1.2 模型输出设计 1.3 实现难点分析 …

NLP 分词技术浅析

一、NLP 分词技术概述 &#xff08;一&#xff09;定义 自然语言处理&#xff08;NLP&#xff09;中的分词技术是将连续的文本序列按照一定的规则切分成有意义的词语的过程。例如&#xff0c;将句子 “我爱自然语言处理” 切分为 “我”、“爱”、“自然语言处理” 或者 “我…