路径跟随
全库目录221
本文目录10
搜索给出相邻多边形走廊，角色还需要转向点与速度计划。本文沿门户、漏斗、转角和制动生成路线，并检查路线失效与实际进度。身体半径已由NavMesh烘焙侵蚀；目标和查询采用见导航目标投影与导航动作交接。
路线几何与速度规划
路径走廊与漏斗
在 NavMesh 上搜索得到的通常是一串相邻多边形，也叫走廊，不是最终转向点。相邻多边形的公共边形成门户边。漏斗算法从起点维护左右两条边界，当漏斗交叉时输出一个拐点，再从该点重新展开。
漏斗的三个要素是：apex 为已确认的最近拐点，左右边界为尚未确认的候选射线。每加入一个门户边端点，用二维叉积符号判断它落在左右边界内侧还是外侧：在内侧只收缩对应边界，越过对侧边界则漏斗交叉，此时对侧端点成为新拐点输出，apex 移到该点并重新展开。全部判定都是叉积符号，不需要归一化和除法。最常见的实现错误是门户边方向不统一：左右端点的判定依赖公共边按同一行进方向排序，生成走廊时必须先统一。
漏斗能把沿多边形中心的折线路径改成走廊内的短路径。结果仍要考虑角色转弯半径、速度和动画，不能让大型角色瞬间贴墙折返。车辆更适合加入曲率约束或使用专门的运动规划。
漏斗的索引与转角提交
二维叉积固定为cross(a,b)=a.x*b.y-a.y*b.x，门户左右按从起点向终点的行进方向排列。保存apex、left、right三个位置及各自门户索引，初始三者都是起点；末尾追加左右均为终点的退化门户。处理新右端点r时，若cross(right-apex,r-apex)>=0，就尝试缩紧右边；right与apex重合，或cross(left-apex,r-apex)<=0时可令right=r，否则它越过左边界，输出旧left作为拐点，将apex移到left，左右同时重置到apex，并从left原索引之后重新遍历。处理新左端点l时采用对称判定：cross(left-apex,l-apex)<=0才尝试缩紧，若同时cross(right-apex,l-apex)<0则输出right。
这里必须回退遍历索引：一旦拐点改变，之前相对旧apex没有收紧边界的门户，可能限制从新apex出发的射线。仅更新apex却继续处理尚未见过的门户，会跳过这些约束。顶点相等与叉积近零使用几何尺度对应的容差，共线射线方向相同时保存当前门户的新端点及其索引；最终每段都按门户顺序复查。漏斗保证的是给定走廊内路径，搜索选择的走廊本身未必包含全局欧氏最短路径。
将守卫面前的走廊投影到水平平面，可以用两个门户检查边界变化。取起点(0,0)，两个门户的左右端点分别为(1,1)/(1,−1)、(2,3)/(2,2)，观察行进平面中的有向面积。第一门户给出斜率区间[−1,1]，第二门户需要[1,1.5]，可行射线只剩斜率1。若第二门户再向上移，使其区间为[1.5,2]，两区间无交集，路径必须在前一门户的上端(1,1)转弯，重新以此为顶点构造漏斗。端点次序反转会交换叉积符号，把收缩误当成越界。
折点、圆弧与速度上限
漏斗给出的折线没有时间信息。角色以有限加速度运动，无法在一个非零速度折点瞬间改变方向。跟随器先把几何路线变成带速度上限的路线，再交给局部避障；前视距离沿这条路线累计，不能直接瞄准凹角后面的点。
对允许原地转向的角色，折点采用停转方案：折点与终点速度上限设为零，直线段上限取最大行走速度。距离下一停止点还有d、减速度上限为aBrake时，连续时间的允许速度为sqrt(2*aBrake*d)。离散控制还需保留一个反应步长dt，解v*dt+v²/(2*aBrake)<=d得到vLimit=sqrt((aBrake*dt)²+2*aBrake*d)-aBrake*dt。例如速度4米/秒、减速度2米/秒²、dt=0.1秒，至少提前4.4米开始制动；到折点前0.5米才切换前视方向已经太迟。
折点处只有实际距离与速度都进入容差才切换下一线段。朝向单独按最大角速度转到新切向；若动画要求身体先转再走，就在朝向误差进入阈值后恢复前进。这里停转覆盖狭窄直角和空间不足的情况，宽走廊还可以保持连续运动。
连续转弯用与相邻线段相切的圆弧替代折点。转向角theta位于(0,π)，选半径R后，两侧切点距原折点dTrim=R*tan(theta/2)；两相邻线段必须有足够长度，圆弧全段也必须位于经过角色半径侵蚀的走廊。检查时求圆弧与多边形边的全部交点，在按角度排序的交点间取中点判断连续覆盖；仅检查切点在内部不足以排除圆弧穿墙。失败就缩小R并重验，达到最小允许半径仍失败时采用停转；有最小转弯半径的车辆则重新做运动规划，不能原地转向。
相邻转角还会共同占用中间直线。对每条连接两个折点的线段，要求两端的dTrim之和不超过该段长度；例如线段长1米、两端各裁去0.7米，单独看每个转角都放得下，组合后却重叠0.4米。按路径顺序构造候选圆弧后，对所有共享线段同时检查；发现重叠就按同一比例缩小这两端半径，重新检查圆弧覆盖与其他共享线段，直到全部成立。某端达到角色允许的最小半径仍无法满足时，该端采用停转并重新生成速度表；车辆进入运动规划失败分支。速度表使用裁剪后的直线长度和圆弧长度，才能把几何路径真正接到制动计算。
圆弧的法向加速度为v²/R，所以弧上速度上限为sqrt(aLateral*R)。若共用总加速度上限aMax，纵向预算还要满足abs(aTangential)<=sqrt(aMax²-(v²/R)²)；先预留独立的纵横预算并使平方和不超过aMax，便于形成可复算速度表。沿各段从终点反向传播v_i<=sqrt(v_next²+2*aBrake*segmentLength)，再正向传播加速限制。近距离连续弯不能各自按最高速度进入，否则前一个弯的出口没有足够距离为后一个弯制动。
跟随时在路线投影点之后按弧长取目标，首选速度方向沿当前可见目标，大小不超过当前速度表与剩余停止距离限制。当前实际速度若已超过允许值，立即最大制动并记录不可及时停车，交给控制器处理实际碰撞；不把超限速度直接改小。速度表是无动态障碍时的计划，局部避障继续限制当步可达速度，导航边界与坡面交接限制走廊内的实际轨迹。
到达与阻塞反馈
终点和停转点都使用前述停止距离限制，动态避障可以暂时改变首选方向，因此到达状态由实际位移反馈判定。输出运动请求时同时保存路线版本、当前门户、目标折点、选定速度以及本步是否存在可行解，控制器返回实际位置、位移和碰撞原因。
走廊版本与可执行性
采用一份有效走廊以后，每一步跟随继续核对路线读取集中的门、连接和瓦片。门关闭或地块重建可能使下一多边形失效，跟随器停止推进该段，保留实际位置并重新寻路。仅区域代价变化时，本例也重新查询，但已安全处于当前多边形中的控制器仍可执行制动。寻路返回部分路径时，终点状态传给行为层，角色抵达不可达边缘只报告部分终点。
例如守卫接近窄门时门突然关闭，旧走廊失效，但守卫仍有惯性。停转或圆弧速度表给出计划制动位置，走廊半平面限制仍有效区域中的本步位移，碰撞系统处理门关闭后的实际接触。控制器在取消阶段继续制动；决策层的路线标签失效不会直接把实际速度置零。
导航验收按同一角色半径测试完整路径段。仅抽查拐点位于多边形内，不能证明连接两点的线段始终位于走廊内；穿过凹形走廊的捷径可能漏过墙体。检查线段与门户顺序及连续扫掠，再运行角色跟随确认动态可达。
验证方法
用两个门户的斜率区间复算漏斗转角，再检查每段线与全部门户的顺序及走廊连续覆盖。共享直线长1米、相邻圆角各裁0.7米时，联合缩小后再验覆盖；速度4米/秒、减速度2米/秒²和0.1秒反应步应预留4.4米。
实现与证据
门户索引与圆弧、制动关系按正文数例推演。漏斗原算法见作者资料；尚未运行漏斗与完整路径跟随，图搜索算法验证按其主归属解释。
相关主题
参考资料
- Mononen：Simple Stupid Funnel Algorithm：原作者门户漏斗算法。