基于导航网格的A星寻路(Navigation mesh)
Posted on 2010-09-26 13:00 Zhiyett 阅读(7024) 评论(14) 编辑 收藏
最近花了几个月的时间实现了导航网格寻路和导航网格自动生成。
□导航网格数据结构定义
由于数据之间有着层级关系,所以采用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. 焊接顶点,《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. 。。。。。
分享到:
相关推荐
Navigationmesh导航网格寻路实现细节
谷歌的开源导航网格寻路算法源码,用于游戏寻路非常合适。
sudo apt install ros-melodic-mesh-navigation 从源安装可以使用rosdep安装所有依赖项rosdep install mesh_navigation 作为显式依赖项,我们指的是以下由我们开发的ROS程序包: 将pluto_robot软件包用于
unity 2D网格寻路,Navigation2D,插件,烘焙,2D网格寻路
它使用A star和Funnel算法计算导航网格上的路径。 用法 将npm包到您的项目中: npm install babylon-navigation-mesh --save 或克隆: git clone git@github.com:wanadev/babylon-navigation-mesh.git npm ...
易语言A_寻路源码,A_寻路,初始化地图,分析地图,自动寻路
This paper studies the effect of using local updates to repair only the affected regions of a navigation mesh in response to a change in the environment. The techniques are inspired by incremental ...
#导航网格 你好。 ## Mesh数据对象Mesh数据对象由四部分组成。 boundary-代表三角形的数组的数组。 内部包含一个具有点索引的数组,该索引代表哪些边是墙。 邻居-邻居的三角形索引数组 points- [x, y]的数组 ...
unity2D寻路Navigation2D (Pathfinding for 2D Games) V1.27 要求Unity 2017.4.1 或更高版本。 Navigation2D uses Unity's built-in Navigation system to make 2D pathfinding possible without any axis ...
底部导航栏控件BottomNavigationView的使用和修改样式 效果:http://blog.csdn.net/qq_37902949/article/details/78528787
上冯UnrealEngine的3D导航插件引擎版本:Master经过4.25测试。 至少应向后兼容4.20,请参阅先前快照的分支,但请注意,功能并未向后移植。 请查看以获取更多信息
Android导航 - Navigation
介绍如何为机器人整合导航包,实现有效控制和自主导航等功能 目录: ROS 与 navigation 教程-目录 ROS 与 navigation 教程-设置机器人使用 TF ROS 与 navigation 教程-基本导航调试指南 ROS 与 ...
ndoid实现顶部导航栏和底部导航滑动隐藏(BottomNavigationView,CoordinatorLayout)
如何设计WEB导航Designing.Web.Navigation
航空导航 Air Navigation Pro v1.0.7 当前版本:1.0.7 软件语言:非中文 软件类别:GPS应用 软件大小:38.62 MB 适用固件:2.3及更高固件 内置广告:没有广告 适用平台:Android 资费提示:已付费版 空中导航是一...
导航网格生成器
EV3-Grid-Navigation 用于网格导航和路径规划的 EV3 项目 ==================== 使用 lejos 库编写的 EV3 项目。 该机器人有 2 个颜色传感器和一个超声波传感器。 机器人从笔记本电脑上运行的 GUI 程序接收命令,...
Navigation 导航菜单 适合初学者 Navigation 导航菜单
导航 基于OSM数据和寻路算法的实时导航 OSM下载网址