Repository: mlange-42/arche
Pull request #2 (2023-02-05 00:08:59)

Entity ID recycling
Implements entity ID recycling using implicit linked lists. See https://skypjack.github.io/2019-05-06-ecs-baf-part-3/


Patch:
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..46620af
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,1 @@
+/coverage.out
diff --git a/ecs/entity.go b/ecs/entity.go
index 7f32d0d..c091474 100644
--- a/ecs/entity.go
+++ b/ecs/entity.go
@@ -1,1 +1,11 @@
 package ecs
+
+// Entity identifier
+type Entity struct {
+	id  uint32
+	gen uint16
+}
+
+func newEntity(id int) Entity {
+	return Entity{uint32(id), 0}
+}
diff --git a/ecs/entity_pool.go b/ecs/entity_pool.go
new file mode 100644
index 0000000..4c14d1d
--- /dev/null
+++ b/ecs/entity_pool.go
@@ -0,0 +1,62 @@
+package ecs
+
+// EntityPool is the interface for entity recycling
+type EntityPool interface {
+	// Get returns a fresh or recycled entity
+	Get() Entity
+	// Recycle hands an entity back for recycling
+	Recycle(Entity)
+	// Alive return whether an entity is currently alive
+	Alive(Entity) bool
+}
+
+// NewEntityPool creates a new, initialized EntityPool
+func NewEntityPool() EntityPool {
+	return &implicitListEntityPool{
+		entities:  []Entity{},
+		next:      0,
+		available: 0,
+	}
+}
+
+// Creates a pool with proper initialization of next
+func newImplicitListEntityPool() *implicitListEntityPool {
+	return &implicitListEntityPool{
+		entities:  []Entity{},
+		next:      0,
+		available: 0,
+	}
+}
+
+// implicitListEntityPool is an EntityPool implementation using implicit linked lists.
+// Implements https://skypjack.github.io/2019-05-06-ecs-baf-part-3/
+type implicitListEntityPool struct {
+	entities  []Entity
+	next      uint32
+	available uint32
+}
+
+// Get returns a fresh or recycled entity
+func (p *implicitListEntityPool) Get() Entity {
+	if p.available == 0 {
+		e := newEntity(len(p.entities))
+		p.entities = append(p.entities, e)
+		return e
+	}
+	curr := p.next
+	p.next, p.entities[p.next].id = p.entities[p.next].id, p.next
+	p.available--
+	return p.entities[curr]
+}
+
+// Recycle hands an entity back for recycling
+func (p *implicitListEntityPool) Recycle(e Entity) {
+	p.entities[e.id].gen++
+	p.next, p.entities[e.id].id = e.id, p.next
+	p.available++
+}
+
+// Alive return whether an entity is currently alive
+func (p *implicitListEntityPool) Alive(e Entity) bool {
+	return e.gen == p.entities[e.id].gen
+}
diff --git a/go.mod b/go.mod
index 183a73f..6ef6626 100644
--- a/go.mod
+++ b/go.mod
@@ -1,3 +1,11 @@
 module github.com/mlange-42/arche
 
 go 1.20
+
+require github.com/stretchr/testify v1.8.1
+
+require (
+	github.com/davecgh/go-spew v1.1.1 // indirect
+	github.com/pmezard/go-difflib v1.0.0 // indirect
+	gopkg.in/yaml.v3 v3.0.1 // indirect
+)
diff --git a/go.sum b/go.sum
new file mode 100644
index 0000000..2ec90f7
--- /dev/null
+++ b/go.sum
@@ -0,0 +1,17 @@
+github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
+github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
+github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
+github.com/stretchr/objx v0.4.0/go.mod h1:YvHI0jy2hoMjB+UWwv71VJQ9isScKT/TqJzVSSt89Yw=
+github.com/stretchr/objx v0.5.0/go.mod h1:Yh+to48EsGEfYuaHDzXPcE3xhTkx73EhmCGUpEOglKo=
+github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
+github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO+kdMU+MU=
+github.com/stretchr/testify v1.8.1 h1:w7B6lhMri9wdJUVmEZPGGhZzrYTPvgJArz7wNPgYKsk=
+github.com/stretchr/testify v1.8.1/go.mod h1:w2LPCIKwWwSfY2zedu0+kehJoqGctiVI29o6fzry7u4=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
+gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
+gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=


Test patch:
diff --git a/ecs/entity_pool_test.go b/ecs/entity_pool_test.go
new file mode 100644
index 0000000..c69f530
--- /dev/null
+++ b/ecs/entity_pool_test.go
@@ -0,0 +1,91 @@
+package ecs
+
+import (
+	"math/rand"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestEntityPoolConstructor(t *testing.T) {
+	_ = NewEntityPool()
+}
+
+func TestEntityPool(t *testing.T) {
+	p := newImplicitListEntityPool()
+
+	expectedAll := []Entity{newEntity(0), newEntity(1), newEntity(2), newEntity(3), newEntity(4)}
+
+	for i := 0; i < 5; i++ {
+		_ = p.Get()
+	}
+	assert.Equal(t, expectedAll, p.entities, "Wrong initial entities")
+
+	e0 := p.entities[0]
+	p.Recycle(e0)
+	assert.False(t, p.Alive(e0), "Dead entity should not be alive")
+
+	e0Old := e0
+	e0 = p.Get()
+	expectedAll[0].gen++
+	assert.True(t, p.Alive(e0), "Recycled entity of new generation should be alive")
+	assert.False(t, p.Alive(e0Old), "Recycled entity of old generation should not be alive")
+
+	assert.Equal(t, expectedAll, p.entities, "Wrong entities after get/recycle")
+
+	e0Old = p.entities[0]
+	for i := 0; i < 5; i++ {
+		p.Recycle(p.entities[i])
+		expectedAll[i].gen++
+	}
+
+	assert.False(t, p.Alive(e0Old), "Recycled entity of old generation should not be alive")
+
+	for i := 0; i < 5; i++ {
+		_ = p.Get()
+	}
+
+	assert.False(t, p.Alive(e0Old), "Recycled entity of old generation should not be alive")
+}
+
+func TestEntityPoolStochastic(t *testing.T) {
+	for i := 0; i < 10; i++ {
+		p := newImplicitListEntityPool()
+
+		alive := map[Entity]bool{}
+		for i := 0; i < 10; i++ {
+			e := p.Get()
+			alive[e] = true
+		}
+		for e, isAlive := range alive {
+			assert.Equal(t, isAlive, p.Alive(e), "Wrong alive state of entity %v after initialization", e)
+			if rand.Float32() > 0.75 {
+				continue
+			}
+			p.Recycle(e)
+			alive[e] = false
+		}
+		for e, isAlive := range alive {
+			assert.Equal(t, isAlive, p.Alive(e), "Wrong alive state of entity %v after 1st removal. Entity is %v", e, p.entities[e.id])
+		}
+		for i := 0; i < 10; i++ {
+			e := p.Get()
+			alive[e] = true
+		}
+		for e, isAlive := range alive {
+			assert.Equal(t, isAlive, p.Alive(e), "Wrong alive state of entity %v after 1st recycling. Entity is %v", e, p.entities[e.id])
+		}
+		assert.Equal(t, uint32(0), p.available, "No more entities should be available")
+
+		for e, isAlive := range alive {
+			if !isAlive || rand.Float32() > 0.75 {
+				continue
+			}
+			p.Recycle(e)
+			alive[e] = false
+		}
+		for e, a := range alive {
+			assert.Equal(t, a, p.Alive(e), "Wrong alive state of entity %v after 2nd removal. Entity is %v", e, p.entities[e.id])
+		}
+	}
+}
diff --git a/ecs/entity_test.go b/ecs/entity_test.go
new file mode 100644
index 0000000..0f89843
--- /dev/null
+++ b/ecs/entity_test.go
@@ -0,0 +1,13 @@
+package ecs
+
+import (
+	"testing"
+)
+
+func TestEntityAsIndex(t *testing.T) {
+	entity := Entity{1, 0}
+	arr := []int{0, 1, 2}
+
+	val := arr[entity.id]
+	_ = val
+}