第1章 基于SDF的搖桿移動

作者：鄭貴榮、葉勁峰

摘要

當前主流的MOBA手游均采用搖桿移動，為了有更好的用戶體驗，搖桿移動需要解決遇到障礙物后繞障礙物滑行的問題，在此提供一種基于SDF的搖桿移動解決方案。

SDF（Signed Distance Field）即有號距離場，表示空間中點到形狀表面的最短距離，一般用正值表示形狀外部，用負值表示形狀內(nèi)部。

因為SDF數(shù)據(jù)的生成較為耗時，因此需要預計算生成。頂視角MOBA游戲只需要做二維SDF計算，為減少數(shù)據(jù)存儲量，先柵格化地圖，通過點到多邊形（障礙物）的距離離線計算柵格頂點的有號距離，從而生成SDF數(shù)據(jù)。運行時使用雙線性過濾采樣可以獲得地圖任意點的有號距離值，與角色碰撞半徑比較判斷是否和障礙物發(fā)生碰撞，檢測過程只需查表和進行插值乘法計算，時間復雜度為O(1)。

SDF的梯度方向代表最大的變化方向，因此可以將梯度算子作為邊界法線，當角色與障礙物發(fā)生碰撞后可沿著法線垂直方向滑行，同樣可以根據(jù)梯度方向快速迭代來處理在MOBA游戲中擊飛后“卡”在障礙物中的問題。對于瞬間位移（比如閃現(xiàn)）且不能穿越障礙物的需求，可以采用圓盤投射，以有號距離作為迭代步長。對于AI尋路，SDF也可以通過修改探索函數(shù)（判斷有號距離與碰撞半徑的大小）來實現(xiàn)，且可以修改碰撞半徑搜索貼近或遠離障礙物的路徑，打破尋路對稱性。

前面講到的SDF是離線預生成的，那么對于MOBA游戲中動態(tài)障礙物的處理，可以使用程序式SDF和CSG運算來實現(xiàn)。不過，SDF在提高效率的同時也存在著存儲空間大、較難動態(tài)更新（地形發(fā)生大的變化）的問題。