Triangles and pathfinding for web games: Making a navigation system

As the most recent addition to the Raygun team, I got asked to write a blog post about anything I like, so this is going to have little to do with Raygun. I figured I’d write about the game I’m working on in my spare time.

Approximately two years ago I decided to make a real time strategy game (RTS) all by myself. This turned out to be a excellent decision, as I now have a hobby project I can work on for the remainder of my life.

After reading a few articles about the general structure of RTS games and having a few ideas myself after my highly successfully career as a Diamond Starcraft 2 player I got to work, and after two years of occasional weekend work I have something between a tech demo (which would be impressive in 1995) and a ball of spaghetti.

In spite of this I’d have to say that it’s been pretty enjoyable to work on something like this, especially when the larger systems come together.

One of the more interesting systems I’ve had to implement has been the navigation system, which itself is really a series of subsystems including spatial partitioning, pathfinding, path simplification and flocking mechanics.

One of the most important things when navigating is understanding how the terrain and the obstacles in it are situated. If we have a clear idea of what areas are nearby each other and which areas are transversable, finding a path becomes a lot easier. This is where spatial partitioning comes in.

Space can be divided up in lots of ways and in many games grids are used. In an older game such as Warcraft 2 the grid was obvious. Every unit occupied a grid space and all movement was in 1 of 8 directions from one grid space to another. So long as a space was not obstructed by another unit or obstacle, movement was valid.

Above you can see an area partitioned into triangles, this is another simple way to partition space. Given a set of adjacent triangles you can find a path from one triangle to another using A* just as you would on a grid.

A Triangulated map has many advantages over a grid partition as triangles can cover greater areas and are scale agnostic. For instance the area in the screenshot above is divided into only a few hundred triangles whereas a grid with each space being the size of the buildings would require over six thousand spaces for the same area. This saves a lot of cpu time as the number of areas to consider when generating the path will be much less.

In addition to these advantages the triangulated map allows for better reasoning about how to get from one place to another. We can think of the borders between adjacent triangles in the path as “gateways” (highlighted in yellow in the picture above). After finding a path we can deduce the gateways a unit would have to move though to get to their destination. This allows us to plan movements along the path in intelligent ways compared to a grid based path where the path would be narrow and very linear.

After finding a series of gateways representing the path we can use some simplification to remove gateways that don’t add anything to the description. This is done by iterating through the gateways and raycasting the left and right side of the next gateway and trimming any gateways which are completely visible from the previous one. This leaves us with only the essential gateways between the start point and destination.

Once we have a simplified set of gateways to travel through we can assign this path to the units and the path can be followed using a flocking system. Flocking systems allow for dynamic  movement by applying a variety of forces to each member of the flock to separate, align and attract them to their destination.

You can see the units are grouped together but spaced apart so that they each have room to move. Also since the destination is not a single point, units won’t clump themselves up when moving along the path through gateways.

Into game development? Raygun has error tracking solutions for all major programming languages and platforms, including Unity3D. Get started with a free 14 day trial of Raygun today.