CODEWITHSUNDEEP
algorithmlanguage-agnosticflood-fill
Paul Manta
Paul Manta

Reputation: 31577

Algorithm for 'flooding' an area

I need to inspect all the cells of a grid that my game character can reach. To do this, I need to start from the characters position and then 'flood' the area to find all the reachable cells (cells that are not blocked by a wall, for example).

In this drawing, the player is P and the walls that block the player are represented by X. I need to inspect all cells in the area in which the player is positioned.

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

Is there any nice iterative algorithm for doing this? Currently I'm doing this recursively.

Upvotes: 1

Views: 188

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183878

Put the initial position in a queue.

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

Upvotes: 2

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

You can use BFS. Represent the area in a rectangular grid. Each cell of the grid is a vertex in the graph and there is an edge between two vertices if and only if both cells are non-walls and the cells are neighbouring.

Upvotes: 1

Related Questions