# Find connected hex of same color

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.

• Are you attempting to implement it now? Dec 29 '12 at 6:00
• Yes... I will let you know how I get on. Will accept if it works but looks like it will! Dec 29 '12 at 6:06
• Let me know if you need anymore help or if anything is unclear. Dec 29 '12 at 6:07
• Will do - it's 6am here so might sleep in a minute and carry on in a while. It's a bit mind boggling for a first go lol. Dec 29 '12 at 6:08

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.

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.