Around The World, Part 14: Floating the origin
In the previous post, we got to see our generated world at close range. This revealed some precision problems that I knew I’d need to deal with eventually, but had been putting off for a rainy day. Now I could ignore them no longer.
The trouble with floats
Godot uses single-precision floating point numbers throughout the engine. I’ll call them “floats” for short. These numbers are stored in 32 bits. In order to allow both very large and very small values, these 32 bits are split into a mantissa and an exponent:
Source: Wikimedia Commons by Tanner, CC-BY-SA 3.0
The mantissa (“fraction” in the above image) stores the actual digits of the number, and the exponent indicates where the decimal (binary) point goes. The consequence is that floats don’t have the same precision throughout the number line: the larger the number, the larger the step becomes between two consecutive numbers that can be represented.
This is fine for most games, where the world is small. But as it turns out, a planet the size of the Earth is actually not small. At Earth’s radius, 6371 km from the center of the planet, 32-bit floats have a precision of about 0.38 meters. It’s a kind of grid that every object will be snapped to, and any movement will have to take place in increments of this step size. And this grid isn’t nicely aligned with the planet surface either, so sideways movement will often also cause the object to move up or down at the same time.
For most of the game, this amount of precision is actually still fine. I don’t plan to generate terrain triangles smaller than a few meters, and at that size any rounding problems will mostly be invisible. But for movement of the player’s ship, the lack of precision is an issue. It seems to jitter as it moves around. (“Ship?”, you say? Yes, I have been working on gameplay systems behind the scenes as well. More about that later!)
Non-solutions
Naively, you might think that we can just change the units of the scene to something smaller, like millimeters instead of meters. This doesn’t work because the numbers just get bigger – the digits of each number remain the same, the only thing that changes is the location of the decimal point in between them. Instead of a precision of 0.38 meters, you now have a precision of 380 millimeters.
A working solution would be to use 64-bit floating point numbers, or “doubles”, instead. For games at the scale of the galaxy, this still isn’t enough, but at Earth scale it’s plenty: a double has a precision of 53 bits, allowing for a precision of nanometers at the planet’s surface.
Godot actually supports using doubles instead of floats throughout the engine. There are a few reasons why I chose not to go this route. First, because it requires recompiling the engine from scratch – actually pretty easy for me, but a bit of a chore. Second, because it’s a fairly recent addition and probably not widely used, so I would expect to encounter bugs. And third, because it’s an all-or-nothing deal: everything in the engine will then work with doubles. This means that basic types like Vector3 suddenly take up twice as much memory, which also means that mesh vertex data takes twice as much memory and twice as long to upload to the GPU. SIMD instructions can only process half as many doubles as floats simultaneously, so CPU efficiency also suffers.
So, in the end I once again chose to make life difficult for myself, and implemented a hybrid solution.
Floating the origin
The key idea, which games like Kerbal Space Program also use, is that floating-point numbers actually are very precise — as long as you don’t stray too far from the origin. So, what if instead of having the origin at the center of the planet, we just put it where we need it to be? Instead of moving the player through the universe, we move the universe around the player. Things far away from the player still won’t be precisely positioned, but they’re so far away that we don’t care. (This idea goes back at least as far as 1984, to the original Elite game on the BBC Micro. This amazing website by Mark Moxon explains how that – and all the rest of that game – works in extreme detail.)
In fact I get to cut some corners here. Because doubles are precise enough for my needs, I can just store each object’s position in 64-bit double precision relative to the world origin. When it’s time to render the frame, I convert this to a 32-bit float relative to the player, for consumption by the Godot engine. This way, all my game logic remains in global coordinates, making it easier to work with. Because these are discrete game objects, not big arrays of vertices, the added CPU and memory overhead should be minimal.
However… now I need to put this 64-bit position on every object in the world. And that’s a whole new can of worms.
Components
Godot’s architecture is heavily based on object-oriented principles, and inheritance in particular. So if you need to have some functionality on every object, regardless of its position in the class hierarchy, you’re out of luck. You’d have to add it to the root Node3D class, but this is part of the engine itself and cannot be modified. (Granted, Godot is open source, you can in fact modify the engine. But I’d prefer to keep using the official builds, so I can easily keep up to date with the latest version.)
Fortunately, Godot’s node system is also very flexible. You can define the additional functionality as a separate node, which is attached as a child to every node that needs it. The new node is a kind of pluggable “component” that you can reuse wherever you need it. This article by GDQuest demonstrates that approach.
However, it never felt quite right. You often need to interact with the sub-node that stores the position, which is tedious, error-prone and slow. What if the node isn’t there, or has been renamed, or if there are multiple? Something that should be trivial (looking up a value on an object) turns into a pile of error handling.
There’s also the matter of memory efficiency. Once I’d started using such pluggable components, it made sense to consistently use them for everything. Tracking the health of an entity? A node. The speed? A node. The current camera focus? Another node. Most of these nodes contain very little data; a few numbers, maybe 16 bytes at most. Some are just markers that don’t store any data at all. But a Godot node by itself is a pretty heavyweight object: it stores a name, parent and owner pointers, a list and a hash map of children, a hash map of signal connections, a list of groups, a bunch of flags, stuff related to networking… hundreds of bytes all together, and all that for storing a few bytes of data.
An alternative approach is to have these pluggable components as plain C# objects, and put these in an array or in individual fields directly on each object. This is what I’d been doing so far. But it was a weird hybrid between Godot node scripts and pluggable objects, and it started to grate on me. It was time to go all the way and turn this into an ECS.
The ECS
ECS stands for entity component system, and it’s a popular pattern in some game development circles. The concept is explained very well in many other places, so I won’t rehash that here. Suffice to say that I chose to write my own, because it’s so fundamental to my game that I’d like to have full control over its features and implementation. And, as long as you don’t need squeeze out every last drop of performance, it’s not all that hard; it took me about a week fulltime to develop and port the existing game code over.
Here’s what it does, in a nutshell. This is going to get rather technical and requires some knowledge of C# and Godot to follow, so if you’re just here for procedural generation and/or pretty pictures, feel free to tune out.
Entities are identified by 64-bit integers. Entity IDs are never reused, but 64 bits are enough to ensure that they won’t run out. Components can be any C# type, including structs and Godot nodes. The overarching World class stores each component in a separate hash map, keyed on entity ID.
Central to the World is an event bus. Events can be any C# type, and objects can subscribe to events of a particular type. Systems are classes that subscribe to one or more events, by implementing the IEventHandler<E> interface. The World itself fires events when components are added and removed. Note that systems don’t implement a dedicated Process(float delta) method called every tick; instead, there is a Process event that they can subscribe to.
Additionally, there are “resources”, which are singleton objects keyed on their type. My procedural generation services are added to the World as resources, so that systems can access them. There is a simple dependency injection mechanism based on reflection, whereby systems can request resources through their constructor. (The new primary constructors introduced last November in C# 12 are great for this!) The event bus and the World itself are also injectable in that way, to allow systems to send events and to create/destroy entities.
Systems typically affect entities in the world through queries, which are also injectable. They are represented by the IQuery<...> interface, where the ... indicates one or more components to query for. The IQuery interface extends IEnumerable, which lets the system iterate over all matching entities and components and manipulate them in whatever way needed.
Right now I’ve only implemented “and” queries, where all requested components must be present. The actual iteration is implemented in the World in a rather simple way: the hash map of the first component is iterated over in its entirety, and for each entry, the hash maps for the other requested component types are probed to see if they’re all present. (If this were a general-purpose library, I would at least iterate over the hash map of the rarest component instead of the first, which is more efficient. But because I’m writing both the ECS and the game, I know which component is rarest, and I just list that first.)
The upshot of all this is that I no longer have node spaghetti. Everything is beautifully decoupled, there is very little boilerplate, and I feel much more comfortable and secure adding new functionality. Here’s an annotated example:
// Class components are mutable, struct components are not, because
// I failed to find a way to return structs by reference instead of value.
// So these have to be classes.
class Position { public Vector3 Value; }
class Velocity { public Vector3 Value; }
// Using the primary constructor to inject the query.
// The World takes care of constructing it and passing it in.
class MovementSystem(IQuery<Position, Velocity> query) :
IEventHandler<Process>
{
public void Handle(Process processEvent) {
foreach (var (position, velocity) in query) {
position.Value += processEvent.Delta * velocity.Value;
}
}
}
// Add this to the world (somewhere in the main function).
world.AddSystem<MovementSystem>();
world.BuildEntity()
.Add(new Position())
.Add(new Velocity())
.Done();
To integrate this ECS with Godot, I added a few special components and systems. There is the InTree component, which contains a Godot Node. The InTreeSystem listens for ComponentAdded<InTree> and ComponentRemoved<InTree> events, and adds/removes the corresponding node from the component into Godot’s node tree. Additionally, there is a generic system called NodeAddSystem<C> that takes a scene path in its constructor, and automatically instantiates that scene whenever a component of type C is added to an entity. The idea here is that I don’t want to store any data on Godot nodes directly, because nodes are difficult to save and load. Instead, data flows only one way: from components to nodes.
End of story
Okay, that’s enough talk about implementation details. I hope this makes it clear why I haven’t been posting any pretty pictures lately. I’ll try to make sure to have some more in the next post!