继续讲哥布林阿呆的故事。上一章它拿到了地图册这一章看它怎么用这本地图册。阿呆被玩家打了一下准备逃回山洞。在开始跑之前它脑子里先冒出两个问题阿呆的问题对应的技术比喻❓ “我现在站在哪块砖上”空间索引查地址根据坐标找门牌号❓ “从这块砖能走到哪些砖”多边形邻接图问路这条街通向哪几条街任何寻路都从这两个问题开始。先回答第一个才知道起点和终点在哪再用第二个A* 才能一块砖一块砖地往外搜。第一部分邻接图把地砖连成一张关系网1. 从一盘散沙开始Unity 的CalculateTriangulation()交出来的数据是这样的vertices: [ (0,0,0), (4,0,0), (4,0,3), (0,0,3), (8,0,0), ... ] indices: [ 0,1,2, 0,2,3, 1,4,2, ... ] ← 每 3 个一组是一个三角形 areas: [ 0, 0, 3, ... ] ← 每个三角形的颜色它只告诉你有哪些砖没有告诉你哪块砖挨着哪块砖。就像给了你一盒拼图碎片没给拼好的样子。我们要做的就是把碎片拼起来变成一张关系网砖的样子 关系网图 ┌────┬──────┬────┐ │ A │ B │ C │ A ── B ── C ├────┼───┬──┴────┤ │ │ │ │ D │ E │ F │ D ── E ── F └────┴───┴────────┘节点 一块砖多边形边 两块砖之间共享的那条边我们叫它“门”Portal2. 怎么知道两块砖挨着——“对暗号”核心思路非常朴素两块砖如果挨着它们一定共用同一条边也就是同一对顶点。想象每块砖都拿着自己的每条边去大厅里对暗号砖 A 喊我有一条边暗号是 (顶点1, 顶点2) 砖 B 喊我也有一条边暗号是 (顶点2, 顶点1) → 暗号对上了顶点相同只是方向相反A 和 B 是邻居用一个字典就能实现每条边只需要查一次整体是 O(边数)// 边的暗号两个顶点编号小的在前方向无关staticlongEdgeKey(inta,intb)ab?((long)a32)|(uint)b:((long)b32)|(uint)a;voidBuildAdjacency(NavPoly[]polys){varwaitingnewDictionarylong,(intpoly,intedge)();for(intp0;ppolys.Length;p){varpolypolys[p];for(inte0;epoly.VertCount;e){intvapoly.Verts[e];intvbpoly.Verts[(e1)%poly.VertCount];longkeyEdgeKey(va,vb);if(waiting.Remove(key,outvarother)){// 暗号对上互相登记为邻居poly.Neighbors[e]other.poly;polys[other.poly].Neighbors[other.edge]p;}else{waiting[key](p,e);// 先在大厅等着}}}// 最后还留在 waiting 里的边 没人对暗号 墙或悬崖}跑完之后每块砖都知道“我的第 0 条边通向 B第 1 条边是墙第 2 条边通向 D……” 这一步离线做完写进文件服务端启动时直接读不用每次重新对暗号。3. 对暗号失败的三种情况现实中有些砖明明挨着却对不上暗号。这正是上一章说的复印机的毛病 情况一同一个点被印了两次砖 A 的角顶点 7 (10.000, 0, 5.000) 砖 B 的角顶点 42 (10.001, 0, 4.999) ← 几乎一样但编号不同暗号(7, x)和(42, x)对不上。阿呆走到这里“前面明明是路怎么过不去”→先焊接顶点按 1 厘米精度把坐标量化相同的合并成一个编号。焊接必须在建邻接之前做。 情况二T 形接缝┌───────────────┐ │ A │ A 的底边(1, 3) 1───────2───────3 B 的上边(1, 2) │ B │ C │ C 的上边(2, 3) └───────┴───────┘ 三个暗号谁也对不上→把长边切开在 A 的底边上插入顶点 2A 的底边变成 (1,2) 和 (2,3)暗号就能对上了。 情况三三块砖抢一条边砖 A桥面 ───────────────── 砖 B桥下 ← 投影重叠有时会共用同一对顶点 砖 C极少见但出现时字典会错误配对。处理方法配对时额外检查高度差或者统计每条边出现的次数超过 2 次就记录告警交给人工检查。✅验证小技巧建完图后统计连通分量。如果一个本该连通的大地图被分成了几十个小岛说明焊接或接缝没处理好。把孤岛涂成红色画出来一眼就能看出问题在哪。4. 门不只是通不通还要记门有多宽邻接关系告诉阿呆A 能通到 B但后面的漏斗算法把路拉直还需要知道这扇门的左门框和右门框在哪砖 B 左门框 ●═══════● 右门框 ← 这就是 Portal 砖 A 阿呆 ↑ 从这里穿过去门框就是那条共享边的两个端点可以在需要时从顶点数据里取不必额外存储。只需要注意一件事左右顺序要按照阿呆前进的方向来定因为漏斗算法依赖它。5. 便利贴也是门Off-Mesh Link手工放的跳板、梯子、传送点在图里就是一种特殊的门普通的门 A ═══ B 共享一条边双向 跳板 P ──▶ Q 两个点可以单向可以隔得很远建图时先找出跳板起点和终点分别落在哪块砖上这正需要下面要讲的空间索引再在两块砖之间加一条特殊边structOffMeshLink{publicVector3Start,End;publicintStartPoly,EndPoly;// 建图时用空间索引查出来publicboolBidirectional;publicbyteArea;// 爬梯子可以设置更高的代价}A* 搜索时砖的邻居既包括普通门也包括从这块砖出发的跳板。6. 跨页的门Tile 之间的缝合大地图切成很多页Tile每一页单独建图页与页之间的边界单独处理第 1 页 │ 第 2 页 ┌─────┐ │ ┌─────┐ │ X │ ←—— 边界 ——→ │ Y │ └─────┘ │ └─────┘做法每页把落在边界上的边单独登记加载相邻页时在边界两侧按坐标匹配允许微小误差连起来。这样可以按需加载和卸载某一页而不用重建整张图。7. 在内存里怎么摆紧凑才快最直观的写法是每块砖一个对象里面放一个Listint存邻居。但几十万块砖就是几十万个小对象对缓存和 GC 都很不友好。更好的方式是把所有数据平铺成几个大数组Polys每块砖固定大小最多 6 条边 [0] 顶点 {3,7,9,-,-,-} 邻居 {1,-1,4,-,-,-} 边数 3 区域 0 标志 0x01 [1] 顶点 {7,12,9,15,-,-} 邻居 {-1,8,0,2,-,-} 边数 4 区域 3 标志 0x01 ... Verts: [x,y,z, x,y,z, ...] Links: [跳板0, 跳板1, ...] 每块砖的跳板起始下标邻居-1表示墙一个特殊值如0x8000标记表示跨页去 Link 表查砖和顶点都用编号而不是指针可以直接写入文件、整块加载只读、连续多个线程同时查询完全不用加锁。第二部分空间索引“我在哪块砖上”1. 为什么需要它服务端收到的永远是坐标怪物现在在(103.5, 12.0, -48.2)玩家点击了(250.1, 8.3, 77.6)而 A* 需要的是砖的编号。最笨的办法是挨个检查每块砖“你包含这个点吗” 一张地图十万块砖每次寻路都要查两次起点和终点再加上射线检测、贴地、随机点……服务器会累死。️ 这就像快递员送件只知道 GPS 坐标然后挨家挨户敲门问是你家吗。我们需要一个邮政编码系统。2. 方案一均匀网格“按区划片”把地图从上往下看XZ 平面划成大小相同的格子每个格子记下和它有交集的砖z ↑ ┌────┬────┬────┬────┐ │ A │A,B │ B │ C │ 格子 (1,0) 记着A、B ├────┼────┼────┼────┤ 格子 (2,1) 记着E、F │ D │D,E │E,F │ F │ └────┴────┴────┴────┘ → x查询时1. 坐标 → 格子编号 col (x - minX) / cellSize ← 一次除法 2. 只检查这个格子里的几块砖建立索引每块砖算出自己的 XZ 包围盒登记到它覆盖的所有格子里。classPolyGrid{floatminX,minZ,cellSize;intcols,rows;int[]cellStart;// 每个格子在 items 中的起始位置CSR 布局int[]items;// 所有格子里的砖编号连续存放publicvoidQuery(floatx,floatz,Listintresult){intc(int)((x-minX)/cellSize);intr(int)((z-minZ)/cellSize);if(c0||r0||ccols||rrows)return;intcellr*colsc;for(inticellStart[cell];icellStart[cell1];i)result.Add(items[i]);}}格子多大合适经验上让每个格子平均落 416 块砖。太大则每格砖太多太小则一块大砖要登记到很多格子里浪费内存。优点缺点实现简单查询极快一次除法砖大小悬殊时不均匀广场一块大砖登记到上百个格子城镇里一个格子挤几十块小砖3. 方案二BV 树“俄罗斯套娃”Detour也就是 Unity 底层用的就是这种。思路是把砖装进盒子盒子再装进更大的盒子[ 整页大盒子 ] / \ [ 西半边 ] [ 东半边 ] / \ / \ [A,B,D] [E,G] [C,F] [H,I,J]查询时从最外层盒子开始点在西半边盒子里吗 是 → 进去 点在 [A,B,D] 盒子里吗 是 → 检查 A、B、D 点在 [E,G] 盒子里吗 否 → 整个跳过 点在东半边盒子里吗 否 → 整个跳过一半的砖瞬间排除每往下一层排除一大片大约 log₂(N) 步就能定位。怎么建递归地把当前所有砖按包围盒中心排序沿最长的轴从中间一刀切成两半直到每个叶子只剩几块砖。优点缺点砖大小不均也没问题天然 3D能区分楼上楼下实现稍复杂查询要沿树往下走几步4. 怎么选场景推荐以平地为主砖大小比较均匀追求简单均匀网格城镇、多层建筑、砖大小差异大BV 树已经切了 Tile两级先用 Tile 坐标定位到页一次除法页内再用 BV 树或小网格实际项目中Tile 定位 页内 BV 树是最常见的组合也和 Detour 一致。5. 找到候选之后到底在不在这块砖上空间索引只是把范围缩小到附近的几块砖最后还要一块一块精确判断。第一步点在凸多边形内吗——“一直在左手边”沿着砖的边界绕一圈逆时针如果目标点始终在每条边的左边它就在砖里面v2 ╱ ╲ ╱ ● ╲ 沿 v0→v1→v2→v0 走一圈 ╱ ╲ ● 始终在左手边 → 在里面 ✅ v0────────v1 ○ 在 v0→v1 的右手边 → 在外面 ❌ ○在左边还是右边用二维叉积判断只是几次乘法// 只看 XZ 平面staticboolPointInConvexPoly(Vector3p,Vector3[]v,intn){for(inti0,jn-1;in;ji){floatcross(v[i].x-v[j].x)*(p.z-v[j].z)-(v[i].z-v[j].z)*(p.x-v[j].x);if(cross0)returnfalse;// 跑到右手边了符号取决于绕向约定}returntrue;}这正是为什么要求砖必须是凸的凸多边形用这个简单判断就够了。第二步在砖上的哪个高度从上往下看点在砖里还要算出砖在这个位置的高度有细节网格上一章的地毯找到点所在的细节三角形用重心坐标插值高度只有三角形直接在三角形内插值。第三步楼上还是楼下阿呆站在桥下头顶就是桥面。从上往下看两块砖都包含这个点═══════════════ 桥面砖 高度 10 阿呆 自己的高度 0.2 ─────────────── 地面砖 高度 0此时要看高度选离阿呆真实高度最近、且差值在允许范围内的那块砖。查询时带一个搜索盒extents比如上下各 2 米、水平各 0.5 米。高度差超出搜索盒的砖直接忽略不然阿呆会突然传送到桥上。第四步哪块都不在——找最近的玩家点击的地方可能是墙里、水里或者导航网格边缘外一点点。这时不能直接说找不到而是在搜索盒范围内的所有候选砖中 找到离目标点最近的那块砖上的最近点 把目标吸附过去。░░░░░░░░░░░│ 墙 ░░ 导航砖 ░░│ ░░░░░░░░░●←──── ✖ 玩家点在墙里 吸附到砖边上最近的点这就是FindNearestPoly的完整含义不只是在哪块砖上而是最近的可走位置在哪。完整流程publicboolFindNearestPoly(Vector3pos,Vector3extents,outintpolyRef,outVector3nearest){candidates.Clear();index.QueryBox(pos-extents,posextents,candidates);// ① 索引缩小范围floatbestDistfloat.MaxValue;polyRef-1;nearestpos;foreach(intpincandidates){if(!filter.Pass(p))continue;// ② 过滤关闭的门等Vector3closestClosestPointOnPoly(p,pos);// ③ 在砖内则返回贴地点否则返回边上最近点floatd(closest-pos).sqrMagnitude;// 实际可给高度差更大权重if(dbestDist){bestDistd;polyRefp;nearestclosest;}}returnpolyRef0;// ④ 最近的那块胜出}第三部分两者合作阿呆的一次完整寻路阿呆位置 (103.5, 12.0, -48.2) 山洞位置 (250.1, 8.3, 77.6) │ │ ▼ 空间索引 ▼ 空间索引 我在砖 #1782 上 山洞在砖 #9031 上 │ │ └──────────────┬────────────────────────┘ ▼ 邻接图 A* 在关系网里搜索1782 → 1790 → 2011 → … → 9031 按区域代价避开水和泥可以走跳板 │ ▼ 每扇门的左右门框 漏斗算法把一串砖拉成几个拐点 │ ▼ 细节网格贴地 最终路点(103.5,12.0,-48.2) → (140.2,11.1,-30.0) → … → (250.1,8.3,77.6)空间索引负责起点和终点邻接图负责中间的路二者缺一不可。除了寻路它们还撑起了其他所有查询查询空间索引邻接图寻路定位起点、终点A* 搜索射线检测能不能直线走过去定位起点沿着门一块一块往前穿碰到墙就停玩家移动校验定位上一帧位置沿表面移动到新位置随机巡逻点定位中心点从中心向外扩散收集范围内的砖贴地定位所在的砖—常见的坑现象原因解决明明连着的路走不过去顶点没焊接或者 T 形接缝建图前焊接、修接缝可视化孤岛怪物从桥下瞬移到桥上搜索盒高度太大或者只按水平距离选砖收紧高度范围选砖时优先考虑高度差玩家点地图边缘提示无法到达只做了点在砖内没做最近点吸附实现完整的FindNearestPoly跳板不起作用跳板端点稍微偏离网格没定位到砖端点定位时使用合理的搜索盒导出时检查失败的跳板寻路偶尔很慢某个格子里堆了上百块砖或索引范围设置过大统计每格的砖数改用 BV 树或调整格子大小不同线程查询偶发错乱把查询的临时状态放进了共享数据数据只读共享临时状态每个线程一份一句话总结邻接图是把一盒拼图碎片拼好记下哪块挨着哪块、门框在哪——这决定了阿呆能不能走过去。空间索引是给每块碎片编上邮政编码让任何坐标都能快速找到所属的碎片——这决定了阿呆多快能出发。