Six Degrees of Pain in the Ass
One of the more interesting aspects of working for Egosoft is that, unlike most game projects, we deal with a full six degrees of freedom. Our games take place in space, so you can go up, down, left, right, forwards, backwards... and you can pitch, yaw, and roll. Your ship, in short, can move pretty much in any way possible in 3D space.

This leads to a number of interesting challenges along the production process, both design and technical. One of them includes the movement of AI ships through 6DOF space.

As we work on The Next Big Thing From Egosoft, one of our goals is to have AI that flies in really interesting and challenging places. In the past, we've used fairly simple bounding-sphere collision avoidance based systems; they're fine for making sure two freighters don't run into each other in peaceable trade lanes, but when it comes to a good, old-fashioned, World War I Flying Ace style furball, it just doesn't cut it.

In fact, one of the things that inspired me to apply to work at Egosoft in the first place was the AI behaviour from the first game in the X series, X - Beyond the Frontier. The game was fantastic but hampered by a rather pitiful combat AI that was easily predictable and woefully unresponsive - to the point where crashing into other, weaker ships was often more efficient than trying to shoot them down. This problem persisted into X2 - The Threat until one of the game patches, and sadly hasn't entirely gone away even in our latest installments to the series.

So for me personally it's really important that we nail this flight AI and deliver some kick-ass moments. That means recreating what I've begun referring to as "the Death Star experience." In the legendary scene from Star Wars, the tiny, fast, maneuverable fighter craft all buzzed around near the surface of the massive, slow, lumbering Death Star. What made it interesting was the proximity of the fighter ships to the surface of the station; there was danger from other fighters, and giant laser guns, to be sure - but there was an even more interesting danger, which was slamming into the station itself. (Let us all pause for a moment of silence in honor of Porkins.)

Of course this came back for an even better reprise in Return of the Jedi, where instead of just flying around near the second Death Star, the Rebels actually had to fly into it. What could be cooler than having a giant, laser-fueled furball inside a massive space station that can obliterate entire planets?


I really want to be able to capture that kind of experience in The Next Big Thing. Maybe not with Death Stars per se, but asteroid fields (who could forget the classic moments from The Empire Strikes Back?), or giant space refineries, or whatever else we might see fit to cram into the universe. And that means good 6DOF AI.

Early on we decided on using navigation meshes to define areas near large objects where smaller craft can fly safely. Combined with other methods for free-space flight, we can provide seamless movement into and out of the navigation mesh system, so that as the AI sees fit, we can either have nice, peaceful, wide-steering, deep-space-style flying, or we can have white-knuckled terror as you corkscrew around a giant fuel pipeline at several hundred miles per hour.

The challenge is that we want to be able to connect objects in space dynamically. Players of the X series will be familiar with station complexes, where dynamic links between space stations can connect a handful or even dozens of stations into a massive single structure. How do you take a navigation mesh created statically, and turn it into a dynamic entity that can provide both high-resolution navigation detail as well as realtime performance?

Here's some tips from my bag of tricks.


A Method for Connecting Navigation Meshes for Six-Degrees-of-Freedom Movement Systems
This method has two prerequisites. First, we need the navigation mesh data for each disparate component of a compound object; that data should be initially defined so that AI can path successfully around the surface of that object if it is free-floating in space. Secondly, we need a low-resolution collision mesh of the actual geometry, so that we can do some quick culling checks later.

Now, suppose we have four or five components that need to be linked into a compound object, such as a giant space station. Each has its own individual, separated navigation mesh and collision geometry. I'll deal with connecting the navigation meshes here; merging the collision geometry is a fairly textbook exercise in CSG and isn't too terribly difficult, or expensive for that matter, provided that your collision mesh is suitably low-resolution.

The first phase of the process is to gather all of the nodes and edges of each disparate navigation mesh, and combine them into a single graph structure. This can be done with a graph storage mechanism of your choice, but it is important to retain both node position and edge connection data for later on in the process.

Once we have a nice node soup brewed up from the separate components, we perform two rounds of culling. Firstly, we check each edge against the collision geometry of the other objects to ensure that we don't overlap any navmesh edges inside the collision bounds of another object. This is a straightforward set of ray/mesh checks and should be fairly quick given a suitable acceleration structure, such as the ones provided by many physics libraries. The second phase of culling is to remove all nodes that are "orphaned", i.e. have no connecting edges. This will reduce the overhead of later phases of the process, and is generally a pretty fast operation as well.

After culling out some of the extras from the node soup, we need to identify each group of connected nodes in the graph (mathematically speaking, we need to find the set of all connected components in the graph). For example, we may have a clump of nodes that are all interconnected over on one side of the graph space, and another clump on the other side, but no edge that connects the two clumps. We need a method to identify this.

Fortunately, this is easy to do using a simple algorithm:

For each node N in the graph   If N has already been seen in a connected component, skip it and move on to the next node   For each edge E that connects to node N      Push the node N2 on the other end of the edge E onto the "open list"   While the open list is not empty      Select the first edge E on the open list      Add the nodes N1 and N2 connected by edge E to the current set S      Add each edge connected to node N2 onto the end of the open list   S now represents a connected component of the graph; shift it onto the list of connected components

Once we complete this process, we will have a list of all connected components of the graph. Now it's time to connect them all together, so that we have a final graph that consists of a single connected component.

Connecting the components together is relatively straightforward:

While there are more than one connected components in the graph   Construct a bounding box surrounding each connected component   Find the two components C1 and C2 whose bounding box centers are closest   Find the closest pair of points between C1 and C2, where one point lies in each group   Ensuring the edge does not intersect with any collision geometry, add an edge between the two located points   C1 and C2 are now a single connected component

If the collision check fails, consider falling back to the second-closest pair of points, and so on.

Obviously this can be improved on quite a bit; for example, I use a kd-tree to accelerate the location of the nearest-pair. Bounding boxes don't have to be recomputed every iteration, but can instead just be updated by merging the bounding boxes of C1 and C2 after each connection step is performed. Experiment with the selection method of C1 and C2 as well; depending on the overall shape of your meshes and how they interconnect, you may get better results with a different selection heuristic.

Lastly, consider doing a k-nearest-neighbor search instead of a nearest-pair search when selecting nodes for adding new edges; this will considerably slow down the merge process, but will result in much more robust "stitching" of the navmesh components rather than just connecting them by tenuous little threads. This might especially be important depending on how you utilize the navmeshes, e.g. if you have a very large number of pathing agents and need them to be able to move in "parallel" rather than get tied up at artificial choke points.

A final word on performance: the killer here is memory allocation, and if you can use pooled allocators and any other trick possible to avoid dynamic memory management overhead, so much the better. With good memory strategies and sufficiently good heuristics/acceleration structures, you can easily merge very large groups of mesh data in a matter of a few seconds. This isn't quite "realtime" in the sense that you can be screwing with the navigation mesh every few frames, but in our case (where building station connections, for example, is a rare and slow process from the player perspective anyways) it's a totally justifiable cost, given the returns.


So go forth, merge some navmeshes, and blow up that Death Star.