Header image

Legendary Orbit Golf: Lessons Learned

posted by Unknown | 06 October 2020

Trying to solve NP-hard problems in realtime is not a good idea

Legendary Orbit Golf (https://ldjam.com/events/ludum-dare/47/legendary-orbit-golf) procedurally generates a small universe, which is a field of planets. In order to not look over clean and make the paths between the start and the destination hard enough to be interesting, we didn't want just spawn them into a fixed grid (quad or hexagon grids come to mind). Instead they should be spaced unevenly and the planets with various sizes should try to pack close together while never overlapping. This problem is commonly referred to circle packing, specially circle packing with different circle sizes. Unfortunately this problem is NP hard and kinda time consuming to find good solutions. The original game idea included a infinite universes, so that you can shot into any direction are guaranteed to eventually hit a planet. We cycled through a various approximation approaches to get a stable planet layout in a reasonable time, the final solution is fairly simple, but is unable to execute continuously, because it is too slow. So we are now just generating one finite universe on startup and that it. Trying various approximation approaches and trying to integrate them and debugging problems around it probably took 2 people over half a day of time.

Celestial mechanics are kinda complicated

The game is basically a gravity physics simulation. But instead of being perfectly realistic, we are making a game, so we have to bend physics. So a general n-body simulation would not fit the intended game play, as this would be to hard for the player to easily chose stable trajectories and for the game it would be too hard to procedurally generate a "fun to play" planet constellation in a reasonable time. Hardcoding a universe would take too much time too.

So we ended up doing simple 1-body simulations, considering the masses of planets and the spaceship vastly different, make the ship insignificant. Planets do not interact with each other gravitationally, they have a gravity well defined by a simple radius and these radi do not overlap, so the ship is only ever being affected by one planet, making a log of game logic and gameplay a lot simpler.

A surprise here was, that single precision floats are not precise enough to do even these simplified simulations, which lead to various inconsistencies between the displayed path (which was simulated using fixed time steps) and the actual movement of the ship (which is simulated using Unity's Time.deltaTime) causing all sorts of problems. Trajectories that were predicated to fling-shot around a planet suddenly spiraled into the planet, orbits where unstable when they should be stable, stable ellipse trajectories around a planet converged to a circle and so on. In the end this took some gameplay adjustments ("it's not a bug, it's a feature") and some more math (kepler's equations) to get consistent results. The simulation and all the problems around it took one person easily over a day.

Learned Lesson

Develop your ideas further early on, invest some more time into researching solutions and possible complications around your key problems (here universe creation and simulation). Toying around and cycles through various, possibly vastly different, approaches during the jam, possibly needing massive refactorings will slow you down and will introduce lot's of subtle bugs.