1

私は、すべてのループを更新する何千もの潜在的な何百万ものオブジェクトを処理できる必要があるシミュレーションに取り組んでいます。すべてのオブジェクトには、（AI）と呼ばれる論理関数が必要です。ただし、オブジェクトの場所に応じて、ロジックの詳細度が決まります。例えば：

[100個のオブジェクトを操作してシンプルに保つ]

  • すべてのオブジェクトには場所（x、y）があります
  • 20オブジェクトは、「関心のあるポイント」の場所から500ポイント離れています。
  • 50オブジェクトは、オブジェクトから500ポイント離れてい20ます（1000ポイント離れています）。
  • 30オブジェクトは、対象のポイントから100ポイント以内にあります。

これは、オブジェクトが仮想市民である詳細な都市シミュレーションであるとしましょう。午後6時に、全員が仕事から家に帰って寝る時間です。

ですから、私たちはすべての市民を繰り返しますが、私は彼らに異なることをしてもらいたいと思っています。

  • 最も遠い物体（50）仕事から家に帰り、朝まで眠ります。
  • 近くの物（20）仕事から家に帰り、一口食べてから朝まで寝ます。
  • 最も近い物（30）仕事から家に帰り、一口食べて、歯を磨き、朝まで寝ます。

ご覧のとおり、関心のあるポイントに近づくほど、ロジックはより詳細になります。

私は、すべてのオブジェクトを反復処理するための最良かつ最もパフォーマンス効率の高い方法を見つけようとしています。これは、オブジェクトでいっぱいの手で比較的簡単ですが、少なくとも500,000個のオブジェクトを効率的に処理する必要があるため、アドバイスが必要です。

また、ループごとにすべてのオブジェクトを反復処理する必要があるのか​​、ループごとに最も近いオブジェクトを反復処理する方がよいのか、10ループごとに遠くのオブジェクトを反復処理する方がよいのかわかりません。

オブジェクトが近くにある他のオブジェクト間で相互作用する必要があるという追加の要件があるため、これを行うための最善の方法は、オブジェクトを四分木に整理することかもしれないと考えていましたが、よくわかりません。四分木は静的コンテンツ用のようですが、前述のように、私が扱っているオブジェクトには場所があり、他の場所に移動する必要があります。私は正しい思考の道を進んでいますか？または「より良い」方法はありますか？

誰かがそれに関連すると思うなら、私もc++で働いています。

アドバイスをいただければ幸いです。

ノート：

  1. 興味のあるポイントは定期的に変化します。それをカメラビューと考えてください。
  2. オブジェクトは動的に作成および破棄されます
4

4 に答える 4

1

特定の点から特定の半径内にあるオブジェクトをすばやく選択したい場合は、四分木または単純な正方形のグリッドが役立ちます。

問題が何百万ものオブジェクトを格納して反復を効率的にする方法である場合、それぞれが 5 つのフィールドを持つ 100 万のオブジェクトではなく、それぞれ 100 万の要素を持つ 5 つの配列がある場合、おそらく列ベースの手法を使用できます。この場合、各オブジェクトは範囲 0 .. 999999 の単なるインデックスです。たとえば、次の構造の 100 万個のオブジェクトを保存するとします。

struct resident
{
    int x;
    int y;
    int flags;
    int age;
    int health; // This is computer game, right?
}

次に、宣言する代わりに、resident residents [1000000]5 つの配列を宣言します。

int resident_x [1000000];
int resident_y [1000000];
int resident_flags [1000000];
int resident_age [1000000];
int resident_health [1000000];

そして、たとえば、代わりにresidents [n].xを使用しますresident_x [n]。オブジェクトを保存するこのような方法は、同じタイプのすべてのオブジェクトを反復処理し、各オブジェクトにいくつかのフィールドを使用して何かを行う必要がある場合に高速になる場合があります (各オブジェクトに同じフィールド セットを使用)。

于 2013-02-14T21:02:58.460 に答える
0

Morton Encoding / Z-Order インデックス付きの Linear Quadtree を使用することを検討します。ビット配列を使用してデータを含むノードを表し、計算を非常に迅速に実行することで、この構造をさらに最適化できます。

私は Javascript を使用してブラウザーでこれを非常に効率的に行い、サブ秒で 6700 万のノードをトラバースすることができました。関心のある領域に絞り込んだら、別の構造でデータを検索します。すべてミリ秒単位です。これを空間ベクトル アニメーションに使用しています。

于 2014-04-05T19:00:13.550 に答える
0

現実の世界と同じように、問題を「クラス」に分解する必要があります。各人のクラスは、距離から計算されます。だから、下層階級は遠く離れていて、上流階級は近くにいる。または、より正確には、「far class」、nearish class、および「here class」、またはそれらに名前を付けたいものは何でも。

1) 各クラスに 1 つのスロットを持つ配列を作成します。このスロットは、そのクラスの各人の「リンクされたリスト」を保持します。クラスチェンジャー（ソーシャルクライマー）の場合、オブジェクトを別のリストに移動するのは非常に迅速です。

2) 全員を適切なクラスに入れ、自分に近いクラスだけを繰り返します。適切なシナリオでは、気にするには遠すぎるオブジェクトがあるため、それらをディスクに戻し、近づいたときにのみリロードすることができます。

于 2013-02-14T21:13:01.873 に答える
0

そこにはいくつかの質問が埋め込まれています: -大量のオブジェクトを処理するにはどうすればよいですか? 一定数の固定オブジェクトがある場合、十分なメモリがある限り、単純にそれらの配列を作成できる場合があります。それらを動的に作成および破棄する必要がある場合、破棄されたオブジェクトを慎重に処理しないと、メモリ リークの危険にさらされます。ある時点で、データベースなどの別のアプリケーションを使用してオブジェクトを格納し、C++ コードのロジックのみを実行する方がよいかどうかを自問する場合があります。データベースは、私が強調する追加機能を提供します。

-他のオブジェクトから一定の距離にあるオブジェクトを見つける方法。これは、地理情報システム (GIS) の典型的な問題です。オブジェクトと属性を保存するために単純なGISを操作しようとしているように聞こえるので、適用できます。SQRT((Xx)^2+(Yy)^2) (距離の式) をすべてのポイントでテストするには、計算能力が必要です。代わりに、「ウィンドウ関数」を使用して必要なすべての点を含む正方形を抽出し、その中を検索して特定の半径内にある点を見つけるのが一般的です。一部のデータベースは、特定の半径内のポイントを返したり、ポリゴンなどの他のジオメトリ内のポイントを返したりするなど、さまざまな GIS 関数を実行するように最適化されています。それ以外の場合は、この機能を自分でプログラムする必要があります。

-オブジェクトのツリー ストレージ。これにより速度を向上させることができますが、オブジェクトが絶えず動き回っていて、ツリーを頻繁に再構築する必要がある場合はトレードオフになります。それはすべて、物事が移動する頻度と、それらに対して計算を実行する頻度に依存します。

-AI コード。何百万ものオブジェクトに対して AI を実行しようとしている場合、オブジェクトの保存と検索に使用される方法論ではなく、これがパフォーマンスの最大の用途になる可能性があります。遠く離れたポイントの単純なコードはパフォーマンスを向上させ、遠く離れたポイントのロジックを実行する頻度は低くなります。これは、モンテカルロ分析を使用して処理されることがあります。モンテカルロ分析では、特定の反復中にポイントのランダムなサブセットに対してロジックが実行され、対象のポイントからの距離が長くなるにつれて実行の確率が低下する可能性があります。

于 2013-02-14T21:13:19.120 に答える