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.

@dan4 what is your current understand of path-finding and the algorithms used? There are ways to optimize such as dividing up your work into sectors, cache calculated paths, not having every object seek a path at the exact same time, and utilize paths already established based on current positions, however you also need to make sure you're not re-checking the same node and checking nodes which you know beforehand are not valid to begin with.

Depending on your understanding of the various algorithms you'll want to do some of your own testing to see which works best for you then worry about optimization if it becomes necessary.

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.

What code have you already written based on your knowledge of the above? Where are you seeing a bottleneck in your approach.

Here is an example, if you know all those red nodes are locked in, all you have to do is pick an edge node which is available and by using BFS for example you'll find the holes by searching all available nodes less the ones marked in red. The left over nodes which could not be reached are going show up as your holes: ‘[[(2,3), (2,4), (3,3)], [(3,1)]]’. You'll want to cycle through all your edges as starting at (0,0) will never reach (0,2).

I wouldn't bother with optimization yet until you're certain you need to do it, and I simply don't have the time to write up posts about the various methods at this time but I would suggest doing some searches online in your free time.

@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.