当前位置: 首页 > 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;并将…...

Android OpenGLES2.0开发(九):图片滤镜

“当你改变想法的时候&#xff0c;记得也要改变你的世界。”——诺曼文森特皮尔 Android OpenGLES开发&#xff1a;EGL环境搭建Android OpenGLES2.0开发&#xff08;一&#xff09;&#xff1a;艰难的开始Android OpenGLES2.0开发&#xff08;二&#xff09;&#xff1a;环境搭…...

SQLite Update 语句

SQLite Update 语句 SQLite 的 UPDATE 语句用于更新数据库表中的现有记录。使用 UPDATE 语句&#xff0c;您可以修改一个或多个列的值。本教程将详细介绍如何使用 SQLite UPDATE 语句&#xff0c;包括语法、示例以及一些最佳实践。 语法 SQLite UPDATE 语句的基本语法如下&a…...

Metaploit-永恒之蓝漏洞利用

1&#xff1a;Metaploit介绍   本次测试主要是利用永恒之蓝漏洞对windows7进行控制利用&#xff0c;掌握Metaploit工具的使用&#xff0c;知道永恒之蓝的漏洞利用原理。永恒之蓝是在Windows的SMB服务处理SMB v1请求时发生的漏洞&#xff0c;这个漏洞导致攻击者在目标系统上可…...

机器学习预处理-表格数据的空值处理

机器学习预处理-表格数据的空值处理 机器学习预处理-表格数据的分析与可视化中详细介绍了表格数据的python可视化&#xff0c;可视化能够帮助我们了解数据的构成和分布&#xff0c;是我们进行机器学习的必备步骤。上文中也提及&#xff0c;原始的数据存在部分的缺失&#xff0…...

数据结构_平衡二叉树

结点类 构造函数分为有参和无参&#xff0c;相同点都是初始化树高为1 class Node { public:int data; // 用于输出int val; // 数据域&#xff0c;用于排序int height; // 树高Node* left;Node* right;Node();Node(int v, int d);static int max(int a, int b); };Node::N…...

C++对象的赋值与复制复制构造函数(指针数据成员)

一、对象的赋值 同类对象之间可以相互赋值&#xff0c;对象赋值的一般形式&#xff1a;对象名2 对象名1; 原理是&#xff0c;赋值运算符的重载。仅赋值&#xff0c;因此赋值前&#xff0c;需要先定义并初始化对象2。 对象的赋值针对指对象中所有数据成员的值&#xff1b; 对…...

Coding Caprice - monotonic stack2

42. 接雨水 class Solution { public:int trap(vector<int>& height) {stack<int> sh;int out 0;for(int i0; i<height.size(); i){while(!sh.empty() && height[sh.top()]<height[i]){int bo height[sh.top()];sh.pop();if(sh.empty()){brea…...

Spring Mvc面试题(常见)

1 Spring MVC的执行流程 用户发起请求,请求先被Servlet拦截以后,转发给SpringMVC框架SpringMVC 里面的DispatcherServlet(核心控制器) 接收到请求,并转发给HandlerMappingHandlerMapping负责解析请求,根据请求信息和配置信息找到匹配的Controller类(当这里有配置拦截器,会…...

opencv # Sobel算子、Laplacian算子、Canny边缘检测、findContours、drawContours绘制轮廓、外接矩形

一、Sobel算子 案例图片 cv2.Sobel(src, ddepth, dx, dy, ksize3, scale1, delta0, borderTypeNone) 功能&#xff1a;用于计算图像梯度&#xff08;gradient&#xff09;的函数 参数&#xff1a; src: 输入图像&#xff0c;它应该是灰度图像。 ddepth: 输出图像的所需深度&am…...

Neo4j插入数据逐级提升速度4倍又4倍

语雀版&#xff1a;https://www.yuque.com/xw76/back/dtukgqfkfwg1d6yo 目录 背景介绍初始方案Node()创建事务批量提交记录Node是否存在生成Cypher语句执行数据库参数优化切换成85k个三元组测试建索引&#xff08;很显著&#xff01;&#xff01;&#xff01;&#xff09;MATCH…...

C++特殊类设计(单例模式等)

目录 引言 1.请设计一个类&#xff0c;不能被拷贝 2. 请设计一个类&#xff0c;只能在堆上创建对象 为什么设置实例的方法为静态成员呢 3. 请设计一个类&#xff0c;只能在栈上创建对象 4. 请设计一个类&#xff0c;不能被继承 5. 请设计一个类&#xff0c;只能创建一个对…...

J8学习打卡笔记

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 Inception v1算法实战与解析 导入数据数据预处理划分数据集搭建模型训练模型正式训练结果可视化详细网络结构图个人总结 import os, PIL, random, pathlib imp…...

前端学习-操作元素内容(二十二)

目录 前言 目标 对象.innerText 属性 对象.innerHTML属性 案例 年会抽奖 需求 方法一 方法二 总结 前言 曾经沧海难为水&#xff0c;除却巫山不是云。 目标 能够修改元素的文本更换内容 DOM对象都是根据标签生成的,所以操作标签,本质上就是操作DOM对象&#xff0c;…...

【踩坑】pip离线+在线在虚拟环境中安装指定版本cudnn攻略

pip离线在线在虚拟环境中安装指定版本cudnn攻略 在线安装离线安装Windows环境&#xff1a;Linux环境&#xff1a; 清华源官方帮助文档 https://mirrors.tuna.tsinghua.edu.cn/help/pypi/ 标题的离线的意思是先下载whl文件再安装到虚拟环境&#xff0c;在线的意思是直接在当前虚…...

golang操作sqlite3加速本地结构化数据查询

目录 摘要Sqlite3SQLite 命令SQLite 语法SQLite 数据类型列亲和类型——优先选择机制 SQLite 创建数据库SQLite 附加数据库SQLite 分离数据库 SQLite 创建表SQLite 删除表 SQLite Insert 语句SQLite Select 语句SQLite 运算符SQLite 算术运算符SQLite 比较运算符SQLite 逻辑运算…...

vllm加速(以Qwen2.5-7B-instruction为例)与流式响应

1. vllm介绍 什么是vllm? vLLM 是一个高性能的大型语言模型推理引擎&#xff0c;采用创新的内存管理和执行架构&#xff0c;显著提升了大模型推理的速度和效率。它支持高度并发的请求处理&#xff0c;能够同时服务数千名用户&#xff0c;并且兼容多种深度学习框架&#xff0c;…...

WordPress弹窗公告插件-ts小陈

使用效果 使用后网站所有页面弹出窗口 插件特色功能 设置弹窗公告样式&#xff1a;这款插件可展示弹窗样式公告&#xff0c;用户点击完之后不再弹出&#xff0c;不会频繁打扰用户。可设置弹窗中间的logo图&#xff1a;这款插件针对公告图片进行独立设置&#xff0c;你可以在设…...

【ELK】容器化部署Elasticsearch1.14.3集群【亲测可用】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1. 部署1.1 单节点1.2 新节点加入集群1.3 docker-compose部署集群 1. 部署 按照官网流程进行部署 使用 Docker 安装 Elasticsearch |Elasticsearch 指南 [8.14] |…...

[SAP ABAP] ALV状态栏GUI STATUS的快速创建

使用事务码SE38进入到指定程序&#xff0c;点击"显示对象列表"按钮 鼠标右键&#xff0c;选择"GUI状态" 弹出【创建状态】窗口&#xff0c;填写状态以及短文本描述以后&#xff0c;点击按钮 点击"调整模板"&#xff0c;复制已有程序的状态栏 填…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...