OpenMMO程序化路网：连接定居点的道路网络生成算法指南-开发者社区

OpenMMO程序化路网：连接定居点的道路网络生成算法指南

【免费下载链接】OpenMMO项目地址: https://gitcode.com/GitHub_Trending/open/OpenMMO

OpenMMO 是一款程序化生成的开放世界 MMO，它的路网系统（Road Network）完全由算法自动生成：先用最小生成树（MST）连接各定居点，再通过 A* 寻路在真实地形上铺设道路，最终输出一张覆盖大陆、沿河谷延伸、跨河建桥的道路网络。本文将带你快速理解这套道路网络生成算法的完整流程。

一张图看懂：程序生成的世界路网

上面这张图就是算法的最终产物：细密的棕色线条是自动铺设的道路，它们绕过湖泊、沿海岸延伸、在山间找到穿行路径。整个流程位于 shared/src/worldgen/roads/ 模块，是地形生成管线的第 6 阶段（详见 doc/TERRAIN_GENERATION.md）。

算法全景：四步生成道路网络

步骤	做什么	核心模块
1. 建骨架	Prim 最小生成树 + K 近邻扩展边	graph.rs
2. 铺路线	逐条边做 A* 寻路，代价含坡度/河流惩罚	astar.rs
3. 并平行	融合几乎重叠的两条道路为共享干道	merge.rs
4. 对网格	把道路与河流交叉点吸附到网格轴，方便放桥	snap.rs

这是生成管线早期阶段的地块视图：蓝色是海洋（道路绝不允许进入），绿色是陆地，细线是河流。路网正是在这样的地图上"长大"的。

第一步：用最小生成树给路网搭骨架

compute_roads()在 roads/mod.rs 中启动。它首先调用prim_mst()，用经典的 Prim 算法把所有定居点连成一棵最小生成树——保证"任何两个城镇之间都能走通"，同时总长度最短。

在此基础上还有两个巧思：

K 近邻扩展：每个城镇再连接最近的 K 个邻居，让大城市成为多方向交汇的枢纽，而不是单调的链状结构；
平行叉口重定向：如果某枢纽向几乎相同的方向（夹角小于 20°）伸出两条路，算法会把长的那条改道，让它绕道经过更近的中间城市，形成自然的 Y 型分叉，避免出现"两条平行道路并排铺设"的怪异画面。

第二步：A* 寻路，让道路懂得"绕山涉水"

有了骨架（边）之后，每条边都要在网格上跑一次 A* 寻路，把抽象的"城镇 A → 城镇 B"变成一串真实的地形格子。代价函数由三部分构成（见 astar.rs）：

坡度惩罚：缓坡只加轻微线性代价，超过 10% 坡度后按二次方急剧加价——20% 坡代价约 0.7，30% 坡约 2.5，50% 陡坡高达 10。于是道路会像真实公路一样绕着山脊走等高线，而不是直冲陡坡；
河流惩罚：正交渡河很便宜，沿河平行走很贵（RIVER_PARALLEL_PENALTY高达 50），所以 A* 倾向于找最短路垂直过河；河岸 1 格缓冲区也有小惩罚，让道路与河道保留一点"呼吸距离"；
干道折扣：踩在已铺设道路上的格子代价减半（EXISTING_ROAD_FACTOR = 0.5）。配合"先处理最长的边"的策略，主干线先成形，支路随后会主动汇入既有干道，形成共享路段。

生成后的道路会被写入RoadNetwork结构（roads: Vec<Road>，每条道路是一串格子坐标），随世界种子一起序列化保存——同一个种子，生成的路网完全一致（这在单元测试deterministic_for_same_seed中有专门验证）。

第三步：合并平行道路，消除视觉重复

两条 A* 路径即使走的是"同一条路"，格子序列也可能略有偏差，渲染出来就像双黄线公路。merge.rs 用两轮扫描来修复：

端点锚定合并：两条共享同一端点的道路若前 30 格（约 240 米）几乎重合，就让后铺的那条直接复用先行者的坐标，直到 Y 型分叉点；
内部合并：没有共同端点、但中段并行超过 60 格的道路，把后者中间段"剪接"到前者上。

合并只重写中间格，永远保留道路的首尾——保证城镇入口和渡口位置不漂移。

第四步：网格吸附，让桥梁严丝合缝

桥是预制的网格对齐模型（支持 H / V / 西北-东南 / 东北-西南四种朝向）。如果道路以斜角切过河流，桥根本放不进去。snap.rs 的snap_crossings_to_grid()会找到每个路河交叉点，取河流的局部流向（而不是道路方向）作为基准，把道路与河流各 ±3 格的窗口强制拉直成互相垂直的网格轴。窗口大小特意留足余量，确保后续两轮 Chaikin 平滑后，桥下仍有一段笔直的"落桥带"。

这套设计值得借鉴的 3 个细节

图与路径分离：先在欧氏空间做廉价的 MST/角度筛选，再在昂贵的网格寻路上执行——把"要不要修这条路"和"路怎么修"彻底解耦；
顺序即智能：只靠"长边先寻路 + 干道代价折扣"这一条简单规则，就涌现出"主干—支路"的层级路网结构，不需要任何专门的干线规划逻辑；
确定性优先：从距离比较的平局打破到 HashMap 的排序遍历，处处保证同一种子得到逐格相同的结果，这让程序化生成的世界可以被服务器和客户端复现、被测试锁定。