衝突判定の分割
画面を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