It’s always bothered me a little that ships in Aurora cannot predict the course of a planet and adjust their own heading to minimize the trip time, so I made a little toy program to see how hard it would be. Here’s a video of the result:
http://db48x.net/Aurora/four different ways of plotting a course in Aurora-2021-08-07_18.33.48.webm(If anyone knows of a way to embed this in the post without uploading it to Youtube or Vimeo, let me know.)
The simplest thing to implement is what Aurora does; each ship simply heads directly towards the planet at every tick. These ships are shown in red, and as you can see they fall behind the planet and must catch up just as ships do in Aurora.
The next thing to do is make a simple measurement of the time it will take to reach the planet, then head for the place where the planet will be in that amount of time. These ships are shown in orange–red. Unfortunately this simple strategy overcompensates and causes the ships to get ahead of the planet before turning towards it.
Since neither of these strategies is amazing, perhaps we need something more sophisticated. A key observation is that we are trying to find an initial heading that minimizes the distance between the ship and the planet; ideally the ship should be zero pixels away from the planet in order to land.
We can easily search this space by considering the distance between the ship and planet at a grid of points in space, and finding the one that gets us the closest. These are the orange ships; you can see that they rarely find a heading that gets them close enough to land, so most of them miss. This is easy to write but rather imprecise in practice. Note that these ships only calculate their course once, on the frame that they are spawned.
For reference, here is a screenshot showing all the points that it considered; the coarseness of this grid is why the ships usually miss. Making the grid finer can make the ships miss less frequently, but at a higher runtime cost. Still, my toy prototype maintains 60fps…
To do better than this we can use a little calculus. Instead of considering points on a fixed–size grid that will always be either too coarse or too expensive, we should adjust the point based on the
slope of the function we are minimizing. This search strategy is called “gradient descent”, and the white ships use it. You can see from the debug output that the search always stops once it gets within half a pixel of the planet, and that it usually only takes a couple of dozen steps to find this point. Occasionally it takes many more, but even so it doesn’t blow the frame budget. Like the grid search ships, these only need to calculate their course once.
I suggest that Aurora should have better navigation. My prototype shows that it is entirely feasible; I didn’t even have to implement gradient descent myself; I just used an open–source library for that.
However, I do want to point out that my prototype does have some flaws, which I have arranged not to show off in this video.
If the jump point is very near the orbit, then the gradient descent search goes a little off the rails. It still finds a good solution, but it can take seconds instead of milliseconds. That’s terrible in a 60fps game, but it would be completely unnoticeable in Aurora. Also, it’s probably just a bug in my code rather than an inherent problem with gradient descent.
One thing that is a problem with gradient descent is that sometimes it finds a solution
in the past. These solutions only work if the ship and the planet both run backwards, which would be silly. The gradient descent algorithm just looks for minima of the function you give it, and this one has more than one of them. In fact, it has infinitely many since the angle wraps around. Mostly those aren’t a problem, though it is funny to see it pick an optimal heading of 16.622303 or −46.64971 radians. I’ve partly solved this problem with an exponential penalty for negative time values and with a better guess for the starting conditions for the search, but it isn’t perfect. I think that if I picked those initial conditions using a simple grid search (like the third type of ship uses), then it would go away entirely.
The third problem is that my collision detection just looks for ships that are within 1px of a planet. That usually works, but if the planet and ship are headed towards each other then they can move past each other between frames and the ship never lands. That’s easy to fix, I just didn’t do it. We’ll just pretend that the captain was napping and the crew didn’t want to wake him.
Another limitation is that I have not yet written the code to do these computations for moons, moons of moons, etc. This would be quite trivial to do for the first three algorithms, and should only be moderately annoying for the gradient descent search. For that one I have to actually compute the derivative of the distance function; luckily I don’t have to do that by hand.
I put my code
on GitLab in case any one is interested in taking a look or running it themselves.
