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中的圓）與障礙物發生了碰撞呢？發生碰撞后角色又該如何移動呢？