Relay Power (Tower Defense)

Contents

Background

When I was in high school, I ran across a Flash game called The Space Game, which was an RTS-like tower defense game, with one pretty interesting mechanic: all your towers had to be connected to a power supply by a series of energy relays in order to work. Unfortunately the game seems to be dead now that Flash is gone, but here’s what it looked like:

I’ve found this relay system fascinating for a long time, and have made my own games using it several times with various degrees of completion. In high-school, I started a 2D RTS in XNA using it, and in college I played around with a couple smaller demos with similar mechanics.

After college, I eventually got a VR headset, and one of the things that VR affords you is the ability to place things in 3-dimensional space much more easily than you could with a keyboard and mouse in 2D. So of course I eventually started trying to do another game like this in VR.

The Game

For this project, I opted to work in Unity, which is the game engine I’m most familiar with. I also had prior code for managing a graph of power-relay nodes from some of my other related projects I could re-use which was already written for Unity. I used the SteamVR plugin/library for VR inputs, and made my own models using Blender. To spice things up, I used Unity’s built-in graphical shader editor to develop custom shaders to do things like draw different textures to represent units under construction. I also found a library of freely licensable sound effects, and open-licensed music.

For the enemy design, I used a modified Boids simulation to allow clusters of fighters to fly in a rough formation. The basic Boids model includes 3 elements: separation, alignment, and cohesion. Quoting wikipedia:

• separation: steer to avoid crowding local flockmates
• alignment: steer towards the average heading of local flockmates
• cohesion: steer to move towards the average position (center of mass) of local flockmates

In addition to this, I added target selection (select a target and steer towards it), and ship classes, where different ships have different alignment and cohesion parameters for each other depending on their class. For example, fighters and bombers each have high cohesion among themselves, but different cohesion to each other. Fighters have high cohesion to bombers, so they will try to form up on bombers like an escort, while bombers have little cohesion to fighters, so they will not try to follow fighters into close range.

Here are some snapshots of the development progress.

In this first demo, mining doesn’t exist yet, so power is the only resource, and there’s only one weapon type (missile launchers). There’s only one enemy type (fighters) and no spawning or win conditions; at the start of the level, the enemies are simply placed far enough away that they’ll take a minute or two to arrive. This first demo shows basic structure placement, construction, relay usage and combat.

This second demo now has a main menu, sound effects, and in-game music. It also now has mining, and resource limitations, in-game UI displays, enemy spawns based on mission progress, and mission completion criteria. It shows a single mission being played from start to finish.

This third demo shows the state of the game at present, with some new player weapons and defenses (such as a shield generator), and new enemy types.

<

Challenges

Graph Routing

The power grid forms a graph, and we need a way to move units of power around it. In this game, power comes in discrete units, and structures need a way to request particular quantities as needed.

Everything connected to the power grid is considered a node. Nodes have two capabilities; the ability to send power to storage and the ability to draw power from storage. Whenever a node tries to send or draw power, it runs Dijkstra’s algorithm to find the shortest path to every node that contains storage, and then caches all of the routes. The cached set of routes is then used to handle all send and draw requests. Whenever the graph is modified, either by a structure bein built or destroyed, a graph generation counter is incremented, which effectively invalidates the caches of all nodes in the graph without having to go through and flush them all. Instead, nodes just check the generation the next time they process a send or draw request to decide whether to refresh their cache.

For a send request, the node goes down its list of connected power storages in order from nearest to farest. If the storage has space for the amount of power being sent, it is all sent to that node. Otherwise, as much as possible is sent to the closest storage, then it tries again to send the remaining power to the second closest storage, and so on. If at the end of this process some power is left, that power is lost because storage is full. Power generators are all also storage, so the shortest route is always to themselves, but this push approach makes for an easily balanced way of putting overflow power into alternate storage.

For a draw request, things proceed much the same way as a send request, but with the signs reversed. If the first storage has enough power in it, it is drawn from there, otherwise any shortfall is pulled from the next closest storage, and so on. One difference is that there are actually two different systems for handling the case where not enough power is available. Some structures are greedy and will take what they can get each frame and accumulate resource over time until they have enough, while others politely wait until the exact amount they need is saved up. These two options are used to balance which types of structures will starve each other for resources. For example, weapons prefer the greedy resource aquisition method, while construction prefers the polite option, since its more important that resources go to weaponry as soon as possible than to construction.

Distributing Discrete Units

One issue I faced was that I wanted to keep both resources (metal and energy) in integer quantities, rather than letting them become floating point. One problem this poses is that, as a game designer, I want to be able to set parameters like how long a structure will take to build, how many resources it will cost, and how many increments constructing it will take independently of one another. It’s pretty easy to handle splitting up the construction time into N discrete steps, since time is handled in floats. However, what do you do if the total cost of construction T isn’t evenly divisible by N?

A pretty simple answer is to just divide by N-1 and put the remainder at the beginning or end, but that can leave a very big difference between the cost of steps 1 through N-1 and step N. I wanted an approach that spreads the total more evenly over the increments.

The approach I took was to first divide the total resource amount over the whole number of steps, then choose a subset of steps to divide the remainder over. Subsetting the remainder can be repeated until there is no remainder.

Lets consider what this looks like if we want to increment up to 31 in 9 steps. First, we divide 31 / 9, which gives us 3 with a remainder of 4. So we know that for every step we have to increment by at least 3, but on some steps we’ll need to increment by more than that. So how do we decide which steps to place extra increments on?

Well, we want to divide up the remainder R, in this case 4, into substeps that increment by K extra on uniform intervals. So ideally, we’d increment by 1 extra every S = N / R steps, but that’s not necessarily an integer boundary, and we can only cause an extra increment on a whole-numbered step. If we choose a smaller S, we’d get too many steps, so we have to choose a larger S, and the next smallest S larger than N / R is ceil(N / R), which in our example is ceil(9 / 4) = 3.

Now we know how often we’re going to be taking an extra step, but how many extra steps will we take? If we add an extra increment every S steps, we’ll end up with ceil(N / S) extra steps. It’s somewhat unintuitive why this should be ceil. Basically, it’s because I chose to place the extra increment at the start of an interval of S steps rather than at the end. This makes it easy to do, because we just do the extra increment when CurrentStep % S == 0, but it also means that the very last step might be smaller than the preceeding steps. Consider the case when N = 3 and S = 2. If we number the steps 0, 1, 2, then you can see that the substep on interval [0, 1] happens at 0, and a second substep happens at 2, even though the second covered interval is incomplete.

So we end up incrementing every S = ceil(N / R) steps, giving us a total of M = ceil(N / S) substeps. That means the amount we should increment by each step is K = floor(R / M), leaving a new remainder of R % M. Ideally, K should be 1, and I think that since R < N (because R = N % T) this is always the case, though I haven’t proved it. However, allowing for K to not be 1 actually allows this approach to elegantly handle initial conditions where T < N by simply not having a special-case for the initial division of T / N, and instead computing it the same way with M = ceil(N / T), and K = floor(T / M).

What that ends up looking like is:

// limit is the total we're trying to reach, T
// rem is how much is left, R
uint rem = limit;
while (rem > 0) {
  // mod is the number of sub-steps between increments, S
  uint mod = CeilDiv(numSteps, rem);
  // div is the number increments that will happen, M
  uint div = CeilDiv(numSteps, mod);
  // incr is the ammount to increment by, K
  uint incr = rem / div;
  rem = rem % div;
  increments.Add((mod, incr));
}

For our example, 31 / 9, we get:

• S = ceil(9 / 31) = 1 and K = floor(31 / ceil(9 / 1)) = 3, with a remainder of 4.
• S = ceil(9 / 4) = 3 and K = floor(4 / ceil(9 / 3)) = 1, with a remainder of 1.
• S = ceil(9 / 1) = 9 and K = floor(1 / ceil(9 / 9)) = 1, with a remainder of 0.

This creates the following increment pattern:

To apply the computed increments, all you have to do is, for each step number C, check if each steps-between-increment S evenly divides C, and if so, add its K to the result.

private uint NextStepTotal() {
  if (step >= numSteps) {
    throw new System.InvalidOperationException("Already completed all steps");
  }
  uint total = 0;
  foreach (var (mod, incr) in increments) {
    if (step % mod == 0) {
      total += incr;
    }
  }
  return total;
}

There are still some possible improvements, for example, this approach tends to cluster larger increments around common factors, especailly 1, so some shift factors might help, but you’d have to be careful to limit shift amounts to be small enough not to lose any increments (so shifts must be smaller than the size of the last S-sized step), and you’d have to make sure that the behavior doesn’t make things worse for some numbers (numbers with more factors might naturally not overlap so much so shifting might cause more overlaps, but I haven’t characterized it to find out).

Boids Performance

One issue with Boids is that it requires each boid to take input from all the other boids in order to determine what it should do. With a large number of boids, this is an n^2 problem, not something you want in a game. Now, realistically, we don’t actually need to query all other ships, since Boids generally includes a sight radius outside of which influence falls off.

Rather than doing an n^2 loop, we can ask the game’s physics engine to tell us which other ships are nearby. The physics engine includes data structures which allow it to perform spatial queries more efficiently than we can with an n^2 loop, so that improves things somewhat, but it’s still a huge problem for lots of ships, especially if they are close to each other.

To deal with this, I added a physics-query rate-limiting system, so ships couldn’t completely tank performance if there were a lot of them. This results in decreased boid following (since ships have an outdated view of what other ships are nearby), but greatly improves performance.

This approach could be made even better if I found a better way to handle the queries. Specifically, the physics engine queries colliders, which are needlessly complicated for the boids simulation, which is fine with just point-based detection. So some other spatial query type could potentially improve performance again.

Target Selection

When their current target is destroyed, a player’s turrets will look for a new target within range. Like with the boids, this involves asking the physics engine for any enemy ships within a radius around the weapon. However, since players can create arbitrarily many turrets, the result is a huge number of queries, especially when there are no enemies around, since then all weapons have no target. Having worse performance when there are no enemies is a bit of an issue.

One thing I did to improve this was implement my own broad-phase target checker. The way this works is I divide up all of space into a grid of cubes. I provide a function that can quickly convert a 3D float vector into an integer-tuple index uniquely defining the center of the grid cube it occupies:

    /// <summary>
    /// Get the index of the cell corresponding to the given position in space.
    /// </summary>
    public static (int x, int y, int z) GetIndex(Vector3 position) {
      int x = Mathf.FloorToInt(position.x / CellSize.x);
      int y = Mathf.FloorToInt(position.y / CellSize.y);
      int z = Mathf.FloorToInt(position.z / CellSize.z);
      return (x, y, z);
    }

I then use these integer tuples as keys in a dictionary of grid squares. Why a dictionary? Using a Dictionary<(int, int, int), GridCell> doesn’t restrict the possible positions of grid-cubes the way a fixed-sized array allocation would, and only has to actually hold a grid-cell instance anywhere there is a ship.

To query the grid, you just loop through the indexes overlapping the area you’re interested in, and look up the corresponding tuple in the dictionary. This works best if the grid is relatively large compared to th size of a ship or turret’s search area, so that a query will typically only have to check 8 or 27 cubes. If the grid cubes are too small relative to the area a query is interested in, this approach quickly starts to cause more problems than it solves.