Hi, I’m Domagoj Cerjan. I’m a frontend engineer with more than 10 years of experience in game development, GIS, fin-tech and general web and web frontend. Since October 2020 I’ve been working for t-matix engineering, where I dabble in all things React and TypeScript, and evangelize functional programming. As a hobby, I develop 3d rendering engines for fun, and, since this is an area I am well familiar with, I often use it to try out different languages and approaches.
Since I love powerful type systems and use TypeScript a lot, both for work and hobby projects, I decided to explore the possibility of building a TypeScript version of one of the most powerful tools available to a game developer – an ECS library.
In order to see what an ECS is and how it helps us, we first have to understand what problems it solves and how objects in games were/are usually represented. When we think about objects in games (take Pong for simplicity’s sake), we usually give these objects some traits which define what they are and how they should behave (a Paddle belongs to a player, and has its position and size defined in the game world; a Ball has a position, size and velocity defined in the same world, etc.). These traits don’t have to be something mathematical in nature, they might be a string tag or some data about which image to use when drawing that object, or even material or mesh references. Essentially, they can be anything that describes that object.
One of the most common approaches is to write an abstract base class that all game objects will inherit from – a GameObject class. As a matter of fact, majority of popular general purpose game engines today use a derivative of the GameObject pattern – Unity GameObject approach (not Unity DOTS, which is an ECS system), Unreal Actors and even OGRE Entities.
A naive OOP implementation would rely on the assumption that GameObject is implemented as an abstract class with some basic properties and state management methods, and can in turn be extended in order to add some other properties and behaviors.
Here is an example of what such a naive OOP approach would look like in TypeScript when given an abstract base class GameObject:
While intuitive and clean, this approach works well only for smaller amounts of objects on the scene and fails when that number starts to reach hundreds of thousands of objects. Unfortunately, this yields maintenance complexity, hinders refactoring and has the potential to grind development to a halt in long-living large projects.
Imagine we had 300 different entity types (which is, in practice, not at all a large number), inheriting from one another and then, one year into the development cycle, it is decided a piece of implemented game logic is not fun enough and another one should be put in its place, fundamentally changing game objects and ruining inheritance hierarchy. Fun, right?
To add fuel to the fire, performance problems come from memory fragmentation due to the excessive use of dynamic memory allocation (this can be battled, though, by writing one’s own memory allocation primitives, and pooling and using C/C++ or rust – not an easy task in itself) and resolving virtual functions left and right, but this is a common problem when going too far with class hierarchies.
Well, this is where an actual ECS saves the day.
What is an ECS?
ECS stands for Entity-Component-System and is essentially a popular architectural approach which taps into concepts like data-driven development and databases. At first glance, it might seem like it has at best some loose relations with game dev, but bear with me.
An Entity is an object that has some traits – Components, which have some behavior – Systems. Pretty similar to the GameObject, but the difference is how these entities are represented, constructed and used. ECS favors composition over inheritance and avoids inheritance hell by simply not using it.
In an ECS, an Entity is nothing more than a unique numeric id, a Component is a structure, essentially pure data, nothing more and nothing less, and a System is a function that operates on one or more different components belonging to the same entity at the moment of execution.
Since ECS libraries leverage the struct of arrays pattern for their components, Entity is literally just an index into the arrays of components the said entity has.
Instead of being intrusive, it allows for composing any number of different components into an entity and then gives the developer the ability to modify the states of those components with systems. In addition, it allows for dynamically adding or removing components to and from an entity during the runtime without depending on polymorphism provided from classical inheritance (i.e. holding a list of pointers to the base abstract component class type).
The same example of a Spaceship written with a bespoke ECS library:
Note that while there is a fair bit more code written upfront with an ECS, it is more explicit and allows us to do something amazing – turn systems (behaviors) on/off as well as add/remove components on a whim! What if a player’s ship has been hit by a rock and its engines are disabled? Just call ecs.unregisterSystem(spaceshipMove)and register it back again after engines have been fixed. Similarly, what if weapons got disabled? Just unregister the shooting system function and observe the simplicity of rapid prototyping and feature introduction!
Want another weapon? Just swap the shooting system. Want to have a shield? Add a Shield component to the spaceship (and register the shield system if it has not already been registered)!
With a classical GameObject approach we would need to introduce either the dreaded ifologies inside the update method or, if done correctly, a finite state machines, and deal with updates in separate states to achieve the same result (which also ends up creating a lot more code).
True power of the ECS pattern lies in the extreme ease of creating more from the components that we already have, the fast iteration on features and the luxury of always being able to work on one segment at a time – if you want to introduce a new renderer, just add a set of new components and system functions, and try them out without a single modification to the old renderer. In a true sense of the best programming practices – ECS pattern enables us to write highly decoupled code without having to worry that everything will crash and burn if some components are missed or certain systems not registered.
With regard to our previously mentioned performance problems – by utilizing the struct of arrays pattern (even though the struct could actually be a dictionary or a map or even a JS object), keeping all the components of the same type close together and never deleting them (reset and initialize the ‘deleted’ component when creating a new one) will cause significantly less CPU cache misses when iterating over them, thus saving time. This is much more noticeable in languages where we have direct control over memory, such as C/C++ and Rust, but it also has some benefits in JS/TS realm because of the explicit ownership of memory and garbage collection avoidance. Haskell is, again, specific; even though you can manually control memory via FFI calls to C libs, deep understanding of Haskell’s laziness is required, but in the end the ECS approach will still reduce the amount of generated garbage memory.
Ok, so now that we have a rough idea of what we want to build, we can write a list of requirements that our ECS library needs to meet:
- provide a single library entry point (i.e. const ecs = new Ecs(…))
- provide an API which allows us to:
- create entities from component sets
- retain the ownership of allocated components to prevent garbage collection – pooling
- destroy entities and ‘release’ components to their pools upon deletion
- query explicitly or iterate over all entities with specific components
- dynamically add or remove components
- dynamically register and unregister systems
- provide a context with access to built-in APIs like graphics device, timers, input…
- ensure the code is type-safe and utilize TypeScript to prevent us from matching wrong components and provide proper code completion.
In order to implement all of the aspects of an ECS, we need to figure out the following:
- how to store our entities and components and prevent garbage collection
- how to access stored entities and components
- how to bend the TypeScript type system to allow for type safety while at the same time being dynamic (add/remove components to and from entities dynamically).
Storing Entities and Components
In order to store the data, we need to somehow represent every single possible combination of components as a table-like structure where an Entity indexes into the table ‘row’ in order to lookup its components, making sure it is as lazy as possible and only creates new tables when a new combination of components is encountered. As long as newly allocated tables and components are never deleted or left to float on the heap without references to them, garbage collection will be prevented and the system will not experience any stuttering as a result of that.
Luckily, in order to store our data, we can pick between two battle-tested approaches, sparse sets and archetype tables.
Sparse sets are a technique that utilizes array random access in order to index into correct component row per entity and pretty much boil down to arrays of arrays of arrays. JS arrays are sparse arrays and could be used to simplify implementation. Naive sparse sets are simpler to use and solve all of the above problems really well.
A naive implementation could just proclaim that there is a single table, numberOfEntities x numberOfComponents sparse matrix in essence, and be done with it. In practice, while it is possible to do it like this (it also provides almost free component adding/removing), one layer of indirection is added to mimic archetypes approach internally, but this complicates things a bit. The downsides are memory consumption (a lot of empty components unless a more archetype-y approach is used), the fact that it is not as good as the archetype tables performance-wise, it is far harder to iterate in parallel (which we really don’t care about since we are limited to a single thread because of JS), and this approach does not reflect the database-y concepts ECS relies on fully.
Archetypes should be thought of as plain database tables. They have their columns as different components. Since we don’t really care for archetype column id’s, we can even reduce them to implicit row indices and then use the sparse array to resolve entity id’s to correct rows. Essentially, if we have two different entity configurations, one with Transform and Sprite, and the other with Transform, Sprite and Spaceship, those belong to two separate archetypes even though they share some component types. An entity’s component signature uniquely defines its archetype.
A naive type representing an Archetype table could look like this:
In the end, writing a proper archetype-based ECS will make it easier to reason about implementation-wise.
In order to access entity’s components, we first need to know its signature. An entity’s signature is simply an array of all component classes, not instances, it has. It makes sense to force the entities to always have at least a single component to avoid complications down the line (additionally, an entity without an aspect really has no obvious use). When determining the signature, we need to ensure that the order of components does not affect the signature we calculate, and converting the array of components into a Set will solve this problem.
In order to express this properly with TypeScript, we need the following type helpers:
Archetypes and Component Pools
As mentioned before, archetypes are structs of arrays of components. Unlike the naive static archetype, in practice, the components an archetype holds need to be determined during runtime as the need for another archetype arises. An archetype, therefore, holds a Map<ClassType, InstanceType>, which is determined when a unique archetype is created.
As is apparent from the code, base archetype implementation is pretty straightforward and reflects the described storage requirements well.
Now, if we don’t create anything, we won’t need to delete anything either, so it makes sense to tackle creation first. When creating, we need to find the next first available row (nextAvailableRow), acquire the components on that row and give the developer a way to initialize referenced components and ensure that. Note that if there are no available rows, the pool needs to grow enough to accommodate more rows (the simplest strategy works really well for ECS requirements – increase the pool by the factor of two). We also need to introduce another type helper which will calculate the type of arguments the initializer function is to receive. When ‘constructing’, or rather initializing a component, care has to be taken to allow to reset a component (since JS lacks memset or similar functions, this is best done by an optional method called reset, which just zeroes out or sets all of the component’s properties to their initial values).
First, the type helper which constructs a new type – a tuple of instances of a passed-in tuple of class types:
This type helper is a nice example of what TypeScript’s type system is capable of. We can take a type and then, depending on some constraint or rule, infer a completely different type. This specific technique is called conditional typing and is a powerful tool which allows us to model some domain rules straight inside the type system without the need to do any runtime checking or validation.
And that’s it for the creation part. Now for something more fun! The deletion. When deleting entities, it is important to note that instead of deleting, we need to overwrite the entity being deleted with the components of the last used row and maintain the index. This way we avoid fragmentation and ensure no memory is allocated or freed. The side-effect of this approach is that the order of iteration is not maintained anymore, but this is actually not a problem because code consuming ECS pattern should not rely on the order of iteration over entities or components.
The only thing left now is to provide a way of accessing the created data. I will present a declarative way (with a query and mutation function) and an imperative way (with a query and a generator).
First the declarative query way:
And the imperative generator way:
There are some useful helper methods we can expose, such as queryWhere and deleteWhere, which add a predicate to filter out which entities will be affected by the operation. We will not be bothering with them here, but they are easy to implement given the code snippets above.
As far as adding or removing components and moving entities from one archetype to another is concerned, the same applies to the given receiveEntity method, which receives an originating archetype, an entity and its components alongside an initializer for the newly added components. This method places the components as the latest added entity, ensuring that the originating archetype index and components are correctly maintained.
It might come as a surprise, but we have actually implemented all that is needed for systems to exist. As soon as archetype’s query and view methods are written, systems are enabled. Neat, right? The only thing that is missing is the code that will register, unregister, run and maintain the index of all systems’ functions given to the ECS. This part is best handled in the library itself to avoid cluttering archetypes.
Library Entry Point
Now that all building blocks have been implemented, we can join them into a single-entry point, with a simple API hiding all the complexities of the internal organization.
The desired api might look like this:
As far as API surface area goes, it is extremely small and easy to both use and learn. Of course, we can extend the API with a lot of new and useful functionality that mainly builds off of already existing functionality.
Here are some possible extensions that can be done without adding a lot of code:
- distinguish between system functions running on specific component sets and systems that don’t run on components but are rather invoked every game-loop tick (i.e. tasks)
- add a priority factor to every system in order to control the order of execution of the said systems
- implement a Query and Filter concepts which are not just plain tuples of component classes but are also able to query based on some logical expressions (for example [Transform, Any(Mesh, Wireframe), Some(Material, PbrMaterial)])
- implement a lifecycle callback system which reacts to component adds/removes, entity creation, update, destruction, and so on.
Implementing an ECS library might not be a long undertaking nor a complex one for that matter, but in essence, it shows how the user-facing API might hide internal complexities and proves that TypeScript is more than suited to provide both type-safety and a pleasant development experience. Code snippets and the approach presented here should be enough to serve as the basis for a full-fledged ECS library that can be used for hobby projects or, with little extra work, might even power commercial ones.
Continue exploring the Dev Corner to meet our dev team and read a tech blog or two
Check out the t-matix main website if you are interested in the t-matix group and want to find out more about our solution as well as industries we cater
December 18, 2019
Continuosly building, testing, releasing and monitoring t-matix mobile apps