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:

Hex map

The result should be:

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

Any suggestions?

Thank you.

  • \$\begingroup\$ Are you attempting to implement it now? \$\endgroup\$ Dec 29 '12 at 6:00
  • \$\begingroup\$ Yes... I will let you know how I get on. Will accept if it works but looks like it will! \$\endgroup\$ Dec 29 '12 at 6:06
  • \$\begingroup\$ Let me know if you need anymore help or if anything is unclear. \$\endgroup\$ Dec 29 '12 at 6:07
  • \$\begingroup\$ 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. \$\endgroup\$ 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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.