Find connected hex of same color

Question

I'm using Lua. I have a hex map. It is randomly generated into an table.

hexmap[y][x].color = "red"

I wish to find each "group" of hex's. i.e. all hex's of the same color that connect to each other will belong to one group.

As an example, in the following image:

The result should be:

1 blue group (all hex's connect) 3 green groups 1 black group

Any suggestions?

Thank you.

Answer 1

Start from the top left and use a BFS flood fill to get all of the same color cells of the starting cell (while marking the cells as visited). Once the BFS finishes keep traversing your hexmap looking for unvisited cells. If you find an unvisited cell start another BFS flood fill (same idea as before). To determine if you have finished either keep a count of the visited cells and see if it matches your N*M hexmap array, or just keep traversing your hexmap looking for unvisited cells.

Example (using your picture above):

1. i = 0, j = 0 (top left of hexmap) [0,0], color is blue.
2. BFS flood fill the starting point only looking for blue cells, this will mark all blue cells as visited.
3. look for the next unvisited cell, which will be the green cell at [0,3].
4. repeat step 2, but instead of blue cells, you are looking for green cells.
5. repeat step 3 and 4 until you are done.