Hex grid cells in range

Keywords: decrease range point, range cell, cell ne, yellow cell, yellow ne, purple cell, orange cell, home cell, current cell, recursive graph, direction, units, nw. Powered by TextRank.

Getting the cells in a range of N is also an important aspect that worth talking about. There are 2 current uses for this feature in Hexarategy:

get the cells that a weapon of range N can target
get the cells the ship can navigate to

The algorithm implementations will depend on the underlying data structure you choose to represent you grid. In this post I will go over algorithms that can be used when using a graph to represent the grid. Let’s start with the weapon range, as the movement range is a bit more complicated since it has some different constrains.

The range of a weapon is defined as all the cells in all directions from the home cell that are < N units away. Think like the inside area of a circle.

57de523c6fd8e.md.jpg

If the yellow cell is the home cell, then the purple cells are all the cells that are 1 units away, and the orange cells + purple cells are all the cells that are 2 units away. So given the yellow colored home cell, how can we get the cells that are N units away?

This is a classical graph walk with a range constraint. Instead of visiting all nodes, or quitting when a node is found, we need to quit when we exhaust our range. So we need to keep track of the range, that’s for sure. We also need to consider when we decrease this range, because for all purple cells the range from the home cell is 1, and we cannot decrease the range each time we visit a purple cell. What we need is to keep track of how many purple cells there are and decrease the range after we have consumed them all. We will need track of this by using 2 extra counters: nodesInNext and nodesInCurrent . nodesInNext will hold the count of the neighbors in the next level and the current will hold how much of the current level we have consumed. There are recursive graph traversing algorithms and there are ones using stacks and queues. We’ll opt for a non-recursive algorithm here

... get the home cell and add it to the queue
goneRange = N //how far is our range?
nodesInCurrent = 1 /*home cell*/, nodesInNext = 0;
while(queue.Count > 0 && goneRange > 0)
{
    nodesInCurrent--;
    currentCell = queue.Dequeue();
    List<Cell> neighborList = new List<Cell>();
    foreach (Cell item in currentCell.neighbors)
    {
        if (item != null) neighborList.Add(item);
    }
    neighborList.Remove(homeCell);
    IEnumerable<HexCell> nlist =  neighborList.Except(result);
    nodesInNext += nlist.Count();
    foreach (Cell neighbor in nlist)
    {
        queue.Enqueue(neighbor);
        result.Add(neighbor);
    }
 
    if (nodesInCurrent == 0)
    {
        goneRange--;
        nodesInCurrent = nodesInNext;
        nodesInNext = 0;
    }
}

the result list will contain all the cells that are in range and we can use that. Note that this doesn’t check for friendly fire.

The movement range calculations are bit more interesting as there is the condition that a rotation move also costs 1 range. Take a look at this diagram

57de52979442d.md.jpg

Starting at the orange cell facing NE the yellow cell is in range 1. The cell NE of the yellow cell is in range 2 as it is in the same direction. The cells to the NW and E of the orange cell are in range 2 because 1 range point would be used to rotate the ship from NE to NW and NE to E. Let’s solve this algorithm with a recursive approach. Here is the outline of what we will try to implement

if no more range points left, return
if the result set doesn’t contain the current cell, add it
for the next 3 directions, if there is a neighbor cell in that direction recurse with range – 1 in that direction otherwise decrease range points.
for the previous 2 directions, if there is a neighbor cell in that direction recurse with range – 1 in that direction otherwise decrease range points.

So if we are facing NE like the diagram, and we have 2 range points, we will go to the yellow neighbor. We still have have range point so we’ll go NE. Now we don’t have any range points so add this cell to the results. Backtrack to the yellow cell and decrease the range points. The next direction is E, but we don’t have any range points. This will hold for all the remaining directions on the this cell, so we backtrack to the orange cell. The next direction is E, and we consumed a range point by turning in this direction so we have 1 point left. There is a cell to the E so go to that cell and add it to the list… you get the idea.

public void CellRangeMovement(Cell currentCell, int rangeLeft, List<Cell> result, Direction direction)
{
 
    if (rangeLeft < 0) return;
    if (!result.Contains(currentCell))
    {
        result.Add(currentCell);
    }
 
    Direction nextDirection = direction;
    int rangeReg = rangeLeft;
    for (int i = 0; i < 3; i++)
    {
        Cell currentNeighbor = currentCell.neighbors[nextDirection];
        if (currentNeighbor != null)
        {
            CellRangeMovement(currentNeighbor, rangeReg-1, result, nextDirection);
        }
        nextDirection = nextDirection.Next();
        rangeReg--;
    }
 
    rangeReg = rangeLeft;
    nextDirection = direction;
    for (int i = 1; i < 3; i++)
    {
        Cell currentNeighbor = currentCell.neighbors[nextDirection];
        if (currentNeighbor != null)
        {
            CellRangeMovement(currentNeighbor, rangeReg - 1, result, nextDirection);
        }
        nextDirection = nextDirection.Prev();
        rangeReg--;
    }
}

One interesting point here is that, you cannot rotate 6 six times clockwise to get all the directions, as that would mean consuming extra ranges, e.g if you are facing NE and want to face NW you would not go E,SE,SW,W,NW. You would just go NE, NW. That’s why you have to check the directions in 2 separate for loops.

Hex grid cells in range

Metadata

Similar posts