1

ゲーム キャラクターが到達できるグリッドのすべてのセルを検査する必要があります。これを行うには、キャラクターの位置から始めて、到達可能なすべてのセル (たとえば、壁によってブロックされていないセル) を見つけるために領域を「塗りつぶす」必要があります。

この図では、プレイヤーは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

これを行うための優れた反復アルゴリズムはありますか? 現在、私はこれを再帰的に行っています。

4

2 に答える 2

2

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

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-25T14:11:13.373 に答える
1

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

于 2012-03-25T14:11:15.153 に答える