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.