領域をフラッディングするアルゴリズム

私のゲームキャラクターが到達できるグリッドのすべてのセルを調べる必要があります。これを行うには、文字の位置から開始し、次に到達可能なすべてのセル（壁などでブロックされていないセル）を見つけるために領域を「フラッディング」する必要があります。領域をフラッディングするアルゴリズム

この図では、プレーヤーはPであり、プレーヤーをブロックする壁面はXです。私は、プレイヤーが置かれている領域のすべての細胞を調べる必要があります。

X X X X X X X X 
X  X X  X 
X P  X X X X 
X X   X X 
X X X X X X X 
X X X X X X X X

これを行うための素晴らしい反復アルゴリズムはありますか？現在私はこれを再帰的にやっています。

出典

2012-03-25 Paul Manta

@sch Nothing反復的な選択肢があるかどうかを知りたいだけです。 –

私は再帰的な解決策が最高だと思います。 –

ウィキペディアには数多くのアルゴリズムがありますが、確か1つはあなたのために働くでしょう：http://en.wikipedia.org/wiki/Flood_fill –

キューに初期位置を入れます。

while queue is not empty 
    remove an entry from the queue 
    add all reachable neighbours not yet marked to the queue (unless they are already in) 
    mark position as reachable 
end while

出典

2012-03-25 14:11:13

これは反復的ではなく、あなたは単に再帰を明示的なスタックに置き換えました。 – orlp

@Nightcracker：間違っています。キューであり、スタックではありません。もう一度モドルをしてください... – wildplasser

そして、それはどのように反復ではありませんか？ –

BFSを使用できます。四角形のグリッド内の領域を表します。グリッドの各セルはグラフの頂点であり、両方のセルが非壁であり、セルが隣接している場合にのみ2つの頂点の間にエッジがあります。

出典

2012-03-25 14:11:15

領域をフラッディングするアルゴリズム

答えて

関連する問題