BoE waypoint system: How insects find their way

A detailed write-up on how I made the waypoint system in BoE.

Posted by on - Intermediate Client Side Coding

Hello!

Aside from enemy targeting, one of the base systems in Brink of Extinction is the enemy path system. Unlike many TD:s, BoE doesn't feature mazing. Instead the levels are open scenes, with the enemy routes more secret to the player. Underneath this, however, there is a system to decide where enemies can and can't walk and to be honest, it is quite simple. In this tutorial I will describe it and share some of the code!

### The requirements

First off, before coding the system I decided on some features that it needed to have:

1. It needed to automatically sort way points to speed up making the system.
2. It needed to be rigid enough to prevent inconsistency between game rounds while still looking smooth.
3. It needed to be fast to allow for many enemies.

This is how I went about building the system around these principles.

### Automatic sorting

Because BoE has many different paths at work at the same time, I use indexes to keep different paths separate. These are set up manually on the first waypoint "pylon" placed, and then just copied over to the next one as they are placed.

The pylons are then collected from the scene and sorted by index number by either x or z coordinates. This means that the system does have one limitation in that it doesn't allow for some of the most intricate level designs that mix x and z coordinates too freely. For example:

Designs one through three works in this system. Design pattern one can be sorted by x from first to last easily. Design pattern two can also be sorted by x as long as the level doesn't require the last turn to be greater than 90 degrees. Design pattern three works because it can be sorted by the z axis. Like in the second pattern, this is assuming the level design doesn't require the way points move away from the constant incremental position by z. Design pattern four cannot be done in this system, which I felt was an acceptable sacrifice for what I wanted to do.

On the Awake() function, all waypoints are collected, sorted by index, then sorted by x or z position depending on whether the index value is less than 0 or greater than 0. Here's the sorting code:

### Rigid smoothness

I wanted the system to produce paths that are somewhat fluid looking, but still rigid and consistent enough to not make game rounds arbitrary and subject to too much randomness in enemy paths. So once the positions are sorted, each position for each enemy is shifted slightly in both x and z. This means that each enemy has a unique set of way points to travel.

For enemies, a way point path can be traveled either in a positive or negative direction. Since sorting will place the waypoints according to their x or z positions, sometimes an enemy will need to walk through these in reverse order. Because of this, when the enemy is enabled, the enemies position is checked relative to the waypoint system it has so that it can get the index of the first way point it needs to travel to.

To check if the enemy is within reach of a waypoint, I check whether the enemy is within the radius of a waypoint:

If it is, then either increase or decrease the index of the waypoint list, depending on what direction the enemy is traveling. The system has a slightly random radius to make things look more lively.

The remaining code is just forward translate and rotation to check in what direction relative the enemy's current direction the next way point is. On top of this there's a system that checks if the enemy is very close to another enemy, in which case an offset is added to the goal position. This system make enemies not overlap too much, but I also don't want enemies to become confused about where they are going, or slow down, as this would make game rounds differ too much given the randomness of the positions etc.

### Speed

To get speed out of the system, I sacrificed some user friendliness. For instance, the radius calculations don't use square roots, instead I multiply the radius and so on. Since enemies are pooled, I only need to run the sorting and setup once, and every time the enemy is respawned it uses the same setup as it had the first time.

What it looks like in the editor (in a large scene!):

In game with randomness:

### Conclusions

Given that there are some things that can't be done in the system and that it's not always super intuitive, it is in no way perfect. But it has proven to be very functional for what I needed to do in the game, and has worked flawlessly - bringing thousands and thousands of enemies to a certain death ever since. ;)

/ Dispersing Minds