5

2次元空間にn個の粒子のセットがあり、各粒子がセット内の他のすべての粒子に対して引力を経験し、それらの間の距離の逆2乗に比例すると、経験した正味の力を計算する巧妙な方法を想像できますか？ n ^ 2の距離計算を実行せずに、各粒子ごとに？

私のプログラムのParticleクラスから：

    public void calculateAttractions(List<Particle> entities)
    {
        foreach (Particle p in entities)
        {
            if (!p.Equals(this))
            {
                Vector2 dx = this.Position - p.Position;
                this.ApplyForce(-dx / dx.LengthSquared());
            }
        }
    }

力ずくの方法では、パフォーマンスの問題が発生する前に、（XNAフレームワークとFarseer物理エンジンを使用して）プログラム内で最大150個のパーティクルしかシミュレートできません。

他に方法がない場合、このコードをどのように最適化するか、またはどのようにチートすることができますか？私は、calculateAttractions（）の呼び出しをパーティクルごとにランダム化してみました。これにより、いつでもパーティクルの約1/3だけが実際に更新されます。これにより、パフォーマンスがいくらか向上しましたが、もちろん精度が犠牲になりました。

私がやろうとしていることは、重力の計算に似ています。このスレッドの誰かが、複素数を操作して方程式を使用することを提案しました。

(z-z')/abs(z-z')**3

しかし、私はzが何を指しているのかわからず、この方程式への参照を他のどこにも見つけることができません。

編集：私は以下の答えを受け入れましたが、私は誰も言及していない解決策を使用することになりました：ルックアップテーブル。基本的に、私は、任意の方向に最大2000ピクセル離れたすべての距離（1ピクセルの解像度）で別の粒子によって1つの粒子に加えられる力を事前に計算します。その後、実行時の距離を計算せずに力を決定できます。正確な解決策ではありませんが、歪みは認識できず、シミュレーション粒子の数を3倍に増やすことができました（n体問題ではなく物理エンジンによって数が制限されるようになりました）。 ）。

4

3 に答える 3

8

  1. まず、力は対称であるため、必要なのは n の 2 乗を 2 で割った計算だけです。

  2. 2 番目に力は距離の 2 乗で減衰するため、それを超えると計算する必要のないしきい値を設定することでこれを概算できます。これは 1 次元でのみチェックする必要があります。同様に、x - x' < t および y - y' < t の場合は計算し、そうでない場合は計算しません。

  3. 2 つの占有ツリーを使用して粒子を小さな正方形またはバケツに入れ、1 つのツリーの各バケツのペアに対して k の 2 乗を 2 で割った距離計算のみを行うことができます。もう 1 つのツリーは、隣接する正方形の境界にあるペアを処理するために、左上に移動されます。2 番目のツリーでは、最初のツリーで行った距離計算を繰り返さないでください。

  4. 更新と更新の間で、一部の粒子がその位置を変更しない可能性があるため、最後の更新以降に静止している 2 つの粒子を含む力を再計算する必要はありません。

  5. 大衆も貢献していると思われるかもしれません。さらなる最適化は、質量が小さすぎる場合、それを超えると計算されないしきい値 t も縮小する可能性があることです。

  6. また、パーティクルの移動を量子化して、最小値を下回る動きが座標の変化として記録されないようにすることもできます。

お役に立てれば！

于 2013-01-27T07:07:35.557 に答える
2

すべての粒子間の力を正確に計算するには、粒子間の距離Nを決定する必要がありますO(N^2)。対称性 (つまり ) に注意O(N^2)することで達成できますが、よりもこれをうまく行う方法はありません。(1/2)N^2dist(i,j) == dist(j,i)

不正行為によってほぼ同じことを行うには、代わりに「近くの」粒子相互作用のみを計算し (これらはとにかく最大のものです)、空間インデックス構造を利用できます。

1 つのアイデアは、特定の粒子に「近い」粒子の小さなセットを効率的に決定できるように、四分木( 3次元では 8 分木) を利用することです。M粒子の力を計算するときは、この縮小されたセットのみを考慮します。Mセットが十分に大きいかどうかを判断するために使用されるしきい値を試してみる必要があります。明らかに小さいセットは非常に高速ですが、不正確であり、大きなセットは正確ですが遅くなります。

粒子が移動すると、空間インデックスも更新する必要があります。四分木でこれを行う 1 つの方法は、リーフごとに上限と下限のパーティクル数を設定し、これらの制約に違反したときにツリーを改良することです。

全体として、適切に分散されたパーティクル セットに基づいて、ツリーの高さは になり、ツリーベースの方法のパフォーマンスをO(log(N))期待する必要があります。O(N*log(N))

于 2013-01-27T07:07:53.357 に答える
1

ごまかしOKとおっしゃっていたので、1つの粒子とグループ全体（粒子自体を含む）の重心との間の引力を計算することで、偽物を作ることができるかもしれません。これは、O(2N) 問題になります (質量の中心の N に、各粒子が経験する力の別の N を加えたもの)。これは、粒子の特定の配置の実際の運動法則から大きく逸脱する可能性がありますが、ほとんどの (ランダムな) 初期配置では妥当な近似値である可能性があります。

于 2013-01-27T07:07:45.897 に答える