# 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.

-
– Byte56 Jan 24 '13 at 19:09

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[0]
remove p[0] 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. – Byte56 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.

-