Data flow in a property centric game engine

Original Author: Fredrik Alströmer

Introduction

I stopped taking on contracts about a year ago to focus on building my own indie game. I decided to build my own engine, and I know, I know, indies shouldn’t build their own engine, but let’s ignore reason for now and instead focus on something else. I wanted to build a property centric engine, using composition for pretty much everything rather than inheritance.

So what does it mean when you say you have a property centric model? In contrast to using inheritance, a game object might no longer be a renderable, physics-simulated, camera-trackable, weapon-carrying, and enemy-discoverable object. Instead it has the corresponding properties.

So what? Potato, pot-ah-to, right?

Well, not really. When a player is playing the game, they see distinct objects, perhaps a couple of monsters, wielding broadswords, strolling down Sunrise Lane or, who knows, maybe a heavyset man in a suit and a hard-hat blocking off the George Washington Bridge. Basically, what the player sees is this:

Fruit Salad

However, the advantage of having a property centric engine, is that instead of dealing with it this way, we have the option of organizing our things somewhat differently. What if we instead dealt with our entities like this?

Sorted Fruit Salad

That is, we have monsters, we have broadswords, and we have Sunrise Lane. (As a side note, these images makes me think of scatter/gather I/O, am I alone here?) Of course, the analogy is greatly simplified, and — as I hinted at above — we’d have a great number of different properties of which only a few are directly related to actual visible objects and their shape. I like this layout and the way it allows us to deal with all instances of a property at once.

The bridge

So how do we create the bridge between the engine’s sorted and ordered view of the world, and the player’s view? An object is bound to have dependent properties, for example, a rendering geometry property which depends on the physical simulation property, so we need to somehow combine them to give the illusion of being independent objects, rather than independent properties.

Data exchange

My research into a property centric design was driven by a fascination for data oriented design, and specifically the “where there’s one there are many” mantra. I got obsessed with arrays of raw data, of lean structures. I wanted this to be the core of my engine.

Each property is handled by a separate manager, which takes care of both memory allocation and ‘ticking’ or updating the properties each frame, and it’s free to move data around and sort it as it sees fit. The data itself is dumb, straight arrays of floats or perhaps structured in groups of vectors or quaternions, or similar smaller groups of data which is generally accessed together.

Raw data in this structure-of-arrays layout can’t really do inheritance (in the traditional OOP sense) even if I wanted to, so the property centric model became the natural choice.

Read and write data

With arrays of raw data, the easiest solution to fetch information from, or pass information to, a different component is to simply read or write the data directly using pointers. This also has the advantage that there can be no immediate side-effects as we’re not calling any functions, and we’re certainly not calling any virtual functions. This approach has several draw-backs, but what it lacks in flexibility, it makes up for in a lack of complexity, so we’ll need to be aware of the limitations and work accordingly. I’ve often found that having to adapt to a simple mechanism has a tendency to make it more robust too, so there’s also that aspect.

We’re effectively passing messages back and forth, quite similar to a data bus. We don’t need to know who receives the data, or who sent it, all we care about is that it is formatted correctly, and how to slap a destination address on it, which is a nice characteristic.

Semi-standardized memory blocks

If we define a set of standard memory blocks, and try to use these as often as possible in our properties, chances are we don’t need to worry about data formatting very often. If you look closely, you’ll notice that data that you typically would want to pass around is probably already using a small defined set of data types. For example, I have a type called f3 which is simply an array of three floats (a not an all too uncommon type when dealing with three dimensional space), and I use fixed time steps interpolating between the previous and the current step of the simulation, thus the most common type in my engine is f3[2]. I also place the ‘current’ value first so I can use the same reference to read both f3 and f3[2], where I need it. I guess this could technically be considered a very naive implementation of (multiple) inheritance, but let’s not go there. It does allow us to interact with objects we know very little about though, so I guess you could call it something similar to polymorphism if you wanted to, and you’re an ad-man with affinity for buzz-words.

We still need to know the ‘interface’ or data layout of our components. Assuming we’re using standardized data-blocks, this can be extracted out of the manager logic, and into a wiring phase which is done by a higher level game object. The game object code creates the properties, passing references to the appropriate data blocks as input, and all managers can remain completely oblivious to how they’re connected.

Wiring it up

It was important to me that each manager would be free to reorganize or sort its data arrays as it saw fit, so I couldn’t use raw pointers without forcing every manager to keep track of who’s referencing which of the properties it’s managing (in order to keep them up to date on the new address). As the number of references can be pretty arbitrary depending on where a specific property is used, I chose to insert an indirection instead, i.e. a lookup table.

Furthermore, I elected to go with a handle scheme instead of straight up pointers into the lookup table. The lookup table still stores pointers into the property data though. Using handles for the lookup has a couple of advantages, the first thing that comes to mind is that we can eliminates the problem of dangling pointers by keeping a version counter in the handle, which is nice. Second, I cut my handles to 32 bits, which is half the size of a pointer on a 64 bit system. And third, I reserve 8 bits of the handle for offsets into the data being pointed to, which lets me store one pointer per property structure, while still allowing a handle to ‘point’ somewhere within that structure. This is useful when I’m storing, for example, both origin and orientation together, and for a particular case I’m only interested in orientation. The offset handling is hidden in the lookup table functions, so as long as we set it correctly during wiring, the user of the handle doesn’t need to worry about it, giving us a bit of flexibility and reducing the sheer number of properties that otherwise would’ve needed to be registered and kept in sync. The observant reader might notice that this limits the maximum size of the data structure to 256 bytes, but as mentioned earlier, I want these to be as small as possible and only contain the data which is generally accessed together. So really, 256 bytes ought to be enough for everybody…

I don’t have graphical UI with little squiggly lines representing wires connecting an input of some property to the output of some other; but in my mind that’s what’s going on, I arbitrarily connect data ‘slots’ to one another and the property managers are none the wiser. As an example, this is how I picture what the wiring looks like when setting up the player camera.

Player camera wiring

The ID of the network entity to track is provided by the server, the camera logic doesn’t know what kind of object we’re tracking, is only given the origin property. During gameplay, it’s not even a server object directly, but a client side prediction property. The rest of the wiring applies an offset (the transformation) to the entity origin before feeding it into a PID controller, controlling a linear momentum property. The output is fed to rendering views as well as ground synthesis (only generate ground mesh where we can actually see it) and directional lighting (the shadow map rendering needs to follow the camera around). Each of these boxes represent separate property managers which, when called, update all the instances of that property, e.g. the PID manager updates all PID controller instances, it doesn’t matter if they’re being used to control the player camera or moving UI elements around.

Where’d the game logic go?

You’ll notice I haven’t really talked about game logic. It hasn’t magically disappeared just because the game engine has a particular architecture, it’s still there. The fact is still that the player will see compound game objects on screen, such as a soldier, and you will need something to keep track of the relevant properties. I still have a soldier game object. The difference is, there’s no soldier-update (or -tick, or -think, whatever you want to call it), there’s pretty much only a create and destroy for client and server side respectively. The create function initializes the appropriate properties, after that the property managers take over and deal with the frame-to-frame work. I’m sure you can think of other functions you’d want for special game logic stuff, but the important notion is that there’s no frame-by-frame update function.

Actually, I lied. I have a soldier-update function. But it is a specialized soldier property which handles animations on the client side, with dependencies on the server object property, if the object starts moving it’ll trigger walk cycle animations, do some simple forward kinematics to aim the gun in the right direction, and so on. It does not move the soldier around on screen, that’s a redraw property wired to a server object property via a client-side prediction property.

Wrap up

I find this design has a certain charm, it keeps the implementation of each property manager focused on doing a single thing, and doing it efficiently.

Additionally, if you focus on keeping your data in a raw format like this, you’ll end up with very lean data. It’ll make you think about that and how to organize it. You won’t end up with objects where, alongside your couple of vectors worth of data, you have a virtual table pointer, references to a couple of engine sub systems, and so on and so forth. Don’t underestimate how objects may balloon thanks to a couple of references, especially if you’re on a 64 bit architecture, and you’re creating maybe a million instances.

Two problems that stand out are particularly affected by the design choice are concurrent access to lookup tables and shared data, if we run updates of separate property managers simultaneously. Note that this doesn’t stop us from dividing the list of properties to update over several threads. Related to this is ordering, if we run property manager updates sequentially, and cannot wait for the next frame to let the value propagate, we’ll need to be clever about in what order we run our updates.

All in all, it’s a neat set up, and it really appeals to how my brain works. So should I have built my own engine? Probably not. It’s been a cool ride though, and I’ve learned a tremendous amount. It hasn’t been without its share of dark moments, but perhaps that’s a topic for a different post.

Feel free to let me know what you think, either in the comments below or poke me on Twitter, I’d love to hear it.

Post scriptum – In the works

Concurrency and multi-threading is something close to heart for me, and having a set up that works reliably in parallel without slapping a lock on everything (mind you, that approach to concurrency will bite you in the behind soon enough). I have not yet come around to implementing this part of the system, but this is what I have planned.

I’ve elected to go for a semi-static directed acyclic graph (DAG) model, where property updates are carried out in a breadth-first manner. Each property can only reference the layers before it, thus all properties in a layer can be updated simultaneously without risking interfering with other properties. I don’t want to have a fixed, compile-time, but rather I want it to sort itself appropriately during wiring. This solves both ordering (properties depending on other properties) and concurrent access.

To achieve this, I’ll reserve a few more bits in the handle to denote the ‘graph depth’ of the referenced property. Thus when I create a property, passing the appropriate dependencies to it, it’ll examine all handles and set its own depth to maximum plus one. I’ll keep all instances of the property sorted by graph depth, and during update, process single depth at a time. During each frame, I’ll step through each populated layer of the graph and fire off multithreaded jobs for each property type, synchronizing after each layer. As each layer only depends on the layers before it there will only be concurrent reads which is fine. In the PID-controlled camera example above, the feed back to the momentum property would have to be queued and applied at the end of the frame (thus explicitly delaying the input by one frame), this doesn’t change the current behavior though as, depending on how the updates are ordered, one of the properties are already reading one frame old data.

This implies I cannot let the property change depth without rebuilding the graph, which is non-trivial as we do not keep track of who depends on us, only who we depend on. I doesn’t stop me from rewiring the dependencies of a property, but it does stop me having it depend on something in its own layer or something further down the line.