Hi,
I'm looking for a way how to detect areas on a grid (hex in my case, but I guess the basic principle would be the same for squares) that are fully enclosed by specific tiles ("walls").
Check the picture for better understanding - that's a random situation, dark blue tiles are the "walls" and bright green are areas (tiles) that I am trying to find. There can be more areas, I need to find all of them.

What came to my mind first was flood fill, but that works from a starting point, which I don't know - I don't know which tile can potentially be in the enclosed area (well, almost all tiles can be).
Then I thought I could simply do the opposite and flood fill the other tiles (white), which would leave the green tiles. But if I started for example in the upper left corner on the picture, the fill would stop very soon.

Do you have any suggestions how this could be done effectively?

Thank you very much for any input.

Tom

Thx, that sounds good, I'll give it a try.
No, the grid isn't going to be huge, I don't know the exact dimensions yet but it will be something like 2x - 4x the size on the image.

Just add every node to an "unvisited" list. Store in each node a pointer (or iterator) to it's counterpart in this list. Now the process is to:

1) Pop a node off the unvisited list and create a new list with the node as it's first element
2) Visit each neighbour of the node, recursively (i.e. flood fill), add them to the current list, and remove from the unvisited list (as each node has a pointer to it's location in the unvisited list, this is O(1)).
3) One of two things will occur; The flood fill will either terminiate, in which case you output the list as fully enclosed, or you'll hit the outer wall, in which case you discard the list as it's not enclosed. In either case, you return to step 1) and repeat until the unvisited list is empty.


This algorithm is O(n) with respect to the number of nodes.

If you want to optimise this solution, you can roll your own list structure that's backed by an array. Insert and delete operations can then be performed without allocation/deallocation, which will speed things up by a great amount. In fact you don't even need separate lists for each set of nodes. You can build the other lists inside the memory of the initial allocation, which allows this algorithm to run with a grand total of 1 call to new and delete.

The search term you need for googling purposes is "connected component labeling" ... The easiest way to do it is to

1. Construct a temporary blank grid.
2. Iterate over the cells of the input grid.
3. For each cell A that is not blue ( in your case ) and that hasn't been marked as discovered do the following
.......... Output A as a seed of a unique connected component.
.......... Perform a floodfill seeded at A that marks the cells of the connected component that A is part of as 'discovered' in the temporary grid.

There are more efficient ways of doing this but probably the above will suffice unless your grids are gigantic.

Thank you very much again, I managed to implement it succesfully.

The key here indeed was the connected-component labeling (http://en.wikipedia....ponent_labeling). I used only it, quite modified because I don't need to differentiate separate areas, I need just two ("outer" and "inner"). So for every label I just store a bool value saying whether tiles with that label are in an enclosed area or not, instead of the otherwise needed equivalence relationship table.

It's all done in two passes (by the CCL), I'm not performing any floodfill.

Thank you very much, both of you. I managed to implement it succesfully.

The search term you need for googling purposes is "connected component labeling" ... The easiest way to do it is to

1. Construct a temporary blank grid.
2. Iterate over the cells of the input grid.
3. For each cell A that is not blue ( in your case ) and that hasn't been marked as discovered do the following
.......... Output A as a seed of a unique connected component.
.......... Perform a floodfill seeded at A that marks the cells of the connected component that A is part of as 'discovered' in the temporary grid.

There are more efficient ways of doing this but probably the above will suffice unless your grids are gigantic.

The key here indeed was the connected-component labeling (http://en.wikipedia....ponent_labeling). I used only it, modified for hexa grid.

It's all done in two passes (by the CCL), I'm not performing any floodfill, so it's pretty straightforward.