0

これが私の問題です。

私のゲームは、効率的なレンダリングと衝突のために、リージョンに分割されています。各リージョンには、動的に移動する多くのオブジェクトがあります。彼らが移動するとき、私は彼らがどの地域にいるかを決定します。

これは、オブジェクトが複数のリージョンに存在する可能性があることを意味します。

オブジェクトAがリージョン1と2にあり、オブジェクトBも1と2にあることがわかっている場合、次のようになります。

for each object in region 1 and 2
if A collides with B...

私は事実上同じペアを2回チェックしているでしょう。

それらを一度だけチェックするにはどうすればよいですか？使用すべきデータ構造またはアルゴリズムはありますか？

4

4 に答える 4

1

オブジェクトに順序を付けることができる場合は、順序によってペアを確認するだけで済みますa < b。配列内のインデックス、ポインター（ポインター値へのアクセスを許可する言語の場合はそうです）。

for(Object a : list) {
    for(Object b : list) {
        if (a.compare(b) < 0) {

非常にシンプルで、実際に問題を解決します。

整数のインデックス付きストレージがある場合は、次のことができます。

for(int i = 0; i < list.length; i++) {
    for(int j = i + 1; j < list.length; j++) {

重複することはありません。これはArrayList、任意のタイプでは機能しますが、おそらく機能しません。いくつかのイテレータのクローンを作成できるかもしれませんが、私はそれには賭けません...

for(Iterator<Object> iter = list.iterator(); iter.hasNext(); ) {
    Object a = iter.next();
    Iterator<Object> iter2 = iter.clone();
    for(;iter2.hasNext();) {
        Object b = iter.next();

しかし、真剣に、それはハックです。それがすべてのJavaコレクションで機能する場合は驚きます。より信頼性がありますが、Javaイテレータを使用したハックの回避策と同じです。

for(Object a : list) {
    Iterator<Object> biter = list.iter();
    while(biter.next() != a) { };
    for(; biter.hasNext(); ) {
        Object b = biter.next();

一般に、java foreach構文for(Clazz object : iterable) {は「かわいい」ですが、sよりもはるかに強力Iteratorではありません。実際、上記の古い整数のforループも魅力のように機能します。

于 2012-11-08T20:11:46.280 に答える
0

以前の計算の結果を保存してみませんか？

事実上、次のようになります。

for each object in region 1 and 2
    if results doesn't contain (A collides with B)
       ...
       results = result of (A collides with B)
于 2012-11-08T17:59:35.260 に答える
0

いいえ。グリッドが小さすぎる可能性があります。また、バウンディングボックスは衝突検出にあまり適していません。挿入と削除を犠牲にして、空の領域を回避します。

于 2012-11-08T18:40:10.270 に答える
0

等間隔のグリッドの代わりに、さまざまなサイズのオブジェクトにインデックスを付けるのに適したクアッドツリー（ http://en.wikipedia.org/wiki/Quadtree ）を使用できます。単一のセルサイズ（一部のオブジェクトには大きすぎ、他のオブジェクトには小さすぎる可能性があります）を選択する代わりに、クアッドツリーに適切なセルサイズを決定させることができます。

ただし、それでも、単一のオブジェクトが複数のツリーノードで発生するのを防ぐことはできませんが、これを達成しようとする目標ではありません。防止する必要があるのは、すべてのオブジェクトが数十または数百で発生することだけです。セルまたはQuadtreeノード。パフォーマンスが低下するためです。

したがって、すべてのオブジェクトがほぼ同じサイズである場合でも、セルがオブジェクトの少なくとも同じ大きさ（または2倍の大きさ？）である限り、通常のグリッドが最良の選択である可能性があります。

于 2012-11-08T20:07:06.430 に答える