昨日作ったフロッキングのプログラムで、
ユニットを増やして実験しようしとしてみたら、
5,60体を越えたあたりからすぐに重くなってしまいました。

数を増やしたときの群れの形成も見てみたかったので、
ネックとなっている、近くのユニットを探す処理の改善を試みました。
具体的には、今までの総当りから、
空間を分割して、付近の空間に属するユニットと調べる、
という方法に変えました。

空間分割の方法には、BSPやらkd木やら四分木やらとあるのですが、
今回はそんな大層なものは使わず、
空間をただ単純な矩形に区切るというだけにしました。

これで、今まで[ユニットの数の2乗]回、比較していたのが、
（ユニット同士が十分に分離してる場合には）
[ユニットの数]回まで減りました。
いわゆるO記法での、O(n^2)→O(n)ですね。

ただ、ユニットの可動領域がウィンドウの広さなので、
これを実装しても100体くらいがちょうどいいかという感じです。