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


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.

enter image description here

It comes quite close at times.

enter image description here

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.