7

私は、とが存在する場所に1つのオブジェクトが存在する可能性があるゲームに取り組んでい(x, y)ます。たとえば、オブジェクトがに存在する場合と存在しない場合がありますが、複数のオブジェクトが同時に存在することはできません。xyints(0, 0)

私は、目前の問題にどのSTLコンテナを使用するか、そしてこの問題を解決するための最良の方法を決定しようとしています。

基本的に、私はオブジェクトとその(x, y)場所から始めます。目標は、そのオブジェクトの周囲のオブジェクトに基づいて、可能な限り最も高く、最も大きい長方形を決定することです。長方形は、現在のオブジェクトの上下にあるすべてのオブジェクトを使用して作成する必要があります。つまり、開始オブジェクトの位置に基づく可能性がある最も高いものである必要があります。

たとえば、以下が私のオブジェクトグリッドを表し、場所にある緑色のオブジェクトから始めているとします(3, 4)。

ここに画像の説明を入力してください

次に、私が探している長方形は、下のピンクの正方形で表されます。

ここに画像の説明を入力してください

したがって、例が示すようにオブジェクトから始めると仮定すると、オブジェクトが、、、、およびにも(3, 4)存在するかどうかを確認する必要があります。これらの場所のいずれかにオブジェクトが存在する場合は、オブジェクトに対してこのプロセスを繰り返して、可能な限り最大の長方形を見つける必要があります。(2, 4)(4, 4)(3, 3)(3, 5)

これらのオブジェクトはかなりまれであり、ゲームの世界は巨大です。newほとんどの要素が空になるため、ゲームの世界全体で2D配列を使用するのは実用的ではないようです。ただし、オブジェクトがいつでも存在するかどうかを確認するには、任意の位置にインデックスを付ける必要があります。

std::map代わりに、私はそのようなものを使用することを考えました：

std::map< std::pair<int, int>, ObjectData> m_objects;

次に、周囲のオブジェクトをチェックしているときmap::find()に、ループで使用して、周囲のオブジェクトが存在するかどうかをチェックできます。

if(m_objects.find(std::pair<3, 4>) != m_objects.end())
{
    //An object exists at (3, 4).
    //Add it to the list of surrounding objects.
}

これを行うことにした場合、私は潜在的に多くの呼び出しを行う可能性がありますが、マップは全世界の2D配列を使用するmap::find()よりもはるかに少ないメモリを使用します。new

私が探しているものを見つけるために使用できる簡単なアルゴリズムについて誰かアドバイスがありますか？を使い続ける必要std::mapがありますか、それともこのような問題に適したコンテナがありますか？

4

4 に答える 4

1

各グリッド位置に保存する必要があるデータの量は? 隣人を示すフラグを探しているだけの場合は、少なくとも 2 つの「ローテク」ソリューションがあります。

a）グリッドがまばらな場合、各正方形が隣接リストを保持するのはどうですか? したがって、各正方形は、隣接するどの正方形が占有されているかを知っています。正方形が占有または空になったときにリストを維持するために、いくつかの作業を行う必要があります。しかし、近隣リストは、グリッド マップがまったく必要ないことを意味します。

b) グリッド マップの位置が本当に単なる点である場合は、グリッド位置ごとに 1 ビットを使用します。結果マップは、各グリッド ポイントにバイトを使用するマップよりも 8x8=64 倍小さくなります。ビット操作は非常に高速です。10,000x10,000 マップには 100,000,000 ビットまたは 12.5MB (約) が必要です

于 2012-12-17T06:14:45.013 に答える
0

空間データ構造を検討することをお勧めします。あなたが言うように、データが「スパース」である場合、四分木近傍検索を実行すると、処理能力を大幅に節約できる可能性があります。私は個人的にRツリーを使用しますが、それはおそらく、私が作成したRツリーライブラリがあり、簡単にインポートできるためです。

たとえば、1000x100010,000個の要素を持つグリッドがあるとします。今のところ、均一にランダムな分布であると仮定すると、（密度に基づいて）は、たとえば、以下を期待します。。。いずれかの次元で接触している3〜5個のオブジェクトのチェーン（この密度では、3つの垂直方向のオブジェクトのチェーンが0.01％の確率で発生します）。検討中のオブジェクトがにあるとし(x,y)ます。ウィンドウサーチは、で開始し(x-5,y-5)てから(x+5,y+5)、線形検索を実行するための最大121個の要素のリストを提供します。長方形ピッキングアルゴリズムが、より高い長方形を形成できることに気付いた場合（つまり、検討中の長方形がこの11x11境界ボックスの端に接触した場合）、ウィンドウ検索を繰り返して別の長方形を探します。5x5オリジナルの一方向の領域。必要に応じて繰り返します。

もちろん、これは非常にまばらなデータがある場合にのみうまく機能します。葉が連想するようにRツリーを適応させる価値があるかもしれません。データ構造（つまりInt -> Int -> Object）ですが、その時点で、より密度の高いデータで機能するソリューションを見つけるのがおそらく最善です。

私はおそらくこれを考えすぎています。おそらくどこかにもっと簡単な解決策があるでしょう。

Rツリーに関するいくつかの参照：

少しクリーンアップすることになった場合は、自分のRツリー実装（パブリックドメイン）へのリンクを使用してこれを編集します。

于 2012-12-16T22:34:53.630 に答える
0

可能であれば、ハッシュマップを使用すると改善されます。これにより、少なくとも O(1) の予想される時間の複雑さで潜在的な広範な検索を行うことができます。

2 つの整数を一緒にハッシュする方法について詳しく説明しているスレッドがここにあります (一意かつ決定論的な方法で 2 つの整数を 1 つにマッピングする)。

コンパイラが C++11 をサポートしている場合は、std::unordered_map を使用できます。そうでない場合、ブーストには基本的に同じものがあります：http://www.boost.org/doc/libs/1_38_0/doc/html/boost/unordered_map.html

于 2012-12-16T19:50:56.103 に答える
0

これは宿題の問題のように疑わしく聞こえます (「長方形は、現在のオブジェクトの上下にあるすべてのオブジェクトを使用して作成する必要がある」という奇妙な条件があるため、解決策は簡単です)。でもとにかくやってみます。便宜上、「オブジェクト」の代わりに「ピクセル」という単語を使用します。

あなたのアプリケーションが本当に重量のあるソリューションに値する場合は、四分木にピクセルを保存してみてください (その葉には、それぞれ数千ピクセルの単純な古い 2D 配列が含まれています)。または、連続するピクセルをグループ化して「形状」にすることもできます (たとえば、24 の個別のピクセルが含まれている場合でも、例は 1 つの「形状」のみで構成されます)。ピクセル座標の最初の非構造化リストがあれば、これらの形状を見つけるのは簡単です。グーグル「ユニオン検索」。連続した形状を保存することの具体的な利点は、最大の四角形を探しているときに、最初のピクセルと同じ形状のピクセルのみを考慮する必要があることです。

連続した形状を保存することの具体的な欠点は、ピクセル オブジェクトが移動している場合 (たとえば、ローグライク ゲームでモンスターを表す場合)、union-find データ構造が増分更新をサポートしているかどうかわからないことです。すべての「フレーム」でユニオン検索を実行する必要があるかもしれませんが、これはかなり悪いことです。

とにかく... を使用しているとしましょう。それはstd::unordered_map<std::pair<int,int>, ObjectData*>私にはかなり合理的に聞こえるからです。(ほとんどの場合、実際のオブジェクトではなく、ポインターをマップに格納する必要があります。これらのオブジェクトをすべてコピーすると、ポインターをコピーするよりもはるかに遅くなるためです。)

typedef std::pair<int, int> Pt;
typedef std::pair<Pt, Pt> Rectangle;
std::unordered_map<Pt, ObjectData *> myObjects;

/* This helper function checks a whole vertical stripe of pixels. */
static bool all_pixels_exist(int x, int min_y, int max_y)
{
    assert(min_y <= max_y);
    for (int y = min_y; y <= max_y; ++y) {
        if (myObjects.find(Pt(x, y)) == myObjects.end())
            return false;
    }
    return true;
}

Rectangle find_tallest_rectangle(int x, int y)
{
    assert(myObjects.find(Pt(x,y)) != myObjects.end());
    int top = y;
    int bottom = y;
    while (myObjects.find(Pt(x, top-1) != myObjects.end()) --top;
    while (myObjects.find(Pt(x, bottom+1) != myObjects.end()) ++bottom;
    // We've now identified the first vertical stripe of pixels.
    // The next step is to "paint-roller" that stripe to the left as far as possible...
    int left = x;
    while (all_pixels_exist(left-1, top, bottom)) --left;
    // ...and to the right.
    int right = x;
    while (all_pixels_exist(right+1, top, bottom)) ++right;
    return Rectangle(Pt(top, left), Pt(bottom, right));
}
于 2012-12-21T23:44:15.923 に答える