“When can we have a ship flying through a hole in a rotating asteroid?” – That was one of the first questions that Chris Roberts asked us when we started working on Star Citizen. We had been tasked with creating the dogfighting AI for this record breaking crowdfunded space sim, and as with all of Chris’s plans, his vision for the AI was no less ambitious. Getting an AI to navigate through an asteroid with a hole is already a hard problem, getting an AI to navigate through a rotating asteroid is a very hard problem, but this sounded like the perfect challenge to us – 3D pathfinding in a dynamic environment.

We achieved many impressive feats of AI flight during our time working on Star Citizen, including high speed dogfighting through dense asteroids and smooth formation flight around obstacles, and were extremely pleased with the result, we sadly never actually got the opportunity to work on navigating through moving asteroids. Despite Chris’ enthusiasm for advanced navigation, other more essential AI requirements, such as controlling the weapons systems and giving a good combat experience to players, had to come first.

However, Mike’s and my obsession with space games long predates Star Citizen. It was while at university, almost two decades ago, that we first met and became friends through our shared ambition to create our own massively multiplayer space combat and trading sim. A vision inspired no doubt by our childhood love of space games, such as Elite, Wing Commander and X-Wing. Since that time, we have created and released several small hobby projects on that theme, including Iridium Rising, of special note as it was the first (and probably only) multiplayer 3D space game for the Raspberry Pi.

One important lesson I have learnt through this process is that not only is good AI an essential ingredient for creating a fun game, but having interesting environments is also vital. Dogfighting in open space quickly becomes dull when there is no cover in which to evade or hide. Players need places from which they can sneak up on a target, or obstacles they can dodge behind. It is good design, building levels that includes varied settings that give games depth. However, a consequence of having complicated levels is that your AI inevitably need to be able to cope with moving round and through 3D structures, both for stalking and fighting, and complicated 3D structures require proper 3D navigation.

It was in 2016 while at Moon Collider, working with Digital Arrow on their forthcoming underwater submarine game Aquanox: Deep Descent, that we started to put together these years of experience to build our first attempt at a full 3D navigation. Digital Arrow needed their AI opponents to be able to fight in deep ocean caves and were looking to the Kythera AI middleware to help make that happen.

Kythera already contained 3D steering and avoidance functionality, but didn’t support pathfinding, and therefore a new system was needed. Our original plan had to been to implement a clever, dynamic waypoint based approach. However, waypoint systems have the fundamental problem that they don’t tell you what to do if you happen to get off the waypoint graph and make things like avoidance, where you might need to stray from the path, problematic. Instead we decided they really needed full pathfinding – surely it couldn’t be that hard?

There are two parts to pathfinding, firstly to build a navigation data structure with a simplified representation of the level geometry and secondly to search for paths through it. We were able to licence Enkisoftware’s excellent octree implementation for the first part, and to reapply A* search code from Kythera’s 2D pathfinding system for the second. Building upon these foundations we got a first prototype working within a month and were delighted that even with this initial version we were able to get the Aquanox AI submarines swimming through networks of caves.

Around the same time, Moon Collider was beginning a new partnership with Descendent Studios on their title Descent: Underground, a 6DOF shooter. They had the similar requirement of needing flying AI drones for their single player campaign. Much to our (and their) delight, with only a little modification we were able to apply the same octree and pathfinding system to their project and have new challenging AI flying around their levels after just one long weekend of work.

It was at this point that we came to the realisation that many developers want to have flying vehicles or creatures in their games, even if not necessarily as a primary gameplay feature. Perhaps the addition of birds attacking the ground based player character would add an extra dimension to gameplay in particular levels. Unfortunately, what frequently ends up happening is that these plans have to be dropped due to resource constraints, studios being unable to allocate the large amount of effort required to build their own 3D navigation and steering systems just for a secondary feature. If we could offer a solution that game developers can just drop in and have immediate results, saving months of effort, then that could be extremely valuable to a large number of people.

For this reason we made the decision to develop a standalone product to enable us to bring this technology to more games. In order to do this we have started a new venture, building upon what we learnt over the years, to build the next generation of 3D navigation systems. The result has been Mercuna, a complete 3D navigation solution for Unreal Engine 4.