Friday, October 10, 2014

Building a Data-Oriented Entity System (Part 4: Entity Resources)

In the last post, I talked about the design of the TransformComponent. Today we will look at how we can store entities as resources.

Dynamic and Static Data

I’m a huge fan of compiling resources into big blobs of binary data that can be read directly into memory and used as-is without any need for “deserialization” or “reference patching”.

This requires two things:

  • First, the data must be swapped to the right endianness when the data is generated.

  • Second, internal references in the resource must use offsets instead of pointers, since we don’t know where the loaded resource will end up in memory and we want to avoid pointer patching.

Initially, this approach can seem a bit complicated. But it is actually a lot simpler than messing around with deserialization and reference patching.

Note though, that this approach only works for static (read-only) data, such as meshes, textures, etc. If data needs to change for each instance of a resource, we must store it somewhere else. If an instance needs to change color, we can’t store that color value in a memory area that is shared with other instances.

So what typically happens is that we split out the dynamic data as “instance data” and let that data refer to the static resource data. Many instances can make use of the same resource data, thus saving memory:

---------------                -----------------
|Instance of A| --------+----> |A resource data|
---------------         |      -----------------
                        |
---------------         |
|Instance of A| --------+
---------------

---------------                -----------------
|Instance of B| --------+----> |B resource data|
---------------         |      -----------------
                        |
---------------         |
|Instance of B|---------+
---------------

We typically hard-code what goes into the instance. For example, we know that the color is something that we want to modify so we add it to the instance data. The vertex and index buffers cannot be changed and thus go into the static data. When we create the instance we initialize the instance data with “default” values from an instance template in the resource data.

You could imagine doing this another way. Instead of hard-coding the data that can be modified per instance, you could say that everything can be modified per instance. In the instance data you would then use a flexible key-value store to store the delta between the instance and the resource data.

This is more flexible than hard-coding, because it allows you to override everything per instance, even texture or vertex data if you want that. It can also save memory, because the instance data will only contain the things you actually override, not everything that potentially could be overridden. So if you have many instances that use the default values, you don’t have to store any data for them.

On the other hand, there are drawbacks to this approach. Accessing value becomes a lot more complicated and expensive, because we always need to perform an extra query to find out if the instance has overridden the default value or not.

We currently don’t use this approach anywhere in the engine. But I think there are circumstances where it would make sense.

Anyway, I’m getting sidetracked. Back to the entity system.

The thing is, the way I envision the entity system, it is very dynamic. Components can be added and removed at runtime, child entities linked in and properties changed. Components that handle static data, such as the MeshComponent do it by referencing a separate MeshResource that contains the mesh data. There is no mesh data stored in the component itself.

Since everything in the entity system is dynamic, there is only instance data. The only thing we have in the resource is the template for the instance data. Essentially, just a set of “instructions” for setting up an instance. There is no need for the instance to refer back to the resource after those instructions have been followed.

Defining the Resource Format

So an entity resource should contain “instructions” for setting up an entity. What should it look like? Let’s start by just writing up what needs to go in there:

struct EntityResource
{
    unsigned num_components;
    ComponentData components[num_components];
    unsigned num_children;
    EntityResource children[num_children];
};

Note: Of course the above is not legal C++ code. I’m using some kind of C-like pseudo-code that allows things like dynamically sized structs in order to describe the data layout. I’ve written about the need for a language to describe data layouts before.

The exact binary layout of the ComponentData is defined by each component type, but let’s use a common wrapper format:

struct ComponentData
{
    unsigned component_identifier;
    unsigned size;
    char data[size];
};

Now we have a common way of identifying the component type, so we know if we should create a MeshComponent, a TransformComponent or something else. We also know the size of the component data, so if we should encounter a component type that we don’t understand, we can ignore it and skip over its data to get to the next component. (Another option would be to treat unknown component types as a fatal error.)

A quick fix to make this layout slightly better is to move all the fixed size fields to the start of the struct:

struct EntityResource
{
    unsigned num_components;
    unsigned num_children;
    ComponentData components[num_components];
    EntityResource children[num_children];
};

Now we can access the num_children parameter without having to look at all the components and their sizes to know how far we need to skip forward in the resource to get to the num_children field.

This may or may not matter in practice. Perhaps, we only need the value of num_children after we have processed all the component data, and at that point we already have a pointer into the resource that points to the right place. But I always put the fixed size data first as a force of habit, in case we might need it.

Sometimes, it makes sense to add offset tables to these kinds of resources, so that we can quickly lookup the offset of a particular component or child, without having to walk all of the memory and count up the sizes:

struct EntityResource
{
    unsigned num_components;
    unsigned num_children;
    unsigned offset_to_component_data[num_components];
    unsigned offset_to_child_data[num_children];
    ComponentData components[num_components];
    EntityResource children[num_children];
};

With this layout, we can get to the data for the i’th component and the j’th child as:

struct EntityResourceHeader
{
    unsigned num_components;
    unsigned num_children;
};

const EntityResourceHeader *resource;
const unsigned *offset_to_component_data = (const unsigned *)(resource + 1);
ComponentData *data_i = (const ComponentData *)
    ((const char *)resource + offset_to_component_data[i]);

const unsigned *offset_to_child_data = (const unsigned *)
    (offset_to_component_data + num_components);
EntityResourceHeader *child_j = (const EntityResourceHeader *)
    ((const char *)resource + offset_to_child_data[j]);

The first time you encounter code like this it can seriously spin your head around with all the casting and pointer arithmetic. However, if you think about what happens and how the data is laid out in memory it is really pretty straight forward. Any mistakes you do will most likely cause huge crashes that are easy to find, not sneaky subtle bugs. And after a while you get used to these kinds of manipulations.

But, anyway, I’m drifting off on a tangent again, because actually for our purposes we don’t need these lookup tables. We will just walk the memory from beginning to end, creating one component at a time. Since we don’t need to jump around between different components, we don’t need the lookup tables.

What we do need though is some way of storing more than one resource. Storing one entity is fine if we are dealing with a “prefab” type of resource, that contains a definition of a single entity. However, what about a level? It will probably contain a bunch of entities. So it would be nice to have a resource type that could store all those entities.

Ok, no biggie, we know how to do that:

struct EntitiesResource
{
    unsigned num_entities;
    EntityResource entities[num_entities];
};

Done, yesno?

Pivot!

Working for a while in this business you get an intuitive feel for when performance matters and when it doesn’t. Of course, intuitions can be wrong, so don’t forget to measure, measure, measure. But level spawning tends to be one of these areas where performance does matter.

A level can easily have 10 000 objects or more and sometimes you want to spawn them really fast, such as when the player restarts the level. So it seems worth it to spend a little bit of time to think about how we can spawn levels fast.

Looking at the resource layout, our spawn algorithm seems pretty straight forward:

  • Create the first entity
    • Add its first component
    • Add its second component
    • Create its child entities
  • Create the second entity
    • Create its first component
    • Create its second component

This is so simple and straight forward that it might seem impossible to improve on. We are walking the resource memory linearly as we step through components, so we are being cache friendly, aren’t we?

Well, not really. We are violating one of the fundamental principles of data-oriented design: Do similar things together.

If we write out the operations we actually perform linearly instead of in an hierarchy and make things a bit more concrete, it’s easier to see:

  • Create entity A
  • Create a TransformComponent for A
  • Create a MeshComponent for A
  • Create an ActorComponent for A
  • Create entity B
  • Create a TransformComponent for B
  • Create a MeshComponent for B

Note how we are alternating between creating different kinds of components and entities. This not only messes with our instruction cache (because each component has its own code path), but with our data cache as well (because each component has its own data structures where the instances get inserted).

So let’s rewrite this so that we keep common operations together:

  • Create entity A
  • Create entity B
  • Create a TransformComponent for A
  • Create a TransformComponent for B
  • Create a MeshComponent for A
  • Create a MeshComponent for B
  • Create an ActorComponent for A

Much better. And we can go even further.

Instead of telling the EntityManager to “create an entity” one hundred times, let’s just tell it to “create 100 entities”. That way, if there is any economy of scale to creating more than one entity, the EntityManager can take advantage of that. And let’s do the same thing for the components:

  • Create entities (A, B)
  • Create TransformComponents for (A,B)
  • Create MeshComponents for (A,B)
  • Create an ActorComponent for A

Notice how we are encountering and making use of a whole bunch of data-oriented principles and guidelines here:

  • Access memory linearly.
  • Where there is one, there are many.
  • Group similar objects and operations together.
  • Perform operations on multiple objects at once, rather than one at a time.

Let’s rewrite the data format to reflect all our newly won insight:

struct EntityResource
{
    unsigned num_entities;
    unsigned num_component_types;
    ComponentTypeData component_types[num_component_types];
};

struct ComponentTypeData
{
    unsigned component_identifier;
    unsigned num_instances;
    unsigned size;
    unsigned entity_index[num_instances];
    char instance_data[size];
};

For each component, we store an identifier so we know if it’s a MeshComponent, TransformComponent, etc. Then we store the number of instances of that component we are going to create and the size of the data for all those instances.

Note that now when we are walking the format, we can skip all instances of an unknown component type with a single jump, instead of having to ignore them one by one. This doesn’t matter that much, but it is interesting to note that data-oriented reorganizations often make a lot of different kinds of operations more efficient, not just the one you initially targeted.

The entity_index is used to associate components with entities. Suppose we create five entities: A, B, C, D and E and two ActorComponents. We need to know which entity each ActorComponent should belong to. We do that by simply storing the index of the entity in the entity_index. So if the entity index contained {2,3} the components would belong to C and D.

There is one thing we haven’t handled in the new layout: child entities.

But child entities are not conceptually different from any other entities. We can just add them to num_entities and add their component instances to the ComponentTypeData just as we would do for any other entity.

The only additional thing we need is some way of storing the parent-child relationship. We could store that as part of the data for the TransformComponent, or we could just store an array that specified the index of each parent’s entity (or UINT_MAX for root entities):

struct EntityResource
{
    unsigned num_entities;
    unsigned num_component_types;
    unsigned parent_index[num_entities];
    ComponentTypeData component_types[num_component_types];
};

If parent_index was {UINT_MAX, 0, 1, 1, 2} in our A, B, C, D, E example, the hierarchy would be:

A --- B --- C --- E
      |
      + --- D

Implementation Details

This post is too long already, so I’ll just say something quickly about how the implementation of this is organized.

In the engine we have a class EntityCompiler for compiling entities and a similar class EntitySpawner for spawning entities.

A component that can compile data needs to register itself with the entity compiler, so that it can be called when component data of that kind is encountered by the compiler.

Ignoring some of the nitty-gritty details, like error handling, endian swapping and dependency tracking, this looks something like this:

typedef Buffer (*CompileFunction)(const JsonData &config, NittyGritty &ng);

void register_component_compiler(const char *name, CompileFunction f,
    int spawn_order);

The compile function takes some JSON configuration data that describes the component and returns a binary BLOB of resource data for insertion into the entity resource. Note that the compile function operates on a single component at a time, because we are not that concerned with compile time performance.

When registering the compiler we specify a name, such as "mesh_component". If that name is found in the JSON data, the entity compiler will redirect the compile of the component data to this function. The name is also hashed into the component_identifier for the component.

The spawn_order is used to specify the compile order of the different component, and by extension, their spawn order as well. Some components make use of other components. For example, the MeshComponent wants to know where the enitty is, so it looks for a TransformComponent in the entity. Thus, the TransformComponent must be created before the MeshComponent.

A similar approach is used to register a component spawner:

typedef void (*SpawnFunction)(const Entity *entity_lookup,
    unsigned num_instances, const unsigned *entity_index, const char *data);

void register_component_spawner(const char *name, SpawnFunction f);

Here the entity_lookup allows us to look up an entity index in the resource data to a an actual Entity that is created in the first step of spawning the resource. num_instances is the number of component instances that should be created and entity_index is the entity index from the ComponentTypeData that lets us lookup which entity should own the component.

So entity_lookup[entity_index[i]] gives the Entity that should own the ith component instance.

The data finally is a pointer to the instance_data from the ComponentTypeData.

That’s certainly enough for today. Next time, we’ll look at a concrete example of this.

21 comments:

  1. Another great post and an awesome series. I understand the chances of this are slim but what are the odds of releasing something similar to the bitsquid foundation library which shows off a bare-bones example of this system? I totally understand that it isn't a quick thing to do but it was so awesome getting to poke around the foundation lib to see how it all fit together. Something like that for this would be the bomb! :) Thanks again for sharing!

    ReplyDelete
    Replies
    1. Thanks. Most likely this will not make it into the foundation library.

      Delete
    2. No worries, just thought I'd check :) Thanks again!

      Delete
  2. When you destroy an entity with multiple "components" , how do you find each component to destroy?

    ReplyDelete
  3. Great article! Reading these raised few questions to my mind:

    1.) How do you handle ComponentSystem creation & update order? There must be some component systems that needs to be update before others, for example if you create some behavioural components to handle actual game logic. There must be some way to register systems?

    2.) How do you expose components properties from code to editors? Is it some serialization based system, or do you have separated JSON scheme in file? I think JSON scheme solution is quite nice since editors doesn't need to know anything about actual code, just editing what ever values they want and at the it can be compiled in to a nice data blob. In engine run-time side you just need to ask values with keys and you can easily load objects from data blob. Loading can be of course automated if you define key for each component value in code. There's benefit that designers can add new values when ever they want and once gameplay programmers have time they can start to create now functionality that uses these values. Downside of course is that you need to keep code and JSON scheme in sync.

    2.) You mentioned MeshComponent as one example and it has reference to MeshResource. What attributes/properties you actually expose from MeshComponent to users and what kind of functionality MeshComponentSystem API provides (e.g. material resource vs. individual material properties)? I'm asking this since you most obviously have some sort of RenderWorld/RenderWorldManager (scenegraph) that keeps all render actors (mesh, skeletal mesh, lights, terrain...) and it has already well defined API. So if component systems represents runtime interface for game logic to access all the needed functionality MeshComponentSystem most likely just passes all calls to actual render world making it just a extra layer of indirection. Another solution what I can think of is that RenderWorld/RenderWorldManager itself is actually MeshComponentSystem. What I mean that it will handle all component types related to rendering e.g MeshComponent, SkeletalMeshComponent, LightComponent. Is this something that you are doing, or am I missing something from big picture?

    Keep up the good work you are doing!

    ReplyDelete
    Replies
    1. Thanks!

      1) Currently, each component registers with a floating point number and the creation order is sorted with respect to this number. But I'm thinking about switching this and instead let each component explicitly declare which components it "depends on" and must be constructed before it. I think that is cleaner.

      2) Components have separate JSON UI-descriptors that describe how the editor should present the data.

      3) Currently, since the component system is a later add-on, it acts as a thin wrapper around the RenderWorld. If we had built the system component based from scratch, perhaps we would have let the RenderWorld and the MeshComponentSystem be the same thing.

      Delete
  4. Just curious here about a few thing regarding the bitsquid engine on the art and level design side of things.

    Will there be a visual shader editor similar to Unreal Engines material editor?

    Have you guys written any thing on the level editor yet? I am asking Because currently with Unity3D and Cryengine you are quite constrained to the level editor. This is bad if you are doing large scale procedural levels, large scale worlds that are made at runtime, etc.

    It would be awesome to see Bitsquid/Autodesk embrace procedural content and large game worlds as well with this engine.

    I love the what you see is what you play functionality with Cryengine but I hate the workflow and the many plugins you have to install for Photoshop, 3DS Max, etc.

    Back on to the programming side of things - I noticed that you guys are using JSON. Does this mean that we can have our users customize the application for their own wants and needs if they want to?

    Just curious here

    Keep up the awesome work!

    ReplyDelete
  5. Yes, there is a visual shader editor and a level editor.

    It is really tricky to make a level editor that is simple to use and understand for beginning users and yet so flexible that it can be used for all kinds of "unusual" scenarios (such as procedural levels or whatever else ideas people might have). At some point you have to decide what your editor is, or it will just become an empty framework. So our editor in the default configuration won't be good for procedural levels, but we are looking into how we can add flexibility to it so that it can be reconfigured.

    Yes, we use JSON for all our data formats, so you can write your own editors if you want to (as long as they output the right JSON data for the engine). That might be the way to go if you want something really special.

    ReplyDelete
  6. Hey, Thank you for the reply Niklas.

    Just got a few more questions -

    I am used to the Physically Based Shading model by now as are most people. Will that be in BitSquid?

    What platforms will be supported?

    When can I start using Bitsquid?

    ReplyDelete
    Replies
    1. Sorry, I can't say much about the release plans until it is official.

      Delete
  7. Hi Niklas, I know that you promised a concrete example on next article but I would like to ask you how do you handle interactions between components (if there's one), for example: How a MeshComponent get rendered in the right position? Does the MeshComponentSystem lookup for TransformComponents to get the right position every time a mesh needs to be rendered?

    ReplyDelete
    Replies
    1. No, the renderer keeps its own copy of the mesh's position. The TransformComponent will reflect the position to the renderer only when it changes.

      The TransformComponent knows (because other components have told it) which positions need to be reflected to the renderer.

      Delete
    2. Let me see if I understood. Generically speaking if component A needs to keep in sync with component B, the component A "register" itself on component B, so whenever component B update its state the component A will be "notified".

      Looking forward to read next article.

      Delete
    3. Yes, that's one way of doing it... but there is not really a general system. Each system decides what makes most since for it, given its particular constraints.

      Delete
  8. Great article series and really interesting!

    thanks to these articles I have a clear idea on all these little "pieces", but what I really don't grasp is the global structure/functionality, and so, I would like to ask some questions:

    1. the components are owned by the (specific) systems or are stored elsewhere? There is, for example a component manager and all systems refer to him to collect the desired components or all data are inside each system and so a system asks to another for its "product" ?

    2. how two system interact with each other? for example If there is a system that updates all TransformComponents and now is the turn of the RenderingSystem that needs those transformations, how the product of the first is pass to the second? copying the entire TransformComponent's array each frame? And what if the rendering needs a 4x4 Matrix version of the TransformComponent, who owns this temporary version? who produces it?

    3. What about if a system needs to match two components and not only one e.g. MeshCmp and TransformCmp? who is in charge to match the correct transform for a specific mesh (based on the entity) and pass all the things to the rendersystem?

    thanks for sharing!

    -DC

    ReplyDelete
    Replies
    1. 1. Each system owns its own component, there is no centralized manager. To talk about a component you have to talk to the specific system managing it.

      2. Each system is responsible for how it wants to expose the data to other systems. In addition to get_transform_of_entity() the TransformComponent could also expose bulk operations to get all the transforms. It could also decide that transforms will never be moved in memory and thus use shared memory to communicate with other systems. It could also expose functions for getting a list of just the transforms that have changed, so that the renderer only needs to update what has changed. It is just a matter of finding the best approach to make all systems performant.

      3. Generally speaking, only one system should be authoritative on a particular piece of data (such as an object's position). Otherwise you are creating lots of trouble for yourself. So decide who owns the data, and if necessary factor it out in a separate component.

      Delete
  9. A few questions regarding the compile function.

    1. How is the json config being created? Is made by hand? Is it created via the editor? What is stored in the json? Is it data layout or something else? Could you show a small example of what might be in the json?

    2. The blob that is returned, is that then stuffed into the instance_data of the ComponentTypeData?

    3. Finally, are you still planning on presenting a more concrete example of this system?

    ReplyDelete
  10. 1. Editor.
    2. Yes.
    3. Hmm maybe mabye not... I lost steam a bit... will see if I get it back.

    ReplyDelete
  11. Your selection of topic is very good and also well written. Thanks for sharing. I feel like all your ideas are incredible! Great job!!!

    office.com/setup

    ReplyDelete