Algorithm to select all cells inside rooms/regions

Question

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.

Answer 1

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)
        // Add the adjacent squares...
        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.

Answer 2

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.