How do I sort edge tiles for a hex grid in order to draw a border?

Question

I am trying to sort the edge tiles of a region in my hexagon map. Once it is properly sorted, I can then try to walk through them and attempt at creating a Civ style border map, but I can't seem to figure out the sorting.

Right now I just have a simple line renderer that represents my results. Red portion of the gradient represents the start of the line.

It comes quite close at times.

I tried playing around with checking the direction I was coming from to change the neighbor sort, but haven't had any luck. I added a Stack so that I can walk back if I hit a dead end. Sometimes it works, but depends on the direction it was coming from.

Don't necessarily pay too much attention to the coordinates themselves. I've gone through the entire https://www.redblobgames.com/ docs and can easily convert from a 2D grid, to Unity's Offset, and to Cube coordinates. This particular code is initially the coordinates from a int[,] that was used in the procedural generation of the map.

public void CalculateEdgeTiles(ref int[,] regionMap)
{
    EdgeTiles = new HashSet<MapCoord>();
    if (Tiles == null)
        throw new Exception();

    MapCoord startingEdgeTile = null;
    
    foreach (var tile in Tiles)
    {
        foreach(var neighbor in tile.Position.ToHexOffsetCoordinateRing(1, true))
        {
            if (regionMap[neighbor.x, neighbor.y] != tile.RegionId)
            {
                EdgeTiles.Add(tile);
            }
        }
    }
    
    var sortedTiles = new List<MapCoord>();
    var queue = new Queue<MapCoord>();
    var stack = new Stack<MapCoord>();
    
    queue.Enqueue(EdgeTiles.First());

    var walkingBack = false;
    MapCoord previousTile = null;
    while (queue.Count > 0)
    {
        var currentTile = queue.Dequeue();
        if (sortedTiles.Contains(currentTile))
            continue;
        
        if (!walkingBack)
        {
            sortedTiles.Add(currentTile);
            stack.Push(currentTile);
        }
        
        var foundNeighbors = new List<MapCoord>();

        foreach (var neighbor in currentTile.Position.ToHexOffsetCoordinateRing(1, true))
        {
            var tile = Tiles.FirstOrDefault(x => x.Position == neighbor);
            if (tile == null || !EdgeTiles.Contains(tile) || sortedTiles.Contains(tile))
                continue;
            
            foundNeighbors.Add(tile);
        }

        if (previousTile == null)
            previousTile = currentTile;
        
        bool addedNeighbor = false;
        var neighborQuery = previousTile.Position.y < currentTile.Position.y
                                ? foundNeighbors.OrderByDescending(x => x.Position.x + x.Position.y)
                                : foundNeighbors.OrderBy(x => x.Position.x + x.Position.y);
        foreach (var neighborTile in neighborQuery)
        {
            addedNeighbor = true;
            queue.Enqueue(neighborTile);
            break;
        }

        walkingBack = false;
        //If we added nothing, pop the stack and start walking back to check the next neighbor.
        if (!addedNeighbor && EdgeTiles.Count != sortedTiles.Count)
        {
            walkingBack = true;
            queue.Enqueue(stack.Pop());
        }

        previousTile = currentTile;
    }

    EdgeTiles = new HashSet<MapCoord>(sortedTiles);
}

I'm hoping I am just missing a simple trick or I was just dumb on one section of the code. Any info is appreciated.

Answer 1

The usual approach here is to pretend like you're solving a maze blindfolded: keep your left hand in contact with the wall, and follow its contours until you reach the exit (or in this case, until you return to your starting point)

Assuming we start with some tile in the region we want to outline, but not necessarily on the edge of that region, we can keep moving in some arbitrary direction until we find a tile with a neighbour in a different region. Make this our starting point (call this our "standing" tile, because it's the one we're standing on), and store the tile in the other region we're touching with our left hand (call this our "held" tile, since we're holding our hand on it)

Rotate your feet:

As long as you can do so without leaving your current region, rotate your "standing" position counter-clockwise around your "held" tile. This represents following the wall around a convex corner. At each step, we add our standing tile to the edge list.

Rotate your hand:

If rotating around your "held" tile would make you leave your region, then instead rotate your "held" tile clockwise around your "standing" tile until this would make your hand enter your standing region. This represents feeling your way around a concave corner.

We can work our way around the whole map, alternating between these two moves, following one as far as we can before switching to the other.

When we return to standing on our starting tile, holding the same tile we were when we started, we've completed our circuit and have all the edge tiles in the correct sequence in our list.

Note that we may return to the same tile more than once over the course of the search, but with our hand on a different neighbour. That's why we need to check both the standing and held tile match our starting state before we can conclude that we've finished tracing the whole edge.

As a bonus, if you keep a list of tiles our hand visits, this gives you the outer border tiles in the containing region(s). Or, if you keep track of each {standing, held} pair you encounter along the way, that gives you the ordered list of edges between this region and its neighbours.

---

This method will not on its own discover holes in your region, if it can have a doughnut shape with a different region nested inside it. To be sure you've found all border tiles in a region that can contain holes, you'd first do a depth-first search or flood fill to get all connected tiles in the region, and note all the neighbouring region tiles you discover along the way.

Pick one of them to place your hand at and trace your first contour, using the method above, keeping track of which tiles your hand touches along the way.

After you're done, check your neighbouring collection again: are there any your hand didn't touch? If so, trace a contour starting with your hand on that tile, and repeat, until your hand has visited every neighbour.

Answer 2

I see you already have an answer to your question, but I'm going to add another answer for anyone who's trying to solve a simpler variant of the question.

Civilization puts borders between hex tiles when the owner of the tiles are different. The simplest algorithm is to look at the edges between tiles:

let H : iterate over all hexes
  let N : iterate over the neighbors of H
    if H and N are owned by different civilizations, draw a border

Here's what it looks like:

You can draw these line segments individually, without linking them up. Note that it handles peninsulas and single-hex cells without any trouble. No special cases needed. Try it out with this interactive demo.

Note that you'll end up drawing each border twice, once for A→B and once for B→A.

If you don't want to draw each border twice, only visit the northwest, west, and southwest neighbors instead of visiting all six.

Alternatively, move the drawn border slightly inside the hex so that you can draw both of them, possibly in different colors:

If you need to link these up into a chain, it's easiest if you try to keep a given civilization on the left side of the chain. Pick any edge where the left side is the given civilization, and the right side is owned by someone else. Look at the yellow arrow #1 in this diagram, where the left side is the blue civilization:

The endpoint of this edge will be a vertex. A vertex is where three hexes meet. Two of these hexes you've already been looking at. Look at the hex in front of you. Is it owned by blue? No. Then turn left.

Now look at the cyan arrow #2 in the diagram. The left side is the blue civilization. The endpoint is where three hexes meet. Look at the hex in front of you. Is it owned by blue? Yes. So turn right.

If you keep the current direction as an int 0…5 then turning left/right will involve ±1 mod 6.

By following the edges one by one you will form a complete chain where you have returned to the original point. I think this works for any shape, no special cases.

Answer 3

I thought I was too smart for my own good. After many, and I mean, many hours of fighting this, I had to fall back to DMGregory's answer in the fullest. Every single time I thought I had it, there some weird generation that gave me a new angle and direction that would not be caught. I was very stubborn walking only the edge cells.

You have to walk the outside!

If you're working with the possibility of single tile peninsulas, there is no choice. I did not truly realize this and was sure it could be done because I had
looked at this guide https://dillonshook.com/hex-city-borders/

For Civ style borders that do not have single tile peninsulas or really odd shapes, it works great. But for what I am doing, any shape is a possibility.

Here is a literal translation of DMGregory's answer in code which I hope is easy enough for others to follow. You can combine this with the guide linked above and the author's github gists.

static List<Vector3Int> FindHexCubePerimeterLoopOutside(List<Vector3Int> cubeCells, Vector3Int startCell)
{
    var perim = new List<Vector3Int>();
    var footCell = startCell;
    
    var startHandCell = footCell.GetNeighborCube(HexDirection.E);
    var handCell = startHandCell;

    if (cubeCells.Any(x => x == handCell))
        throw new Exception("Start Cell Must be the top right most cell");

    var handMovedFromStartingLocation = false;
    var finished = false;

    //Yes, this happened to me. Still refining my actual regions and merging is apparently flawed.
    if (cubeCells.Count == 1)
    {
        Debug.LogWarning("Only 1 Tile Perimeter");
        return cubeCells;
    }

    perim.Add(startCell);
    do
    {
        var footMoved = false;
        
        //The starting direction is always relative to the hand
        foreach (var footDirection in CounterClockwiseDirections(handCell.CubeCoordDirection(footCell)))
        {
            var newFootLocation = handCell.GetNeighborCube(footDirection);
            if (cubeCells.Any(x => x == newFootLocation))
            {
                if (newFootLocation == footCell)
                    continue;
                
                //It's possible and common that we ended up crossing a single body of water
                //The tile muse be connected
                if (footCell.HexCubeDistance(newFootLocation) > 1)
                    continue;
                
                footCell = newFootLocation;
                perim.Add(newFootLocation);
                footMoved = true;
            }
            else if (footMoved)
                break;
        }
        
        var handMoved = false;
        
        //The starting direction is always relative to the foot's.
        foreach (var handDirection in ClockwiseFromDirections(footCell.CubeCoordDirection(handCell)))
        {
            var newHandPosition = footCell.GetNeighborCube(handDirection);
            
            //Just like the other distance check, we need to make sure that if the hand position is back to the original position
            //that the current foot cell is a neighbor because it is possible that we are walking back out of an inlet.
            if (newHandPosition == startHandCell && footCell.HexCubeDistance(startCell) <= 1 && handMovedFromStartingLocation)
            {
                finished = true;
                break;
            }

            if (cubeCells.All(x => x != newHandPosition))
            {
                if (newHandPosition == handCell)
                    continue;

                handMovedFromStartingLocation = true;
                handCell = newHandPosition;
                handMoved = true;
            }
            else if (handMoved)
            {
                break;
            }
        }
        
        if (!handMoved)
            throw new Exception();
        
    } while (!finished && perim.Count < MaxPerimeterResult);

    
    if (perim.Count >= MaxPerimeterResult)
        Debug.LogError("Cancelled out of the perimeter loop. Stuck.");
    
    var lastCell = perim.Last();
    if (lastCell == startCell)
        perim.RemoveAt(perim.Count - 1);
    
    return perim;
}

It would be too much to show all of the code and I tweaked a lot of it to use cube coordinates, but the hard part is done. You just need to translate this to be whatever coordinate system you are using. If you do, the actual drawing of the border from the linked guide should just fall right in.

Here's the results.