Hex Map Area Borders

Today we’re going to learn how to create a nice border around the perimeter of an area in a hex map using Unity and a LineRenderer. Here I have it as a dotted purple line but you can make it look like anything you want with the flexibility of the line renderer!

The foundation of the hex code here is adapted from the Hex Map Series by Catlike Coding which has been super helpful for getting started. So if there’s any bits of code I missed here it’s likely from there, but please let me know in the comments if you’re getting stuck or confused anywhere.

First up we’ll need a little background code for the data we’ll be operating on for the rest of this article.

/* HexDefinition.cs */

using UnityEngine;
using System.Collections.Generic;

public class HexCell : MonoBehaviour {

  public HexCoordinates coordinates;

  HexCell[] neighbors = new HexCell[6];

  public HexCell GetNeighbor (HexDirection direction) {
    return neighbors[(int)direction];
  }

  public void SetNeighbor (HexDirection direction, HexCell cell) {
    neighbors[(int)direction] = cell;
    cell.neighbors[(int)direction.Opposite()] = this;
  }
}

public class HexCity : MonoBehaviour {

  public HexCell Cell {get; set;}

  //How much of a max radius the city influences on the surrounding cells
  public int AreaOfInfluence{ get{ return 2; } }
}


public struct HexCoordinates {

  public const float outerRadius = 0.48f;
  public const float innerRadius = outerRadius * 0.866025404f;

  [SerializeField]
  private int x, z;

  public static Dictionary<HexCornerDirection, Vector3> corners = new Dictionary<HexCornerDirection, Vector3>(){
    {HexCornerDirection.N,  new Vector3(0f, outerRadius, 0f)},
    {HexCornerDirection.NE, new Vector3(innerRadius, 0.5f * outerRadius, 0f)},
    {HexCornerDirection.SE, new Vector3(innerRadius, -0.5f * outerRadius, 0f)},
    {HexCornerDirection.S,  new Vector3(0f, -outerRadius, 0f)},
    {HexCornerDirection.SW, new Vector3(-innerRadius, -0.5f * outerRadius, 0f)},
    {HexCornerDirection.NW, new Vector3(-innerRadius, 0.5f * outerRadius, 0f)},
  };
}

public enum HexDirection {
  NE, E, SE, SW, W, NW
}

public enum HexCornerDirection {
  N, NE, SE, S, SW, NW
}

public static class HexDirectionExtensions {
  public static HexDirection Opposite (this HexDirection direction) {
    return (int)direction < 3 ? (direction + 3) : (direction - 3);
  }

  public static HexDirection Previous (this HexDirection direction) {
    return direction == HexDirection.NE ? HexDirection.NW : (direction - 1);
  }

  public static HexDirection Next (this HexDirection direction) {
    return direction == HexDirection.NW ? HexDirection.NE : (direction + 1);
  }

  public static HexDirection Previous2 (this HexDirection direction) {
    direction -= 2;
    return direction >= HexDirection.NE ? direction : (direction + 6);
  }

  public static HexDirection Next2 (this HexDirection direction) {
    direction += 2;
    return direction <= HexDirection.NW ? direction : (direction - 6);
  }

  public static HexCoordinates Offset(this HexDirection direction){
    switch(direction){
      case HexDirection.NE:
        return new HexCoordinates(0, 1);
      case HexDirection.E:
        return new HexCoordinates(1, 0);
      case HexDirection.SE:
        return new HexCoordinates(1, -1);
      case HexDirection.SW:
        return new HexCoordinates(0, -1);
      case HexDirection.W:
        return new HexCoordinates(-1, 0);
      case HexDirection.NW:
        return new HexCoordinates(-1, 1);
    }
    return new HexCoordinates(0, 0);
  }

  //inverse of above and only handles neighboring coordinates
  public static HexDirection CoordDirection(HexCoordinates first, HexCoordinates second){
    var xDiff = second.X - first.X;
    var zDiff = second.Z - first.Z;

    if(xDiff == 0 && zDiff == 1){
      return HexDirection.NE;
    }
    if(xDiff == 1 && zDiff == 0){
      return HexDirection.E;
    }
    if(xDiff == 1 && zDiff == -1){
      return HexDirection.SE;
    }
    if(xDiff == 0 && zDiff == -1){
      return HexDirection.SW;
    }
    if(xDiff == -1 && zDiff == 0){
      return HexDirection.W;
    }
    if(xDiff == -1 && zDiff == 1){
      return HexDirection.NW;
    }

    Debug.LogWarning("Getting default coord direction because you're comparing not neighbor cells");
    return HexDirection.NE;
  }

  public static HexCornerDirection Previous (this HexCornerDirection direction) {
    return direction == HexCornerDirection.N ? HexCornerDirection.NW : (direction - 1);
  }

  public static HexCornerDirection Next (this HexCornerDirection direction) {
    return direction == HexCornerDirection.NW ? HexCornerDirection.N : (direction + 1);
  }
}

1. Find the Area#

The first step is finding the set of cells that we’ll use to find the perimeter around. For my implementation I started with a variation on a flood fill algorithm that is also close to a Voronoi diagram. There’s a great article here about it as well as many more great articles about hex maps, pathfinding and much more.

Since my city areas are changing infrequently I update them at startup and whenever one of the cities grows in influence (which affects their max radius of influence).

  /* FindCityInfluencedTiles.cs */

  //Find each cities area of influence that flood fills out from each city to a max distance based on the city pop
  public Dictionary<HexCell, HexCity> FindCityInfluencedTiles(List<HexCity> cities) {
    var frontier = new List<HexCell>();
    var costSoFar = new Dictionary<HexCell, int>();
    var seed = new Dictionary<HexCell, HexCity>();

    //Set the distance to 0 at all start poitns and each start point its own seed
    foreach(var city in cities){
      frontier.Add(city.Cell);
      costSoFar[city.Cell] = 0;
      seed[city.Cell] = city;
    }

    while (frontier.Count > 0) {
      var current = frontier[0];
      frontier.RemoveAt(0);
      var maxDistance = seed[current].AreaOfInfluence;

      for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
        HexCell next = current.GetNeighbor(d);
        if(!costSoFar.ContainsKey(next) && costSoFar[current] < maxDistance){
          costSoFar[next] = costSoFar[current] + 1;
          seed[next] = seed[current];
          frontier.Add(next);
        }
      }
    }

    return seed;
  }

  void UpdateCityInfluencedTiles(){

    var cityInfluencedTiles = grid.FindCityInfluencedTiles(cityList);
    var grouped = cityInfluencedTiles.GroupBy(x => x.Value);
    foreach(var groupKey in grouped){
      groupKey.Key.influencedCells = groupKey.Select(x => x.Key).ToList();
    }
  }

2. Find the perimeter of the area#

Now that we have a set of cells for an area we need to find the cells on the perimeter of the area so that we can then find the points along edges of the cells for the line to go.

/* FindPerimeterLoop.cs */

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class HexPerimeter
{

  public static List<HexCell> FindPerimeterLoop(List<HexCell> cells){
    //start by finding the top right most cell to start a loop from
    var startCell = cells.OrderByDescending(t => t.coordinates.Z).ThenByDescending(t => t.coordinates.X).FirstOrDefault();

    //trace right and down as much as we can until the bottom is found, then start going left and up
    //It's possible to go back the way we came if there is a one cell peninsula
    var perim = new List<HexCell>();
    var travelDirection = HexDirection.SE;
    var currentCell = startCell;
    do
    {
      var directionPriorities = directionPriority(travelDirection);
      foreach (var direction in directionPriorities)
      {
        var nextCell = currentCell.GetNeighbor(direction);
        //Add if in the original set of cells
        if (cells.Any(c => nextCell == c))
        {
          perim.Add(currentCell);
          travelDirection = direction;
          currentCell = nextCell;
          break;
        }
      }
    }
    while (currentCell != startCell);

    return perim;
  }

  //Which way should we go given which way we came from?
  //The way the directions are set up this works out to going around clockwise given the start at top
  static IEnumerable<HexDirection> directionPriority(HexDirection dir){
    yield return dir.Previous();
    yield return dir;
    yield return dir.Next();
    yield return dir.Next2();
    yield return dir.Opposite(); //Last resort go back the way we came
  }
}

This works by finding the top right-most cell and then marches around the perimeter by prioritizing the direction to travel in. For example, if our last move was to the cell south east of us our priorities would look like this:

This priority ordering will ensure we stay along the outside edge of the area.

We also need to include the 5th priority as going back to where we came from in the case where there is a peninsula of cells that stick out from the rest. In that case our perimeter will contain those cells twice as the algorithm marches out and back, but this is what we want so that the line can follow around the outside.

3. Find the points for the line#

And now for the fun part: finding all the world coordinates for our line renderer. We’ll do this by iterating over the perimeter cells keeping track of which direction we came from and which direction we’re going. These directions will let us determine which kind of “bend” we’re dealing with. This bend type will then determine how many corners of the current hex cell we’ll need to add to our line before moving on.

/* GetLinePositions.cs */

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class HexPerimeter
{
  //Convert the cell perim to a list of world coords on the hex border around the cells
  public static List<Vector3> GetLinePositions(List<HexCell> cellPerimeter){
    var ret = new List<Vector3>();

    HexDirection prevDir;
    HexDirection nextDir;
    HexCell firstHexCell = cellPerimeter[0];
    HexCell lastHexCell = cellPerimeter[cellPerimeter.Count - 1];
    HexCell nextHexCell = null;
    for(int p = 0; p < cellPerimeter.Count; p++){
      var cell = cellPerimeter[p];
      if(p > 0){
        lastHexCell = cellPerimeter[p - 1];
      }

      prevDir = HexDirectionExtensions.CoordDirection(cell.coordinates, lastHexCell.coordinates);

      if (p + 1 < cellPerimeter.Count) {
        nextHexCell = cellPerimeter[p + 1];
      }
      else {
        nextHexCell = firstHexCell;
      }
      nextDir = HexDirectionExtensions.CoordDirection(cell.coordinates, nextHexCell.coordinates);

      var bendType = GetBendType(prevDir, nextDir);

      var currentCorner = startingCornerMap[prevDir];

      for(int i = 0; i < (int)bendType; i++){
        AddDir(ret, cell, currentCorner);
        currentCorner = currentCorner.Next();
      }

    }

    return ret;
  }

  // the value signify how many vertices are used on the line going around the corner
  enum HexBendType{
    Inner = 1,
    Straight = 2,
    Outer = 3,
    Acute = 4,
    Uturn = 5
  }

  //Maintaining the clockwise motion starting from the top right most cell, translate the previous/next tile pair into a bend direction
  static HexBendType GetBendType(HexDirection prevDir, HexDirection nextDir){
    if(prevDir == nextDir.Opposite()){
      return HexBendType.Straight;
    }
    if(prevDir == nextDir){
      return HexBendType.Uturn;
    }

    //Not sure what the axiom is here that makes this works but it does!
    if(nextDir == prevDir.Next2()){
      return HexBendType.Inner;
    }
    if(nextDir == prevDir.Previous2()){
      return HexBendType.Outer;
    }
    if(nextDir == prevDir.Previous()){
      return HexBendType.Acute;
    }

    //Shouldn't hit here
    Debug.LogWarning("Unknown bend type " + prevDir + " " + nextDir);
    return HexBendType.Straight;
  }

  //For the perimeter line what hex corner do we need to start adding on
  static Dictionary<HexDirection, HexCornerDirection> startingCornerMap = new Dictionary<HexDirection, HexCornerDirection>(){
    {HexDirection.NE, HexCornerDirection.SE},
    {HexDirection.E, HexCornerDirection.S},
    {HexDirection.SE, HexCornerDirection.SW},
    {HexDirection.SW, HexCornerDirection.NW},
    {HexDirection.W, HexCornerDirection.N},
    {HexDirection.NW, HexCornerDirection.NE},
  };

  static void AddDir(List<Vector3> ret, HexCell cell, HexCornerDirection dir){
    ret.Add( HexCoordinates.corners[dir] + cell.gameObject.transform.position );
  }
}

And that’s the gist of it! All that’s left is the function to tie it all together:

  /* SetupBorderLine.cs */

  void SetupBorderLine(){
    var perim = HexPerimeter.FindPerimeterLoop(selectedCity.influencedCells);

    var linePositions = HexPerimeter.GetLinePositions(perim);

    cityBorderLine.positionCount = linePositions.Count;

    for(var c = 0; c < linePositions.Count; c++){

      cityBorderLine.SetPosition(c, linePositions[c]);
    }

    cityBorderLine.gameObject.SetActive(true);
  }

When you set up your LineRenderer just make sure the Use World Space and Loop boxes are checked.

Hope you learned something and saved some time!