Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
Are you attempting to implement it now? – Luis Estrada 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! – Chris Evans Dec 29 '12 at 6:06
Let me know if you need anymore help or if anything is unclear. – Luis Estrada 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. – Chris Evans Dec 29 '12 at 6:08
up vote 3 down vote accepted

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.
share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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