把章节变成可单步观察的过程
分类：算法
先说结论
NavMesh 寻路先在“可行走多边形图”上找到一条走廊，再通过门户和漏斗算法把多边形序列收紧成实际拐点。搜索得到的多边形列表不是角色最终要逐点行走的折线。
四个多边形的路线成本
候选路线 1：P1 -> P2 -> P4，成本 4 + 7 = 11
候选路线 2：P1 -> P3 -> P4，成本 3 + 5 = 8
图搜索选择：P1 -> P3 -> P4接下来漏斗算法还可能把这条三多边形走廊压缩成一个直线路径。若 P3 的门被动态障碍关闭，图连接或局部可行区域必须更新，然后重新搜索；只移动表现上的门模型不会自动改变寻路结果。
NavMesh 解决什么问题
规则网格把空间切成大量格子，而 NavMesh 把“可以行走的连续区域”表示成一组相邻的凸多边形。
它回答的不是：
角色下一帧一定站在哪里？而是：
从起点所在的可行走区域，能否经过一串相邻多边形到达终点所在区域？
如果能，怎样从这条多边形走廊中提取一条可移动的路径？因此要区分三件事：
NavMesh：描述哪里可以走。
路径搜索：选择经过哪些多边形。
移动与避障：让角色沿路径前进，并处理短时间尺度上的变化。NavMesh 不等于完整移动系统。转向、加速度、角色半径、局部避让和碰撞响应通常还需要其他模块参与。
完整事实链
一条典型的 NavMesh 路径请求可以拆成以下链条：
场景几何与导航规则
↓
烘焙或生成可行走多边形
↓
建立多边形之间的邻接关系
↓
把起点与终点映射到 NavMesh
↓
在多边形图上搜索
↓
得到多边形走廊
↓
从走廊门户中提取拐点
↓
角色沿拐点移动
↓
环境变化时验证、局部避让或重新寻路这条链上任何一步失败，都不应该被“返回一条看起来合理的直线”掩盖。
跟着代码做：先在多边形图上找到走廊
先把几何问题缩小成四个多边形节点：
Start --2--> Hall --2--> Door --2--> Goal
\ ↑
--------6--> Balcony --3------数字表示穿过相邻多边形的代价。下面用 .NET 6 的 PriorityQueue 实现一个不带启发函数的最小版本；它等价于在多边形图上运行 Dijkstra，也是理解 A* 走廊搜索的第一步。
using System;
using System.Collections.Generic;
static List<string> FindCorridor(
Dictionary<string, List<(string To, float Cost)>> graph,
string start,
string goal)
{
PriorityQueue<string, float> open = new();
Dictionary<string, float> cost = new() { [start] = 0f };
Dictionary<string, string> parent = new();
open.Enqueue(start, 0f);
while (open.TryDequeue(out string current, out float queuedCost))
{
if (current == goal)
break;
if (queuedCost > cost[current])
continue; // 跳过队列里已经过时的旧记录
foreach ((string To, float Cost) edge in graph[current])
{
float nextCost = cost[current] + edge.Cost;
if (cost.TryGetValue(edge.To, out float oldCost) &&
nextCost >= oldCost)
continue;
cost[edge.To] = nextCost;
parent[edge.To] = current;
open.Enqueue(edge.To, nextCost);
}
}
if (!cost.ContainsKey(goal))
return new List<string>();
List<string> path = new() { goal };
while (path[^1] != start)
path.Add(parent[path[^1]]);
path.Reverse();
return path;
}构造输入并运行：
Dictionary<string, List<(string To, float Cost)>> graph = new()
{
["Start"] = new() { new("Hall", 2), new("Balcony", 6) },
["Hall"] = new() { new("Door", 2) },
["Door"] = new() { new("Goal", 2) },
["Balcony"] = new() { new("Goal", 3) },
["Goal"] = new()
};
List<string> corridor = FindCorridor(graph, "Start", "Goal");
Console.WriteLine(string.Join(" -> ", corridor));输出：
Start -> Hall -> Door -> Goal逐轮观察队列：
取出 Start：发现 Hall 成本 2，Balcony 成本 6
取出 Hall：发现 Door 总成本 4
取出 Door：发现 Goal 总成本 6
取出 Balcony：到 Goal 总成本 9，不优于已有的 6
取出 Goal：搜索结束，沿 parent 反向恢复走廊这时得到的只是多边形 ID 列表，角色还不知道具体该走哪几个世界坐标。
第二步：从多边形走廊得到移动点
相邻多边形共享的一条边叫门户。可以先写一个容易理解、但路径质量一般的版本：取每个门户中点。
using System.Numerics;
static Vector2 Midpoint((Vector2 Left, Vector2 Right) portal) =>
(portal.Left + portal.Right) * 0.5f;
foreach ((Vector2 Left, Vector2 Right) portal in corridorPortals)
movementPoints.Add(Midpoint(portal));假设走廊有两个门户：
门户 1：Left=(2,1)，Right=(2,3) -> 中点=(2,2)
门户 2：Left=(5,0)，Right=(5,4) -> 中点=(5,2)角色可以沿 (2,2) -> (5,2) 移动，因此系统已经跑通。但每道门都走中点可能产生不必要的折线。后面的 Funnel 算法就是在同一组门户上收紧左右边界，只在必须转弯时输出拐点。
学习顺序因此是：
多边形图搜索 -> 得到 corridor
corridor 相邻边 -> 得到 portals
门户中点法 -> 先得到能走的路径
Funnel -> 再把路径拉直
移动组件 -> 最后沿世界坐标移动第三步：让一扇门变成动态阻挡
如果 Door 被锁住，最小处理是让搜索图不再提供这条连接，然后重新搜索：
graph["Hall"].RemoveAll(edge => edge.To == "Door");
List<string> detour = FindCorridor(graph, "Start", "Goal");
Console.WriteLine(string.Join(" -> ", detour));当前示例图中的 Start -> Balcony 仍然存在，所以输出会改为：
Start -> Balcony -> Goal这清楚地区分了两个层次：附近角色短暂挡路时通常只改局部速度；门关闭导致多边形连接失效时，才修改导航拓扑或触发重新寻路。真实 NavMesh 不一定直接修改这个字典，但决策依据相同。
烘焙数据是什么
烘焙是把场景与导航规则转换为导航数据的过程。输入通常可能包括：
可参与导航计算的几何。
不可行走的区域。
坡度、高度差、净空等通行约束。
角色尺寸或对应的导航代理规格。
区域成本与特殊连接。输出通常包含：
可行走凸多边形。
多边形顶点与边。
相邻多边形关系。
区域类型或通行成本。
跨越普通邻接无法表达的特殊连接。不同引擎对烘焙参数、数据分块和增量更新的实现不同。通用事实是：搜索依赖已生成的导航表示；具体参数含义必须以所用系统的文档和数据为准。
为什么常用凸多边形
凸多边形有一个重要性质：
多边形内部任意两点之间的线段仍在多边形内部。这使得在一个多边形内部连接入口和出口相对简单。凹区域可以被拆成多个凸多边形，再通过邻接边连接起来。
多边形图搜索
NavMesh 可以抽象成图：
节点：可行走多边形。
边：两个多边形之间可以通行的共享边或连接。
成本：距离、区域代价或它们的组合。路径搜索常使用 Dijkstra 或 A 星，但搜索对象是多边形图，而不是每一个世界坐标。
教学示例：逐步展开
以下字母和成本都是教学示例：
起点在 A，终点在 F
A -- B -- D -- F
\ |
C--E可视化时可以逐帧展示：
| 步骤 | Open 集 | 已确定节点 | 当前动作 |
|---|---|---|---|
| 0 | A | 无 | 起点映射到 A |
| 1 | B、C | A | 展开 A |
| 2 | C、D、E | A、B | 选择当前估计成本最低者 |
| 3 | D、E | A、B、C | 更新邻居成本与 Parent |
| 4 | E、F | A、B、C、D | F 首次进入候选集 |
| 5 | … | … | 满足搜索终止条件后回溯 |
交互演示不应只显示最后路径，还应允许查看：
每个多边形的 G、H、F。
它由哪个 Parent 到达。
共享边是否可通行。
区域成本如何改变搜索顺序。
起点或终点映射失败发生在哪一步。最小伪代码
function FindPolygonCorridor(startPosition, endPosition):
startPoly = LocateNavigablePolygon(startPosition)
endPoly = LocateNavigablePolygon(endPosition)
if startPoly is missing:
return Failure("起点不在可接受的导航区域")
if endPoly is missing:
return Failure("终点不在可接受的导航区域")
openSet.push(startPoly)
cost[startPoly] = 0
while openSet is not empty:
current = openSet.popLowestEstimatedCost()
if current == endPoly:
return Success(RebuildByParent(current))
for each passable neighbor of current:
nextCost = cost[current] + TraversalCost(current, neighbor)
if neighbor is unseen or nextCost < cost[neighbor]:
cost[neighbor] = nextCost
parent[neighbor] = current
openSet.update(neighbor, nextCost + Heuristic(neighbor, endPoly))
return Failure("起点与终点所在导航区域不连通")这里没有规定 LocateNavigablePolygon 的搜索半径，也没有规定 TraversalCost 的具体权重；这些属于系统规则，不能凭通用算法猜测。
多边形走廊不是最终折线路径
图搜索回溯得到的是：
A → B → D → F它表达“经过哪些区域”，称为多边形走廊。
相邻多边形的共享边可以看作一个门户。若直接连接每个多边形中心，路径常会左右摆动，而且中心点并不一定是最自然的通行位置。
因此还要从门户序列中提取拐点。
门户与漏斗算法
把走廊中的共享边依次展开，可以形成左右边界：
起点
\ 左边界
\ | portal 1 |
\| portal 2 |
| portal 3 | → 终点
右边界漏斗算法的核心直觉是：
从当前漏斗顶点观察后续门户。
不断收紧可见的左右边界。
如果一侧越过另一侧，说明直线已经不能继续穿过走廊。
把相应边界点确定为拐点，再从该点重新展开漏斗。可交互的逐步状态
一个好的逐步演示至少应显示：
当前漏斗顶点 Apex。
当前左边界 Left。
当前右边界 Right。
正在处理的门户。
本次更新是“收紧边界”还是“产生拐点”。
最终拐点与原始多边形中心连线的差异。还应允许暂停在边界交叉的那一步，因为“为什么此时必须产生拐点”是理解漏斗算法的关键。
漏斗算法的边界
漏斗算法优化的是给定走廊内部的路径。它不会主动换到另一条多边形走廊。
如果图搜索阶段选择的走廊代价模型不合适，单靠漏斗算法不能修正全局路线选择。
同时，路径点需要考虑角色的有效通行空间。是否已经在烘焙数据中按代理尺寸收缩边界，取决于具体导航系统，不能假定所有实现都相同。
进阶：动态障碍
动态障碍会带来两个层次的问题：
短暂阻挡：路径拓扑仍然可用，只是当前有人或物挡路。
结构改变：某条通道长期封闭，原来的多边形连接已经不再可通行。它们不应使用同一种处理方式。
局部避让
对于短暂、可绕开的移动障碍，常见思路是保留全局走廊，在移动阶段做局部避让。
优点：
不必因每个短暂交会都重建导航数据。
响应频率可以高于全局寻路。限制：
局部避让可能陷入对峙或局部最优。
它不能证明目标仍然全局可达。
狭窄通道被完全堵死时，继续局部绕行可能没有解。修改导航拓扑
对于真正改变通行性的障碍，可以让对应区域不可通行、更新局部导航数据，或改变相关连接状态，然后重新验证路径。
不同系统可能采用切割、分块重建、动态表面或连接开关等机制。它们是具体实现选择，不应混写成统一的 NavMesh 行为。
何时重新寻路
重新寻路的触发条件必须来自明确规则。通用上可以观察的事实包括：
当前走廊中的后续连接失效。
角色长期无法向下一个路径点取得进展。
目标移动到原终点投影之外。
导航数据版本改变，旧路径需要重新验证。至于“多久算长期”“目标移动多远才重算”都是行为参数，不能从算法名称推导出来。
不可达点
“终点在 NavMesh 上”不等于“终点可达”。
至少要区分：
终点无法映射到导航区域。
起点无法映射到导航区域。
两点都在 NavMesh 上，但属于不连通的区域。
存在拓扑路径，但连接受代理能力或通行规则限制。
搜索因资源限制中止，尚不能证明不存在路径。失败结果应该保留这个差别，方便调用方决定是提示失败、选择其他目标，还是等待导航数据更新。
最近可达点不是天然正确答案
把非法终点替换成“最近 NavMesh 点”是一种产品或行为决策，不是 NavMesh 算法必然规则。
它可能导致角色走向墙的另一侧、悬崖边或与用户意图不同的位置。若系统需要这种替代行为，必须明确：
允许搜索的范围。
距离与区域成本的定义。
是否要求与起点连通。
找不到时怎样暴露原始失败。合法出生点
合法出生点比“点落在某个多边形里”要求更多。
一个可验证流程可以拆成：
1. 候选点是否能映射到允许的导航区域。
2. 候选点周围是否有足够净空容纳代理。
3. 是否与允许活动的导航分区连通。
4. 是否落在禁止出生的区域或语义范围内。
5. 当前是否与动态占用物发生冲突。
6. 从出生点到最低限度的安全目标是否存在有效路径。这些条件分别来自导航、碰撞、玩法语义和运行时占用，不能只用一次“采样到 NavMesh”代替全部验证。
教学示例：出生点状态面板
以下字段只是教学示例，用于展示验证链，不代表固定规则：
候选点：P3
导航投影：成功
区域类型：允许
连通分区：与目标一致
净空检测：通过
动态占用：失败
最终结果：拒绝，并保留“动态占用冲突”原因交互演示可以逐项开关条件，观察同一个候选点为什么从“合法”变为“非法”。
正常、边界与失败情况
正常情况
起终点都能映射到同一连通区域。
图搜索得到多边形走廊。
门户序列有效。
漏斗算法生成有限的拐点。
移动过程中走廊保持可通行。边界情况
起点恰好在多边形边界或多个多边形交界处。
起点与终点位于同一个凸多边形。
门户宽度接近代理所需净空。
走廊包含几何上退化或非常短的门户。
目标持续移动。
多个区域成本相同，存在多条等价路线。边界输入需要稳定的几何容差与确定性规则，但容差的具体值属于实现参数。
失败情况
烘焙数据缺失或版本不匹配。
起点或终点无法定位。
导航图不连通。
特殊连接不允许当前代理使用。
动态障碍使后续走廊失效。
路径点仍存在，但角色因碰撞或控制约束无法通过。失败应携带阶段和原因，而不应统一变成空路径后让调用方猜测。
复杂度与代价
设多边形图有 V 个节点、E 条邻接边。
使用二叉堆优先队列时，图搜索常见复杂度可写为：
O((V + E) log V)实际成本还取决于：
启发函数质量。
区域成本计算。
起终点定位的数据结构。
导航图的切分粒度。
动态更新造成的重建范围。
同时存在的路径请求数量。漏斗算法对走廊中的门户数量 P 通常是线性处理：
O(P)更细的多边形可能让局部表达更准确，但会增加图规模、内存和搜索节点数；更粗的多边形减少节点，却可能难以表达狭窄或复杂区域。这是数据质量与运行成本之间的权衡。
最重要的收获
NavMesh 是可行走空间的多边形表示，不是完整移动系统。
搜索阶段在多边形图上得到走廊。
门户与漏斗算法把走廊变成更直接的拐点路径。
动态障碍要区分短暂局部阻挡与导航拓扑改变。
“在 NavMesh 上”不等于“从起点可达”。
合法出生点必须同时验证导航、净空、连通、语义和运行时占用。
失败原因属于算法输出的一部分，不能用静默替代点掩盖。