An introduction to ECS by example
In this post, I'm taking a closer look at how an ECS system works, talking about the pros and cons of different approaches, and trying to answer if it's something that could be used outside of gaming.
What is an ECS
ECS is a programming pattern commonly used in high-end game engines, simulations, visual effects and CAD/CAM software, among others. The acronym stands for Entity-Component-System, and it forms the foundation of the ECS architecture. Unlike the traditional object-oriented programming approach based on inheritance, this architecture uses composition. While it's not as well-known for smaller projects, ECS is a go-to choice for top-tier applications where performance is of utmost importance. This is because it efficiently utilizes CPU instruction and data caches.
In the following sections, we'll explore the ECS design of a basic game.
Components
To create basic movement, two main components are used: transformations and movement. Transform2d enables entities to be positioned within the world, while Move handles updates to movement. These components can be represented as plain objects.
type
Move* = object
direction*: Vec2
speed*: float32
Transform2d* = object
world*: Mat2d # Matrix relative to the world
translation*: Vec2 # local translation relative to the parent
rotation*: Rad
scale*: Vec2
children*: array[10, Entity]You might be wondering why we're opting for an array[10, Entity] instead of using types like seq that reference memory. The reason is that using such types would violate the principle of data locality, which is a fundamental requirement of a strict ECS implementation.
Storing components
To maintain data locality in a strict ECS architecture, all components are stored in linear arrays. It's worth noting that, for now, these arrays are sparsely populated and therefore not space-efficient. The explanation for their indexing can be found in the section on Populating the World.
type
Array*[T] = object
data: ptr array[maxEntities, T]
World* = object
moves*: Array[Move]
cameraShake*: ref Shake
transforms*: Array[Transform2d]It's worth noting that the cameraShake component, being a singleton, utilizes a ref instead.
It's worth mentioning that creating a custom heap array of a fixed size that's automatically managed by the memory system is quite easy in Nim. Additionally, if you want to learn more, you can refer to the official documentation.
I manually declare an enum value for each component, which is used to establish a "has-a" relationship. The section on Entity's signature explores the usage of these values in more detail.
type
HasComponent* = enum
HasMove,
HasShake,
HasTransform2dEntities
The Entity is a unique identifier that represents a distinct item in the world. Its implementation is as follows:
type Entity* = distinct uint16
This imposes a limitation on the maximum number of entities that can exist, which will be discussed later.
Association
Transforms can have child transforms attached to them, which is utilized to group entities into larger structures (such as a character being a hierarchy of body parts). A scene graph offers a mechanism to transform a child node's transform relative to its parent node's transform.
How can a child be linked to its parent? The answer is by using their Entity handle.
type
Transform2d* = object
...
children*: array[10, Entity]However, this method sets a strict constraint on the number of children that can be linked to a parent. In the Unconstrained Hierarchies section, I explain how to surpass this restriction.
Entity management
To ensure that an entity is referencing valid data, a specialized data structure called a SlotTable can be used. When you insert a value into the SlotTable, you receive a unique key that can be used to retrieve the value.
var st: SlotTable[string]
let ent: Entity = st.incl("Banana")
assert st[ent] == "Banana"
echo ent # Entity(i: 0, v: 1)A SlotTable ensures that keys to deleted values will no longer function by increasing a counter. This means that the version of the internal slot corresponding to the value and that of the key must match. When a value is erased, the slot's version is incremented, rendering the key invalid.
This functionality is achieved by storing the version number in the upper bits of the integer. To retrieve the version number of a key, bitwise operations are used:
template version(e: Entity): untyped = e.uint16 shr indexBits and versionMask
var st: SlotTable[string]
let ent1 = st.incl("Pen")
st.del(ent1)
echo ent1 in st # false
echo ent1.version # 1If a larger number of entities is needed, a wider unsigned type can be used to accommodate more bits for indexing. In such cases, a SparseSet can be used to store the components. This data structure keeps the values in a dense internal container, making it efficient for storing sparsely populated arrays.
Entity's signature
The SlotTable is utilized to store a dense sequence of set[HasComponent], which represents the signature for each entity. A signature is essentially a bitset that describes the component composition of an entity. The role of signatures is explained further in the Systems section.
type
World* = object
signatures*: SlotTable[set[HasComponent]]
...Populating the world
The entity obtained from the SlotTable serves as an index for the "secondary" component arrays, which may contain holes due to entities being created and deleted. The SlotTable recycles entities as they become available.
var st: SlotTable[string]
let ent1 = st.incl("Pen")
let ent2 = st.incl("Pineapple")
st.del(ent1)
let ent3 = st.incl("Apple")
echo ent1 in st # false
echo ent1 # Entity(i: 0, v: 1)
echo ent2 # Entity(i: 1, v: 1)
echo ent3 # Entity(i: 0, v: 3)One way to create a new entity with Transform2d and Move components is to insert {HasTransform2d, HasMove} into the signatures. Then, using the index of the entity returned by the SlotTable, you can set the corresponding items in the world.transforms and world.moves arrays.
template idx*(e: Entity): int = e.int and indexMask
var world: World
let ent = world.signatures.incl({HasTransform2d, HasMove})
world.transforms[ent.idx] = Transform2D(world: mat2d(), translation: vec2(0, 0),
rotation: 0.Rad, scale: vec2(1, 1))
world.moves[ent.idx] = Move(direction: vec2(0, 0), speed: 10'f32)Unconstrained Hiearchies
Efficient implementation of the one-to-many association between a parent Transform2D and its children can be achieved through the use of another component, the Hierarchy. The traversal of the Hierarchy is explained in the Systems section.
type
Hierarchy* = object
head*: Entity # the first child, if any.
prev*, next*: Entity # the prev/next sibling in the list of children for the parent.
parent*: Entity # the parent, if any.The standard textbook algorithm for prepending nodes in a linked list has been adapted to work with the Entity type instead of pointers.
template `?=`(name, value): bool = (let name = value; name != invalidId)
proc prepend*(h: var Array[Hierarchy], parentId, entity: Entity) =
hierarchy.prev = invalidId
hierarchy.next = parent.head
if headSiblingId ?= parent.head:
assert headSibling.prev == invalidId
headSibling.prev = entity
parent.head = entityMultiple hierarchy arrays can be created, for example, one for the model and another for entity scene graphs.
type
World* = object
...
modelSpace*: Array[Hierarchy]
worldSpace*: Array[Hierarchy]To optimize memory efficiency and iteration speed, it is necessary to sort the hierarchies by parent. This can be achieved by using a SparseSet.
Mixins
Components can be viewed as a mixin idiom, where classes can be "included" rather than "inherited".
proc mixMove*(world: var World, entity: Entity, direction: Vec2, speed: float32) =
world.signatures[order].incl HasMove
world.moves[entity.idx] = Move(direction: direction, speed: speed)Systems
Another bitset called Query encodes the set of components required for operations on entities. When iterating over all entities, only the ones whose signature includes Query are processed, while the rest are skipped.
const Query = {HasTransform2d, HasMove}
proc sysMove*(game: var Game) =
for entity, signature in game.world.signatures.pairs:
if Query <= signature:
update(game, entity)A performance issue arises when the number of entities is large, as the total iteration cost for all systems can become high. More complex solutions can be implemented to address this problem.
Tags
At times, values are added to HasComponent without a corresponding component. Such values are employed to trigger further processing or signal a result in an efficient manner.
type
HasComponent = enum
...
HasDirtyTags are added/removed at run-time without a cost:
proc update(game: var Game, entity: Entity) =
template transform: untyped = game.world.transforms[entity.idx]
template move: untyped = game.world.moves[entity.idx]
if move.direction.x != 0.0 or move.direction.y != 0.0:
transform.translation.x += move.direction.x * move.speed
transform.translation.y += move.direction.y * move.speed
world.signatures[entity].incl HasDirtyData is usually transferred between systems by storing it in components. To compute the current world position of each entity after being modified by sysMove:
const Query = {HasTransform2d, HasHierarchy, HasDirty}
iterator queryAll*(parent: Entity, query: set[HasComponent]): Entity =
var frontier = @[parent]
while frontier.len > 0:
let entity = frontier.pop()
if query <= db.signatures[entity]:
yield entity
var childId = hierarchy.head
while childId != invalidId:
frontier.add(childId)
childId = childHierarchy.next
proc sysTransform2d*(game: var Game) =
for entity in queryAll(game.world, game.camera, Query):
world.signatures[entity].excl HasDirty
let local = compose(transform.scale, transform.rotation, transform.translation)
if parentId ?= hierarchy.parent:
template parentTransform: untyped = world.transforms[parentId.idx]
transform.world = parentTransform.world * local
else:
transform.world = localTo display each entity on the screen, sysDraw accesses transform.world and obtains the current world position of each entity.
Comments
Post a Comment