hexarategy

23 minute read

Shield Visual Effects

Even though I had put up some text to indicate the shield status of a ship, it doesn’t go without some visual effect to indicate a shield presence. This is mainly because I’m too lazy to read that info text every time I want to give some command to the ship. A more catchy indication is required.

Also during the economical phase you can’t move ship or adjust power diversion. I found myself clicking on ships multiple times during the economy phase without realizing that it was that phase only to thing “why aren’t my clicks registering?” followed by a “duh!“ second. So I used a similar effect to indicate that you can’t select ships at the moment.

Discovering enemy units and planets

At first I though that the game could be a game of perfect information where you know where all the planets are and where your enemies are based. But then first I made the planets invisible so you have to explore around to find planets to colonize. Then I though well I’ll also make the enemies invisible until you scan them. The procedure is quite simple: Every ship and planet has a set property called exploredBy. When creating the units you add yourself to the set. Then during the Update() call of every ship in transit you scan the neighboring cells with a radius of N and if there is anything on that cell you add yourself to their explored list and make them visible. Setting a sight line of 1 is okay for planets but could be dangerous for enemy ships as you would end up right in the middle if you go the max distance. So setting this to 2 or 3 is going to better I guess. But this is also a tactical choice: Do you spend all your power on the engines and have nothing attack/defense when you end up in the attacking range of an enemy ship, or do you travel less but have your guard up?

Here is the new stuff in action on a very small map for testing purposes

https://youtu.be/bJFR6VIMcSI

Turn processing and economy

2 easy parts don’t require much on the 3D side, but are a pain on the GUI part. The unity GUI is quite inferior compared to the browser that I can say. As far as I can guess it was even worse in 4.x and this is the revamped GUI system in unity 5 which still not that good. So the turn system. Turns are conducted in phases.

Movement/exploration/combat turn

Economical phase

Every 4 turns there is an economy return the others are for moving around, colonizing etc. During the movement phase the player still collects income from the colonies and pays ship maintenance costs but cannot buy ships or do research. In the economy phase the player cannot do the things done in the movement phase, but does the things not allowed in the movement phase. Every turn the ships also generate power and burn fuel.

At the beginning of the economy turn the player collects the income and pays the maintenance costs and whatever is left over he can use to purchase ships or technology. There is a nice report that displays what happened economy wise at the beginning of the turn like this

One thing to mention is that if there is an enemy ship in the neighbor cells of a colony then it will not produce any income. All the colonist are fearing for their lives and will not work.

I’ve also added a nice bar at the top that displays the current star date and the credit points the player has and a button to confirm that the turn has ended.

Planet colonization

This one wasn’t tricky as I expected it to be. To colonize a planet all you have to do is send a colony ship to that planet. No resistance – no ground battle the colony is yours. The colony ship disappears from the grid as it is turned into a colony base on the surface and a colonization message is displayed. Now you can get all that extra production, yeah.

https://youtu.be/l5AC7sPvD44

Planets and some info panels

over the weekend I’ve added some planets to the grid. That was straight forward, find some nice planet surface textures and apply them on to a sphere. The info panels for the planets were GUI text at first with a canvas etc. But if you rotate these along the X-axis so that they lay flat on the grid the font rendering gets screwed up big time so I changed that to 3D text mesh. The results are pleasing.

the planet names are 3 arrays of 5 meaningless names and a unique selection is made at random from these arrays.

While at the subject of panes I also changed the ship info pane to a text mesh. The previous videos had examples of UI text and how ugly it looks when rotated as the ship info text. Now it’s much smoother:

One of the tricky things here was to keep the text facing towards the user as the ship rotates. The text is a child component of the ship, and is positioned 0,0,-10 relative to the ship. When the ship rotates so does the axis for the text and it would end up in different positions for each rotation of the ship. To keep it below the ship for all rotation the positioning has to be with respect to the world axis. To accomplish this I had to get the TransformPoint for the ship location with respect to the ships origin and add the difference vector. Now when you set the position of the text you get this effect. Something along the lines of

Vector3 p = ship.asset.transform.TransformPoint (Vector3.zero);
text.transform.position = p + new Vector3 (0, 0, -10f);

Here is some video action

https://youtu.be/CXCGkh642OI

Ship mechanics

over the last week I’ve been thinking about how the ship mechanics should function. I wanted to come up with something that doesn’t require micro-managing a fleet of ships but is yet flexible enough for a nice tactical combat. The method I’m going to try out has the following properties

This looks to a like sweet spot is managing the ships vs stream lining battles but I can’t be sure until I have actually played some battles.

https://youtu.be/kw8HuirxIys

Hex grid border highlighting

So, I’ve been polishing the grid looks a little bit and one of the things I’ve seen posted around the forums and Q/A sites is how to draw a line around the hexagon cell borders to indicate possible movement ranges. Previously I’ve been doing this by actually highlighting all the possible cells, but it’s looks a lot better if you just highlight the borders. Here’s the results I’ve got after this implementation

Calculating the border cells is a different task which I’ve explained over here. After we have the cells that we can navigate to we need to filter out the border cells. If you look carefully the edges that need highlighting from all the cells in range are the ones that do not have a navigable neighbor. In the image the cell (4,-6,2) and (5,-6,1) are both in range, but they share a border with a navigable cell, so that edge should not be highlighted. The algorithm should be like this:

  1. Get all the cells in range and the starting cell, and add the starting cell to the cells in range.
  2. for all the cells loop
    1. for all the neighboring cells of the current cell loop
      1. if the cells current neighbor = null or cells in range doesn’t have the neighbor highlight that edge

The actual highlighting is done by placing a quad with a bar texture with the correct rotation and coordinates easily calculated from the current cell we are processing.

https://youtu.be/UkWKeim-n_Y

Avoiding obstacles in path during movement

Up until now there were any obstacles (excluding ship) so I really didn’t care for a proper path finding algorithm to select the cells that the ship would follow to reach it’s target. A simple rasterization of the cells were the way to calculate the path, but since I’ve added some asteroids it I also thought I’d spice up the path finding too.

In this picture the rasterization algorithm would pick the yellow line and the cells with the red dots on them, which are actually obscured by asteroids. The correct path is the path with the purple arrows. How to you choose these? Well luckily there are a couple of ways. The brute force version would be to do a breadth first search to find the target cell which would lead to wasted movements for sure. The next best approach is the select the next cell in the BFS not at random or in order but based on a heuristic, a good guess to which cell would lead quicker to the target cell. The easiest heuristic that comes to mind is the hex distance calculated as Math.max( x2-x1, y2-y1, z2-z1). You also add the total cost of movement to this cell, something that you know for sure. Why do we add the cost of movement? Because we may need a rotation to get to that neighbor cell, which is also a movement cost. So from the starting cell, you look at all the neighbors and calculate the distance to the target cell + the cost of movement to that cell and choose the closest one. You add the current cell to the visited list. Why? because in the next step the current cell will show up as a neighbor, and we don’t want to check that cell again. Then you advanced to that cell and do the same until you have reached your target. Is it possible that the target cell is never found or a ship will be there to block us? No because the target cell validity check is done before hand (the green cells). This is a simplified version of the A-start algorithm. Here it is in action

https://youtu.be/8oQPrgEamu8

Navigation order processing

Having ships is useless if you can’t boss them around the grid. So how would you do that, be also allowing multiple ships to move at any given time without running into each other? The first iteration of the path finder was the rasterized path finder I explained here. This method will provide a list of cells that the ship must travel through (I since have added a new algorithm that takes into account any obstacles in the way. It just returns a different list of cells which isn’t of any significance for the navigation command system). When the user clicks on a ship, we need to store that clicked cell and it’s ship into a temporary variable. The first click will also highlight the possible cells the ship can navigate to. The post about cells in range explains how there are calculated. The second time the user clicks on a cells, it can mean 3 things

  1. the user wants to navigate to a cell
  2. the user wants to cancel the selection
  3. the user wants to select another ship from his fleet
  4. the user wants to attack an enemy ship

We will address the first 3 items. Items 2 and 3 are simple so let’s get them out of the way first. If the user wants to cancel the selection, he just clicks on a cell not highlighted by the cells in range call. We just need to check if the clicked cell is in the list returned from this call. If not reset the variable that holds the clicked ship to return to the initial state. If the user wants to select another ship to move, if has clicked on a cell with one of his ships. Since he can’t attack that ship, just check if the clicked cell has a ship on it and if that ship belongs to the player. If true, set the selected cell to that one.

Here is an image of a state machine that shows to transitions and states

The red transition is cancelling the selection, and the green transition is selecting another ship to navigate.

Now let’s explore the case where the user wants to navigate to a cell. We need to support multiple ships wandering around at the same time, so the user doesn’t have to wait for the first ship to arrive before issuing a second order. This means we need a queue of navigation orders that will be processed at each update. We create an object that will store the source cell, target cell, the path the ship will take and the ship model and the ship object that carries meta data associated with the ship. At each update call we will process each item in the command queue and make the required movement to the next cell in the path. After each item in the queue is processed it gets queued again. This way all the ships movements will be updated once for every update call. If there is another ship in the next cell for the ship we are processing just skip that command item for this frame. This will make the current ship wait if there is another ship blocking the path, until the ship moves away from that cell. There is an edge case that needs to handled here, which is that if the blocking ships final cell is that cell, then the current ship will wait forever. To mitigate this case checking if any ships will end up at a cell blocking the way needs to be considered when creating the command. Processing the cells in the path of the command object is quite similar. Each update call, dequeue the next path from the paths and move towards that cell. If the ship has reached the cell, transfer the ship to that cell and discard that cell from the path. If the path queue is empty, it means we have reached our destination. So here is the algorithm outlined in a list

  1. copy the command item queue to a new queue, call it nextQueue
  2. while there are items in the queue, loop

    1. get the current command
    2. currentCell = the cell this ship is on now
    3. next cell = peek at the head of the path for the current command
    4. if there is a ship on the next cell, enqueue that command in nextQueue and continue the loop
    5. check if the ship needs a rotation to get the current cell, and process the rotation if required
    6. move the ship towards the next cell
    7. if the ship is in the next cell, transfer the ship to that cell.
    8. if there are more paths to process, requeue the current command in nextQueue##
  3. copy nextQueue back to command item queue

Ship movement collision

So, in the last movement video there were ship passing through each other like they were ghost ships of some sort. I could have just added a mesh collider and blew up the ship when they touched each other but that wouldn’t really make sense for ship of the same player. No same captain wouldn’t deviate from a collision course with a friendly ship (unless they’re unconscious or something). So the simplest way was to let one of the ship wait until the other one passes, and then carry on with the navigation.

https://youtu.be/iVI2z1xUZsc

Movement improments

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:

https://youtu.be/Ij2ARqzowb4

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:

https://youtu.be/-Vxquzv15hc

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.

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

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

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.

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 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:

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

And the Cell object will have a structure similar to

Cell[] neighbors = new Cell[6];

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

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

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:


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

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.


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

The odd case (yellow and green arrows):

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