Алгоритм «затопления» территории

Question

Мне нужно осмотреть все ячейки сетки, до которых может дойти мой игровой персонаж. Для этого мне нужно начать с позиции персонажей, а затем «затопить» область, чтобы найти все доступные ячейки (например, ячейки, которые не заблокированы стеной).

На этом чертеже игрок - 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 

Есть ли хороший итерационный алгоритм для этого? В настоящее время я делаю это рекурсивно.

Answer 1

Поместить начальную позицию в очередь.

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

Answer 2

Вы можете использовать BFS .Представьте область в прямоугольной сетке.Каждая ячейка сетки является вершиной в графе, и между двумя вершинами есть ребро, если и только если обе ячейки не являются стенками и соседние ячейки.