# Algorithm to select all cells inside rooms/regions

I have a 2d game map consisting of several 'rooms'

For example, here is a 2D map grid: (Brown cells = wall tiles) If I click on a tile (that isn't brown), I would like to obtain an array of all the cells in the region that I clicked. (If the region is bounded by brown tiles, otherwise do nothing)

For example, there are two regions in the image above, both colored in grey. If I clicked cell (4,4) I would get a 4x5 array of cells starting at (3,3).

Does anyone know a good performance efficient algorithm for this? I need to account for non-square rooms ideally.

This is called floodfill. You can look it up on Wikipedia.

One way of implementing consists of having a list of visited squares v and pending squares p, and do something like

v = {}
p = {}
p <- (x, y)
while p is not empty
(this_x, this_y) = p
remove p from p
if (this_x, this_y) is not in v, and (this_x, this_y) is not a wall
v <- (this_x, this_y)
p <- (this_x + 1, this_y + 1)
p <- (this_x + 1, this_y - 1)
p <- (this_x - 1, this_y + 1)
p <- (this_x - 1, this_y - 1)
end
end


The squares in the room are those left in v when you finish.

There are also several ways to optimize this, but you should get the main idea.

• This algorithm easily goes out of bounds and does not account for a selection outside the area bounded by walls. Have to be careful with it. – MichaelHouse Jan 25 '13 at 19:23
• Depends on the language in which you implement it, and the semantics you give to values out of bounds. This is perfectly safe in lua, if you consider nil values to be walls. – Panda Pajama Jan 26 '13 at 5:13

A simple flood fill algorithm will suit you just fine. Have it make a list of tiles as it progresses. If a neighboring tile is outside the bounds of your grid, then that entire region is not bounded by the brown tiles, and can be ignored.