1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Are you attempting to implement it now? \$\endgroup\$ Commented Dec 29, 2012 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\$ Commented Dec 29, 2012 at 6:06
  • \$\begingroup\$ Let me know if you need anymore help or if anything is unclear. \$\endgroup\$ Commented Dec 29, 2012 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\$ Commented Dec 29, 2012 at 6:08

1 Answer 1

Reset to default
4
\$\begingroup\$

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.
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.