Hexagonal Map Madness! (Part 2) - Division Between Players

Last time, we took a look on how to generate hexagonal maps using a method called "drunkard walk". Now that we have randomly generated maps we like, I think it's time to see how we could set up areas for each player.

First, before we dive into the areas, we have to make some additions to the code we wrote last time. :)

Storing Neighbors

To make life easier, we can keep track of each cell's neighbors. As you probably already know, a hexagonal cell can have at most six neighbors. These neighbors can be stored as references in the Hex class like this:

public class Hex
{
 private int x = 0; // X coordinate
 private int y = 0; // Y coordinate
 private HashSet<hex> neighbors; // Neighbors        

 public Hex(int x, int y)
 {
  this.neighbors = new HashSet<hex>();
  this.x = x;
  this.y = y;
 }

 public HashSet<hex> getNeighbors()
 {
  return this.neighbors;
 }

 public void addNeighbor(Hex hex)
 {
  this.neighbors.add(hex);
 }

 public int getX()
 {
  return this.x;
 }

 public int getY()
 {
  return this.y;
 }
}

Wow, the word "neighbor" really starts to look funny when you write it that many times. Anyway... Note that we also added 'get' methods for the coordinates, as we will need them later on.

Now that we have the possibility to keep track of the neighbors, we can modify the map generation algorithm to store the references. It is wise to do this neighbor referencing stuff right after the map generation, as it (in most cases) has to be done only once per map. Here's how we do it:

public HashSet<Hex> drunkardWalk(int size, int steps)
{
 // A set of hexagon cells
 HashSet<Hex> map = new HashSet<Hex>();
 // We'll start from the origin
 Hex root = new Hex(0, 0);
 map.add(root);

 // The main generation loop. We will continue
 // walking until we have met the total size 'size'
 while(map.size() < size)
 {
  // (Check part 1 for this)
 }

 // Set up the neighbor references
 for(Hex hex : map)
 {
  for(Hex other : map)
  {
   if(hex == other) continue;
   if(hex.getX() == other.getX())
   {
    if(hex.getY() == other.getY() - 1 ||
       hex.getY() == other.getY() + 1)
    {
     hex.addNeighbor(other);
    }
   }
   else if(hex.getY() == other.getY())
   {
    if(hex.getX() == other.getX() - 1 ||
       hex.getX() == other.getX() + 1)
    {
     hex.addNeighbor(other);
    }
   }
   else
   {
    if(hex.getX() % 2 == 0)
    {
     if(hex.getX() == other.getX() - 1 &&
        hex.getY() == other.getY() - 1)
     {
      hex.addNeighbor(other);
     }
     else if(hex.getX() == other.getX() + 1 &&
       hex.getY) == other.getY() - 1)
     {
      hex.addNeighbor(other);
     }
    }
    else
    {
     if(hex.getX() == other.getX() - 1 &&
        hex.getY() == other.getY() + 1)
     {
      hex.addNeighbor(other);
     }
     else if(hex.getX() == other.getX() + 1 &&
       hex.getY() == other.getY() + 1)
     {
      hex.addNeighbor(other);
     }
    }
   }
  }
 }
}

Phew! I know this isn't the most efficient (or the most clear, for that matter) way of doing this, but it gets the work done. Remember that if you are not doing "sides-up" layout, you have to swap X and Y coordinates in some cases. You could speed this up by doing other.addNeighbor(hex) as well and checking for existing neighbor situations before doing the jungle of 'if' checks, although it adds to the complexity as well.

Well, we managed to get through that, and now it's time for the actual area division!

Starting Areas and Neutral Areas

Okay, time to assign cells to players. First off, let's add 'owner' property to the Hex class:

private int owner = -1;

public int getOwner()
{
 return this.owner;
}

public void setOwner(int owner)
{
 this.owner = owner;
}

In this code, the 'owner' is just a number of the player. '0' is the first player, '1' is the second player and so on. '-1' means that the cell is not owned by anyone (e.g. it's neutral).

Let's start with a scenario that we want each player to have an equal amount of continuous area when the game starts, and the rest of the map is "neutral", that is, not assigned to anyone. This is rather simple to achieve: for each player, we choose a root cell (pretty much like we did in the drunkard walk method), and expand the area from that cell until we have the size we want.

// Generate a map (check the part 1!)
HashSet<Hex> map = drunkard(150, 50);

// Convert the set to an array
Hex[] mapArray = map.toArray(new Hex[map.size()]);

// Generate starting areas for each player
for(int i = 0; i < playerCount; ++i)
{
 // Select randomly until we have a hex with six neighbors
 Hex root = null;
 while(root == null)
 {
  int cellIndex = (int)(Math.random() * map.size());
  Hex tmp = mapArray[cellIndex];
  if(tmp.getNeighbors().size() == 6 &&
     tmp.getOwner() == -1)
  {
   // Check that the neighbors are neutral
   boolean suitable = true;
   for(Hex n : tmp.getNeighbors()
   {
    if(n.getOwner() != -1)
    {
     suitable = false;
     break;
    }
   }

   // Neighbors not neutral, pick a new root...
   if(!suitable) continue;
   
   // The root is suitable!
   root = tmp;
  }
 }

 // Now, 'root' is the center cell, we can set
 // the owners to 'root' and its neighbors
 root.setOwner(i);
 for(Hex neighbor : root.getNeighbors())
 {
  neighbor.setOwner(i);
 }
}

There we go, now we have a simple population method. Here's what the result looks like:

Simple map population with three players

The way the area should be expanded is pretty much up to you. If you want a nice, circular area, you add the root cell plus all the neighboring cells - although if you want to have seven cells per area, you must choose the root cell so that it has six neighbors, just like in the code exampla above. Another method could be to use the drunkard walk with suitable step value. This approach will produce (usually) non-uniform areas, if you wish to get that kind of areas.

Well, that's it for now. The next post will be about populating the map in a bit more difficult fashion. Stay tuned. :)