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

For example, here is a 2D map grid: (Brown cells = wall tiles)

enter image description here

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.


2 Answers 2


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)

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.

  • \$\begingroup\$ 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. \$\endgroup\$
    – House
    Commented Jan 25, 2013 at 19:23
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 26, 2013 at 5:13

A simple flood fill algorithm will suit you just fine.

enter image description here

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .