Game Pivot and Trajectory Interception Deep Dive

Hey all! In this dev log I'll talk through the design and technical challenges associated with trajectory prediction and AI in an ambitious project like Retrograde: Legends and how an ultimately design driven core loop pivot has enabled me to leverage months of prior learning to build a better technical approach to orbital mechanics AI behavior in a fraction of the time.

First, some background: I'm refactoring much of Retrograde's core loop to focus more on what's really fun - orbiting planets and blowing stuff up in microgravity. As part of that I've decided to move away from the economic and open-world simulation aspects of the game that seemed to distract from the core experience. 

The game's new direction is a darkly humorous, orbital mechanics roguelike in which you are stellar warlord bent on conquering the galaxy one planet at a time. Engage in Newtonian physics powered pitched battles in orbit around planets, moons and stars. Use real-world inspired propulsion systems, weapons and sensor mechanics to destroy all resistance. Collect materials to add components to your ship and maintain your home system's Dyson sphere on your quest for galactic conquest.

The Challenges Associated with Trajectory Prediction and NPC AI

The previous iteration of the game yielded a depth of knowledge about the design and technical puzzles involved in building such ambitious gameplay and AI systems tied to orbital mechanics and the vast distances involved in a believable hard sci-fi space sim, originally set in our solar system. 

The AI in particular became a serious concern from a technical perspective due to performance problems and from a design perspective due to the difficulty of getting NPC ships to traverse and fight effectively and believably. First: the calculations required to complete necessarily long and detailed trajectories and collision predictions for all AI ships coupled with the AI's reliance on on-demand calculation of hypothetical trajectories to determine optimal maneuvers created huge performance bottlenecks. 

Second: the major shifts in navigational scale that enabled the AI to tread the needle between other ships or dock at a station while also being able to plot accurate courses between planets within a solar system were very difficult to maintain and required a lot of "magic numbers" that led to bad AI behavior when anything from the scale of the map to the mass of reactors changed.

Third: because the first iteration of Retrograde: Legends was not just an orbital mechanics and combat sim but also a living-world and economic sim, NPC ships had to be managed on two separate logic layers, meaning the ships had to be able to manage navigation within the physics simulation using their trajectories and propulsion systems while also being able to despawn themselves at any moment and continue functioning through a lower resolution "strategic layer". This transference of data between two separate simulation layers in order to create seamless and consistent encounters with NPCs across huge areas greatly increased the technical complexity of both layers and the intermediary logic that managed transferring NPCs from strategic to physics simulation and vice versa.

Approach to NPC AI in the Pivot

After months of work and testing, I decided to pivot the game to be smaller scale and more focused on the most fun interactions I'd discovered in the earlier prototype. There are many reasons this is the correct way to serve the vision of an fun, accessible, hard sci-fi, orbital mechanics game but I'd be lying if I said that getting a chance to start fresh on the AI without all of the economic and strategic sim logic wasn't a major draw to a smaller version of the game.

In the new iteration of Retrograde: Legends, the player fights through a myriad of procedurally generated star systems one planet at a time. Because the play area is now constrained to a single planetary system at any time, the performance and trajectory resolution concerns that plagued the previous iteration of AI are much less of a concern now.

This has allowed me far more headroom to create finer resolution trajectory predictions giving NPC ships more detailed information about their environment and potential collisions and intercepts and also freed up production time to be spent on overall better AI behavior rather than wrestling with the basic technical design of the prediction systems.

How Does Trajectory Prediction Work?

There are several methods that can be used to predict the trajectory of objects influenced by one or more gravitational fields. The method I used for the first iteration of AI and trajectory prediction is basic numerical integration. The method I've chosen for the second iteration is a slight variation on that technique but using a dynamic timestep.

Here's how it works. Every object in the game has a position, velocity and acceleration at any given time. Position is self explanatory. Velocity describes how fast an object is moving and in what direction. Acceleration describes how quickly an object's velocity is changing and in what direction.

Using these variables, it's possible to describe the path an object will travel over some future period of time, given we know that object's current velocity. 

You must decide on how many points you want your object's trajectory to have then determine the timestep between each point. More on the time step later. The first calculation we need to do is to determine the object's current acceleration. This is influenced by whether the object is under thrust and the direction and magnitude of any nearby celestial bodies. Acceleration here describes how much our velocity changes due to external forces acting on this object over the next time step.

Acceleration = Gravitional Acceleration + Thrust Acceleration

The next step is applying our new acceleration to our velocity. We have to multiply the acceleration of this time step by our delta time. This describes how much time should have passed between this step in our trajectory and the last.

Velocity = Acceleration * Delta Time

Velocity is just change in position over time so in order to determine the position of our object at the given point in time, we add velocity to position.

Position = Position + Velocity

The formulas themselves are very simple and more importantly, easy to maintain and read. I've found the complexity comes mainly through the implementation of the algorithms to be performant and the set up of the backing data to be accessible and organized in such a way that allows AI systems to answer the questions they need without needing to redo work each on demand while also providing accurate enough predictions to be able to moderate the rate at which the trajectory prediction needs to be recalculated.

The new position, acceleration and velocity are stored in an array and the new position is compared against every other point in every other trajectory being calculated. This full list of trajectories is pruned to ensure that only objects that really need trajectories calculated are being worked on such as all ships, missiles and any object that an NPC ship might be tracking.

Trajectory collision detection is the most expensive part of the entire trajectory prediction and AI system because of the number of times the algorithm is required to iterate. If there are 20 ships each with a trajectory 100 points long, each ship must check its 100 points against the 100 points of nineteen other ships. This piles up to a big performance pileup very quickly.

To alleviate this strain, trajectories are split into groups which are calculated in batches spread across multiple frames to keep the per-frame performance impact of increased trajectory loads at the expense of each trajectory's refresh rate which is acceptable for the level of detailed needed for a cartoonishly scaled game like this.

A knock on effect of a smaller play area in this iteration of the game is that I'm able to tweak how the time step in the trajectory prediction works. Normally in solving a problem like this you want to keep the time step of each trajectory point constant to ensure accuracy. However I wanted to be able to build trajectories that maintained a set distance per step to allow for longer trajectories at more consistent performance cost to avoid some big pitfalls and inefficiencies at longer trajectory lengths observed in the earlier method.

The new method uses a dynamic time step estimated from the calculated time step of the previous trajectory point to scale acceleration and velocity. The pseudocode goes as follows:

Acc = Thrust Acc + GravAcc

Vel = Vel + Acc * Last Delta Time

Pos = Pos + Vel * Last Delta Time

Delta Time = Point Distance / Velocity.Magnitude

Last Delta Time = Delta Time

Of course removing the fixed time step in favor of a fixed step distance introduces inaccuracy into the trajectory prediction immediately but I've found that the newly reduced playspace size renders the short term inaccuracies with this method a non-issue especially when coupled with direct velocity tracking intercept methods at short-distances. The performance and overall long term accuracy improvements make up for it in other areas as well.

AI Logic and Trajectory Interception

If you're still with me, thanks for reading! You're probably wondering when I'm going to get to the point. Here it is! 

The biggest shortcoming of the prior iteration of AI's logic was its difficulty in intercepting and staying within a given range of a target. For a game in which much of your time is spend fighting NPC ships, their inability to perform this basic task consistently was a huge turn off.

The ability to chase a target and stay with it is basic and fundamental to any game's AI. The microgravity, frictionless, variable acceleration environment of Retrograde's game space makes this already complex problem even more difficult. 

The main problem to solve is: what heading and burn time is required to achieve an interception with a target object (likely also under thrust and definitely being gravitated) where the two objects come within a given radius of each other at the same time? After playing the game for a few minutes, figuring this out as a player becomes fairly second nature, but teaching it to a computer is much harder.

Because objects are always being gravitated towards a planetary body, giving them variable acceleration even without thrusting, the usual Physics 101 solutions to interception problems don't really apply. Additionally, the direction of the encounter cannot be assumed and because these are vehicles that can thrust at any time the solution must be flexible enough to respond to rapid changes in velocity.

I searched for solutions online and found some interesting whitepapers out of the industrial robotics and missile guidance fields that solved similar problems but these approaches often assumed clear line of sight to a target, which can't be assumed while orbiting a planet, or massive difference in delta-v between interceptor and target such as a missile chasing down a plane, which also can't be assumed given we want to solve both ship to ship and missile to ship interception here. Without a easy precedent on how to solve this, I tried to break the problem down into component parts and tackle it step by step.

The first step is to determine the closing speed of the two objects. Closing speed tells us whether the objects are moving closer or further from each other and how quickly. I found a great formula online for this and use closing speed to estimate the time it would take for the interceptor to hit the target given its current velocity magnitude and closing speed. This time estimation isn't very precise but its function is to provide a sufficient approximation for the closest intercept point. This estimate becomes more and more dialed in as the interceptor closes distance to its target.

Once this estimated intercept point is determined, the challenge becomes how to rotate and thrust the interceptor in order to adjust the equivalent point in its own trajectory to match the point in the target's trajectory.

By thrusting the interceptor in the direction of the line connecting the future point in its trajectory to the future point in the target's trajectory we can fudge a decent heading. I'm still fiddling with blending positions and velocity vectors of the two future trajectory points here to determine the interceptor's thrust heading. Using one or the other tends to over or undershoot depending on the closing speed of the engagement.

Once our heading is determined, we calculate how much change of velocity is required to achieve the desired trajectory change and convert that into a burn time and then let it rip. This works well enough but calculation has been underestimating burn time. I think it's due to not taking the effect on required delta-v gravitational force has but because the decision loop here refreshes fairly quickly, interceptors are able to make up lost burn time by iterating over the logic again and burning again as needed. 

Conclusion

This solution to trajectory interception in a microgravity and frictionless environment is not an accurate representation of how interceptions like this take place in the real world. An "arcadey" game like Retrograde requires ships to exhibit levels of thrust and specific impulse that are farfetched in order to yield engaging gameplay. The resulting maneuverability changes the problem space but doesn't diminish the difficulty of calculating and achieving trajectory-based intercepts in orbit. The actual solutions to intercepting an object in orbit around a body normally involve transfer orbits, take place over a much longer period of time and tend to assume well comparatively behaved targets. 

Overall this system took about four work days to build. This represents a fraction of the time spent on the prior iteration of AI traversal and interception and I'm very happy with the performance, utility and consistency of the new system. There is still a lot of functionality to add to AI but the current state is good enough to move forward with into other mechanics.

The improvement to performance gained from better handling of trajectory data and the removal of "hypothetical trajectory" checks also can't be understated. With 20 ships active and navigating in the prior iteration of Retrograde, I was lucky to hit 45 fps. Now with 20 ships, 120+ is achievable. The game feels so much better. 

It feels great to have this problem worked out early into a pivot. AI was a risk that ballooned in severity over time in the prior iteration of Retrograde so it feels good to have learned from that experience and attacked this problem head on a week into a big pivot. Having functional and flexible AI ships provides an important base for porting, refining and testing the game's combat and prototyping the roguelike core loop. I can't wait to share more! Thanks for reading.