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

​深度优先搜索算法(英语:Depth-First-Search,缩写为DFS)是一种用于遍历或搜索树或图的算法。

寻路地图搭建:

游戏AI实现-寻路地图搭建-CSDN博客

算法过程:遍历方向为从竖直向上沿顺时针方向

1.首先将开始节点放入队列中。注:黄色代表已检测、灰色代表已检测不符合的节点。

------------------>

2.从队列中取出第一个节点,检测是否为目标点。

  如果是则返回目标点,否则将没有检测过的子节点加入到队列中。

按照从遍历方向不停的将子节点加入队列。。。。

3.如果当前不存在未检测的直接子节点,则将父节点加入到队列中,

   重复步骤2,直到找到目标点。

代码实现:

寻路算法类:

public class DFS : FindPathAlgorithm
{public DFS(int[,] mapData, int xCount, int zCount) : base(mapData, xCount, zCount){}public override List<Vector2Int> FindPath(Vector2Int startPos, Vector2Int goalPos){DataNode dataNode = this.DFSFind(startPos, goalPos);if (dataNode == null){Debug.LogError("寻路有误,请检查参数是否正确");return null;}return Utils.GetPath(dataNode);}public DataNode DFSFind(Vector2Int startPos, Vector2Int goalPos){//存储要检测的点Queue<DataNode> frontier = new Queue<DataNode>();//存储已经检测的点List<Vector2Int> reached = new List<Vector2Int>();frontier.Enqueue(new DataNode(startPos, null));reached.Add(startPos);while (frontier.Count > 0){DataNode currentNode = frontier.Dequeue();if (currentNode.pos == goalPos){return new DataNode(goalPos, currentNode.parent);}Vector2Int nextNodePos = GetNextNode(currentNode.pos, reached);//如果没有找到合适的子节点,就将当前节点的父节点加入队列if(nextNodePos.x >= 99999999){frontier.Enqueue(currentNode.parent);}else{frontier.Enqueue(new DataNode(nextNodePos, currentNode));reached.Add(nextNodePos);}}return null;}Vector2Int GetNextNode(Vector2Int current, List<Vector2Int> reached) {for (int i = 0; i < Utils.pointDir.Count; i++){Vector2Int neighbor = current + Utils.pointDir[i];if (this.IsCanAdd(neighbor, reached)){return neighbor;}}return Vector2Int.one * int.MaxValue;}bool IsCanAdd(Vector2Int current, List<Vector2Int> reached){if (reached.Contains(current))return false;if (current.x >= 0 && current.y >= 0 && current.x < xCount && current.y < zCount){//如果是障碍物,则不能被Addif (this.mapData[current.y, current.x] == 1){return false;}return true; }return false;}
}

结果:

参考链接:

DFS Pathfinding | Unity (youtube.com)

深度优先搜索 - 维基百科,自由的百科全书 (wikipedia.org)

Depth First Search (DFS) Explained: Algorithm, Examples, and Code - YouTube

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/492301.html

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

相关文章

Yolov3源码解析

1. 制作数据集 我做的是三目标检测&#xff0c;人狗马目标检测 然后使用精力标注助手对图像进行目标标注。到出为xml文件。 得到这样格式的数据集 1. 1 读取xml文件&#xff0c;求建议框&#xff0c;向量数据库 import os from xml.dom.minidom import parse from kmeans im…

《变形金刚:赛博坦的陨落》游戏启动难题:‘buddha.dll’缺失的七大修复策略

《变形金刚&#xff1a;赛博坦的陨落》游戏启动时提示buddha.dll缺失&#xff1a;原因与解决方案 作为一名软件开发从业者&#xff0c;我在日常工作中经常遇到电脑游戏运行时出现的各种问题&#xff0c;如文件丢失、文件损坏和系统报错等。今天&#xff0c;我们就来探讨一下《…

java全栈day16--Web后端实战(数据库)

一、数据库介绍 二、Mysql安装&#xff08;自行在网上找&#xff0c;教程简单&#xff09; 安装好了进行Mysql连接 连接语法&#xff1a;winr输入cmd&#xff0c;在命令行中再输入mysql -uroot -p密码 方法二&#xff1a;winr输入cmd&#xff0c;在命令行中再输入mysql -uroo…

简单配置,全面保护:HZERO审计服务让安全触手可及

HZERO技术平台&#xff0c;凭借多年企业资源管理实施经验&#xff0c;深入理解企业痛点&#xff0c;为您提供了一套高效易用的审计解决方案。这套方案旨在帮助您轻松应对企业开发中的审计挑战&#xff0c;确保业务流程的合规性和透明度。 接下来&#xff0c;我将为大家详细介绍…

Microi吾码|开源低代码.NET、VUE低代码项目,表单引擎介绍

Microi吾码&#xff5c;开源低代码.NET、VUE低代码项目&#xff0c;表单引擎介绍 一、摘要二、Microi吾码介绍2.1 功能介绍2.2 团队介绍2.3 上线项目案例 三、Microi吾码表单引擎是什么&#xff1f;四、Microi吾码表单引擎功能4.1 模块引擎 - 由表单引擎驱动4.2 流程引擎 - 由表…

Spring Cloud Sleuth 分布式链路追踪入门

您好&#xff0c;我是今夜写代码,今天学习下分布式链路组件Spring Cloud Sleuth。 本文内容 介绍了分布式链路的思想 Sleuth 和 Zipkin 简单集成Demo,并不涉及 Sleuth原理。 为什么要用链路追踪&#xff1f; 微服务架构下&#xff0c;一个复杂的电商应用&#xff0c;完成下…

低级计算机网络知识总结

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

了解 SpringMVC 请求流程

文章目录 1. Spring 基础 - SpringMVC 请求流程1.1 引入1.2 什么是 MVC1.3 什么是 Spring MVC1.4 请求流程核心架构的具体流程步骤补充 1.5 案例**Maven 包引入****业务代码的编写**DaoServiceControllerwebapp 下的 web.xmlspringmvc.xmlJSP 视图 2. Spring 进阶 - Dispatcher…

基于Spring Boot的数码产品抢购系统

一、系统背景与目的 随着电子商务的快速发展&#xff0c;数码产品在线销售已成为主流趋势。然而&#xff0c;传统的数码产品销售方式存在抢购过程繁琐、库存管理混乱、用户体验不佳等问题。为了解决这些问题&#xff0c;基于Spring Boot的数码产品抢购系统应运而生。该系统旨在…

【MambaSR复现】【Windows系统下Mamba环境配置】triton 、causal conv1d和mamba_ssm模块配置保姆教程

注&#xff1a;在此之前确保环境中已经安装packaging模块 pip install packaging若此模块安装过程中出现图下报错&#xff1a;这是由于环境创建时候的权限问题导致的&#xff0c;具体解决方案见我另一篇博文&#xff01; 1.Triton模块安装 注意&#xff1a;必须先安装triton&…

git branch -r(--remotes )显示你本地仓库知道的所有 远程分支 的列表

好的&#xff0c;git branch -r 这个命令用于列出远程分支。让我详细解释一下&#xff1a; 命令&#xff1a; git branch -rdgqdgqdeMac-mini ProductAuthentication % git branch -rorigin/main作用&#xff1a; 这个命令会显示你本地仓库知道的所有 远程分支 的列表。它不…

spring使用rabbitmq当rabbitmq集群节点挂掉 spring rabbitmq怎么保证高可用,rabbitmq网络怎么重新连接

##spring rabbitmq代码示例 Controller代码 import com.alibaba.fastjson.JSONObject; import com.newland.mi.config.RabbitDMMQConfig; import org.springframework.amqp.core.Message; import org.springframework.amqp.core.MessageProperties; import org.springframewo…

【人工智能学习之HDGCN18关键点修改】

【人工智能学习之HDGCN18关键点修改】 训练部分修改部分 训练部分 请参考文章&#xff1a;【人工智能学习之HDGCN训练自己的数据集】 修改部分 参考源码中25关键点的区域划分&#xff0c;我们将18关键点划分为&#xff1a; 头部&#xff1a; 鼻子左眼和左耳右眼和右耳 上肢…

面试题整理3----nc命令的常见用法

面试题整理3----nc命令的常见用法 1. NC是什么2. NC的常用参数2.1 开启指定端口TCP监听(-l小写的L)2.2 测试端口是否能访问(-v)2.3 开启指定端口UDP监听(-u)2.4 端口扫描(-z)2.5 指定超时时间(-w)2.6 指定本地端口号连接(-p)2.7 指定的命令(-e) 1. NC是什么 nc&#xff08;Net…

C语言实现八大排序算法

目录 1.插入排序 1.1 直接插入排序 1.2 希尔排序 2. 选择排序 2.1 直接选择排序 2.2 堆排序 *TopK问题&#xff1a; 3. 交换排序 3.1 冒泡排序 3.2 快速排序 1. Hoare版本 2. 挖坑法 3. 前后指针法 4. 快速排序优化 5. 非递归快速排序 4.归并排序 1.递归式归并…

【昇腾】NPU ID:物理ID、逻辑ID、芯片映射关系

起因&#xff1a; https://www.hiascend.com/document/detail/zh/Atlas%20200I%20A2/23.0.0/re/npu/npusmi_013.html npu-smi info -l查询所有NPU设备&#xff1a; [naienotebook-npu-bd130045-55bbffd786-lr6t8 DCNN]$ npu-smi info -lTotal Count : 1NPU…

使用Python脚本进行编写批量根据源IP进行查询的语句用于态势感知攻击行为的搜索

使用Python脚本进行编写批量根据源IP进行查询的语句 以下根据ip-list集里面的IP地址&#xff08;可以自行扩充&#xff09;&#xff0c;然后采用srcaddress "{ip}" or 的形式进行打印并存储在路径为&#xff1a;桌面的IOC结果.txt --------------------------代码如…

【Qt】信号、槽

目录 一、信号和槽的基本概念 二、connect函数&#xff1a;关联信号和槽 例子&#xff1a; 三、自定义信号和槽 1.自定义槽函数 2.自定义信号函数 例子&#xff1a; 四、带参的信号和槽 例子&#xff1a; 五、Q_OBJECT宏 六、断开信号和槽的连接 例子&#xff1a; …

揭开 Choerodon UI 拖拽功能的神秘面纱

01 引言 系统的交互方式主要由点击、选择等组成。为了提升 HZERO 系统的用户体验、减少部分操作步骤&#xff0c;组件库集成了卓越的拖拽功能&#xff0c;让用户可以更高效流畅的操作系统。 例如&#xff1a;表格支持多行拖拽排序、跨表数据调整、个性化调整列顺序&#xff1…

低代码企业管理的革命:Microi吾码产品深度测评

低代码平台Microi吾码&#xff1a;帮助企业快速构建自定义数据管理与自动化系统 在现代企业的数字化转型过程中&#xff0c;如何快速响应市场变化并高效管理内部数据&#xff0c;已成为各类企业面临的重要挑战。低代码平台作为一种创新的技术解决方案&#xff0c;为企业提供了…