スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

【ゲーム開発】普通の空間分割で当たり判定処理を削れるか?

ただ空間を下の絵のように分割しただけでは効果は得られません。
なので、一切読む必要もない記事なっております。
しかし個人的に面白かったので記事に上げました。
とりあえずこの画像を御覧下さい。

空間分割用

今画面上に弾がばばーっと出ております。
画面右下の赤い数字は124と表示されておりますので124個の弾が存在していると言う事になります。

もし何もしなければ、124個全ての弾と自機との当たり判定を行うことになります。
ただ、124個くらいのオブジェクトで当たり判定の回数を減らした所で・・・と思うかもしれません。

しかも、場合によっては処理が多くなるケースも有ります。
そんな事はありますがせっかくなので紹介したいと思います。


今自機は「15」と書かれたエリアに存在します。
このエリア付近の弾以外は自機と接触している可能性は一切ありません。
良く用いられる当たり判定を軽減する処理に、空間分割と呼ばれるものが存在します。
・・・と言っても、今回紹介するのはめっちゃ簡単な方法なのでまだまだ改善の余地はあります。


さて、空間分割を使うその前に・・・。

この絵の当たり判定を矩形同士(長方形同士)の当たり判定でやっていると仮定します。
矩形同士の当たり判定は、最大四回の判定を経て当たっているかどうかを判断できる判定方法です。

if(自機の左と接触? && 自機の上と接触? && 自機の下と接触? && 自機の右と接触?)
{
  当たっています!
}

文字で書くとこんな感じでしょうか・・・。
要するに四方当たっているかどうかのチェックをするだけで判定できるので
便利で簡単な方法になってます。
この判定を、先程の例で行くと124個の弾分行う訳です。

しかし、ちょっとだけ考えてみます。
例えばこのゲーム、横シューティングなんですがどこから弾が沢山現れますか?
恐らく全方位シューティングでない限り大体は右側から弾がやってくる事が多いと思います。
(勿論ゲームや場合によりその限りではありませんが。)

と言う事は上の例でいくと、
基本的に「自機の右と接触?」の条件が満たされていなければ当たってないと言えます。

if(自機の右と接触? && 自機の上と接触? && 自機の下と接触? && 自機の左と接触?)
{
  当たっています!
}

if の条件を少し変えるだけで、それ以降の判定をしなくなります。
たったこれだけで多くの弾の判定を一回分だけで済ませる事が可能です。
御自身のゲームはどこからの判定が多くなるか?
それを考えて弾いてやればいい訳ですね。

しかし、先程も書いたとおり攻撃パターン等により自機の上から来る事が多くなったり
左から攻撃をしてくるなんて場合もあるかもしれませんので
一概にコレがいいと言う訳ではありません。



それでは普通の空間分割について始める前にもう一度同じ画像を貼っておきましょうか・・・。
空間分割用

さて、画像に0~24の番号が割り振られて、赤い線が引かれてると思います。
ゲーム内を仮想的な空間に分割している図です。


画面が「640×480」で、横に5つ、縦に5つの、5×5 の空間に分割されてます。
今自機は「15」番にいますので、それ以外は当たっている可能性はありません。

この「15」番・・・どうやって導き出せばいいのでしょうか。
これは単純にいくと「こっからここまでの範囲は9番」、「こっからここまでの範囲は15番」など
場合分けで今の番号を導き出す方法があります。
しかしこれでは駄目です。

当たり判定を減らすために判定を削る所で、
番号を求めるための判定をしちゃうと意味がありません。
しかも、毎フレーム動くものですからその度に何処の番号にいるかの判定はしないといけません。
ここは計算式一発で番号を得られるので計算式で導きましょう。


int NowSpaceIndex = 対象X座標 / 分割幅X + 対象Y座標 / 分割高さY * 横の分割数

「対象X座標 / 分割幅X + 対象Y座標 / 分割高さY * 横の分割数」
こいつが、計算式です。

NowSpaceIndex という変数は、今どこの空間に所属しているかを表す変数です。
この計算は小数点が出てきますが、整数型(int 型等)で大丈夫です。
実数型(float 等)で計算しては駄目です。


実際に計算してみます。
今の自機座標、X座標が大体5くらい、Y座標が310くらいですかね?

これをベースに考えてみましょうか。

対象X座標(5)
分割幅X(640/5 = 128)
対象Y座標(310)
分割高さY(480/5 = 96)
横の分割数(5つ)

情報はこのようになってます。


では実際 NowSpaceIndex を計算すると、
5 / 128 + 310 / 96 * 5
= 0.0390625 + 3.22916666... * 5

となりますが、整数型の計算で小数点以下はばっさりなくなりますので
= 0 + 3 * 5 = 15 となり、自機がいるエリアである「15」が導けました。

たった一回の計算式で所属している番号が導けます。
所属する番号を保持して、今の計算式を使えばこれで当たり判定を軽くできる!!


やった!! 万歳!!!


・・・と喜びたいところです。

実はこれ、もう一つ考えなくてはいけない所があります。
同じ番号かどうかを判断し、違うのであれば当たり判定をしなければよい。
確かに所属する番号が解り、一見良さそうに思えます。

2D のゲームにはポリゴンにテクスチャが貼ってあるため頂点情報は四つあるはずです。
今の計算式はある一点のみしか計算しておらず、空間にすっぽり入っているからこそ簡単に思えました。


しかし、考えなければいけないのは右側のボスのように
「9, 14, 19」の空間・・・つまり空間をまたいで所属しているケースです。
しかもこのボス・・・空間を縦に三つもまたいでいる事にも問題があります。

何が問題なのかと言うと、左上と右上の頂点は「9」番に所属し、
左下と右下の頂点は「19」番に所属しています。


四点の頂点情報なので、間の「14」番には所属していない事になるんですよね。
これを回避するにはいくつか方法はあります。


簡単な方法として、空間一つ一つの幅をもっと広げると言う物があります。
要するに、空間を縦、あるいは横に三つ以上またがせないと言う回避法です。
あまりにも力技です。
しかし、またいでも二つまでというルールを設ければ回避は可能です。

しかしオブジェクトのサイズなんてどれくらいなのかわかりません。
変化して当然でしょうし、
もっと大きくなる可能性もあるのでこの方法では回避出来ないケースもあるでしょう。



もう一つ簡単な方法として、ボスのような大きなオブジェクトに対しての当たり判定は
空間分割を使わないという手があります。

ボスと接触判定をするのは自機、自弾、ボムくらいでしょうか?
しかもそこまで多くの接触をするとも考えにくいのでわざわざ空間に分けてどうこうするより
普通に判定した方が速く処理ができるかもしれません。


では一番判定が多いであろう自機と敵の弾。
自機四つの頂点に対して、敵弾も四つ頂点がありますので
自機一つの頂点に対して、敵弾四つの頂点が同じ番号かを調べる必要があります。

つまり、一つの弾に対して 4*4 の、最大で16回の判定が・・・
今回は124個の弾があるので、124*16 = 1984回最大で必要になります。


もし同じ番号に所属する場合、矩形同士の判定をする必要があるので、
更に最大で4回の判定を行う場合があります。
敵弾が124個のこの例で行けば最大で 1984*4 = 7936回もの判定を行う事になります。


非常に多くなりました。
何もしない矩形同士の当たり判定は 124*4 の判定で解るので最大で496回の判定です。
16倍・・・えらい違います。
物凄く遅くなるのが解って頂けたんじゃないかと思います。


実際、そのエリアに124個の弾がある状況はないと思うので
ここまで大きな回数にはならないですが、それでも最大回数を見てしまえば
余計な判定をしている事に変わりはありません。



え・・・じゃあ空間分割ってめっちゃ遅いの??
と疑問に思うかもしれません。

ベタに組むとそんなに遅くなるんですよという記事を書きたかっただけなんです。
非常に長い記事ですな・・・。
とりあえず、記事も大分長くなったので一回ここで終わりにします。


え!?速くなる方法を紹介するんじゃないの!?
と思われた方は残念。

タイトル通り、「普通の空間分割で当たり判定処理を削れるか?」と言う点に注目しただけなんです。
記事冒頭に書いた通り、普通の空間分割だけでは無理です。


「計算式で、何処の番号に所属しているかが解ります。
これで余分な if を使わず番号を得られるので当たり判定の回数は減ります」

そういう記事を数件発見しました。
言葉通りに取るなら、確かに当たり判定の回数は減っています。
しかし、他の部分がネックになっていては話になりません。


多分そう言う話をしたくて記事に書いている訳ではないのは解っているんですが、
その後どうするの?と言う所にまで着目されてなかったのが気になりました。



実は、四分木空間分割と、モートン順序と呼ばれるものを組み合わせれば
今回のような空間をまたぐ場合や、処理の遅さをカバー出来るようです。
時間があればそっちも記事にしたいですね。

と言う訳で長くなりましたが今回はこんなところで、さようなら~

この記事へのコメント

トラックバック

URL :

検索フォーム
プロフィール

DVDM

Author:DVDM
自作ゲームの開発過程ブログ。
赤髪愛なら誰にも負けない。

 
Pixiv バナー


ブロとも申請フォーム
最新記事
カテゴリ
最新コメント
最新トラックバック
RSSリンクの表示
リンク
ブロとも一覧
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。