5

私はグリッド ユニバースで作業しています。オブジェクトは 2 次元マトリックスの整数位置にのみ存在します。

いくつかの用語:

正方形 - 個別の場所。各正方形には int x 座標と int y 座標があり、x と y のペアが同じ 2 つの正方形はありません。

隣接: 正方形 X は、x 座標または y 座標のいずれかの差の大きさが 1 以下の場合、別の正方形 Y に隣接しています。 、W、および NW 方向が隣接しています。

Legend:
'?' - Unknown Traversibility
'X' - Non Traversable Square
'O' - Building (Non Traversable)
' ' - Traversable Square

問題：

次の一般的な状況を考えます。

? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? O O ? ? ?
? ? ? O O ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?

ビルダーが 4 つの建物の 1 つに隣接している場合、既存の 4 つの建物の少なくとも 1 つにも隣接する共通の隣接する正方形を共有するように 2 つの建物を建設したいと考えています。この共通の隣接する正方形はブロックされていません。 .

基本的な有効なソリューション:

X X X X X X X X          X X X     X X X          X X X X X X X X
X X X X X X X X          X X X     X X X          X X X X X X X X
X X X X X X X X          X X X     X X X          X X X X X X X X
X X X O O X X X          X X X O O X X X          X X X O O X X X
X X X O O X X X          X X X O O X X X          X X O O O X X X
                         X X X O   X X X                O X X X X
      O O                X X X O   X X X                X X X X X
                         X X X     X X X                X X X X X

現在、4 つの建物に隣接するすべての通過可能な正方形を反復処理し、隣接する 3 つの通過可能な正方形を持つ正方形を探しますが、これにより次のような状況が発生することがあります。

X X X X X X X X          X X X X X X X X          X X X X X X X X
X X X X X X X X          X X X X X X X X          X X X X X   X X
X X X X X X X X          X X   O     X X          X     X X   O X
X X X O O X X X          X X   O O O X X          X     O O O X X
X X X O O X X X          X X   O O   X X          X X   O O   X X
X X X     X X X          X X         X X          X X         X X
X X X O O X X X          X X X     X X X          X X X     X X X
X X X     X X X          X X X     X X X          X X X     X X X

アルゴリズムを改良する方法について何か考えはありますか?

編集:別の失敗したケースを追加しました。

編集:これらの条件が満たされる可能性のある構成がないかどうかも知りたいです。実行可能な解決策が保証されているわけではありません。これを成功させる方法がない場合は試したくないです。

4

3 に答える 3

1

私が考えることができる唯一の解決策は、共通の隣接する正方形からマップの端まで経路探索を行うことです. すべての問題のケースは「隣接する正方形がブロックされている」に要約されるように見えるので、ブロックされていないことを確認する方法は、その正方形からマップの開いた端までの道を見つけることです.

それが最も効率的なアプローチかどうかはわかりませんが、A* パスファインディング ルーチンはかなり広く実装されているため、実装はかなり簡単です。そして実際には、最短経路は必要ないので、経路だけが必要なため、マップの端に到達するまで、隣接する正方形から始めて空きスペースを塗りつぶすだけで済みます。

于 2011-03-31T15:38:20.823 に答える
1

あなたの無効なケースは、空き領域が 2 つの部分に分割されているためですよね? その場合、大まかな方法​​は、建物の配置後に空きスペースを塗りつぶし、接続されたスペースが正しいサイズ (建物の配置前よりも 2 マス少ない) であるかどうかを確認することです。それは過剰に思えます。自由空間の正方形のグラフがまだ接続されているかどうかを本当に知りたい. より具体的には、新しい建物の周りのすべての自由空間の正方形がまだ接続されているかどうかを知りたいと考えています。それらはローカルに接続する必要がありますか、それともパスを任意に長くすることができますか? つまり、これは有効ですか:

XXXXXXXXX
XXX
XXXXXX
XXXXXX
XOXX
XXOOXX
XXOOXX
XXXX
XXXXXX
XXXXXX

これで問題がなければ、パスが非常に長くなる可能性があるため、これは難しい問題です。

于 2011-03-22T18:42:28.167 に答える
1

新しい建物が直交して隣接していないことを確認することで、問題のケース 1 のようなケースが排除され、新しい建物が元の建物のいずれかと隣接していないことを確認することで、問題のケース 2 がクリアされます。

これは、問題ケース 2 よりも圧迫されていないと安全に想定できる場合に機能するはずです。出口の正方形が 1 つしかない場合、上記で提案された「1 つ以下」の条件に違反する必要がある唯一の解決策です。

于 2011-03-22T18:29:57.950 に答える