Building an ECS #2: Archetypes and Vectorization

Arrays, array, arrays

The ABC problem

A a[3];
B b[3];
B b[2];
0: [A B]
1: [A ]
2: [A B]
0: [A B]
2: [A B]
1: [A ]
3: [  B]
0: [A B]
2: [A B]
1: [A ]
0: [  B  ]
1: [ B C]
2: [A B C]
3: [A B ]
4: [A ]
5: [A C]
6: [ C]

Archetypes

// Type [A]
A a[2];
// Type [A, B]
A a[2];
B b[2];
// Type [A, C]
A a[2];
C c[2];
0: [A]
1: [A]
2: [A B]
3: [A B]
4: [A C]
5: [A C]
for (int i = 0; i < 10; i ++) {
a[i] += b[i];
}
struct ComponentArray {
void *elements; // vector<T>
int size;
};
struct Archetype {
Type type;
vector<ComponentArray> components;
int length;
};

Finding entities and components

struct Record {
Archetype *archetype;
int row;
};
unordered_map<EntityId, Record> entity_index;
Record& r = entity_index[10];
Type& type = r.archetype->type;
for (int i = 0; i < type.size(); i ++) {
if (type[i] == A) {
return r.archetype->components[i].elements[r.row];
}
}
struct Archetype {
Type type;
vector<EntityId> entity_ids; // Entities stored in archetype
vector<ComponentArray> components;
int length;
vector<Edge> edges;
};

This is the big trade off of archetypes: we gain iteration speed at the cost of copying components when adding (and removing) components.

Adding components

  • Find destination archetype
  • Insert entity into component arrays of destination
  • Copy overlapping components from source to destination
  • Remove entity from component arrays of source

Finding an archetype

using TypeHash = uint64_t;
unordered_map<TypeHash, Archetype*> type_index;
An example archetype graph
struct Archetype;struct ComponentArray {
void *elements; // vector<T>
int size;
};
struct Edge {
Archetype *add; // traverse right
Archetype *remove; // traverse left
};
struct Archetype {
Type type;
vector<EntityId> entity_ids;
vector<ComponentArray> components;
int length;
vector<Edge> edges;
};
Archetype *node = root;
for (int i = 0; i < type.size(); i ++) {
Edge *edge = &node->edges[type[i]];
if (!edge->add) {
edge->add = create_archetype(node, type[i]);
}

node = edge->add;
}

AoS vs. SoA

struct SoA_Archetype {
A a[100];
B b[100];
C c[100];
};
struct EntityType {
A a;
B b;
C c;
};
EntityType AoS_ArcheType[100];

Summary

// Entities, types and entity index
using EntityId = uint64_t;
using Type = vector<EntityId>;
unordered_map<EntityId, Type> entity_index;
// Type flags
const EntityId INSTANCEOF = 1 << 63;
const EntityId CHILDOF = 2 << 62;
// Component data
struct ComponentArray {
void *elements; // vector<T>
int size;
};
// Archetype graph
struct Archetype;
struct Edge {
Archetype *add;
Archetype *remove;
};
struct Archetype {
Type type;
vector<EntityId> entity_ids;
vector<ComponentArray> components;
int length;
vector<Edge> edges;
};

--

--

--

I write lots of code.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Elementary Guide to Hashicorp’s Nomad with Linux.

Hashicorp’s Nomad and Javascript project wallpaper

Attention! How To Add Value To Your Business By Developing Mobile Apps?

Replacing Ternary Operators With the Elvis Operator

15 Reasons You’ll Love Programming

2D Galaxy Shooter P1: Shield Strength Challenge Activated!

Sudo privilege escalation

I gave up holidays to get shit done.

Moving to a new ElasticSearch index without impacting live traffic

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sander Mertens

Sander Mertens

I write lots of code.

More from Medium

Saving Data in Unity3D Using BinaryReader and BinaryWriter

FIDO WebAuthn Passwordless: Let’s go bananas!

The making of an Art Auction House

Compiler Adventures, part 2: Constant Propagation

A blurry photo of a galaxy, with a bright blob in the middle surrounded by fuzzy swirling clouds of gas. Next to it, a crisp and sharp image of the same galaxy, showing many dots of light and and individual clouds where previously there was just a blur of color.