偶看新闻东京超恐怖传说百度云:基于导航网格的A星寻路(Navigation mesh)
来源：百度文库 编辑：偶看新闻 时间：2024/04/28 16:43:57
最近花了几个月的时间实现了导航网格寻路和导航网格自动生成。
□导航网格数据结构定义
由于数据之间有着层级关系，所以采用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. 。。。。。