# What data structure do I use to store Archetypes in ECS?

I am implementing an ECS with "archetypes" similar to how they are defined in Unity:

A unique combination of component types is called an Archetype. For example, a 3D object might have a component for its world transform, one for its linear movement, one for rotation, and one for its visual representation. Each instance of one of these 3D objects corresponds to a single entity, but because they share the same set of components, they can be classified as a single archetype:

In this diagram, entities A and B share archetype M, while entity C has archetype N.

You can fluidly change the archetype of an entity by adding or removing components at runtime. For example, if you remove the Renderer component from entity B, then B moves to archetype N.

I know that an archetype is a group of entities with a specific set of components. However, I am confused as to how to actually store the different archetypes. The tutorials I've found online are all quite vague or opaque. I'm using JS.

My first instinct was to use a hash table using a bit array denoting the set of components as the key and the archetype data structure as the value. However, this doesn't seem to work well in JS because TypedArrays use reference equality.

Another approach I tried was using the bit array as an array of integers which index nested hash tables, but this approach is convoluted and introduces several unnecessary layers of indirection.

A third approach I tried was indexing a hash table using the string representation of the bit array but I'm not sure about the performance implications of this approach. (Strings are slow)

What is the ideal data structure (eg array, hash table, set, etc.) to store archetypes or references to archetypes?

To be clearer, I'm looking for a way to determine which archetype an entity belongs to upon addition/removal of components. I'm also looking for a data structure in which to store that component data such that it is friendly to iteration.

An example is Unity, however, other approaches that work are fine as well.

I'm not looking for specific implementations or code, but if they help explain then that's ok, but rather general ideas or guidelines.

Avoiding conditionals

I assume some leeway here, as you've asked for a general approach. The point here is to eliminate the main potential bottlenecks. Unless you are creating very large numbers entities per frame (as in e.g. a particle system), it seems unlikely you will ever need such code - but you asked ;)

First we set up our constants:

//component type (enum)
const LIFE = 1;
const WEAPON = 2;
const JUMP = 3;
const JETPACK = 4;
const GRAPPLE = 5;
const SLIME = 6;
const TELEPORT = 7;
const COMMANDER = 8;

//entity type (enum)
const GRUNT = 0;
const SCOUT = 1;

//bitfields by entity type (archetypes) - faked as arrays, should have minimal impact on performance.
const bitfieldsByEntityType = {}; //or []
bitfieldsByEntityType[GRUNT] = [1,1,1,0,0,0,0,0]; //has life, weapon, and jump abilities
bitfieldsByEntityType[SCOUT] = [1,0,0,1,0,0,0,1];


Then we set up the component creator functions:

function creatorFuncNull()
{
//return undefined; //don't even need to write this, as this is exactly what empty JS functions do.
}

function creatorFuncLife()
{
//various setup steps here if required
let component = new LifeComponent(100); //see caveat, below.

return component;
}
//all your creatorFuncs will return a component this way.
//...TODO define rest of your creator funcs...


Next we map the creator functions into an array by unique index, with null creator at [0]:

const componentCreators = [];
//indices here need to match the above constants
componentCreators[0] = creatorFuncNull; //special at [0], take note
componentCreators[1] = creatorFuncLife;
componentCreators[2] = creatorFuncWeapon;
componentCreators[3] = creatorFuncJump;
componentCreators[4] = creatorFuncJetpack;
componentCreators[5] = creatorFuncGrapple;
componentCreators[6] = creatorFuncSlime;
componentCreators[7] = creatorFuncTeleport;
componentCreators[8] = creatorFuncCommander;


The core function that does the work of creation:

function createEntity(bitfield)
{
let i, bit, componentIndex;
for (i = 0; i < 8, i++) //fixed length loop will be unrolled by the compiler, eliminating loop conditional checks.
{
bit = bitfield[i];

//create and assign to component slot
entity.components[i] = componentCreators[bit * (i+1)];
}
}


Lastly, make use of what we've created:

let bitfield = bitfieldsByEntityType[GRUNT];
let entity = createEntity(bitfield);


e.g. if i == 5, and the bit is set i.e. bit == 1, then we will call into componentCreators[1*5=5], but if the bit is not set, we call [0*5=0], the null creator function. Using multiplication here avoids any conditionals like if (bit == 0) or if (bit == 1). Any unset bit will return undefined at that component slot for that entity - as it should.

(i+1) is used as bitfieldsByEntityType assumes LIFE is 0, WEAPON is 1 etc. - whereas componentCreators assumes LIFE is 1, WEAPON is 2 - to avoid the null creator function at [0].

Trivial to convert to a true bitfield once comfortable with the approach. For greater understanding, see Strategy Pattern - including the null strategy pattern, and Builder Pattern.

Avoiding allocations

Notice that we call new LifeEntity() in the above. This is a massive DON'T, even more so than avoiding conditionals. What you actually need here is to pre-allocate some fixed number of entities before gameplay begins (say 10k) and then assign those into a pool structure (can be just an array or queue if you like) for retrieval (whereupon they are removed from the pool) and immediate re-use; when entities are destroyed, they are returned into this pool for later reuse. So instead of

let entity = new LifeComponent(100);

we would have something like

let args = {lifeValue: 100}; //flexible args object that can be passed regardless of components on this or that entity
let entity = LifeComponentPool.retrieve(args);


But this is a whole other topic. See Object Pool Pattern for more.

You're on the right track, but, oddly enough, Unity's reference documentation doesn't offer the most robust definition of the term Archetype. Granted, I won't be doing that either in this answer but, in the interest of clarity, I'll attempt to further flesh out what the documentation touches on.

An Archetype defines the specific set of components processed by a System. All entities with those components will get processed by said System. That distinction might seem trivial but this concept will shape the architecture of your ECS moving forward.

Also note that an entity's component composition may satisfy multiple Archetypes (and therefore be processed by multiple systems). So in that diagram you referenced, Entities A and B are also valid candidates for Archetype N.

So how does one implement Archetypes in a language like JavaScript? Well, its far from trivial, but you can start by creating a manager class, which some implementations label as the Engine (some implementations refer to it as the World class). This Engine class/object stores your lists of Components and Systems and contains logic to register Entities with Systems when they have the requisite components attached.

With respect to the inner workings of an ECS Engine, they run the gamut, from linked-lists, to bitfields to sparse sets and probably all manner of combinations in-between.

I can't point you to anything Javascript-specific but here are a few resources in other languages that you can check out to see what you can glean from them:

• Richard Lord's Ash Entity Component System - its a classic linked-list implementation written in AS3 (scripting language for the now defunct Flash browser runtime and plugin). The github repo also has links to his blog where his discusses ECS architecture in more depth.
• Retinazer - A bit-field lookup driven implementation written in Java (and indirectly based on Ash). One of the more interesting implementations I've come across.
• EnTT - A C++ implementation that leverages Sparse Sets. Check out the author's series of blog articles ECS Back and Forth, he (Michele "skypjack" Caini) goes to great lengths to explain how his ECS works. Very insightful stuff, the entry about Archetypes should be especially useful.