Sparse Set

SparseSet is Shipyard's default storage. This chapter explains the basics of how it works, the actual implementation is more optimized both in term of speed and memory.

Overview

SparseSet is made of three arrays:

• sparse contains indices to the dense and data arrays
• dense contains EntityId
• data contains the actual components

dense and data always have the same length, the number of components present in the storage.
sparse on the other hand can be as big as the total number of entities created.

Let's look at an example:

let mut world = World::new();

let entity0 = world.add_entity((0u32,));
let entity1 = world.add_entity((10.0f32,));
let entity2 = world.add_entity((20u32,));

The World starts out empty, when we add 0u32 a SparseSet<u32> will be generated.

At the end of the example we have:

SparseSet<u32>:
    sparse: [0, dead, 1]
    dense:  [0, 2]
    data:   [0, 20]

SparseSet<f32>:
    sparse: [dead, 0]
    dense:  [1]
    data:   [10.0]

You can see that SparseSet<u32>'s sparse contains three elements but dense does not.
Note also that both sparse don't contains the same number of elements. As far as SparseSet<f32> knowns entity2 might not exist.

Removal

Removing is done by swap removing from both dense and data and updating sparse in consequence.

Continuing the previous example if we call:

world.remove::<(u32,)>(entity0);

The internal representation now looks like this:

sparse: [dead, dead, 0]
dense: [2]
data: [20]

dense and data shifted to the left, sparse's first element is now dead and the third element is now 0 to follow dense's shift.

Iteration

Iterating one or several SparseSet is different. With a single SparseSet it's as simple as iterating data.
To iterate multiple SparseSets the smallest will be chosen as "lead". We then iterate its dense array and for each entity we check all the other SparseSets to see if they also contain a component for this entity.