spatial hasing
TIC-80で小さなshoot'em upを作ったのでそのメモ。collision判定のブロードフェーズで、以下のオープンソースのspatial hashを使いました。MIT licenseです。collision detectionのブロードフェーズ
全探索で計算するとそれぞれお互いに衝突判定をとるので、計算量はO(n^2)になります。敵の数が少ない場合は計算できますが、衝突判定を行うもの同士が多くなると、すぐに計算量が大きくなって処理落ちしてしまいます。敵500でも、n^2の計算量だと、250000回の判定になるので、計算量を落とすための工夫が必要です。4分木, BVH, kd-tree などのアプローチがありますが、spatial hashing は仕組も簡単で、実装も軽いです。
Nibiruman:2080での要件
キャラの大きさは最小単位の同一のサイズが大半をしめる。一部ボスと爆発の判定などで少し大きめ判定をとる場合はあり。毎フレームキャラは動くので、位置の更新は毎フレーム行う。キャラの数の制約はだいたい500程度でればうれしい。
entityの登録
2D平面を指定サイズのグリッドに分割します。指定サイズは作成時に指定します。以下だとサイズ10のグリッドになります。
PX_SHA=shash.new(10)
ベースのentityの半径のサイズが3なので、直径の6より少し大きくしています。
ハッシュの値はどのグリッドの場所によって決まり、O(1)で計算されます。entityを登録すると、entityのAABB(軸平行な境界ボックス)が含まれるすべてのグリッドのハッシュ値のマップにentityが登録されます。
self.PX_SHA:add(e, e.aabb0.x, e.aabb0.y, e.aabb_size.x, e.aabb_size.y)
下の図では、playerは、青の矩形に含まれる４っつのグリッドのハッシュ値のテーブルに登録されます。
位置の更新
以下で位置を更新します。
self.PX_SHA:update(e, e.aabb0.x, e.aabb0.y, e.aabb_size.x, e.aabb_size.y)
位置を更新すると、古い位置のハッシュ値のマップからentityが削除され、新しい位置に登録し直されます。
衝突判定
衝突判定をする場合、以下のようにeachのメソッドを呼び出して、指定した、AABBに含まれるentityに対して、衝突判定などを行います。内部でAABB同士の衝突判定が行われ、AABB同士が重なっているものが、引数に渡したfunctionから渡されます。
self.PX_SHA:each(b.aabb0.x, b.aabb0.y, b.radius*2, b.radius*2,
function(o) blt_vs_ene(o,b) end)
end
リスト
Nibiruman:2080 では、衝突判定をとるオブジェクト同士、敵の弾、プレイヤとだけ衝突判定とるもの、の３つのshashを作成して、計算量を減らすようにしています。
ライブラリの利用
shashでシンプルで軽量なspatial hashを使用することができました。TIC-80でLove2Dや別のluaで書かれたものが割とそのまま利用できます。PICO-8だと、luaの標準ライブラリが使えないっぽいので、その他のゲームエンジン向けのluaのコードが利用できるのは、かなりのアドバンテージだと思います。
0 件のコメント:
コメントを投稿