Q52: 如何设计寻路系统？

核心结论

寻路系统不是“选一个 A* 算法”就结束了，它真正要解决的是：

• 如何表示可行走空间
• 如何在动态环境中找到可接受路径
• 如何控制大量单位同时寻路的成本

算法只是其中一环，地图表示、动态障碍、路径平滑和请求调度同样重要。

一、寻路系统真正负责什么

它至少要处理三件事：

• 找到从起点到终点的可行路径
• 让角色沿路径稳定移动
• 在环境变化时重新规划或避让

所以“搜索路径”和“沿路径移动”不是同一件事。

二、先选地图表示方式

常见方式包括：

• 网格
• 导航网格
• Waypoint 图

1. 网格

实现直观，适合规则地图，但节点多时成本高。

2. 导航网格

更适合真实 3D 场景和不规则地形，很多游戏最终都会采用这种方式。

3. Waypoint 图

适合结构相对稳定、路径点明确的场景，但灵活性有限。

寻路体验很大程度上由地图表示方式决定，而不只是算法名字。

三、A* 很常见，但不是全部答案

A* 之所以常用，是因为它在可接受成本下通常能找到较优路径。

但真正落地时还要考虑：

• 启发函数
• 节点规模
• 动态障碍
• 大量并发请求

也就是说，A* 是核心搜索器，不是完整寻路系统。

四、动态障碍比静态地图更难

真实游戏场景里经常有：

• 玩家和怪物互相阻挡
• 临时机关
• 技能生成的障碍区域

这类障碍通常不能每次都全量重烘焙地图。

更常见的做法是：

• 静态地图由导航网格或静态图描述
• 动态障碍通过局部避让、局部重规划或阻塞标记处理

五、大量单位同时寻路时，调度比算法更关键

如果上百上千单位同一时刻都发起完整路径搜索，系统很容易被打爆。

所以工程上常见做法包括：

• 寻路请求排队
• 同路径结果复用
• 远距离分段规划
• 低优先级单位降频更新

这往往比继续优化单次搜索更有效。

六、寻路结果不等于最终移动效果

角色拿到路径后，还需要：

• 路径平滑
• 转向控制
• 局部避让
• 到达判定

否则即使路径理论上正确，角色移动看起来也会很僵硬。

七、服务器和客户端的职责要分开

在线游戏里通常是：

• 服务端负责权威位置和合法路径约束
• 客户端负责表现层平滑和本地显示

不要让客户端自己决定最终可达性和位置结果，否则容易被利用。

八、工程上更稳妥的设计

常见做法是：

• 静态可行走空间提前构建
• 寻路请求统一调度
• 动态障碍用局部避让和局部重算
• 大群体移动做降频和分层处理

这样才能在精度、性能和体验之间取得平衡。

九、常见误区

1. 选了 A* 就等于搞定寻路

不对。地图表示、动态障碍和请求调度同样关键。

2. 所有单位都要实时精确最短路

不现实。很多单位只需要可接受路径，而不是数学意义上的最优路径。

3. 寻路和移动可以混成一个模块

不建议。搜索和运动控制关注点不同。

参考资料

• A*、导航网格和群体移动相关公开资料