Luke Jones

00101010

Entity Component Systems in Rust

2019-03-26 - Reading time: 11 min

Adventures in Entity Component Systems (in rustlang)

On and off for the last year and a bit I've been playing with game engine architecture as a way of sharpening my programming skills and in particular my Rust skills. Game engines are the ultimate interactive program, they have:

  • event loops
  • user I/O
  • graphical displays,
    • including for I/O (menus, HUD, in-game actions etc)
  • sound
  • physics (from basic to full newton)
  • memory management (for more complex game engines at least)

And these systems all need to interact with each other. Numerous volumes have now been written on the subject of game engine architecture now compared to 20 years ago when I first wondered about game programming. One of the systems that has emerged over time is the Entity Component System.

The majority of games and game engines have been written in C or C++. Some in other languages like Javascript, or even Pascal. Rust is a fairly new entry to the arena and one I hope picks up more steam for game programming as the years go on. It offers many benefits for engines, such as easy threading and concurrency, clear data ownership rules and data lifetimes, and the ability to jump to here_be_dragons mode with unsafe code. Data ownership and lifetime enforcement can pose some hurdles though, particularly if you are not used to thinking with that concept in mind.

I suppose the ownership and lifetimes is why an Entity Component System is a popular type of data/object management system with Rust folk. I realised early on that the heart of the game (engine) was going to be the ECS, and while there are many good Rust written crates for an ECS implementation available, I wanted to write my own as an exercise. And so getting it right (for some definition of right) early on would save me a lot of headaches later on down the track. In this post I'll explain the what/where/how/why and some of the intricacies of using Rust for it.

What is an ECS?

Let's start with some terminology definitions;

  • Entity - This is conceptually the container for components. In reality/code it is nothing more than an ID of some type, be it an integer or string or hash.
  • Component - A component is of the type "has a..". A player has a bounding box, has a position, has a velocity, has a direction etc - each of these is an individual component.
  • System - Like components, there will be many Systems. A system in this sense is a "machine" that takes the components it is interested in and does work with them. For example collisions will take all positions, physics objects, and AABB (Axis Aligned Bounding Box) and check for collisions.

Why use an ECS?

There are many reasons; the classic example involves the "diamond of death" when using a class-based inheritance scheme for game Entities. This topic is covered in numerous places already, and in much better detail than I'll manage here - because this is really an OOP language problem, and Rust isn't OOP as such.

In Rust particularly though, the reasons to use an ECS derive from those data ownership and lifetime rules, along with strict typing (amongst other things). Note: as of Rust 2018 edition, the ability to use trait objects has been expanded, such that you can store a trait object, pass them as an arg, or return, all without complexity and overhead of boxing them - this might change things up a little in respect to how game objects can be managed and handled.

But the number one reason should be this: it's easy to expand, easy to trim/chop/change, easy to use. Let's say you wanted a new type of TODO !

The parts in depth

Entities and Components

Let's expand the idea of an Entity a little more. It is only an ID, this means that when creating your Entities, you can just use an increasing integer counter.

But how do you use that ID and what is its relationship to a component?

Okay, now let's pretend we have two components defined; Position and Velocity, the key parts of movement in XYZ game. You will have multiple Entities using these two components, so some form of storage is needed, such as an array per component.

Now we need a way to get the correct component for an entity; what's good for that? The Entity ID of course, it starts from 0 and increments as entities are added. Let's use the Entity ID to access components via the array index. This means that when creating an entity, we need to insert the component in to the relevant array at the correct index location.

What you should end up with is something like this (but starting at 0 usually);

Component 0 1 2 3
Position x x
Velocity x

The Entity ID is being used as an index in to the arrays - position, velocity, something - so if we want the components of entity 2, just grab them from the arrays at that index number; entity 2 has a position and a velocity component.

Keeping track

How do we know which Entity ID has which component? We could use a for loop to iterate through each of the component arrays to find and track components and their position in the array (which is the ID) but this would be super highly inefficient. A faster way is to maintain another array for entity ID's - this array would operate similar to how we described the component arrays with the index position being the ID, but here instead of storing a component we store only an integer, and this integer is used as a bitmask.

A bitmask works by using a single bit in an integer of n size to signify one thing. For an ECS we can use a single bit in an u32 integer to relate to each component type available such as in the following rust snippet:

// Bits: 0000 0000 0000 0000 0000 0000 0000 0000
pub const EMPTY     :u32 = 0;
// Bits: 0000 0000 0000 0000 0000 0000 0000 0001
pub const POSITION  :u32 = 1;
// Bits: 0000 0000 0000 0000 0000 0000 0000 0010, integer 1 shifted left 1
pub const VELOCITY  :u32 = 1<<1;
// Bits: 0000 0000 0000 0000 0000 0000 0000 0100, integer 1 shifted left twice
pub const SOMETHING :u32 = 1<<2;

What this is doing is using the bitshift operator << to shift the bits of 1 over the requested amount as seen in the comments above each line. Since the number 1 is represented in binary as:

0000 0000 0000 0000 0000 0000 0000 0001

we use this as the base integer to shift.

Using this we can now mask together some components in to an unsigned integer, let entity_mask = POSITION|VELOCITY , this integer has its rightmost bits set to 0011 which is the two components 'or'ed together, the or function of boolean logic takes the 'on' bit of either part and adds it to the new binary.

0000 0000 0000 0000 0000 0000 0000 0001 or
0000 0000 0000 0000 0000 0000 0000 0010 =
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0011

Now store this masked integer in one more array - we'll call it entity_masks - in the index position corresponding to the Entity ID - this is the array I described at the start of this section.

The World data struct and Entity/Component store is probably looking like this now;

const MAX_ENTS :u32 = 200;

struct World<'a> {
    entity_masks: [u32; MAX_ENTS],
    parts: Parts,
}

struct Parts {
    /// Used to keep track of which index number has which components
    position  : HashMap<u32, Position>,
    velocity  : HashMap<u32, Velocity>,
    something : HashMap<u32, Something>,
}

A small note about the code above: due to how rust works, it was easier to use a HashMap at the time for parts. However the principles are the same, where you access a standard array using the Entity ID (index number), you also use that number to fetch the required component from the HashMap.

Creating a new entity

Adding a new entity is straightforward now - here we'll go over just the basics, then later talk about some of the issues that will be raised such as tracking free entity ID.

To add a new entity with position & velocity components we'll write something like this:

world.entity_masks[free_slot] = POSITION|VELOCITY;

world.entities.parts.position.insert(
    free_slot,
    Position::new(x, y),
);

world.entities.parts.velocity.insert(
    free_slot,
    Velocity::default(),
);

Do keep in mind that everything throughout this article is intended to be as verbose as possible without being overly cumbersome in order to try and illustrate the concepts thoroughly.

With the code above, we would first find a free slot, that is, a slot containing a 0 (EMPTY), then create the bitmask required, and insert that in to world.entity_masks, we will then use that slot identifier as the key to insert the components in to the hashmap per component.

Working with an Entity

The last part of the puzzle is working with each entity. Typically you'll want to run a 'system' on each component of set of components, and there are numerous ways to do this so I'll try and stick to simplicity here. As an example lets say the player pressed a button and now we need to update the velocity and position of the players components.

A very basic way to do this would be to have a function with a list of systems to call on each game-loop. A better way would be utilizing traits and trait objects, but that can also lead to complexity - however you manage it there will be trade-offs to make. This short example of updating the player movement uses two systems called in sequence:

// Don't do it like this. This is only to illustrate use
impl World {
    fn update_velocity(&mut self, entity: u32) {
        if (self.entity_masks[entity] & VELOCITY == VELOCITY) {
            self.parts.velocity[&entity].v += added_vel; // vector struct
        }
    }
    fn update_position(&mut self, entity: u32) {
        if (self.entity_masks[entity] & VELOCITY | POSITION == VELOCITY | POSITION) {
            let velocity = self.parts.velocity[&entity].v;
            self.parts.position[&entity].p += fancy_calculation(velocity);
        }
    }
}
// game loop calls world.update_velocity(player_id);

Note the self.entity_masks[entity] & VELOCITY | POSITION expression. the & binary operator evaluates each bit in the comparison to on only if 'all' bits compared are on. So a 0001 & 0010 will evaluate to 0000 and 0011 & 0010 will evaluate to 0010. Using this combined with the index/ID you can check which components an entity owns.

End

And that's about it really. You use the index number of a main entity tracking array as the ID of an entity, and the integer contained in that index location is the bitmask which states which components the entity has. The index number being the ID also means it is used to reference the actual component it has in each array/hashmap of components. It's nice concept, and eliminates some issues you get with class inheritance plus works around Rust's lack of inheritance.

In my own code I had originally done the above using a macro to avoid the repetition it involves, but for the purposes of this article I expanded it so as to provide a solid example.


use std::collections::HashMap;

const MAX_ENTS: usize = 10_000;
pub const EMPTY     : u32 = 0;
pub const POSITION  : u32 = 1<<0;
pub const VELOCITY  : u32 = 1<<1;
pub const AABB      : u32 = 1<<2;
pub const PHYSICS   : u32 = 1<<3;
pub const INPUT     : u32 = 1<<4;
pub const SPRITE    : u32 = 1<<5;
pub const ANIMATION : u32 = 1<<6;
pub const PLAYER    : u32 = 1<<7;
pub const AI        : u32 = 1<<8;
pub const ITEM      : u32 = 1<<11;
pub const CIRCLE    : u32 = 1<<12;

/// A struct of `HashMap` for each entity part type
///
/// The objects stored in each `HashMap` are keyed to the
/// entity ID number for quick loop up
#[derive(Default)]
pub struct Parts {
    pub position : HashMap<u32, parts::Position>,
    pub velocity : HashMap<u32, parts::Velocity>,
    pub aabb     : HashMap<u32, parts::AABB>,
    pub physics  : HashMap<u32, parts::Physics>,
    pub input    : HashMap<u32, parts::InputTypes>,
    pub sprite   : HashMap<u32, parts::Sprite>,
    pub animation: HashMap<u32, parts::Animation>,
    pub player   : HashMap<u32, parts::Player>,
    pub ai       : HashMap<u32, parts::Ai>,
    pub item     : HashMap<u32, parts::Inventory>,
    pub circle   : HashMap<u32, parts::Circle>,
}
impl Parts {
    pub fn remove_ent_parts(&mut self, ent: u32) {
        self.position.remove(&ent);
        self.velocity.remove(&ent);
        self.aabb.remove(&ent);
        self.physics.remove(&ent);
        self.input.remove(&ent);
        self.sprite.remove(&ent);
        self.animation.remove(&ent);
        self.player.remove(&ent);
        self.ai.remove(&ent);
        self.item.remove(&ent);
        self.circle.remove(&ent);
    }
}

/// Stores all entities
///
/// Enables ability to pass the required arrays to Systems. We can't do this if the
/// World struct contains them because of ownership conflicts in Rust.
pub struct Entities {
    /// Used to keep track of which index number has which components. The
    /// index number that the entity is created at is then used as the key
    /// for the object hashmaps in `_entities`
    ///
    /// Eg: POSITION + AABB (= 5, can be used for collidable object positions)
    pub mask: [u32; MAX_ENTS],
    /// The struct of HashMaps for each entity part type
    pub parts: Parts,
    /// `next_free` is used to keep track of how far the array has been used.
    /// For example if only 42 entities have been created then when inserting a new entity
    /// `create` will iterate through to find either first `EMPTY` or insert at `next_free`
    /// and increment
    pub next_free: u32
}

impl Entities {
    pub fn new() -> Entities {
        Entities {
            mask: [EMPTY; MAX_ENTS],
            parts: Parts::default(),
            next_free: 1
        }
    }
    /// Remove the specified entity index and set as `EMPTY`
    pub fn remove(&mut self, ent: u32) {
        if self.mask[ent as usize] != EMPTY as u32 {
            self.parts.remove_ent_parts(ent);
        }
    }
    /// Find the first `EMPTY` ID number to use
    pub fn get_free_slot(&mut self) -> Option<u32> {
        for index in 0..self.next_free {
            if self.mask[index as usize] == EMPTY as u32 {
                self.next_free += 1;
                return Some(index);
            }
        }
        None
    }
}

Full code available here. It's been a wee while since I've had time to work on this so beware code-smells!

There's all-sorts of nice ECS out there now, and one of the smaller ones I've seen which remains nicely generic is rustic-ecs. This is just an entity tracking and creation really, anything like systems to work on the components of an entity still require work such as in examples above. If I rewrite my own ECS I'll probably use this one as a model.