問題タブ [quadtree]

私の 2D ゲームには、静的オブジェクトと動的オブジェクトがあります。複数のカメラが存在する可能性があります。私の問題:現在のカメラのビュー四角形と交差するオブジェクトを決定します。

現在、私はすべての既存のオブジェクトを反復処理し (動的か静的かは気にしません)、それらのカメラ ビュー rect で AABB チェックを実行します。これは、非常に動的なオブジェクトには受け入れられるようですが、数万のオブジェクトが存在する可能性がある静的オブジェクト (シーン全体に散在する静的レベルのジオメトリ) には受け入れられないようです。

私の問題を解決できる複数のデータ構造を調べました。

• 四分木

これは私が最初に検討したことでしたが、問題はシーンが固定サイズになることです。(静的オブジェクトには使用できますが、動的オブジェクトには使用できません)

• 動的 AABB ツリー

良さそうに見えますが、リバランスのオーバーヘッドが多くの動的オブジェクトにとって大きすぎるようです。

• 空間ハッシュ

ここでの主な問題は、カメラでズームアウトすると、ほとんど存在しない膨大な数の空間ハッシュ バケットをクエリする必要があり、パフォーマンスが低下することでした。

一般に、この問題を適切に解決するための私の基準は次のとおりです。

• 動的サイズ: ソリューションによってシーン サイズが制限されたり、サイズ変更のために大量の再計算が必要になったりしてはなりません。

• 良好なクエリ パフォーマンス (カメラの場合)

• 非常に動的なオブジェクトの適切なサポート: 位置が絶えず変化するオブジェクトを処理するために必要な計算は適切である必要があります。

ゲーム内で一度に正常に動作する動的オブジェクトの最大数は、おそらく 5000 です。すべてのオブジェクトがフレームごとに位置を変えることを考慮してください。フレームごとにオブジェクトの AABB をカメラと比較するよりも、頻繁な挿入と削除を考慮して、高速化できるデータ構造さえありますか?

私はD3 視覚化ライブラリ(http://mbostock.github.com/d3/)を使用して理解しようとしています。力指向のコードを見ていると、クアッドツリーを使用して粒子にかかる力を計算しているようです。 . コードは

quad.count は quadtree ノード内のパーティクルの数です。しかし、https://github.com/mbostock/d3/blob/master/d3.geom.js#L696のquadtree コードを見ると、 への参照が見つかりません。また、その計算方法もわかりません。おそらく各ノードの「重量」または「料金」を変更するためにいくつかのことを変更したいので、私は尋ねます。count

四分木の除去方法を書いています。

これで、ノード内のアイテムを削除するときに、その兄弟をチェックして、ノードを折りたたんで1つにマージする必要があるかどうかを確認する必要があります。

兄弟をチェックするために、親ノードへのポインターを格納する必要がありますか、それともこれを再帰的かつより適切に行う方法がありますか？

ありがとう

[(x1,y1),(x2,y2), ..., (xn,yn)]モートンでソートされたポイントのコレクションがあります。これらのポイントからポインターベースの圧縮された四分木を構築したいと考えています。Eppstein et al と Aluru を読むと、これは比較的単純な作業であるという印象を受けます。

残念ながら、両方の記事の説明には疑似コードがなく、やや扱いにくいものになっています。したがって、ツリーを構築するために必要な具体的な操作を説明する高レベルの擬似コードを誰かが提供できるかどうか疑問に思っています。

作成中のゲームでクワッドツリーを衝突検出に使用しようとしていますが、異なるクワッド間を移動している可能性のあるオブジェクトを処理する方法がわかりません。

私が考えることができる唯一の方法は、フレームごとにツリー全体をクリアしてから、そこにすべてを追加することですが、それはCPUを集中的に使用し、あまり効率的ではないようです. フレームごとに各オブジェクトをチェックして、現在のクワッドの境界の外に移動したかどうかを確認し、移動した場合は削除して再読み込みしますか? フレームごとにすべての移動オブジェクトに対して衝突チェックを実行することになるため、これもかなり非効率的なように思えます。

また、四分木についてですが、その中で動き回るオブジェクトとは関係ありませんが、同じクワッド内の複数のオブジェクトをどのように処理しますか? それらについて私が読んだほとんどのサイトでは、クワッド内のオブジェクトは 1 つ、場合によっては 2 つだけにする必要があり、それ以上のオブジェクトを取得した場合はツリーに押し下げると書かれています。こんな状況だったら？3 つの円があり、それらはすべてその下のレベルの端にあるため、それ以上下に行くことはできませんが、同じレベルに 3 つすべてがあり、人々はあなたが持つべきではないと言っています。

2 次元の空間シミュレーションでエージェントを追跡するための適切なデータ構造は何ですか?

quadtrees (私は理解しています) と kd-trees (私はよく理解していません) への言及を見てきました。

エージェントが効率的に「自分の場所を知っているので、自分の近く (自分の特定の半径内) にいるエージェントを知りたい」と言うことができるものを探しています。

例 (疑似コードでもかまいません) をいただければ幸いです。

私はJavaで働いています。

私は四分木を作っているので、そこにオブジェクトを挿入するのを手伝う必要があります。私はそれを行うという概念を理解していますが、再帰とJavaが変数を渡す方法は得意ではありません。

ルートと呼ばれるノードを含むQuadtreeクラスがあります。Nodeクラスには、その中に4つのノードがあります。これはそれを構成する4つのクワッドです。クワッドツリーを作成するとルートノードが作成され、createChildrenQuads（）を呼び出すまで、各ノード内の4つのノードは作成されません。ただし、ルートノードの場合、クワッドツリーを作成するときにそのメソッドが呼び出されます。

したがって、アイテムをノードに挿入する方法についての私の思考プロセスは次のとおりです。

1. ルートノードから開始します
2. 各ノードの場合：
   1. 現在のノードの子クワッドのどれが現在のアイテムに適合するかを確認してください
   2. それらの1つに収まる場合は、そのノードに挿入します（再帰メソッドを呼び出して最初からやり直します）
   3. いずれにも当てはまらない場合は、現在のノードのオブジェクトのリストに追加して実行します

これに基づいて、私はこれを作成しました：

四分木に関しては、私が持っているロジックは問題ないと思います。コードをデバッグすると、すべてが正常に機能しているように見えます。ただし、私の問題は、Javaがパラメーターを参照ではなく値で渡すことであると考えています。そのため、正しい場所にパラメーターを追加しても、ローカル変数であるため、「保存」されません。それが問題だと思いますが、間違っている可能性があります。

そこで、insertメソッドが現在のノードを返すように少し変更して、すべてが正しく「保存」されるようにしました。これは私が思いついたものです：

しかし、私はまだ同じ問題を抱えています。今、私は自分の問題が何であるかわかりません。

これをゲームに使用していて、すべてのクワッドがある場所の周りに輪郭を描くようにしています。クリックしてエンティティをクワッドツリーに追加できます。私のコードの両方のバージョンは同じように動作するようです。クワッドツリーにエンティティを追加すると、エンティティが追加されてそこにとどまるため、Javaが参照を渡す方法が原因で、エンティティが「保存」されないという私の理論は間違っていると思います。

ただし、私のコードは（少なくとも私の心の中では）各エンティティを可能な限り低いレベルでクアッドツリーに配置し、ツリーを下るときに各ノードに新しい子クワッドを作成する必要があります。ただし、実際に発生するのは、新しいエンティティを現在のクワッドに追加するだけで、ツリーをまったく下がらないように見える場合や、レベルが1〜2下がる場合があります。これは、簡単に数個下がることができる場合です。より多くのレベル。

誰かがコードや私のロジックに何か問題があるのを見ることができますか？

私は地形エンジンのようなMinecraftを作成していますが、正確には八分木とは何か疑問に思っていました。私のエンジンでは、エンジンの各部分をチャンクまたは領域に分割しました。これは、私が読んだものから、それと関係があります。また、インデックスがゲーム内のパフォーマンスを向上させるかどうか、もしそうならどれくらいになるのだろうかと思っていました。パフォーマンスを向上させるための他のアイデア/方法をいただければ幸いです。裏面カリングはすでに含まれていることに注意してください。ボックスまたは側面が非表示になっている場合は、その側面を表示しないでください。

人口密度に応じて QuadTree を構築するための Java コードを探しています。また、コードで Google マップを使用しているので、実装方法を知っている人がいれば非常に助かります。ありがとう