Auto-Leveling: How to Align a Ship
One of the most frequently requested features from the classic Descent games for DU was auto-leveling. Many players swear by it, and it's also a good set of "training wheels" for those unfamiliar with 6DoF or more traditional flight games. It's taken a lot of thought regarding implementation, and it's finally here in DU with the second "Jingle" build (2881).
Auto-level - a system by which the roll of the ship is automatically adjusted to align the ship to its environment, such that the player can stay focused on pitch and yaw when flying.
Roll - rotation around the forward-reverse axis. When a plane banks to make a turn, it's rolling.
Pitch - rotation around the left-right axis. Look up and down. You've just pitched your head.
Yaw - rotation around the vertical axis. Look left and right. Your head just yawed.
Raycasting - travelling along a straight line from a source point to a target point and reporting the first (or all) surface(s) hit along the way.
Cube - in classic Descent, the fundamental building block of any environment in the game. Every space in those games is built out of deformed cubes whose sides can be closed or open. The data structure behind these cubes was fundamental to the way the classic Descent engines worked, right down to the renderer.
A History Lesson
The implementation of classic Descent's auto-leveling system was simple - the game knew which cube the player's ship occupied, so it was a simple matter to determine which face of the cube the bottom of the ship was most closely aligned to, and it could be rolled to match. This does not adapt well to modern games, and there are a few reasons for this:
- The concept of the deformed cubes was essential to get the games to run at an acceptable rate back then. Graphics cards hadn't been invented yet, so the functionality we now rely on them for was performed by the ill-suited CPU, using a software-based renderer. One could go into all sorts of detail on this topic, but, basically, cubes made it a lot easier to run. Nowadays, we don't have those kinds of limitations, so structures like that have fallen to the wayside. As such, the data that these cubes tracked is no longer simple to keep, as a ship now exists in "space", rather than a location relative to the cube in which it resides.
- Because environments are built out of arbitrary geometry, there's not necessarily a flat, well-defined "floor" to which to align. Take BAMM, for example. The bottom section is mostly rough rock. Barely any of that is flat, even checking against simpler collision geometry, so aligning the ship to the surface directly below it is out of the question, as that would result in something like this:
- Even putting aside rough surfaces, there's another kind of geometry that causes even an approximation of the classic system to fall apart: round tunnels. Alignment to the surface of a round tunnel is basically impossible, because the target changes as the ship rolls. This would make flight in Tycho infuriating.
What to do?
The first line of thought, and this was kind of alluded to in the section above, is simply checking the surface below the ship. While we don't have cubes anymore, we do have the magic of raycasting. We could raycast straight down (relative to the ship, of course) from the center of the ship, but we'd run into the issues mentioned above.
Another idea pitched way back when was to simply auto-level to -Z (straight down relative to the world). There are three issues with that approach that caused us to reject it: First, it is a severe step back from the functionality that existed in classic Descent, since a ship wouldn't be able to flip over with auto-level engaged. Second, it'd make levels like Tycho completely unflyable, since Tycho relies on being able to realign to the plane of a ring to fly through it effectively. Finally, this approach does not handle the all-too-common situation where a ship's nose is pointed directly up or down.
In case you've never met a programmer before, here's something that drives us nuts: unhandled cases. A programmer must always be on the look out for so-called "edge cases", otherwise, those sorts of situations don't get explicitly handled, which leads to a programmer's worst nightmare: UNDEFINED BEHAVIOR. So, yeah, that last issue with the -Z option really cheesed my onions.
So, once we decided against these approaches, we kind of let the issue sit for a while. "A while" in this case probably being well over a year. Meanwhile, every so often, we'd get someone asking where auto-leveling is. And then just a couple of weeks ago, I had an idea.
The Running Average
Doing a simple raycast from the bottom of the ship wasn't going to work, I knew that, but what if I did multiple raycasts and averaged the result? And then, from there, to keep flight smooth, keep a running average of the results over the past second or so?
The basic principle was something like shocks in a car. Each wheel is equipped with a spring, such that, when a car goes over rough terrain, the springs keep the chassis from jerking suddenly and allow the wheels a bit of freedom in vertical movement. That was the thought, anyway. In practice, it didn't do much better than a single raycast would have. In addition, there was a case I hadn't even considered, one that would have never come up in classic Descent: corners.
Of course there are corners in classic Descent, but they're the unrealistic old-game kind: infinitely sharp. Real corners have curves (heh), and so modern games, including DU, have corners that have in-between surface geometry. On no map is this more apparent than Rama.
This edge right here made the development of the running average approach incredibly painful. One would typically fly the main room of Rama aligned to the floor, but that stupid edge, even with only one cast hitting it, would cause the ship to roll, which would then get the other casts to hit the wall below it, so you'd end up sideways, more or less. Disorienting and unfun.
Speaking of disorienting and unfun, another place where this method broke down was the U-shaped tunnels in each base of Colosseum. I tend to fly through them vertically, not bothering to rotate with them. With this auto-level implementation, I would invariably come out of them sideways.
There was another issue with this approach: raycasts take up more CPU time the farther they go, so there needed to be an upper limit on how far they cast out. This creates a -gulp- unhandled case. Wanting to avoid UNDEFINED BEHAVIOR (which, in this case, ended up being turning over infinitely), I came up with a way to handle the out-of-range case: default to the world axes.
For the sake of map-builders' sanity, our map kit is built to align to the world axes. As such, it can very easily be assumed that any given room large enough to let a ship go out-of-range on its level casts would be completely aligned to the world. So the ship would just roll to the nearest world axis. Easy enough.
So a ship near the floor would level to follow the geometry of the floor, while a ship up high would not. Playing around with this, I realized that the world-alignment just felt better. So I decided to try it with only world-alignment.
Stupid edge in Rama: resolved. Curved walls on the side of Rama: resolved. Curved tunnels which still exhibited some of the behavior mentioned above: resolved. Uneven surfaces: resolved. Grates: resolved. Random slants: resolved. The Colosseum U-shaped tunnels: resolved.
It felt so good. Again, the map kit is aligned to the world axes, so, as it turns out, any space within a map would be aligned to the world, at least in the direction one would be flying anyway. This difference is best made apparent in the outer ring of Mobius. All those tunnels are slanted, so flying sideways down them would have a ship drag along the floor or ceiling. But who does that for any appreciable distance?
Because the world-alignment method was so successful, I completely removed the raycasting code and packaged it all up. This was finished a day before the first "Jingle" build (2874) was put out.
Of course, you can, just like in the 90s, just turn it off in the settings. Personally, I haven't even bothered to turn it off, and I despised the implementation in the old games.
The Rest of the Story, for Pedants Like Me
For those of you familiar with 3D math and linear algebra and the like, you'd know that of course you can't roll to align perfectly to an axis if you're pitched away from alignment with it. Technically, what's actually happening is that the nearest world axis is projected onto the ship's YZ plane (X being the forward direction for Unreal) and then the roll is made towards that direction.