How to calculate the border hexagons in a grid with blocking elements?

Question

I have a hexagon grid with cubic coordinates. I want to calculate clockwise all border hexagons for a given movement range. At the moment, I am iterating every neighbor that is not in the range and is not blocked. If a hexagon has such a neighbor, it is a boundary hexagon:

public void HighlightBorder(List<Hexagon> totalRange)
{
 if (totalRange == null || totalRange.Count == 0) return;
 foreach (Hexagon hexagon in totalRange)
 {
 var neighbors = DirectNeighbors(hexagon);
 if (neighbors.All(neighbor => totalRange.Contains(neighbor) || neighbor.IsBlocked)) continue;
 var outerneigbors = neighbors.Where(neighbor => !totalRange.Contains(neighbor)).ToList();
 if (outerneigbors.Any()) hexagon.Highleight();
 }
}

This results in the following:

enter image description here

(yellow start, gray = blocked, red = border, movement range = 6)

Many border hexagons are missing, as they are either not bordered at all or only with blocked hexagons. The desired result is this:

enter image description here (yellow start, gray = blocked, red = border, movement range = 6, green = missing border hexagons)

How can I achieve this?

I have already tried to find all extreme points (lowest y, highest z), (highest x, lowest y) etc. and rotate from a starting extreme in the respective direction. For example, I start at the lowest z, highest x hexagon and move in the direction (-1,1,0) until I find the lowest z, highest y hexagon and continue from there with the corresponding direction.

I tried to use the distance to the center hexagon. I start with the hexagon that is furthest away, iterate each neighbor and continue with the next hexagon that is furthest away. This works for a normal grid, but not for one with blocked hexagons or the example shown.

I assume there must be a relatively simple algorithm, such as "always to the right, bottom right, bottom left, etc".

• Zibelas: I would probably use just some flood fill and remove the tile from it if it touches just a red border but not a gray one and remove it as well if it only touches another green one. To catch the three green ones at the left (-4/10/-6 and co), I would add to your board a gray border all around.
• Jachuc: Thanks for the input! It's a pretty good approach, but I'm not sure if a frame around the entire board is feasible. In the meantime, I thought of another solution: Any cell that doesn't have 6 valid neighbors (not null, not blocked, in range) must be a border. I like this solution because it's pretty simple, but it causes problems if you have blocked hexagons inside the range (which shouldn't count as a border).

Answer 1

You only need a couple of changes to your loop:

public void HighlightBorder(List<Hexagon> totalRange)
{
 if (totalRange == null || totalRange.Count == 0) return;
 foreach (var hexagon in totalRange)
 {
 var neighbors = DirectNeighbors(hexagon);
 // Highlight cells touching the edge of the map.
 if (neighbors.Count < 6) {
 hexagon.Highlight(); // Green
 continue;
 }
 // I avoid LINQ in game code if the corresponding explicit iteration
 // is barely any longer - that way, I know I'm not adding overhead.
 
 foreach (var neighbor in neighbors) { 
 if (neighbor.IsBlocked || !totalRange.Contains(neighbor) {
 hexagon.Highlight(); // !Contains => Red
 // Otherwise, IsBlocked => Green
 break;
 }
 }
 // No need to waste extra allocations mucking with "outerneighbors".
 }
}

This new version avoids memory allocation within the loop (provided DirectNeighbors is set up to be non-allocating), so you should also observe this to run faster and create less pressure on the garbage collector than the previous version.

---

If you want to avoid drawing borders around blocked tiles in the middle of the range, you need to make another change in this section:

foreach (var neighbor in neighbors) { 
 if (!totalRange.Contains(neighbor) {
 hexagon.Highlight();
 break;
 }
 if (neighbor.IsBlocked && !IsIsland(neighbor, totalRange, hexagon) {
 hexagon.Highlight();
 break;
 }
}

Here IsIsland() is a function that checks whether this blocked cell is part of a span of blocked cells that are completely bordered by cells in range. You can do that by walking around the border between blocked-and-open cells, as shown in this answer,checking if you step outside the totalRange anywhere along the way. I'd recommend caching the results so you don't have to run this search many times for the same island.

Once you have this border-walking subroutine, you can also use it to enumerate your border tiles directly, without necessarily visiting every tile in the interior. You'd follow the algorithm shown in the linked answer:

1. Scan in an arbitrary direction from your start tile until you encounter a tile that's either absent, blocked, or out of range.

2. Walk around the border between in-range cells and absent/blocked/out-of-range, keeping track of the in-range cells you visit.

3. Once you return to the start of your walk, if you touched an out-of-range cell anywhere along the way, you've found the entire outer perimeter! Highlight all in-range cells you walked through.

4. If you didn't find any out-of-range cells, then you got unlucky and hit an island. Go back to 1 and continue scanning from the furthest in-range tile you've found so far in the arbitrary direction you picked: you'll have to hit the outer edge eventually if you go far enough this way!

• Jachuc: 3. is not true if you have a movement range of 1 and two blocking hexagons interrupt the walking algorithm before it reaches the last hexagon. This may be an unlikely scenario for most use cases, but for me it is not, as the center hexagon is always blocked. I was able to solve this by continuing to run the algorithm when the start is reached and when totalrange <= 9 hexagons until the start is reached again.
• DMGregory: Returning to the start of your walk means returning to the same tile in the same orientation. Using the terminology of the linked answer, this means your "foot" is on the tile where it was when you started walking the perimeter (not the start of your scan), AND your "hand" is on the tile it was. It sounds like you're counting cases where you return to the start tile with your hand in a different spot.