当前位置: 首页 > news >正文

游戏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)

相关文章:

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

戴克斯特拉算法&#xff08;英语&#xff1a;Dijkstras algorithm&#xff09;&#xff0c;又称迪杰斯特拉算法、Dijkstra算法&#xff0c;是由荷兰计算机科学家艾兹赫尔戴克斯特拉在1956年发现的算法。 算法过程&#xff1a; 1.首先设置开始节点的成本值为0&#xff0c;并将…...

9 OOM和JVM退出。OOM后JVM一定会退出吗?

首先我们把两个概念讲清楚 OOM是线程在申请堆内存&#xff0c;发现堆内存空间不足时候抛出的异常。 JVM退出的条件如下&#xff1a; java虚拟机在没有守护线程的时候会退出。守护线程是启动JVM的线程&#xff0c;服务于用户线程。 我们简单说下守护线程的功能: 1.日志的记录…...

Linux 端口操作

安装netstat yum -y install net-tools 检测端口占用 netstat -npl | grep "端口" 安装lsof lsof yum -y install lsof 检测端口占用 lsof -i :端口号 安装nc yum -y install nc 查看对方端口是否开放 nc -vz 对方ip 对方端口 安装telnet telnet yum -y in…...

【USB-HID】“自动化键盘“ - 模拟键盘输入

目录 【USB-HID】"自动化键盘" - 模拟键盘输入1. 前言2. 模拟键盘2.1 STM32CubeMX 配置2.2 修改代码配置2.3 发送按键信息 3. 接收主机Setup数据3.1 获取PC下发的数据 4. 总结 【USB-HID】“自动化键盘” - 模拟键盘输入 1. 前言 对于模拟键盘的实现&#xff0c;网…...

基于Spring Boot+Vue 的高校运动会管理系统

目录 1 绪论1.1研究背景1.2 研究意义1.3 相关开发技术简介1.3.1 Vue.js1.3.2 Spring Boot1.3.3 MySQL 2 系统分析2.1 需求分析2.1.1 功能需求2.1.2 非功能需求 2.2 系统可行性分析2.2.1 经济可行性2.2.2 技术可行性2.2.3 操作可行性 3 系统概要设计系统功能描述业务流程分析 4 …...

Linux应用程序中终止进程的几种方法

目录 1、正常退出进程的方法 1.1、exit(int status) 函数 1.2、_exit(int status) 函数 1.3、_Exit(int status) 函数 2、异常退出进程的方法 3、何时使用这些方法&#xff1f; 在 Linux 应用程序中&#xff0c;终止进程的方式有多种&#xff0c;通常取决于进程是否需要进…...

电脑文档损坏:原因剖析和修复方法

在使用电脑的过程中&#xff0c;许多用户可能会遇到文档突然提示损坏、无法打开的情况。这种情况的发生往往让人感到困惑&#xff0c;特别是当并未进行任何明显错误操作时。以下是一些常见的原因以及应对方法。 一、文档损坏的常见原因 1、非人为的异常操作&#xff1a; 在编…...

了解ARM的千兆以太网——RK3588

1. 简介 本文并不重点讲解调试内容&#xff0c;重点了解以太网在ARM设计中的框架以及在设备树以及驱动的一个整体框架。了解作为一个驱动开发人员当拿到一款未开发过的ARM板卡应该怎么去把网卡配置使用起来。 2. 基础知识介绍 在嵌入式ARM中实现以太网的解决方案通常有以下两种…...

【Nginx-4】Nginx负载均衡策略详解

在现代Web应用中&#xff0c;随着用户访问量的增加&#xff0c;单台服务器往往难以承受巨大的流量压力。为了解决这一问题&#xff0c;负载均衡技术应运而生。Nginx作为一款高性能的Web服务器和反向代理服务器&#xff0c;提供了多种负载均衡策略&#xff0c;能够有效地将请求分…...

低级计算机网络知识总结

1 应用层 1.1 HTTP(TCP) 浏览器访问WWW服务器过程&#xff1a;首先进行域名解析&#xff0c;然后通过TCP向服务器发送连接请求 HTTP本身是无连接&#xff0c;无状态的。无状态特性使服务器能够支持大量的并发HTTP请求。实际应用中&#xff0c;通常使用Cookie加数据库跟踪用户…...

linux sysrq的使用举例

在menuconfig中选择m和 *的区别&#xff1a; *: 模块驱动编译到内核中&#xff0c;启动时自动加载 M:标识作为内核模块编译 空格:表示该功能不编译到内核中&#xff0c;即新的内核将不支持该功能。 m&#xff1a;模块会被编译&#xff0c;但是不会被编译到内核中&#xff0c;只…...

数字IC后端设计实现篇之TSMC 12nm TCD cell(Dummy TCD Cell)应该怎么加?

TSMC 12nm A72项目我们需要按照foundary的要求提前在floorplan阶段加好TCD Cell。这个cell是用来做工艺校准的。这个dummy TCD Cell也可以等后续Calibre 插dummy自动插。但咱们项目要求提前在floorplan阶段就先预先规划好位置。 TSCM12nm 1P9M的metal stack结构图如下图所示。…...

Oracle 适配 OpenGauss 数据库差异语法汇总

背景 国产化进程中&#xff0c;需要将某项目的数据库从 Oracle 转为 OpenGauss &#xff0c;项目初期也是规划了适配不同数据库的&#xff0c;MyBatis 配置加载路径设计的是根据数据库类型加载指定文件夹的 xml 文件。 后面由于固定了数据库类型为 Oracle 后&#xff0c;只写…...

【记录】Django解决与VUE跨域问题

1 梗概 这里记录Django与VUE的跨域问题解决方法&#xff0c;主要修改内容是在 Django 中。当然其他的前端项目 Django 也可以这样处理。 2 安装辅助包 pip install django-cors-headers3 配置 settings.py INSTALLED_APPS [ # ... corsheaders, # ... ] 为了响应…...

Yolov10本地部署,torch找不到GPU问题解决

在本地部署跑Yolov10的模型.具体分为以下几步,也是踩了一些坑: 1.YoloV10 代码拉取 2.安装CUDA 1.查看CUDA支持版本 2.下载安装CUDA 3.下载CUDNN 3.创建python虚拟环境 Anaconda下载安装 虚拟环境安装配置 4.运行 1.yoloV10代码拉取 源码地址: GitHub - THU-MIG/yolov10: YOLO…...

el-upload 上传文件 入参格式为form-data格式,入参字段为code、name、type、file(文件)的形式,如何实现?

el-upload 是 Element UI 中用于文件上传的组件。如果你需要上传文件并将其封装为 form-data 格式&#xff0c;并且包含字段如 code、name、type 和 file&#xff0c;你可以通过自定义 before-upload 或 action 进行处理。 1. el-upload 的基本用法 Element UI 的 el-upload …...

VUE组件插槽使用示例,弹窗样式

在Vue.js中&#xff0c;插槽&#xff08;slots&#xff09;是一种非常强大的功能&#xff0c;它允许你在父组件中向子组件传递内容。插槽主要有三种类型&#xff1a;默认插槽、具名插槽和作用域插槽。下面是一些示例来展示如何使用这些插槽。 默认插槽 默认插槽是最简单的插槽…...

ARM嵌入式学习--第八天(PWM)

PWM -PWM介绍 PWM&#xff08;pulse Width Modulation&#xff09;简称脉宽调制&#xff0c;是利用微处理器的数字输出来对模拟电路进行控制的一种非常有效的技术&#xff0c;广泛应用在测量&#xff0c;通信&#xff0c;工控等方面 PWM的频率 是指在1秒钟内&#xff0c;信号从…...

新能源汽车大屏可视化第三次数据存储

任务&#xff1a; 将数据存放到temp.csv 链接&#xff1a; 1.排行页面 https://www.dongchedi.com/sales 2.参数页面 https://www.dongchedi.com/auto/params-carIds-x-9824 完善打印&#xff1a; 1. [{‘series_id’: 5952, ‘series_name’: ‘海鸥’, ‘image’: ‘https://…...

linux 替换yum源镜像

1. 备份源镜像 sudo cp /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.bak 2. 下载国内镜像阿里云 如果没有wget可以用curl 代替 sudo wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo 清华大学 sudo wget -…...

SAP:如何修改已释放的请求

SAP:如何修改已释放的请求 QQ出了一个新功能&#xff0c;把10年前的旧日志推给自己。这个10年前的日志&#xff0c;是用户反映在SE10中把请求释放后发现漏了内容&#xff0c;想修改已释放的请求。经调查写了一个小程序&#xff0c;实现用户的需求。 *&-------------------…...

js的?. 和??和||有什么区别

let a 0; let b null; let c Hello;console.log(a ?? default); // 0 console.log(b ?? default); // "default" console.log(c ?? default); // "Hello"console.log(a || default); // "default" (因为 0 是假值) console.log(b |…...

clickhouse 分布式表创建、增加、更新、删除、查询

创建分布式表 --先创建本地表 设置自动过期时间3天 CREATE TABLE IF NOT EXISTS ck_database.ck_databaseon cluster default(cluster name) (table_id String COMMENT id,item_id String COMMENT 业务id,desc Int64 COMMENT 描述,time DateTime DEFAULT now() COMMENT 数据…...

推送本地仓库到远程git仓库

目录 推送本地仓库到远程git仓库1.1修改本地仓库用户名1.2 push 命令1.3远程分支查看 推送本地仓库到远程git仓库 删除之前的仓库中的所有内容&#xff0c;从新建库&#xff0c;同时创建一个 A.txt 文件 清空原有的远程仓库内容&#xff0c;重新创建一个新的仓库&#xff0c;…...

LSTM长短期记忆网络

LSTM&#xff08;长短期记忆网络&#xff09;数学原理 LSTM&#xff08;Long Short-Term Memory&#xff09;是一种特殊的递归神经网络&#xff08;RNN&#xff09;&#xff0c;解决了标准RNN中存在的梯度消失&#xff08;Vanishing Gradient&#xff09; 和**梯度爆炸&#x…...

ABAP SQL 取日期+时间最新的一条数据

我们在系统对接的时候&#xff0c;外部系统可能会推送多个数据给到我们。 我们 SAP 系统的表数据中日期和时间是作为主键的&#xff0c;那么如果通过 ABAP SQL 取到最新日期的最新时间呢。 解决方案&#xff1a; 方式 1&#xff1a;SELECT MAX 可以通过两个 SELECT MAX 来取…...

SAST静态应用安全测试常见的编码规则

行业优先级难易度标准标准名称数量 军工12易GJB 5369:2005GJB_5369&#xff08;国家军用标准航天型号软件C语言可靠性编程规范&#xff09;138军工行业最早的C语言编码标准&#xff0c;强制性4易GJB 8114:2013GJB_8114&#xff08;国家军用标准C/C语言可靠性编程规范&#xff…...

AI相关专业名词汇总解释

1.SFT Supervised fine-tuning&#xff0c;“有监督微调”意味着使用有标签的数据来调整一个已预训练好的语言模型&#xff08;LLM&#xff09;&#xff0c;使其更适应某一特定任务。通常LLM的预训练是无监督的&#xff0c;但微调过程往往是有监督的。 详解&#xff1a;https:/…...

【C语言】指针数组和数组指针

前言 指针数组和数组指针是C语言中经常混淆的两个概念&#xff0c;虽然他们的名字相似&#xff0c;但其含义却完全不同。 指针数组 指针数组本质是一个数组&#xff0c;特点是数组中的元素均为指针&#xff0c;其定义形式为&#xff1a; 数据类型 *指针名[长度] 例如 int *…...

联邦学习中:公共物品属性的一般定义

在经济学和相关领域中,公共物品属性具有特定的含义,在论文中与联邦学习数据交易等情境相关联时,其意义如下: 公共物品属性的一般定义 非排他性 公共物品一旦被提供,很难或不可能排除其他人使用。例如,路灯照亮了街道,一个人使用路灯照明并不会阻止其他人同时使用,无法…...

前端的Python应用指南(一):快速构建 Web 服务器 - Flask vs Node.js 对比

随着前端开发技术的不断发展&#xff0c;前端开发者的技术栈也在不断扩展。如今&#xff0c;前端开发者不仅要掌握 HTML、CSS、JavaScript&#xff0c;还要掌握后端技术&#xff0c;成为全栈开发者。而在后端技术的选择上&#xff0c;Python 和 Node.js 是两种非常流行的选择。…...

典型案例 | 旧PC新蜕变!东北师范大学依托麒麟信安云“旧物焕新生”

东北师范大学始建于1946年&#xff0c;坐落于吉林省长春市&#xff0c;是中国共产党在东北地区创建的第一所综合性大学。作为国家“双一流”建设高校&#xff0c;学校高度重视教学改革和科技创新&#xff0c;校园信息化建设工作始终走在前列。基于麒麟信安云&#xff0c;东北师…...

【UE5】pmx导入UE5,套动作。(防止“气球人”现象。

参考视频&#xff1a;UE5Animation 16: MMD模型與動作導入 (繁中自動字幕) 问题所在&#xff1a; 做法记录&#xff08;自用&#xff09; 1.导入pmx&#xff0c;删除这两个。 2.转换给blender&#xff0c;清理节点。 3.导出时&#xff0c;内嵌贴图&#xff0c;选“复制”。 …...

ROS+PX4+Gazebo仿真环境配置全流程解析

上一期文章介绍了我们即将发布的仿真平台&#xff0c;并提到后续需要在Ubuntu系统上进行PX4软件在环仿真。本期文章将为大家详细介绍如何配置Ubuntu环境以及安装ROS和PX4仿真环境。具体配置包括&#xff1a;Ubuntu 20.04 ROS Noetic PX4 Python3。 需要注意的是&#xff0c…...

STM32F103单片机HAL库串口通信卡死问题解决方法

在上篇文章 STM32F103单片机使用STM32CubeMX创建IAR串口工程 中分享了使用cubeMX直接生成串口代码的方法&#xff0c;在测试的过程中无意间发现&#xff0c;串口会出现卡死的问题。 当串口一次性发送十几个数据的时候&#xff0c;串口感觉像卡死了一样&#xff0c;不再接收数据…...

基于微信小程序的电影院订票选座系统ssm+论文源码调试讲解

第2章 开发环境与技术 本章节对开发基于微信小程序的电影院订票选座系统需要搭建的开发环境&#xff0c;还有基于微信小程序的电影院订票选座系统开发中使用的编程技术等进行阐述。 2.1 Java语言 Java语言是当今为止依然在编程语言行业具有生命力的常青树之一。Java语言最原始…...

解决新安装CentOS 7系统mirrorlist.centos.org can‘t resolve问题

原因 mirrorlist.centos.org yum源用不了 解决办法就是 # cd /etc/yum.repos.d/ # mv CentOS-Base.repo CentOS-Base.repo_bak # vim CentOS-Base.repoCentOS系统操作 # mv /etc/yum.repos.d/*.repo /etc/yum.repos.d/*.repo_bak # curl -o /etc/yum.repos.d/CentOS-Linux-Ba…...

分布式系统架构3:服务容错

这是小卷对分布式系统架构学习的第3篇文章&#xff0c;虽然知道大家都不喜欢看纯技术文章&#xff0c;写了也没多少阅读量&#xff0c;但是个人要成长的话&#xff0c;还是需要往深一点的技术上去探索的 1.为什么需要容错 分布式系统的本质是不可靠的&#xff0c;一个大的服务…...

鸿蒙项目云捐助第十四讲云函数的初步使用

鸿蒙项目云捐助第十四讲云函数的初步使用 在开发项目的过程中&#xff0c;云端充分利用已成为一种驱势。云监控&#xff0c;云运维&#xff0c;云开发&#xff0c;云办公等等软件层出不穷&#xff0c;本地软件云端化也成为一种潮流。在这股大潮中&#xff0c;华为云也是独树一…...

【5G】5G的主要架构选项

最初&#xff0c;在3GPP讨论中考虑了所有可能的聚合和核心网络组合&#xff0c;共有八个架构选项。以下重点介绍option2、3、4和7。 1. 独立组网 (Standalone, SA) 架构选项 2 &#xff1a;Standalone architecture with 5G-core 特点&#xff1a; 5G核心网&#xff08;5GC, …...

【Laravel】端口问题导致菜单打不开

以下是修改 Laravel 应用程序的端口配置&#xff0c; 修改环境变量 APP_URL 来实现 app/Providers/AppServiceProvider.php <?phpnamespace App\Providers;use Illuminate\Events\Dispatcher; use Illuminate\Support\ServiceProvider; use Illuminate\Support\Facades\URL…...

网络安全等级保护系统定级流程与示例

一、定级流程 安全保护等级初步确定为第二级及以上的等级保护对象&#xff0c;其运营使用单位应当依据《网络安全等级保护定级指南》进行初步定级、专家评审、主管部门审批、公安机关备案审查&#xff0c;最终确定其安全保护等级。 二、定级方法 等级保护对象的级别由两个定级…...

项目练习:若依-ruoyi系统的部署与运行(前后端分离版)

文章目录 一、我的环境二、代码下载三、数据库配置四、项目配置文件修改五、启动运行六、验证 一、我的环境 jdk&#xff1a;8 MySQL&#xff1a;5.7 Redis&#xff1a; nodejs&#xff1a;v16.13.2 npm&#xff1a;8.1.2 vue&#xff1a;5.0.8 开发工具 idea Navicat for MyS…...

【UE5 C++课程系列笔记】10——动态单播/多播的基本使用

目录 概念 申明动态委托 一、DECLARE_DYNAMIC_DELEGATE 二、DECLARE_DYNAMIC_MULTICAST_DELEGATE 绑定动态委托 一、BindDynamic 二、AddDynamic 三、RemoveDynamic 执行动态委托 ​一、Execute 二、ExecuteIfBound 三、IsBound 四、Broadcast 动态单播使用示…...

Netcat:网络中的瑞士军刀

免责声明&#xff1a;使用本教程或工具&#xff0c;用户必须遵守所有适用的法律和法规&#xff0c;并且用户应自行承担所有风险和责任。 文章目录 一、引言二、简述三、Netcat功能&#xff1f;四、参数选项五、Netcat 的常见功能六、高级用法多连接处理创建简单的代理 七、Netc…...

清理C盘小记

突然C盘就爆满了&#xff0c;想当初还是给他预留了120G的空间&#xff0c;感觉到现在也不够用了&#xff0c;担心出现死机的情况就赶紧进行了清理。有一说一&#xff0c;清理回收站是真的有用。 参考&#xff1a;C盘清理指南&#xff0c;清理出30G起&#xff0c;超详细总结&am…...

Qt WORD/PDF(四)使用 QAxObject 对 Word 替换(QWidget)

关于QT Widget 其它文章请点击这里: QT Widget 国际站点 GitHub: https://github.com/chenchuhan 国内站点 Gitee : https://gitee.com/chuck_chee 姊妹篇: Qt WORD/PDF&#xff08;一&#xff09;使用 QtPdfium库实现 PDF 操作 Qt WORD/PDF&#xff08;二…...

软件工程 设计的复杂性

复杂性代表事件或事物的状态&#xff0c;它们具有多个相互关联的链接和高度复杂的结构。在软件编程中&#xff0c;随着软件设计的实现&#xff0c;元素的数量以及它们之间的相互联系逐渐变得庞大&#xff0c;一下子变得难以理解。 如果不使用复杂性指标和度量&#xff0c;软件…...

《解决两道有趣的编程问题:交替数字和与简单回文》

在编程的世界里&#xff0c;算法和逻辑的挑战无处不在。今天&#xff0c;我们将用 Python 来解决两道有趣的编程问题&#xff0c;分别是计算交替数字和以及生成简单回文。 一、交替数字和&#xff08;Alternating Sum of Numbers&#xff09; 1. 问题描述 给定一系列整数&am…...

C语言(结构体练习)

设计一个结构体,存放一个学员信息并显示&#xff0c;存放两个学员信息&#xff0c;算他们的平均分。 #include <stdio.h> #include <string.h>// 定义结构体 typedef struct {char name[50];float score; } Student;// 函数声明 void display(Student student); f…...