1

小さな 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]);

これは不要です。同じオブジェクトを相互に複数回チェックします。どうすればそれを回避できますか? (n がオブジェクトの数であると仮定すると)行列を持つことを考えたn*n後、オブジェクトのペアにアクセスするたびに、次のようにします。

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

そして、私が訪れたオブジェクトのペアを常に知っていました。

これは機能しますが、最初n*nにすべてを設定するためだけに、これらのセル、時間をすべて設定する必要があり0ます。たぶん、すべてを に設定できますが[]、これはまだ実行可能な解決策とは思えません。もっと良いものはありますか？

明らかに、私が選んだ言語は Javascript ですが、C、C++、および Python は比較的流暢に知っているので、それらで答えることができます (ただし、Javascript、C、および C++ の構文はほとんど同じです)。

4

2 に答える 2

3

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

于 2012-04-11T09:23:06.337 に答える
0

スプライトに最大サイズがある場合は、配列を並べ替えて、画面上で vert+maxsize の下にあるものの比較をスキップできます...

于 2012-04-16T21:28:28.437 に答える