第1章 基于SDF的摇杆移动

作者：郑贵荣、叶劲峰

摘要

当前主流的MOBA手游均采用摇杆移动，为了有更好的用户体验，摇杆移动需要解决遇到障碍物后绕障碍物滑行的问题，在此提供一种基于SDF的摇杆移动解决方案。

SDF（Signed Distance Field）即有号距离场，表示空间中点到形状表面的最短距离，一般用正值表示形状外部，用负值表示形状内部。

因为SDF数据的生成较为耗时，因此需要预计算生成。顶视角MOBA游戏只需要做二维SDF计算，为减少数据存储量，先栅格化地图，通过点到多边形（障碍物）的距离离线计算栅格顶点的有号距离，从而生成SDF数据。运行时使用双线性过滤采样可以获得地图任意点的有号距离值，与角色碰撞半径比较判断是否和障碍物发生碰撞，检测过程只需查表和进行插值乘法计算，时间复杂度为O(1)。

SDF的梯度方向代表最大的变化方向，因此可以将梯度算子作为边界法线，当角色与障碍物发生碰撞后可沿着法线垂直方向滑行，同样可以根据梯度方向快速迭代来处理在MOBA游戏中击飞后“卡”在障碍物中的问题。对于瞬间位移（比如闪现）且不能穿越障碍物的需求，可以采用圆盘投射，以有号距离作为迭代步长。对于AI寻路，SDF也可以通过修改探索函数（判断有号距离与碰撞半径的大小）来实现，且可以修改碰撞半径搜索贴近或远离障碍物的路径，打破寻路对称性。

前面讲到的SDF是离线预生成的，那么对于MOBA游戏中动态障碍物的处理，可以使用程序式SDF和CSG运算来实现。不过，SDF在提高效率的同时也存在着存储空间大、较难动态更新（地形发生大的变化）的问题。