衝突判定の分割

画面を4分割して判定する場合のアルゴリズムを考えていた。

これはオブジェクトの中心座標をすべて足してオブジェクト数で割って分割座標を作った場合に、どのぐらい衝突判定の負荷が減るかというのを検討したプログラムの画面。
オブジェクトは100個あって、初期配置はランダム、移動方向もランダムだ。座標を計算してちょうど真ん中に交点が来るように線が描画される。数字はそれぞれの領域とヒットする画像の数で、またがるやつがいるから合計は100を越えることが多い。
真ん中の数字は4つの数字をそれぞれ2乗して合計したもので、これがおおまかに言って衝突判定の負荷となる。分割しないと100個あるから10000になり、理想的に4分割されれば2500となる。
単純に4分割するため、オブジェクトが左下と右上に集中するとどうしても分散できないのは仕方のないところ。
ちなみに衝突判定10000回というのは敵100匹に自分の弾100発とか、敵の弾10000発と自機1つとかのあんまりあり得ないレベルの話になるので、分割処理が必要になるのは同じ配列同士の衝突判定だけでよさそうだ。
同じ配列同士だと同じオブジェクトの判定や、判定2回目を省略することで半分弱ぐらいになるから、実際には分割しなくても問題なさそうな雰囲気。
このテストコードを置いておく。

#!ruby -Ks
require "dxruby"

class Box < Sprite
  def initialize
    super
    self.image = Image.new(30, 30, [255, 200, 0, 0])
    self.x = rand(639-self.image.width)
    self.y = rand(439-self.image.height)
    @dx = (rand(4)*2-3)/2.0
    @dy = (rand(4)*2-3)/2.0
    self.collision = [0, 0, 29, 29]
  end

  def update
    self.x += @dx
    self.y += @dy
    @dx = -@dx if self.x <= 0 or self.x >= 639-self.image.width
    @dy = -@dy if self.y <= 0 or self.y >= 479-self.image.height
  end
end

class Collision < Sprite
  attr_accessor :count
  def hit(o)
    @count += 1
  end
end

font = Font.new(32)
object = Array.new(100) {Box.new}
image = Image.new(1,1,[255,255,255])

s = Collision.new

Window.loop do
  object.each do |o|
    o.update
  end

  total_x = 0
  total_y = 0
  object.each do |o|
    total_x += o.x + o.image.width / 2
    total_y += o.y + o.image.height / 2
  end

  Window.draw_scale(total_x / object.size, 0, image, 1, 480, 0,0,1000)
  Window.draw_scale(0, total_y / object.size, image, 640, 1, 0,0,1000)

  s.count = 0
  s.collision = [0,0,total_x / object.size, total_y / object.size]
  Sprite.check(object, s)
  Window.draw_font(100,100, s.count.to_s, font,:z=>10000)
  c1 = s.count

  s.count = 0
  s.collision = [total_x / object.size, 0, 639, total_y / object.size]
  Sprite.check(object, s)
  Window.draw_font(420,100, s.count.to_s, font,:z=>10000)
  c2 = s.count

  s.count = 0
  s.collision = [0, total_y / object.size, total_x / object.size, 479]
  Sprite.check(object, s)
  Window.draw_font(100,340, s.count.to_s, font,:z=>10000)
  c3 = s.count

  s.count = 0
  s.collision = [total_x / object.size, total_y / object.size, 639, 479]
  Sprite.check(object, s)
  Window.draw_font(420,340, s.count.to_s, font,:z=>10000)
  c4 = s.count

  object.each do |o|
    o.draw
  end

  Window.draw_font(280,220, (c1*c1+c2*c2+c3*c3+c4*c4).to_s, font,:z=>10000)

  break if Input.keyPush?(K_ESCAPE)

  Window.drawFont(0, 0, Window.fps.to_s + " fps", font)
  Window.drawFont(0, 24, Window.getLoad.to_i.to_s + " %", font)
end