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.


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\$ – MichaelHouse Jan 25 '13 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\$ – Panda Pajama Jan 26 '13 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.