あたり判定するときにわざわざn²通り試すのは、数が少なければいいけれど、そうでなければ賢いとは限らないという話があるようです。
回避する方法はいくつかあるみたいですけど代表的なものは

①空間をいくつか小さな格子に分けてオブジェクトを突っ込む
②オブジェクトの並びを特定の軸方向にソートして前から順番に重なっているものだけ判定する

という２系統がある、と自分は理解しました（合ってるのか？）
②のほうは、もうちょっと応用してx軸でソートして、重なっている個数が一定以上になったらy方向でソートしてという方法（RDC法？）とかがあるみたいです。
実装は簡単そうなのでたぶん書ける。（多分・・・）

問題は①なんですけどこいつは結構種類があってしかも難しいんですよね
種類としては　均一格子、4分木(8分木)、kd-tree、BSP-treeとかがあるみたいですけど、BSP-treeはとりあえず理解不能

これらのほかに本で読んだ「h格子（階層化格子）」というものがあるようなんですけれど、どうやらネットで調べてもなかなか見つからないという・・・。
直感的に明らかに高速そうなので、作ってみました。

アルゴリズム
①空間分割
まず適当な大きさの空間に均等に割る。以下こうして形成された格子の集まりを一番上の層という。
格子の大きさはワールドに存在する最大のオブジェクトよりも大きくないといけない。（別に正方形である必要はないが、正方形のほうが楽。）
次に分けた空間をさらに４つずつ分割にしていき、新たな層をつくる。（ちょうど四分木のように、ただし必ずしも４っつに分ける必要はない）
そうしてできたさらに小さな格子がまだ十分に大きい場合は、それらをさらに４分割していく。
ただし最小の格子の大きさはワールドに存在する最小のオブジェクトより大きくないといけない
以下より小さな格子で構成された層をより下の階層の層という。
そして、より下にいる階層の各格子を、それを含んでいるより上の格子に登録する。登録された格子を親の格子という
こうして下の層にいる格子から上にのみめぐっていけるツリーができる。

②オブジェクトの登録
オブジェクトを、ある階層の格子より小さくなるできるだけ下の階層の格子に登録する。こうすることでオブジェクトは最大でも４つの格子にのみ登録され
しかも同程度のオブジェクトとはかなり隔てられている。
次に衝突判定を行う。これは下の階層の格子に登録されているオブジェクトから行う（正確には順序によらない）
まずもっとも下の階層にいるそれぞれのオブジェクトが、自分の格子と同じ格子に登録されているオブジェクトと判定を行う
次にそれら登録されている格子の親に当たる格子に登録されているオブジェクト（つまりより大きなオブジェクト）と判定を行う。これは一番上の層にいる親に至るまで続ける
そして一番下の階層にいるオブジェクトすべての判定が終了したら、次にその一つ上の階層のオブジェクトの判定を行う
この時より下の階層にいるオブジェクトは、上の階層のオブジェクトとの判定をすでに済ませているので、下の階層にいるオブジェクト（つまりより小さなオブジェクト）
との判定はスキップできる
つまり、一つ上の階層にいるオブジェクトの判定も、一番下の階層のオブジェクトとおなじようにすればよい。
これを最上階の階層まで続けると、すべてのオブジェクトの衝突判定が終了する

--------------------------------------------------------------------------------------------------------

利点：各オブジェクトの登録作業が定数時間で終わる、またオブジェクトの追加も自由。判定数は比較的少ない
また４分木のように小さなオブジェクトが大きな格子に登録されることも原理的にない。
またハッシュを用いることで、空間が無限に広くても対応できる。オブジェクトが動いても判定速度に影響しない

欠点：
メモリを使いすぎる。ハッシュを使えばある程度解決する
普通のやり方だとオブジェクトの形が正方形か円かに限られる。最悪の場合の計算量がオブジェクトの数の２乗に比例する

・・・概してソートを基にした時と比べて利点がわからないｗ
まぁいくつかそうでない場合もあるみたいですけど・・・

h格子って始めて見ましたが、ぱっと説明見た感じ4分木に似てますね。

h格子とは関係ないですが、衝突判定にAABBとかのバウンディングボリュームを使う時は空間分割にBounding Volume Hierarchy（日本語だとバウンディングボリュームツリーかな？）を使うのが個人的にオススメです。
BVHは基本的なのだったら作るのも使うのも結構楽で、速度も良いですよ（ただ、4分木と同じで動的なオブジェクトを使う場合は気を付けなければいけませんが）。

コメントありがとうございます^^;

大熊猫 さんが書きました:h格子って始めて見ましたが、ぱっと説明見た感じ4分木に似てますね。

そうですね。均一格子と４分木のいいとこどりをしたような感じです。４分木と比べると空間の広さを容易に無限大へ拡張できるのと、階層のルートのノードがオブジェクトの大きさに従って自由に決められる点などにおいてもすぐれています。また挿入削除移動も高速です。まぁ後はソートと比べて光線との判定が容易なことくらいですかね。
自分の環境では上記のプログラムはオブジェクトの数が２００００でも格子を小さく割ることでリアルタイムに判定できました（重力や分子間力等加えると流体のようになってテンションあがりましたｗ）

大熊猫 さんが書きました: 衝突判定にAABBとかのバウンディングボリュームを使う時は空間分割にBounding Volume Hierarchy（日本語だとバウンディングボリュームツリーかな？）を使うのが個人的にオススメです。

自分の本には階層ボリュームとして紹介されています。どちらかというと空間分割というよりはオブジェクトのバインドという表現に近いんですかね。空間の大きさが関係ないところも魅力なのかなぁと思ってたりします。ただ動くオブジェクトとの判定には向いていないみたいですね。見るからに高速そうな感じがしますが・・・ワールドのオブジェクトとの判定に最適といった感じですか。