15
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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!
\$\endgroup\$
  • \$\begingroup\$ PS I don't think this problem is ever impossible, the map coloring problem is quite different (for one thing it's the other way around, shapes->colors instead of colors->tile assignments). \$\endgroup\$ – Junuxx Oct 17 '13 at 15:53
  • \$\begingroup\$ I like this approach quite a bit, but isn't there a possibility for it to run for a long time, trying to balance the area sizes? \$\endgroup\$ – manabreak Oct 20 '13 at 7:06
  • 1
    \$\begingroup\$ @manabreak: I made something to try it out. With a small change to step 2 (reassign by cycling through all players instead of reassigning randomly) it works quite well. I'll try to write it up when I have time. \$\endgroup\$ – Junuxx Oct 20 '13 at 13:04
  • 1
    \$\begingroup\$ That looks exactly what I was looking for. :) \$\endgroup\$ – manabreak Oct 20 '13 at 13:50
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ While you provide excellent documentation and pseudocode for your algorithm, I am not sure this matches what the questioner asks about. The question mentions 'biggest "chunks" cannot be more than four cells each', whereas your algorithm creates as large a connected group as possible. \$\endgroup\$ – fnord Oct 17 '13 at 17:05
  • \$\begingroup\$ @fnord No, it doesn't. You did not read my answer properly. I explicitly put a limit in the pseudocode: "if player has not yet reached expected territory size in cells". Please remove your downvote. Feel free to check the revision history on the question to satisfy yourself that this was the case since before your comment and downvote. \$\endgroup\$ – Engineer Oct 17 '13 at 17:06
  • \$\begingroup\$ The question asks to have "no more than four adjacent cells", yet for each user to have an expected portion of the map. This, to me, implies e is going for something more akin to how Risk games randomly apportion the map out for all of the players. Your answer divides the map into "maximally-sized 'home territories'". True, your algorithm stops when the expected territory size limit is reached, but I do not see a way for that player to get new "islands", though you do mention it in later text. \$\endgroup\$ – fnord Oct 17 '13 at 17:24
  • \$\begingroup\$ @fnord Your logic is at fault. In your final sentence, you admit that my algorithm stops at island size n, and thereafter contradict yourself by saying that you "do not see a way" yet that I do "mention [how to get islands] in later text". Have I or have I not answered the question? This generalised algorithm may be used to either scatter cells (by limiting n to 1) or to create islands (by setting n > 1). So you have, in one single algorithm, not only the ability to scatter, but also to group. How does this not answer the OP's question? How is it worthy of a downvote? \$\endgroup\$ – Engineer Oct 17 '13 at 17:37
  • \$\begingroup\$ I would edit my comment above, but it is too late. "I do not see a way in your algorithm". though you do mention the concept in later text. \$\endgroup\$ – fnord Oct 17 '13 at 17:56
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Stochastic approaches are inefficient. For an approach like mine that takes considered steps, runtime approaches O(n) for n map cells. For your algorithm, it's O(n*m), where m is the number of cells desired per island (actually, for each potential island). Always best to aim for algorithms that have a readily estimable runtime. Instead of fixing a haphazardly-generated map, better to generate a map that isn't broken or haphazard in the first place, in n steps, thus maintaining a controlled, efficient process. \$\endgroup\$ – Engineer Oct 18 '13 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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