配列内の要素のペアを一度だけ訪問するには？

Question

私は小さな2Dゲームのために物理学をプログラミングしています。画面上のすべてのオブジェクトを画面上の他のすべてのオブジェクトと照合する必要があります。それはO(N^2)なので、私はそれが本当に好きではありません。私が念頭に置いていた何

：

for (var i = 0; i < objects.length; i ++) 
    for (var j = 0; j < objects.length; j ++) 
     if (collide(objects[i], objects[j])) doStuff(objects[i], objects[j]); 

これは不要であり、私は1つに対して、別の複数回同じオブジェクトをチェックします。どうすればそれを避けることができますか？

visited[i][j] = 1; 
visited[j][i] = 1; 

そして、私はいつもだろう：私は、私はこれに私が希望するオブジェクトのペアを訪問するたびに（nはオブジェクトの数であると仮定）n*nあろうマトリックスを有すると考えられ、そして私が訪れたオブジェクトのペアを知る。

しかし、私はこれらのセルをすべてn*n回に設定する必要があります。開始時にすべて0に設定してください。たぶん、私は[]にすべてを設定することができますが、これはまだ私にとって実行可能なソリューションのようには思われません。何か良いことがありますか？

明らかに私の言語はJavascriptですが、私はC、C++、Pythonを比較的よく知っていますので、（JavaScript、C、C++にはほとんど同じ構文がありますが）それらに答えることができます。

Answer 1

あなたはO（N^2）が避けられないだろうが、あなたは半分で、それを削減することができます

for (var i = 0; i < objects.length; i ++) 
    for (var j = i; j < objects.length; j ++) 
     if (collide(objects[i], objects[j])) doStuff(objects[i], objects[j]); 

衝突が対称であると仮定。リフレクティブで、衝突のテストが高価な場合は、内部ループからdoStuff(object[i], object[i])を移動して衝突のテストを避け、内部ループを開始することができますi+1

Answer 2

スプライトの最大サイズがある場合は、画面上でvert + maxsizeが小さいものを比較するのをスキップしてください...