衝突判定アルゴリズムの選択

「何も考えずに思いつく限り全部実装してみろや!」ってところですが、そんなに衝突ラブではないので、そこそこに速そうで実装が簡単そうなアルゴリズムを探しにいく必要があるわけです。しかも3Dじゃないのでそんなに必死こかなくていいし。

お馬鹿にも総当たりで実装している衝突アルゴリズムO(n^2)の代替として、最初はRDC(Recursive Dimension Clustering)を考えていたのですが、どうやら座標軸ごとのソート処理が重いようでなかなか速度がでないみたいです。なので、より単純版らしい"sort and sweep"を試すことにしました。O(n * log(n))になるらしいです。

・・・と調べてみると"sort-and-sweep"って呼び方一般的じゃないのかも。
"sweep-and-sort", "sweep-and-prune"とか言われることが多いようだ。
で、"sweep-and-prune"で調べていくと、示し合わせたようにRadium softwareに辿りつく訳です。
http://www.radiumsoftware.com/0310.html
3年前の記事かぁ、なんかぐったり。

ふむふむ、sweep and pruneの前処理でソート済み配列を構築するコストを低減する方法があるわけね。
・・・ということで"radix based sweep and prune"を勉強中です。今のプログラムは衝突判定がキモになるようなプログラムではないのですが、速くなると聞くと心踊ってしまうのでした。
当たり判定のオブジェクトも今は50個弱ですが、すぐに200個ぐらいまで行くだろうし。