当り判定のアルゴリズムを考える
ミサイルコマンド風ゲームについて、現在の課題は、当り判定ルーチンの処理を軽くすること。
現在のコードは以下のような感じになっている。
'<バクハツ 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回あたりの時間が増えてしまっては意味がない。
なので、このあたりのバランスを見つつ実装する予定。