QuadTree

建物はどーせ規則的に並べるんだからハッシュ?的に判定して、動くのだけにQuadTreeを適用するのがいろいろいいんじゃないかという結論になった。もちろん脳内で。
今までソートとかで作ったような内部ノードが値を持つ木にすると、値が変わった時に木の再構築がとてもだるそうで嫌。だから葉だけに値を持たせようってなるわけだけれど、それじゃ何を基準にして木をつくるのかわからん。マップ全体を4つの領域に等分して、一つの領域に二つ以上のなんかがあったらその領域をまた4等分するって感じで再帰的に分割していったらそれっぽくなるとは思ったけど、点じゃないからなんかだめっぽい。てかこんなの作ろうとした日にはバグ取りで丸二日つぶれるに違いない。

総括

n*nでマップを格子状に区切って、それぞれの格子に、その中にあるオブジェクトへのポインタをリストで持たせる。
ゴリ押しでいいや。ゴリ押しがいいや。