Movement improvements

===================

on the last movement post I mentioned some of the improvements that I would be making to the ship movements. Here is the demo video of some of these improvements. There are still some rough edges as can be seen (like ships passing through each other) which I will fix later. There are a few options about fixing colliding ships, I’m thinking of elevating the ship in the +Z axis so it will fly over the other ship. Another option would be to select a different route. Current the way of selecting the hex cells to reach the target is done like this:

the yellow line is a direct line between the source and target cells. In the previous movement videos ship were taking this direct route. To rasterize the this route, I select N+1 equally distanced points on the line. N is the hex distance between the two points calculated as Math.max( x1-x2,y1-y2,z1-z2) . These points are the green dots on the yellow line. Each of these points will fall into a cell on the grid and these are the cells that the ship will follow to reach the target, as I highlight them in white. So here is the video of the ship moving along the grid:

## Hexarategy

### Re: Hexarategy

Ship movements

===============

Tacked another core feature this evening, which is the movement of the ships around the grid. Thankfully Unity provides a nice method of moving object around. I’ll get to that but before this I tried doing stuff the old fashioned way, by calculating the direction vector between the source and target, and applying a translation vector with the delta time to move the object. This does work but it runs into 2 problems:

1. the movements are jittery. The diagonal edges on the ship were re-rendering giving a sort of escalator effect

2. comparing vectors to know when to stop the animation is not nice because of the huge delta you need to provide to the comparison. Which means that there is a snap effect after you consider the vectors equal, because you have to center the object on the target cell.

The best method is to use the Vector3.MoveTowards() method which guarantees that it will never overshoot. Now comparing vectors with a rather small epsilon works nicely and the stop / recenter animation look quite smooth. Here is what it looks like currently:

There are obvious things that need to be done, like the ship should follow the hex grids and not cut through diagonally. Also the ship needs to rotate in the direction that it needs to navigate. Also a nice after-burner effect would be cool when the ship is moving.

===============

Tacked another core feature this evening, which is the movement of the ships around the grid. Thankfully Unity provides a nice method of moving object around. I’ll get to that but before this I tried doing stuff the old fashioned way, by calculating the direction vector between the source and target, and applying a translation vector with the delta time to move the object. This does work but it runs into 2 problems:

1. the movements are jittery. The diagonal edges on the ship were re-rendering giving a sort of escalator effect

2. comparing vectors to know when to stop the animation is not nice because of the huge delta you need to provide to the comparison. Which means that there is a snap effect after you consider the vectors equal, because you have to center the object on the target cell.

The best method is to use the Vector3.MoveTowards() method which guarantees that it will never overshoot. Now comparing vectors with a rather small epsilon works nicely and the stop / recenter animation look quite smooth. Here is what it looks like currently:

There are obvious things that need to be done, like the ship should follow the hex grids and not cut through diagonally. Also the ship needs to rotate in the direction that it needs to navigate. Also a nice after-burner effect would be cool when the ship is moving.

### Re: Hexarategy

Cells in range

==============

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:

1. get the cells that a weapon of range N can target

2. get the cells the ship can navigate to

The algorithm implementations will depend on the underlying data structure you choose to represent you grid. Today 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.

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

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

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

1. if no more range points left, return

2. if the result set doesn’t contain the current cell, add it

3. 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.

4. 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.

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.

==============

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:

1. get the cells that a weapon of range N can target

2. get the cells the ship can navigate to

The algorithm implementations will depend on the underlying data structure you choose to represent you grid. Today 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.

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

Code: Select all

```
... 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 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

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

1. if no more range points left, return

2. if the result set doesn’t contain the current cell, add it

3. 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.

4. 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.

Code: Select all

```
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--;
}
}
```

### Re: Hexarategy

hex grid neighbors

==================

In the graph based storage of hex grids an important function for the cells is for them to keep track of their neighbor cells.

One way you can build the neighbors list is as you are constructing the grid itself. This can be done on a direction basis. Each cell has the following the directions:

1. NW (northwest)

2. NE (northeast)

3. E (east)

4. SE (southeast)

5. SW (southwest)

6. W (west)

We will use an array of size 6 in each cell to store the neighbors. Each position in the array will correspond to a direction. It doesn’t really matter which index is which position as long as your are consistent about it. If you use an enumeration structure you will automatically assign integers for each direction, which you can then use as the indices for the neighbors array. Keep in mid that not every cell has exactly 6 surrounding cells. Depending on the position on the board some cells may have 3 or 5 but never more than 6. Here is an example to clarify things:

Let’s assume the following values for the 6 directions:

And the Cell object will have a structure similar to

if the cell we are looking at has a neighbor on the NW side, then neighbors[0] will point to the neighbor cell. Incidentally the neighboring cells neighbors array would have the original cell at the SE (3) position. So this relation holds:

For cells with 6 neighbors the original cell is refers to it’s neighbors in a direction and the neighbors refer to the original cell in the opposite direction.

How can we calculate the opposite direction? Quite easy: The position you want + 3 modulo 6. The module will make the directions wrap around after reaching the end of the direction array.

Ok so let’s start of with the easiest direction: the W – E connection.

In this diagram the white arrows show the W-E relationship between cells. Remember that we are populating the neighbor list as we create the grid, so the neighboring cells must exist before we can add their pointers to the neighbor list. If we start from the bottom left corner, the first cell has no neighbors to the W, so we can skip that. On to the second cell to its right. This guy has a neighbor to the west so we can add this to the list, and the opposite neighbor relation also holds. We can do this for the rest of this row, and go on to the next row. On the next row, the same is true: skip the first add the rest. So the condition for creating the E/W relation can be written

The assumption here is that all the cells in the grid are stored in an array called cells. This is a 1 dimensional array. I felt that this may be a bit counter intuitive and deserved a remark. The function will be called for each X, Z coordinate with the position of the cell in the cells array.

For the SW and SE relations we need to distinguish between the cases of even and odd rows. Why? because the the first and last hex of the rows change which neighbors they have. The first element of the 2. row (index 1 so odd) has a SW and SE neighbor but the last hex is missing a SE neighbor. The first element of the 3rd row (index 2) is missing the SW neighbor. None of the cells on the first row have a SE or SW neighbor. So our conditions are:

Let’s take a look at the even case, the purple and orange arrows:

The first cell doesn’t have a SW neighbor, so that’s will be a special case. The rest of the cells have both neighbors.

The odd case (yellow and green arrows):

==================

In the graph based storage of hex grids an important function for the cells is for them to keep track of their neighbor cells.

One way you can build the neighbors list is as you are constructing the grid itself. This can be done on a direction basis. Each cell has the following the directions:

1. NW (northwest)

2. NE (northeast)

3. E (east)

4. SE (southeast)

5. SW (southwest)

6. W (west)

We will use an array of size 6 in each cell to store the neighbors. Each position in the array will correspond to a direction. It doesn’t really matter which index is which position as long as your are consistent about it. If you use an enumeration structure you will automatically assign integers for each direction, which you can then use as the indices for the neighbors array. Keep in mid that not every cell has exactly 6 surrounding cells. Depending on the position on the board some cells may have 3 or 5 but never more than 6. Here is an example to clarify things:

Let’s assume the following values for the 6 directions:

Code: Select all

```
`NW = 0, NE = 1, E = 2, SE = 3, SW = 4, W = 5`
```

Code: Select all

```
`Cell[] neighbors = new Cell[6];`
```

For cells with 6 neighbors the original cell is refers to it’s neighbors in a direction and the neighbors refer to the original cell in the opposite direction.

How can we calculate the opposite direction? Quite easy: The position you want + 3 modulo 6. The module will make the directions wrap around after reaching the end of the direction array.

Ok so let’s start of with the easiest direction: the W – E connection.

In this diagram the white arrows show the W-E relationship between cells. Remember that we are populating the neighbor list as we create the grid, so the neighboring cells must exist before we can add their pointers to the neighbor list. If we start from the bottom left corner, the first cell has no neighbors to the W, so we can skip that. On to the second cell to its right. This guy has a neighbor to the west so we can add this to the list, and the opposite neighbor relation also holds. We can do this for the rest of this row, and go on to the next row. On the next row, the same is true: skip the first add the rest. So the condition for creating the E/W relation can be written

Code: Select all

```
function addCell(x,z,i) {
if (x > 0)
{
cell.neighbors[W] = cells[i - 1];
cells[i-1].neighbors[W + 3 % 6] = cell;
}
}
```

For the SW and SE relations we need to distinguish between the cases of even and odd rows. Why? because the the first and last hex of the rows change which neighbors they have. The first element of the 2. row (index 1 so odd) has a SW and SE neighbor but the last hex is missing a SE neighbor. The first element of the 3rd row (index 2) is missing the SW neighbor. None of the cells on the first row have a SE or SW neighbor. So our conditions are:

Code: Select all

```
if (z > 0 ) {
if (z % 2 == 0) {
...
} else {
...
}
}
```

The first cell doesn’t have a SW neighbor, so that’s will be a special case. The rest of the cells have both neighbors.

Code: Select all

```
if (z % 2 ==0) {
cell.neighbors[SE] = cells[i - width]
//add the opposite too
if (x > 0) {
cell.neighbors[SW] = cells[i - width - 1]
//add the opposite too
}
}
```

Code: Select all

```
if (z % 2 == 0) {
...
} else {
cell.neighbors[SW] = cells[i - width]
//add the opposite
if (x < width - 1) {
cell.neighbors[SE] = cells[i-width+1]
//add the opposite
}
}
```