シューティングゲームにおける弾の空間分割 - 当たり判定

シューティング作成スレより.

二次元のシューティングゲームでは実際どれほど効果があるかは微妙なところだけど,三次元ではよく出てくる話なのでとっかかりとして知っておいても良いのかもしれない.
シューティングゲーム(アクション,格闘ゲームなどでも)では毎フレーム(1/60秒ごと)に敵や敵が撃った弾との当たり判定をしなければいけないんだけど,弾幕系のシューティングゲームでは1000発以上の弾が出現することもあるため,毎回すべての弾との判定を行うのはちょっと大変.しかも,自機が画面下端にいるのに上端付近にある弾と当たり判定を行うのも無駄っぽい.

当たり判定はすごく簡単で,下のように当たり判定として設定した赤い矩形(四角形)同士が重なるかどうかを判定していけば良い.当たってないのに当たったと判定されるとプレイヤーはイラっとするので基本的に表示するアイコンよりも判定の矩形は小さくする.

これを弾の数分繰り返せばいいんだけど,上の書いたとおり遠くの弾まで計算しなくてもいいんじゃね?と思うはず.でも,弾が自機から離れた遠くにあるのか近くにあるのかは結局その弾をチェックしないとわからないんじゃない?と思うはず.僕も昔思ってた.*1

自機もそうだけど,弾にはみんなX座標とY座標がセットになって与えられている.そして,弾はたいてい何かしらの配列に保存されているのでC言語風に書けば次のようにして当たり判定がチェックできる.

int i;
for(i=0; i<bullet_length; i++){
  if(hit_test(my_x, my_y, bullet[i].x, bullet[i].y)){
    //i番目の弾と接触
  }
}

これだけの情報しか無い場合は当然,上のようにチェックするしかないんだけど,あらかじめ保持しておく情報をもう少し増やしてやると無駄な当たり判定をしなくてすむ.
簡単に書くと「空間分割」の名前の通り,画面を任意の数に分割しておいて,各領域ごとにその領域の中にある弾の情報を保持しておく.そうすると,自分がいる領域にある弾とだけ当たり判定すればいいので当たり判定の回数が激減する.

各領域にいる弾の情報はどうやって管理するかというと,まずすべての弾はある一つの配列に保存されているとする.これに加えて,各領域と同じ数の配列を用意してやる.

BulletList bullets = {弾1, 弾2, 弾3, 弾4, 弾5, 弾6};
BulletList space[16];

今回は16個に画面を分けたので,弾の情報を入れておけるようにさらに16個の配列を用意する.一つの領域に複数の弾が入ることがあるので,当然BulletListはリストや配列っぽいもの.今回の場合は各領域に入っている弾は次のようになる.

space[0], space[3], space[5], space[9], space[11] ,space[14]
にそれぞれ一個ずつ.それ以外は空っぽの状態となる

あとは自分のいる領域が14であることがわかれば,space[14]の弾とだけ当たり判定をすれば良いことがわかる.
ちなみに,このspaceの中の情報も当然更新してやらないといけないので,手続きとしては結局次のようになる.

  • 弾一つずつについての処理
    • 弾を動かす
    • どの領域に入るか計算してspaceに入れる
  • その他の敵とかも動かす
  • 自機と同じ領域にいる敵物体一つずつについて
    • 自機と当たり判定

どの領域にいるかを計算する手間が増えるけど,当たり判定を行うためのif文は減らせる.ぶっちゃけ1000個程度を計算するのは今のCPUにとっちゃたいした仕事じゃないので初めは普通にぶん回しておけばいいと思う.
それと,どこの領域にいるかを計算するときにif文を使って計算すると意味がないので一応書いておく.例えば次のようなフィールドを考えよう.

どの領域に入るか計算してspaceに入れるときに下のようにif文で切り分けてしまうとあまり意味がない.当たり判定でやらなければいけない一般的に「重い処理」と言われるif文を減らすために空間分割しているからだ.

  • x座標が0〜49でy座標が0〜49だったら0番
  • x座標が50〜100でy座標が0〜49だったら1番
  • x座標が0〜49でy座標が50〜100だったら2番
  • x座標が50〜100でy座標が50〜100だったら3番

これはif文を使わずに次のように一発で計算することができる.

space_index = x / 50 + y / 50 * 2

もう少し一般化すると

space_index = x / (X座標を区切る幅) + y / (Y座標を区切る幅) * (X座標を区切る数)

かけ算,割り算をビット演算でできると嬉しいので区切る幅とかは2のべきじょう(2,4,8,16,…)にすると良いかも.まぁ,そこまでやっても効果は微々たるものだと思うので,二次元シューティングゲームではそれほど期待しない方がいいね.

おまけ1

3分20秒当たりで弾が1000発以上出てる.

おまけ2

三次元の衝突判定のための良い分布を持つハッシュ.
http://lucille.atso-net.jp/blog/?p=85

*1:考慮するべき事柄かどうかは考慮してみないとわからないっていうフレーム問題に近いかもね