I'm making a game on a hexagon grid.

A ‘region’ is a list of all the tiles of a certain colour that are connected.

I'm trying to devise a function that will return the ‘holes’ in a region.

The function would take as input an array of tiles, which you can assume are all connected to one another.

The function will return the array of arrays of tiles which are the ‘holes’ in the region.

For example, (see image below) with an input of an array which contains all the tiles coloured red, I want to return something like:

[[(2,3), (2,4), (3,3)], [(3,1)]]

Any advice on a possible approach would be appreciated.

Write a floodfill routine and start it on a hex that you know is part of the fully connected tiles (or the reachable first tile, or the initial position or something else). Those are the tiles that are non-relevant.

Then find the tiles outside the non-relevant set, and run a floodfill on one of them. That's a hole. Continue finding other tiles that are outside the non-relevant set and outside any holes you found thus far, and use floodfill to find their set of tiles.

Thanks @Alberth

Let me check I understand you correctly

From the set of all possible tiles,

subtract the region,

subtract the area which is outside the region, and can be found by a flood fill from a starting tile

what's left are the holes

separate the holes

So I guess there are two issues with this approach, #1 is picking a good starting tile to do the flood fill, #2 is potentially if the total set of tiles is very large.

Hi @Rutin. I'm quite confident at implementing a variety of the most common path-finding algorithms. Could you elaborate on how your ways to optimize would be applied within an approach to the specific problem I have? Thanks.

dan4 said:
So I guess there are two issues with this approach, #1 is picking a good starting tile to do the flood fill, #2 is potentially if the total set of tiles is very large.

I don't see so many options of optimization here, but at least we know tiles at the boundary can not be a hole, so no need to start flood fill for them.

So you could loop over all interior cells in the outer loop.

Skip if the cell has a color, otherwise floodfill with a new color.

During the flood fill you could check for reaching a boundary cell. If so, the current region is not a hole. (But you could finish the fill regardless, so all cells in the region become colored and skippable.)

If you did not reach the boundary, the colored region must be a hole - memorize that set and continue.

@JoeJ Boundary tile ≠ hole tile is a good point. Thanks for that.

@Rutin I've written lots and lots and lots of code in the past based on my knowledge of the above. Thanks for your example approach for the specific problem. And thanks for the tip about optimization.

Start with the full set of empty/off-colored tiles, which in your case is the set of all tiles not part of your input.

Pick a tile from the set which is on the border, i.e. “outside”, and perform a flood-fill algorithm against tiles that are also in the set (not referring to color at this point since the initial construction handles the selection criteria). Subtract the result from the set. Repeat this process until no more border tiles exist in the set. What remains are the “inside” tiles, aka holes.

dan4 said:
So I guess there are two issues with this approach, #1 is picking a good starting tile to do the flood fill, #2 is potentially if the total set of tiles is very large.

I am not sure that a region could not have a tile at the border, so I didn't dare making assumptions of safe starting points. At some point you likely have to make assumptions anyway (eg a hole is less than ½ the area), but it's all problem-specific, and without that information I can only guess.

As for size, how large is large? Also, how often do you need this information, and does it ever change? You asked for a way to solve it, without stating any constraints. My algorithm will give you a solution. Criticizing that solution based on information you didn't include in the question is euhm, let's say, non-optimal.