blob: c6303d3d6c42931fe69fc27635a5266023b9b142 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
package coffee.liz.ecs
import kotlin.concurrent.atomics.AtomicInt
import kotlin.concurrent.atomics.ExperimentalAtomicApi
import kotlin.concurrent.atomics.incrementAndFetch
import kotlin.reflect.KClass
import kotlin.time.Duration
/**
* [World] that updates in [System.dependencies] topological order.
*/
@OptIn(ExperimentalAtomicApi::class)
class DAGWorld<Outside>(
systems: List<System<Outside>>,
) : World<Outside> {
private val entities = mutableSetOf<Entity>()
private val componentCache = mutableMapOf<KClass<out Component>, MutableSet<Entity>>()
private val systemExecutionOrder: List<System<Outside>> = buildExecutionOrder(systems)
private val nextEntityId = AtomicInt(0)
override fun createEntity(): Entity =
Entity(nextEntityId.incrementAndFetch())
.also { entities.add(it) }
override fun removeEntity(entity: Entity) {
entity.componentTypes().forEach { componentType ->
componentCache[componentType]?.remove(entity)
}
entities.remove(entity)
}
override fun query(vararg componentTypes: KClass<out Component>): Set<Entity> {
if (componentTypes.isEmpty()) return entities.toSet()
val firstType = componentTypes[0]
val candidates = componentCache[firstType] ?: return emptySet()
return candidates
.filter { entity -> componentTypes.all { entity.has(it) } }
.toSet()
}
override fun update(
state: Outside,
deltaTime: Duration,
) {
refreshComponentCache()
systemExecutionOrder.forEach { system ->
system.update(this, state, deltaTime)
}
}
private fun refreshComponentCache() {
componentCache.clear()
entities.forEach { entity ->
entity.componentTypes().forEach { componentType ->
componentCache.getOrPut(componentType) { mutableSetOf() }.add(entity)
}
}
}
private fun buildExecutionOrder(systems: List<System<Outside>>): List<System<Outside>> {
if (systems.isEmpty()) return emptyList()
val systemMap = systems.associateBy { it::class }
val inDegree = mutableMapOf<KClass<out System<Outside>>, Int>()
val adjacencyList = mutableMapOf<KClass<out System<Outside>>, MutableSet<KClass<out System<Outside>>>>()
// Initialize graph
systems.forEach { system ->
val systemClass = system::class
inDegree[systemClass] = 0
adjacencyList[systemClass] = mutableSetOf()
}
// Build dependency graph (reversed - dependencies point to dependents)
systems.forEach { system ->
system.dependencies.forEach { dependency ->
if (systemMap.containsKey(dependency)) {
adjacencyList[dependency]!!.add(system::class)
inDegree[system::class] = inDegree[system::class]!! + 1
}
}
}
// Kahn's algorithm
val queue = ArrayDeque<KClass<out System<Outside>>>()
val result = mutableListOf<System<Outside>>()
queue.addAll(inDegree.filterValues { it == 0 }.keys)
while (queue.isNotEmpty()) {
val currentClass = queue.removeFirst()
result.add(systemMap[currentClass]!!)
// Process dependents
adjacencyList[currentClass]?.forEach { dependent ->
inDegree[dependent] = inDegree[dependent]!! - 1
if (inDegree[dependent] == 0) {
queue.add(dependent)
}
}
}
if (result.size != systems.size) {
error("Circular dependency detected in systems")
}
return result
}
}
|
