How to divide hex grid evenly among n players?

Question

I'm making a simple hex grid based game, and I want the map to be divided evenly among the players. The map is created randomly, and I want the players to have about equal amount of cells, with relatively small areas. For example, if there's four players and 80 cells in the map, each of the players would have about 20 cells (it doesn't have to be spot-on accurate). Also, each player should have no more than four adjacent cells. That is to say, when the map is generated, the biggest "chunks" cannot be more than four cells each.

I know this is not always possible for two or three players (as this resembles the "coloring the map" problem), and I'm OK with doing other solutions for those (like creating maps that solve the problem instead). But, for four to eight players, how could I approach this problem?

Answer 1

This is what I would do:

1. Assign all cells to random players. On big maps this should be very likely to produce pretty even numbers of tiles for all players, on smaller maps you'll probably need to do some corrections.
2. Break up chunks that are too large. The easiest thing to do would be take all tiles in chunks and again assign each tile randomly.
3. In case of unbalanced numbers of cells (e.g. player A has 24 cells, player B has 16), reassign a couple of the cells from overrepresented players to underrepresented players.
4. Check again for chunks. If step 3 introduced new chunks, go back to step 2. If not, nice map!

Answer 2

Assuming you have a hexmap of n cells in total, and p players, where p <= n, the best way to to tackle this is through round-robin distribution via cellular automata (CA).

Initialisation

Randomly (and/or using some or other heuristic, such as distance from map centre) pick a starting cell for each player. Since p <= n, this shouldn't be a problem.

Cellular automata

You require full connectivity between your hex cells. I would suggest a 6-neighbor array per cell:

class Cell
{
   //... other members...
   Cell[6] neighbours = new Cell[6];
}

Use of fixed size arrays allows the concept of topographical directions between cells to exist, which a list or vector would not. I recommend this, as it may make certain navigation ops easier.

You can also store your hexmap in a 2D array, with offsets per row. This may however be slightly less intuitive than storing a neighbour array per cell, only because of the geometric offset on every other row.

Make sure every cell is connected to everything that is a neighbour. You can do this row by row, cell by cell as you generate the full hexmap. P.S. If you ultimately want a non-rectangularly bounded hexmap, you can then simply remove individual cells and references to those cells, to form negative spaces, allowing you to create an organic map outline.

Round-robin distribution

Pseudocode:

count number of neutral cells in entire map, minus those starting cells taken by players
while neutral cells remain (or while true)
   for each player
      if player has not yet reached expected territory size in cells
         for each cell already constituting this player's territory
           if territory can grow by one cell into a neutral neighbour
              grow into neighbour
              reduce neutral cell count for entire map by one
              if no more neutral cells remain in map
                 break out of outermost while loop immediately
              else
                 continue to next player immediately
begin game

This algorithm will give each player a chance to grow its territory by one, in a round robin fashion, provided that player's territory still has valid growing space. If certain players are blocked from growing further, the algorithm will in spite of this continue to grow the territories of players who do still have valid growing space. You could easily restrict every player to the same number of cells as soon as one of them hits a limit, but that should be easy enough for you to figure out, if desired.

This will provide maximally-sized "home territories" for each player. If you want to have "island" territories in addition, in order to fulfill the cell count quota for that player, then once a player runs out of local space to grow, you can then pick a new start cell from the neutral cells list and proceed with the same "growth" process, from there. This way, you will end up with nicely-sized, coherent sets of islands for each player, rather than random noise.

Answer 3

Another approach would be to start with a distribution that's 'fair' but regular, and then use an appraoch similar to Simulated Annealing to break up the regularity without losing the fairness:

• Start by assign colors to all the cells of your grid in a regular pattern (e.g., have a repeating '123412341234' pattern on the first row, followed by '341234123412' on the next, etc.). This may lead to a non-uniform distribution of colors if your map is particularly poorly shaped, but I'm presuming that you're starting with a fixed map, so you should be able to find some equidistributed regular coloring of it.
• Then repeat the following for as many steps as you feel like (there is no real 'doneness' criterion, so experimentation will tell you what a minimum reasonable number of steps is):
  • Pick two elements of the grid at random
  • If they have the same color, try again (there's no point otherwise, since then swapping will be a no-op. You only have a 1/4 chance of hitting the same color, and a 1/16 chance of hitting the same color twice in a row, so you should never have to retry too much)
  • Provisionally swap the colors of those two elements
  • Test the sizes of the newly-formed regions in the elements' locations after the swap:
    • do a simple flood-fill outwards from each element's new spot to determine how large a region of that color the swap would make.
  • If either of these two regions is larger than your threshold, undo the provisional swap; otherwise, 'finalize' the swap of the two elements' colors.

The keys here are that the fact you're swapping two spots means that you never unbalance the colors, and likewise the test that you do before finalizing your swap ensures that you never create regions that are too large. If you have some means of displaying your grid, you could even visualize this process to watch how it 'builds' its regions through the repeated swaps.

If you can't start with an equidistributed regular coloring, incidentally, then you should still be able to do something similar to equidistribute the coloring: while your coloring isn't equidistributed, pick an element at random; then, if it's one of the over-represented colors, provisionally set its color to one of the under-represented colors and then check to make sure that doesn't create too large a region of the new color.