私は、とが存在する場所に1つのオブジェクトが存在する可能性があるゲームに取り組んでい(x, y)
ます。たとえば、オブジェクトがに存在する場合と存在しない場合がありますが、複数のオブジェクトが同時に存在することはできません。x
y
ints
(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
がありますか、それともこのような問題に適したコンテナがありますか?