NavMesh上的直线探测
奇怪的折线文章的来源是年前关卡测试同学报的一个BUG：某个NPC在两个路点之间走了一条折线，而这两个路点之间明显是可以直线的。剔除掉无关场景数据之后，NPC所走的路径如下所示：
下图是显示Navmesh Polygon后的详细情形：
之所以会选择折线而不是直线，是因为Detour的寻路算法为A*，在每次选择下一个Navmesh Polygon的时候使用的是出Polygon和入Polygon的共享边的中点来做确定Cost和启发式Cost评估。如下所示，梯形右上两边长之和（橙色箭头)大于左下两边长之和(绿色箭头）。
直线探测
做过基于规则格子的A* 寻路的同学回忆一下，在写A*寻路的时候，往往会先做一次直线可达性探测，如果直线可达失败才会继续走A* 算法去寻路潜在的路径。基于规则网格实现的时候，这个直线探测等同于把这条连接[起点,终点]的线段以每格子为一像素，做一次光栅化操作得到经过的格子列表，再分别判断每个格子是否可行走来完成整条线段的是否通达。
所以我们可以给Detour增加一个类似的直线可达性寻路的函数，在A*运行之前，先快速判断起点到终点是否直线可达，快速的解决此问题。但Navmesh Polygon不是规则网格而是凸多边形，所以我们的直线可达性探测也进化为线段和Polygon的相交性测试。实现直线探测后的Detour，如下图所示连接起点和终点的红色线段，分别与自起点始的Navmesh Polygon求交，会得到如填紫色区域的激活Polygon。这些途经的Polygon刚好又都是可行走区域，故自起点至终点是直线可达区域，无需走A*寻路。
世界不是平的
第二部分所述的直线探测往往不能正常工作，其原因是因为我们的模型过于理想化：严格限制起点和终点在同一平面。大部分时候，在XY平面看起来是直线连接的两点，在XZ/YZ平面的呈现是下面这样的曲线。
Navmesh的Polygon数据终究和规则网格不同，Polygon是3D空间的Polygon，而不是平面上的2D多边形，所以我们的直线探测在绝大部分情形下会失败。这也是传统的规则网格在做3D空间寻路较为困难的原因。当然，规则网格并不是不可以扩展到3D空间。 但如果我们把NavMesh 的全部Polygon看作一个整体曲面片一些粘在一起的曲面片集合，利用基础的微分几何知识，我们可以把XZ/YZ平面的这条奇形怪状的曲线看成“曲面上的直线”——测地线。但Polygon曲面参数化、求解测地线的过程复杂繁琐，在这Navmesh这一特定的应用场景下不太适用。
投影到XY平面的直线探测
既然一开始我们观察到的直线是在XY平面的，一个很自然的想法是把线段和Polygon都投影到XY平面去处理，这样我们就不需要去处理空间曲线和凸多边形的求交问题，依旧是直线段和平面多边形的求交。投影到XY平面实现直线探测寻路的结果在我们游戏里可以顺利通过BUG测试，甚至在直线可达的时候，性能相比其使用A*还有一点小小的优势(性能提高近一倍）。 但我们不得不考虑的是，通过测试就可以了吗？这个方案会不会有一些其它的问题？
[*] 问题 I：在多远距离的寻路上优先使用直线可达性测试(对于在客户端做寻路的大世界游戏来说，Navmesh分块加载和分层寻路是基本操作，因此事与文题无关故这儿不展开讨论) ？
[*] 问题 II ：此算法和流程需要兼容哪些边界情形？
[*] 问题 III ：在增加直线可达性测试之后，寻路的整体性能是如何变化的？虽然寻路在直线可达的时候性能有所提高，但如果寻路起点终点不是直线可达的时候，则它会降低寻路的速度。所以我们需要评估的是寻路的整体效率而不是做汇报似的只谈优点无视成本。
[*] 问题 IV ：增加直线可达性测试之后，会在探测的过程中产生一系列与始终点连线相交Polygon List，那么这些Polygon除了用于本次寻路，还有其它用途吗？如果起点到终点是直线不可达时有用吗？即设起点为A点，终点为B点，最大的直线可达点为C点，故AC = A + AB * t (0<= t <= 1) ,当 t < 1时，AC经过的Polygon List对后续的寻路来说是否有额外的利用价值？
[*] 问题 V ：Detour的A*实现会出这个问题根源是什么？可不可以改进原有算法的缺陷从而达到解决这个问题的目的？
直线探测的性能代价
第三个问题是关于直线探测的性能，增加直线探测的额外代价评估如下：
一般来说A*算法和直线探测的关系不是线性，A*在复杂场景或远距离的寻路上探测集增长和体积成正比，而直线探测潜在的探测集增长则只是一维。所以也可以认为增加直线探测所带来的额外代价似乎可以忽略。
通过对直线探测性能代价的分析，同样可以回答第一个问题，即我们始终可以把直线探测当作A*的前置步骤来用。当然这只是理论分析，实际的应用场景的性能测试，需要测试数据来辅助证实。
边界条件处理
边界条件$I$，既然直线探测是在XY平面内的2D探测，那么会不会出现 -> Navmesh Polygon Set非一一对应的情形？这个问题是显然的。如下图所示的旋转楼梯，显然每一级台阶在XY平面上的投影会至少被覆盖2次。
边界条件$II$，Nav Link存在的情形，如下图所示，蓝点和绿点是一对Nav Link，但是它们中间存在黑色的障碍障碍，故使用我们之前的算法判定，则两点间直线不可达。但事实上因为Nav Link的存在，等于是给这两个不可达的点开了一个绿色通道，做到了无视障碍或行走高度从而直线可达。
实际场景中大部分的寻路没有这么极端，Nav Link可能会存在直线探测的某一次步进的路径中，时不时打断我们的探测算法，从而回退到原始的A*算法里去。 关于这两种边界的处理，第一种情形我们需要进化我们的算法，避免把错误的Polygon加入到直线可达的解里；第二种情形，我们需要让我们的探测算法可以“智能”的利用NavLink跳过这些障碍，并优先选择更短的路径。处理这这个边界条件之后的算法描述如下：
NavMesh直线探测法(3)
输入：起点(Start),终点(End)
中间变量: Ps(Start所在多边形)、Pe(End所在多边形)、L0(投影到XY平面的起点指向终点的线段)、
Pc,Pb,Pa均为存储多边形的临时变量span class="p">,Db,Dn为存储距离的临时变量
step 1: 检测起点(Start)和终点(Stop)是否可达，如果均可达，计算Ps,Pe,L0，令Pc = Ps ,执行
step 2，否则返回探测失败
step 2: 置Pb为Null，Pc加入路径列表和Closeset,遍历Pc的所有非NavLink邻接多边形Pa, 如果Pa
等于Pe完成直线探测，返回路径列表. 否则如果投影到XY平面的Pa和L0相交且不在CloseSet中，则Pb = Pa,
计算Pb和Pe的距离Db，退出循环，执行下一步
step 3: 遍历Pc的所有NavLink邻接多边形Pn,如果投影到XY平面的Pn和L0相交,计算Pn到终点的距离Dn,
如果Dn < Db，则Pb = Pn ,Db = Dn ，循环完成后执行下一步
step 4 : 如果Pb无效，则返回探测失败,否则Pc = Pb且执行step 2边界条件I是通过始终约束下一次扫描的Polygon始终是在当前Polygon的邻接多边形中来解决的。
边界条件II则是通过step 3来解决的，在Nav Link存在的Polygon中，可能会存在多个Polygon同时和直线相交且和当前Polygon相连的情形，这时选取和终点距离最近的那个Polygon。
那些失败的直线探测
第四个问题，如果直线探测失败，那么这条线段会途经一些Polygon，那么这些Polygon在后续的寻路过程中可以利用过来吗？如下图所示，橙色线段所经过的Polygon，看起来直接丢弃非常可惜。
稍微想一想可能有哪些障碍类型，可能还会有下图这样的样子，看上去针对性的处理都不太复杂。
但看看真实的Navmesh，则看起来要有个简单通用的处理方式去复用PolygonList就不容易了。
另一些思路
回顾一开始这个BUG产生的原因：回忆一下，之所以A算法会选择绿色路径，本质原因是因为从蓝色点到第一条共享边的连接点选择的是中点，从而导致了后续一连串的错误的Cost估算。
重复一下：Cost评估选择的参考点是Polygon入边和出边的中点。如果我们评估Cost的时候选择的不是每条边的中点，而用的是如下图所示的更恰当的线段，那么无疑就能得到更逼近最优解的结果——蓝色线段的Cost无疑会更小。
抽象一下，如果能找到从S点出发，经过边A、边BestEdge再最终到达E的最短的三条连线段做为A的估计值，这样找出最小Cost的边做为下一个备选节点，就不会出现Detour算法所找出来的折线路径。
又或者简单的修复原算法：当待选边和线段SE的相交则优先选择该边，否则使用原算法计算到终点的启发式代价。
这些算法会带来更优的结果，但同时也带来更大的计算代价。
往长远一点看，参考用于规则网格的JPS和JPS+算法，Navmesh上或许可以做出大幅提高运行效率且更快内存也消耗更低的处理方法来，本文权资为抛砖引玉。 [赞同] 最后三图，想法一致，实现后略有性能15%降低，但会在特定地形(如凹槽绕路等)有问题 这个bug可以说是detour祖传，几乎大一点的mmo用起来都可能碰到了，从poly到直线选取路线的算法决定了。解决方案跟本文类似 虽然普通游戏不行，但是丧尸游戏就刚刚好 也不行，navmesh的边不一定是corridor的法线，有专门的corridor map寻路 很好奇对navmesh做一下height-aware relaxation会是什么效果
页:
[1]