当り判定のアルゴリズムを考える - プチコンで遊ぼう！ (はてなブログ版)

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

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

'<バクハツ 　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 ルーチン１回あたり、最大で EMAX*XMAX の処理量となる。
EMAX=15、XMAX=25の時、EMAX*XMAX=375となってしまい、意外と大きな処理量。

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

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

爆発の最大半径をXRMとする。(現在のコードではXRM=12としてある)
短冊領域の幅を XRM*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座標から短冊領域はただ１つ決まるので、索引リストに登録された爆発それぞれに対して、
これまで同様の判定を行う。

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

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