1.3 利用栅格数据预计算SDF

SDF记录的是点到障碍物的距离，核心思想即空间换时间；如果动态计算点x的有号距离φ(x)，那么复杂度跟物理碰撞检测的方案没什么区别。因此，我们需要预计算得到整张地图的SDF数据，因为不可能存储地图上所有的点，需要根据障碍精度对地图进行栅格化，比如主流MOBA游戏的5v5地图可以使用256×256的栅格。

首先介绍一种基于栅格的SDF预计算方法。

根据场景障碍生成如图1.2所示的栅格地图，灰色表示阻挡，白色表示可行走区域。使用Meijster算法[1]计算栅格中任意格子到栅格阻挡区中最近格子的距离：

图1.2 栅格地图

从而得到一张栅格地图的SDF数据，如图1.3所示。

图1.3 SDF颜色越深，φ值越小

如果使用2字节表示每个格子的SDF,256×256栅格地图的内存大小为256×256×2=128(KB)。在得到栅格地图的SDF数据后，如何检测角色（图1.3中的圆）与障碍物发生了碰撞呢？发生碰撞后角色又该如何移动呢？