Repository: mlange-42/arche (go)

Issue:
Archetype graph
Currently, on archetype transition the engine searches for the matching archetype by brute force using the components bitmask.

This could be improved by constructing an archetype graph. Each archetype would hold a list of which archetypes are reached by adding or removing a certain component type.

![grafik](https://user-images.githubusercontent.com/44003176/217200459-dca5790e-0373-446a-9f0a-5253db1e899b.png)

Image source: [ajmmertens.medium.com](https://ajmmertens.medium.com/building-an-ecs-2-archetypes-and-vectorization-fe21690805f9)

Pull request description:
Archetype graph
Implements an archetype graph for faster lookup of transitions

Fixes #17

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index e4a5cdf..388b8de 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,7 +2,9 @@
 
 ## [[unpublished]](https://github.com/mlange-42/arche/compare/v0.2.0...main)
 
-Nothing
+### Other
+
+* Use of an archetype graph to speed up finding the target archetype for component addition/removal (#42)
 
 ## [[v0.2.0]](https://github.com/mlange-42/arche/compare/v0.1.4...v0.2.0)
 
diff --git a/ecs/archetype.go b/ecs/archetype.go
index c83395e..2556de4 100644
--- a/ecs/archetype.go
+++ b/ecs/archetype.go
@@ -14,6 +14,8 @@ type archetype struct {
 	indices    [MaskTotalBits]uint8
 	entities   storage
 	components []storage
+	toAdd      map[ID]*archetype
+	toRemove   map[ID]*archetype
 }
 
 var entityType = reflect.TypeOf(Entity{})
@@ -40,6 +42,8 @@ func (a *archetype) init(capacityIncrement int, components ...componentType) {
 	a.mask = mask
 	a.components = comps
 	a.entities = storage{}
+	a.toAdd = map[ID]*archetype{}
+	a.toRemove = map[ID]*archetype{}
 	a.entities.init(entityType, capacityIncrement)
 }
 
@@ -110,3 +114,21 @@ func (a *archetype) Len() uint32 {
 func (a *archetype) Set(index uint32, id ID, comp interface{}) unsafe.Pointer {
 	return a.components[a.indices[id]].set(index, comp)
 }
+
+func (a *archetype) GetTransitionAdd(id ID) (*archetype, bool) {
+	p, ok := a.toAdd[id]
+	return p, ok
+}
+
+func (a *archetype) GetTransitionRemove(id ID) (*archetype, bool) {
+	p, ok := a.toRemove[id]
+	return p, ok
+}
+
+func (a *archetype) SetTransitionAdd(id ID, to *archetype) {
+	a.toAdd[id] = to
+}
+
+func (a *archetype) SetTransitionRemove(id ID, to *archetype) {
+	a.toRemove[id] = to
+}
diff --git a/ecs/world.go b/ecs/world.go
index b9ddc3a..335e0e4 100644
--- a/ecs/world.go
+++ b/ecs/world.go
@@ -201,7 +201,7 @@ func (w *World) Exchange(entity Entity, add []ID, rem []ID) {
 		}
 	}
 
-	arch := w.findOrCreateArchetype(mask)
+	arch := w.findOrCreateArchetype(oldArch, addIDs, rem)
 
 	allComps := make([]componentPointer, 0, len(keepIDs)+len(addIDs))
 	for _, id := range keepIDs {
@@ -231,11 +231,39 @@ func (w *World) copyTo(entity Entity, id ID, comp interface{}) unsafe.Pointer {
 	return arch.Set(index.index, id, comp)
 }
 
-func (w *World) findOrCreateArchetype(mask bitMask) *archetype {
+func (w *World) findOrCreateArchetype(start *archetype, add []ID, rem []ID) *archetype {
+	curr := start
+	mask := start.mask
+	for _, id := range rem {
+		mask.Set(id, false)
+		if next, ok := curr.GetTransitionRemove(id); ok {
+			curr = next
+		} else {
+			next, _ := w.findOrCreateArchetypeSlow(mask)
+			next.SetTransitionAdd(id, curr)
+			curr.SetTransitionRemove(id, next)
+			curr = next
+		}
+	}
+	for _, id := range add {
+		mask.Set(id, true)
+		if next, ok := curr.GetTransitionAdd(id); ok {
+			curr = next
+		} else {
+			next, _ := w.findOrCreateArchetypeSlow(mask)
+			next.SetTransitionRemove(id, curr)
+			curr.SetTransitionAdd(id, next)
+			curr = next
+		}
+	}
+	return curr
+}
+
+func (w *World) findOrCreateArchetypeSlow(mask bitMask) (*archetype, bool) {
 	if arch, ok := w.findArchetype(mask); ok {
-		return arch
+		return arch, false
 	}
-	return w.createArchetype(mask)
+	return w.createArchetype(mask), true
 }
 
 func (w *World) findArchetype(mask bitMask) (*archetype, bool) {


Test patch:
diff --git a/ecs/world_test.go b/ecs/world_test.go
index 7d052e2..0fe6b6f 100644
--- a/ecs/world_test.go
+++ b/ecs/world_test.go
@@ -281,6 +281,28 @@ func TestRegisterComponents(t *testing.T) {
 	assert.Equal(t, ID(1), ComponentID[rotation](&world))
 }
 
+func TestArchetypeGraph(t *testing.T) {
+	world := NewWorld()
+
+	posID := ComponentID[position](&world)
+	velID := ComponentID[velocity](&world)
+	rotID := ComponentID[rotation](&world)
+
+	archEmpty := world.archetypes.Get(0)
+	arch0 := world.findOrCreateArchetype(archEmpty, []ID{posID}, []ID{})
+	archEmpty2 := world.findOrCreateArchetype(arch0, []ID{}, []ID{posID})
+
+	assert.Equal(t, archEmpty, archEmpty2)
+
+	arch01 := world.findOrCreateArchetype(arch0, []ID{velID}, []ID{})
+	arch012 := world.findOrCreateArchetype(arch01, []ID{rotID}, []ID{})
+
+	assert.Equal(t, []ID{0, 1, 2}, arch012.ids)
+
+	archEmpty3 := world.findOrCreateArchetype(arch012, []ID{}, []ID{posID, rotID, velID})
+	assert.Equal(t, archEmpty, archEmpty3)
+}
+
 func TestTypeSizes(t *testing.T) {
 	printTypeSize[World]()
 	printTypeSizeName[pagedArr32[archetype]]("PagedArr32")