読者です 読者をやめる 読者になる 読者になる

プチコンで遊ぼう! (はてなブログ版)

任天堂3DSのプチコンで遊ぼう! [twitter:@eida_s]

はてなダイアリーから移行しました。 はてなダイアリーのURLを開いても自動的にこちらにリダイレクトされますのでご了承ください。

当り判定のアルゴリズムを考える

プチコン

ミサイルコマンド風ゲームについて、現在の課題は、当り判定ルーチンの処理を軽くすること。

現在のコードは以下のような感じになっている。

'<バクハツ  X,Y:ザヒョウ R:ハンケイ S:ハッセイゴノケイカジカン>
DIM XX(XMAX),XY(XMAX),XR(XMAX),XS(XMAX)
'<テキICBM  X,Y:ザヒョウ>
DIM EX(EMAX),EY(EMAX)

@JUDGEMS
FOR I=0 TO EMAX-1
 IF EX(I)>=0 THEN GOSUB @JUDGEMS0
NEXT I
RETURN

 @JUDGEMS0
 IX=EX(I):IY=EY(I)
 FOR J=0 TO XMAX-1
  IF XS(J)==0 THEN GOTO @JUDGEMS1
  R=XR(J):V=IX-XX(J):U=IY-XY(J)
  IF R*R<(V*V+U*U) GOTO @JUDGEMS1

  (当りの処理)

  J=XMAX
  @JUDGEMS1
 NEXT J
 RETURN

上記の処理では、@JUDGEMS ルーチン1回あたり、最大で EMAX*XMAX の処理量となる。
EMAX=15、XMAX=25の時、EMAX*XMAX=375となってしまい、意外と大きな処理量。


そこで、以下のアルゴリズムを考えた。

画面を横方向に短冊状の領域に分けて考える。

爆発の最大半径をXRMとする。(現在のコードではXRM=12としてある)
短冊領域の幅を XRM*2 とする。

すると、任意の爆発は、最大でも2つの連続する短冊領域の中に収まる。
(最大時の爆発の横幅は XRM*2+1なので)

この短冊領域ごとに、そこに含まれる爆発への索引リストを持つことにする。
索引リストはXI$()として持つことにする。
爆発の中心のX座標をXX(I)とすると、それが含まれる短冊領域の添え字Cは以下のようにして求める。

C=FLOOR(XX(I)/(XRM*2))

XI$(C)の索引リストに、添え字 I を登録する。

XX(I)が短冊領域の左半分ならば XI$(C-1)、右半分ならば XI$(C+1) の索引リストにも、添え字 I を登録する。

ICBMのX座標から短冊領域はただ1つ決まるので、索引リストに登録された爆発それぞれに対して、
これまで同様の判定を行う。

画面に爆発が一様に分布していると仮定した場合、
ひとつの短冊領域の索引リストに登録された爆発の数の期待値は、以下の通りとなる。
(XMAX/(256/(XRM*2)))*2


このアルゴリズムで処理した場合、@JUDGEMS ルーチン1回あたりの処理量の期待値は、
EMAX*(XMAX/(256/(XRM*2)))*2

よって、EMAX=15、XMAX=25、XRM=12の時、処理量の期待値は 15*4.6875 = 70.3125 となる。

これで処理量はおよそ 1/5 となる計算。(あくまで確率的な計算上では...)

ただし、これはループの回数が減る、ということであって、ループ1回あたりの時間が増えてしまっては意味がない。
なので、このあたりのバランスを見つつ実装する予定。