Generate equal regions in a hex map

Taking for example large (X by Y) hex map, how can I divide the map into N regions of connected hexes to simulate countries?

The goal is to generate a hex map that looks like a real life map with countries with different shapes but equal sizes.

-

Have you tried Lloyd's Algorithm? The procedure is pretty simple, and will generate fairly regular looking regions (depending on how many iterations you run).

1. Tile the map with blank hexes to start.
2. Choose N hexes at random. These will represent the "center of mass" for each country.
3. Tag each hex with the center hex it is closest to (Voronoi Diagram). Country i is the set of all hexes closest to the i'th center hex.
4. Compute the new center of mass for each country.
5. Repeat steps 3 and 4 as many times as you want to smooth out the generated regions.

You don't have to run it very long to produce a nice looking map. This example required only three iterations.

-
Very nice, and +1 for having an example especially, but I'd be a little worried that these are a little too regular! That said, the results really do look gorgeous particularly at that scale, and it's also an excellent way of seeding other methods. – Steven Stadnicki Jun 11 '13 at 18:38
My example was inspired by a blog post about polygon map generation. The author added some noise to the edges of each region to make a more jagged look (scroll to the bottom to see it). You'd need to use a lot more hexes than I did to make that a viable option, but it's certainly doable. – Michael Kristofik Jun 11 '13 at 18:48

One simple way you could try.

1. Randomly select `n` hexes. Each one will start a group.
2. For each group try to expand the initial hex in a random direction.
3. If all hexes around the chosen hex are occupied, mark as tapped, change hex.
4. Repeat until each group is 20 hex long or have no more space to expand (all hexes tapped).

I didn't test but this should generate Islands and somewhat avoid long thin braces. Also, Most likely there will be neighbors borders but not necessarily each one will be in touch of other, that density will depend on the value of `n`.
Some groups also might be cornered by others and reach less than 20 size, you can assure grown space by spawning the starter hexes at a minimum distance of each other.
Test and tweak as needed.

Also, not related with this problem but very, very useful to working with hexes, visit this page: http://www.redblobgames.com/grids/hexagons/#basics
It aggregates a whole bunch of hex info in a single place with a nice visual.

-
Should probably include a mechanic for group A to give nodes to group B, if group B borders group A and doesn't have anywhere else to go. As long as group A has empty space to expand into to replace the lost nodes. Then it doesn't matter where they started. Since this acts kind of like a "retreat". – Byte56 Jun 11 '13 at 15:03
I'm thinking maybe starting a country at a time, form the corner groups first, then the edges ones would give what I want. I will try it when I get home. – MadCatPT Jun 11 '13 at 15:22
@Byte56 Yeah, I actually thought of something like this a bit during my lunch. If the cornered group have nowhere to grown, it just take a hex of another group and let that group find an empty space at next iteration. It should have some safeguard to avoid 2 cornered groups to infinitely bully each other though. – petervaz Jun 11 '13 at 15:32
Real countries often have boundaries on rivers or mountains. As you're expanding in a random direction, you might try decreasing the probability of expanding if the next hex is on the other side of a river or a mountain ridge. – amitp Jun 12 '13 at 13:58
@amitp If the OP were expecting those factors to be accounted he probably would have mentioned them. I'm not assuming, just working inside the original premisses. – petervaz Jun 12 '13 at 14:10

I definitely think some type of graph structure would make this possible. Basically create an edge between two Hex nodes if they are next to each other to simulate the whole map. However, I am not sure the exact algorithm for generating a "country" within that map. The thing is, depending on how you want the country to "look" you would need different algorithms.

Off the top of my head, I would recommend picking a point and moving outwards from there, picking a random tile within your "growing country" which has an adjacent tile that is not part of the country.

A strategy pattern could be used to switch out algorithms depending on what type of country look you want. http://en.wikipedia.org/wiki/Strategy_pattern i.e. do you want a slim coastline country like chile? Or do you want something that is more round and contained?

Graph properties may also allow you to tweak what you want the end "country" to look like: http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)

Want a large country? Tweak the graph properties and force the generated country (which is just a graph) to have the properties that give it a "look" you will want.

Last but not least, Graphs will also be very useful for defining borders between countries. You could build a graph that has a connection between two nodes if countries border each other. This might be useful for some type of partitioning in your game and will allow you to possibly optimize certain things further along in development.

-

One small note: you say 'looks like a real life map with countries of different shapes but equal sizes), but 'real' countries are vastly different in size even within certain regions — even the 'large' countries of Europe can vary hugely, with e.g. France being more than twice as large as Italy. With that said, there are obviously gameplay regions to try and keep sizes roughly the same - just be aware that a little variation here is probably a good thing!

My initial approach to the problem would be to 'evolve' (rather than 'grow') your regions:

• Start with some concrete division of the map into roughly equal-sized chunks by straight lines (for instance, if you wanted 6 countries, then you might divide the map into three horizontal slices, and then split each of those slices 'on the diagonal' into two pieces). This is obviously easy to do programmatically, especially since it doesn't have to be very exact (in fact, probably shouldn't be very exact).
• Do an initial pass on the division, building a 'boundary' data structure: a set of hexes which have some neighbor currently belonging to a different country. This would also be a good time to tally a count of how many hexes are in each country.

Now, for as long as you want, run the following pseudocode:

``````Pick a random hex A from the boundary list;
Pick a random neighbor B of this hex from a different country;
if (A's country has more hexes than B's country has) {
change hex A to belong to B's country;
} else if (B's country has more hexes than A's country has) {
change hex B to belong to A's country;
} else {
flip a coin to decide which to change;
}
if ( the changed hex's old country has become disconnected ) {
undo and reject this move;
} else {
update the boundary list around the changed hex and its neighbors;
}
``````

This will maintain a rough balance between the size of any two neighboring countries, and the 'disconnected' check (which can be done with a simple flood-fill algorithm) makes sure that no country ever breaks apart into pieces. Updating the boundary list is a constant-time operation - the changed hex will obviously always still be on the boundary, and you can just check its six neighbors to see if any of them has either become a boundary cell (because its neighbor is now in a different country) or stopped being a boundary cell (because its neighbor's in the same country now), modifying the boundary set as needed.

For a refinement of this approach, you can even make the condition of which hex to change a bit randomized - rather than always 'balancing' the two countries, you can always make the swap with a certain probability, and even gradually diminish that probability over time (similar to the cooling process in a Simulated Annealing algorithm) to start to force them to be roughly the same size.

Note that this won't guarantee that all areas are exactly the same size (which is impossible unless N perfectly divides your grid size anyway), and it won't even guarantee that all countries are within one hex of each other in area; it should guarantee (run for enough iterations) that each country is no more than one hex larger or smaller than each of its immediate neighbors, though.

-