Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
Related: gamedev.stackexchange.com/questions/31909/… –  Byte56 Jan 24 '13 at 19:09

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
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
1  
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.

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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