程序员经验分享-hwhale

基于导航网格的A星寻路(Navigation mesh)

2023-05-16

最近花了几个月的时间实现了导航网格寻路和导航网格自动生成。

□导航网格数据结构定义

    由于数据之间有着层级关系，所以采用XML进行定义。
    navmesh基本元素：顶点(Verts)+可走边(Edges)+凸多边形(Polys)

□导航网格寻路

   1.以凸多边形为节点，以可走边为relation，进行A星寻路。

   2.寻路结果使用LOS算法进行路径平滑，其中视线采用Z轴横切面而不是直线来实现。

   3.寻找凸多边形。先使用八叉树进行空间划分，然后根据点跟AABB盒相交进行查找。

□导航网格自动生成

   主要是提供

   1.Cleaner：合并重复的顶点（即焊接顶点）、删除共线情况、删除没有用到的顶点、删除没有的poly（即删除不规范、删除面积过小）、重置顶点ID和Poly ID。

   2.MergingPolys:合并多边形，包含对相同边进行合并和32合并。

   3.PolygonClipping:多边形剪切，地形数据必须是三角网格（若不是，可以使用Triangulate三角化）。输入障碍物后，使用包裹法（Jarvis步进法）进行构造凸多边形，然后再对各个三角网格进行剪切操作。

    4.Triangulate:三角化。

    5.GeneratingEdges:生成边操作。

    6.Deleter：删除指定顶点、删除指定poly、删除指定Edge

    7.BoudingBoxCreater:障碍物的输入可以使用AABB盒，但只对有连接关系的三角网格进行生成包围盒，如一座桥上的两个栅栏，必须为它生成2个AABB盒，而不能只生成一个。

    8、NavMesh：导入、导出、遍历操作等
    9、Poly：遍历操作、顶点删除操作等

 

截图：

1、（未路径平滑）

 

 

2.路径平滑后

 

所花时间：0.412872 ms（跟网格数量有关）

 

参考资料：

1. 焊接顶点,《3d数学基础：图形与游戏开发》14.4.2节

2. 32合并， 《人工智能游戏编程真言》里面有一篇 “4.3 建立接近最优的导航网格”专门介绍如何建立 基于导航网格的3d寻路，4.3.6节。

3. http://www.ai-blog.net/archives/000152.html

4.生成边： http://www.terathon.com/code/edges.php

5.根据点生成三角网格，delaunay算法， http://www.travellermap.com/tmp/delaunay.htm

http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/

6.几何操作：《计算机图形学几何工具算法详解》

7. 。。。。。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

基于导航网格的A星寻路(Navigation mesh) 的相关文章

  • 靶机渗透练习96-hacksudo：Thor

    靶机描述 靶机地址 xff1a https www vulnhub com entry hacksudo thor 733 Description Box created by vishal Waghmare This box should

  • 靶机渗透练习97-hacksudo：ProximaCentauri

    靶机描述 靶机地址 xff1a https www vulnhub com entry hacksudo proximacentauri 709 Description Box created by hacksudo team member

  • 靶机渗透练习98-hacksudo：L.P.E.

    靶机描述 靶机地址 xff1a https www vulnhub com entry hacksudo lpe 698 Description Box created by hacksudo team members mahesh paw

  • 靶机渗透练习99-hacksudo：FOG

    靶机描述 靶机地址 xff1a https www vulnhub com entry hacksudo fog 697 Description This box should be easy This machine was create

  • 通过Python调用OpenMV识别小球获取坐标

    OPenMV介绍 OpenMV是基于Python的嵌入式机器视觉模块 xff0c 目标是成为机器视觉界的 Arduino 它成本低易拓展 xff0c 开发环境友好 xff0c 除了用于图像处理外 xff0c 还可以用Python调用其硬件资

  • 基于HAL库的STM32串口中断接收16进制数据

    最近 xff0c 要弄Lora组网 xff0c 采集温湿度通过网关和ESP8266数据上传服务器 xff0c Lora的库采用hal编写 xff0c 因此要改用Hal库编写程序 ESP8266的串口中断是基于标准库编写的 xff0c 因此

  • 模仿标准库函数，利用UART_IT_RXNE和UART_IT_IDLE两个标志，写了一个hal库串口接收的程序，只用到在中断写

    突然间发现 xff0c 原来的标准库的程序 xff0c 改成hal库 xff0c 把hal库里的一些规则 形式掌握好 xff0c 只需要做一些小的改动即可 这里是串口2的接收中断的代码 xff0c 用串口1实现这个功能 xff0c 修改一下

  • RTK+GPS提高定位精度原理解析（一个小白写给另一个小白系列）

    目录 GPS定位原理回顾 RTK基本概念 RTK组成 RTK传输差分示意 RTK数据链接 坐标转换 RTK应用 后记 我们在上一篇文章导航定位系统的原理解析 xff08 一个小白写给另一个小白 xff09 中跟大家介绍了GPS定位的基本原理

  • 项目管理风险把控：三点估算法

    施工时间划分为乐观时间 最可能时间 悲观时间 乐观时间 也就是工作顺利情况下的时间为a 最可能时间 最可能时间 xff0c 就是完成某道工序的最可能完成时间m 悲观时间 最悲观的时间就是工作进行不利所用时间b 活动历时均值 或估计值 61

  • Git中 fork, clone,branch之前的区别你真的都了解了吗

    一 是什么 fork fork xff0c 英语翻译过来就是叉子 xff0c 动词形式则是分叉 xff0c 如下图 xff0c 从左到右 xff0c 一条直线变成多条直线 转到git仓库中 xff0c fork则可以代表分叉 克隆 出一个

  • 进入计算机专业学习的一些体会和思考以及今后的学习规划

    一 前言 这篇文章 xff0c 我分享了刚刚进入计算机专业学习的一些体会和思考以及今后的学习规划 xff0c 今后计划在CSDN进行学习上的反馈 xff0c 欢迎大家一起交流 xff0c 有大佬看到多多指教 x1f64f 二 体会与思考 在

  • ▲什么是类？类有什么作用？

    目录 一 什么是类 xff1f 二 类与对象是什么关系 xff1f 三 类和结构体有什么区别呢 xff1f 四 如何创建一个类 五 如何创建一个类的对象 1 对象的创建 2 创建对象的初始化 1 默认构造函数 2 普通构造函数 3 复制构造

  • 【STL】vector容器如何使用？

    文章目录 前言vector的理解vector的成员类型vector的创建vector的迭代器vector的容量vector元素访问vector的元素修改 前言 上篇博客简述了string类 xff0c 实际上就是一个用来装字符的容器 xff

  • 2022/4/9-蓝桥杯C++B组题解-G题-积木画

    宽为1 1种 xff1e a 1 61 1 宽为2 2种 xff1e a 2 61 2 宽为3 先排最左边2列 种数a 2 避免重复情况下 xff0c 排最右边1列 钟数1 这个情况种数a 2 1 61 2 先排最左边1列 种数a 1 避免

  • 动态规划算法

    一 前言 动态规划是一种常用的算法 xff0c 在算法领域十分重要 xff0c 但对于新手来说 xff0c 理解起来有一定的挑战性 xff0c 这篇博客将明确步骤来一步一步讲解动态规划到底该如何理解与运用 二 解析动态规划算法 1 特点 把

  • 常见背包问题

    一 前言 若你想学习或正在学习动态规划 xff0c 背包问题一定是你需要了解的一种题型 xff0c 并且大多数人最初都是从背包问题入坑进而打开动态规划这一大门 背包问题分为多种 xff0c 你可以先掌握最常见的主要是三类 xff1a 01背

  • 如何配置ublox ZED-F9P 高精度模块+Ntrip DTU 网络电台(连接千寻/CORS/自建站）实现网络RTK定位

    格林恩德F9P RTK模块 xff0c 集成高精度板卡 ZED F9P 可同时接收GPS 北斗 xff0c GALILEO GLONASS 卫星系统的L1 L2频点 xff0c 结合高精度天线一体化设计 xff0c 体积小 xff0c 重量

  • 快速入手优先队列

    一 理解优先队列 标准模板库 xff08 Standard Template Library STL C 43 43 功能强大 xff0c 为开发者提供了标准模板库 xff0c 其中封装了很多实用的容器 容器可以理解成能够实现很多功能的系统

  • dfs和bfs能解决的问题

    一 理解暴力穷举之dfs和bfs 暴力穷举 暴力穷举是在解决问题中最常用的手段 xff0c 而dfs和bfs算法则是这个手段的两个非常重要的工具 其实 xff0c 最简单的穷举法是直接遍历 xff0c 如数列求和 xff0c 遍历一个数组即

  • C语言中给指定的内存地址赋值（通过指针）

    应用中的实际问题 xff1a 通过I2C接口发送到MCU一个地址数据 xff08 unsigned char AdData xff0c 一个待写入数据 xff08 unsigned char DaData 希望将DaData的值写到MCU内

随机推荐

  • ubuntu 14.04+indigo环境下dashgo d1+lms100运行环境搭建建图

    1 设置用户的串口读取权限 sudo usermod a G dialout your user name your user name替换为实际用户名 2 安装ROS依赖包 sudo sh c 39 echo 34 deb http pa

  • L298N双路驱动直流电机方案（支持PWM+正反转）

    目录 写在前面 xff08 吐槽吐槽 xff09 正文 最后 写在前面 xff08 吐槽吐槽 xff09 我想要驱动两个直流电机 直流电机 xff0c 说白了 xff0c 就是那种小马达 xff0c 小时候玩四驱车时那种没有正负极的马达 x

  • 基于业务测试的增量代码覆盖率实现

    前言 xff1a 本文主要实现的功能是代码增量覆盖率 xff0c 且基于覆盖率已实现 xff0c 可拿到全量覆盖率结果的情况下 xff0c 给出的增量代码覆盖率方法实现 xff0c 虽然各类语言有差别 xff0c 但是实现的基本思路都是一致

  • 测试工程师进阶测试开发工程师

    黑盒测试 xff1a 没有开发基础的测试工程师通常由黑盒测试做起 xff0c 不过根据个人经验 xff0c 这部分工作依然会给我们带来很多经验性的东西 xff0c 比如熟悉浏览器特性 xff0c 熟悉公司业务流程 xff0c 业务知识 xf

  • 轻量级接口自动化测试工具

    相信所有公司在起步自动化的时候做的都是接口自动化 xff0c 为什么呢 xff1f 理由很简单 xff0c 接口自动化复用性强 xff0c 易维护 xff0c 他的产出效率要远远高于UI自动化 xff0c 想想如果你的公司有成百上千的接口

  • JAVA实现HTTPS协议POST请求JSON报文

    HTTPS和HTTP的区别 超文本传输协议HTTP协议被用于在Web浏览器和网站服务器之间传递信息 HTTP协议以明文方式发送内容 xff0c 不提供任何方式的数据加密 xff0c 如果攻击者截取了Web浏览器和网站服务器之间的传输报文 x

  • Jmeter之JAVA Request的应用

    当我们使用Jmeter进行接口测试的时候 xff0c 我们一定会遇到一个问题 xff0c 那就是如果这些接口不是http协议的 xff0c 是经过封装以后的接口 xff0c 用Jmeter该怎么解决呢 xff1f 当你想到这个问题 xff0

  • FreeRTOS例程3-串口中断接收不定长的数据与二值信号量的使用

    FreeRTOS例程3 串口中断接收不定长的数据与二值信号量的使用 知乎 zhihu com

  • 使用airtest实现UI自动化之环境搭建

    1 xff0c 安装python python版本为3 7 1 2 xff0c 安装airtest xff0c pocoui模块 在安装时碰到的问题 xff1a 1 xff09 使用pip命令报错 xff0c 报SSL证书无法识别错误 解决

  • HTTP Digest Authentication在实际应用中的问题

    作者 xff1a 老王 Basic认证实际上是明文传递密码 xff0c 所以 RFC2617里定义了Digest认证以取代它 xff0c 其计算方法如下 xff1a 其中HA1计算方法为 xff1a 如果qop选项的值为auth xff0c

  • 1天精通Apipost--全网最全gRPC调试和智能Mock讲解！

    gRPC 接口调试 grpc 作为一个老程序员 xff0c 最近公司技术架构用到了gPRC xff0c 但国内很少有支持这个的工具 xff0c 大部分都只是支持http 由于我同时也是Apipost骨灰级用户 xff0c 于是就在他们官网的

  • CAN总线波特率的设定——以STM32为例

    波特率的设定 首先是几个名词的含义 xff0c CAN里面1个位的构成如下 注意采样点的位置在PBS1和PBS2的中间 根据这个位时序就可以计算波特率了 最小时间单位 xff08 Tq xff0c Time Quantum xff09 同步

  • 2021电赛备赛心路历程（含代码例程）

    作为一个电子学院学生 xff0c 大二暑假才开始自学单片机知识 xff08 还是因为报名了电赛而不得不去学 xff09 xff0c 深感愧疚 从今年7月至8 4的将近四周时间内哩哩啦啦学了一些基础模块 xff08 其中光是练习点灯和其他基础

  • 20201114-三轴云台storm32 BGC HAKRC调试+

    storm32 BGC HAKRC 2轴云台支持俯仰 xff08 抬头低头 xff09 以及横滚 xff1b 三轴多了一个航向 支持锁头模式 xff0c 拍摄更方便 可以控制俯仰通过接收机或者其他单独PWM通道 可以设置跟随模式或者锁定模式

  • KEIL5中头文件路劲包含问题

    方式1 xff1a 1 Keil中添加头文件相对路劲的方法 在c c 43 43 配置中添加路劲 xff0c 最终是将添加的绝对路径转化为相对路径 xff1b 注意 xff1a 相对路径的当前位置指 uvproj文件所在位置 在C C 43

  • php curl函数应用方法之模拟浏览器

    curl 是使用URL语法的传送文件工具 xff0c 支持FTP FTPS HTTP HTPPS SCP SFTP TFTP TELNET DICT FILE和LDAP curl 支持SSL证书 HTTP POST HTTP PUT FTP

  • WireShark基本抓包数据分析

    WireShark抓包数据分析 xff1a 1 TCP报文格式 源端口 目的端口 xff1a 16位长 标识出远端和本地的端口号 顺序号 xff1a 32位长 表明了发送的数据报的顺序 确认号 xff1a 32位长 希望收到的下一个数据报的

  • VScode下运行调试C++文件

    1 下载vscode 这个可以直接去官网下载 2 下载mingw64 下载mingw64就是下载C 43 43 的编译器g 43 43 和调试器gdb 这个也可以去官网下载 xff0c 下载安装完成后去配置环境变量 我将mingw64安装在

  • c++模板的优点和缺点

    作为C 43 43 语言的新组成部分 xff0c 模板引入了基于通用编程的概念 通用编程是一种无须考虑特定对象的描述和发展算法的方法 xff0c 因此它与具体数据结构无关 但在决定使用C 43 43 模板之前 xff0c 让我们分析一下使用

  • 基于导航网格的A星寻路(Navigation mesh)

    最近花了几个月的时间实现了导航网格寻路和导航网格自动生成 导航网格数据结构定义 由于数据之间有着层级关系 xff0c 所以采用XML进行定义 navmesh基本元素 xff1a 顶点 Verts 43 可走边 Edges 43 凸多边形 P

热门标签