Init

1 files changed, 127 insertions, 0 deletions

diff --git a/composeApp/src/commonMain/kotlin/coffee/liz/ecs/DAGWorld.kt b/composeApp/src/commonMain/kotlin/coffee/liz/ecs/DAGWorld.kt
new file mode 100644
index 0000000..d314065
--- /dev/null
+++ b/composeApp/src/commonMain/kotlin/coffee/liz/ecs/DAGWorld.kt
@@ -0,0 +1,127 @@
+package coffee.liz.ecs
+
+import kotlin.reflect.KClass
+
+/**
+ * World implementation that executes systems in dependency order using a DAG.
+ */
+class DAGWorld(systems: List<System>) : World {
+    private val entities = mutableSetOf<Entity>()
+    private val componentCache = mutableMapOf<KClass<out Component>, MutableSet<Entity>>()
+    private val systemExecutionOrder: List<System>
+    private var nextEntityId = 0
+
+    init {
+        systemExecutionOrder = buildExecutionOrder(systems)
+    }
+
+    override fun createEntity(): Entity {
+        val entity = Entity(nextEntityId++)
+        entities.add(entity)
+        return entity
+    }
+
+    override fun destroyEntity(entity: Entity) {
+        // Remove from all component caches
+        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()
+
+        // Start with entities that have the first component type
+        val firstType = componentTypes[0]
+        val candidates = componentCache[firstType] ?: return emptySet()
+
+        // Filter to entities that have all component types
+        return candidates.filter { entity ->
+            entity.hasAll(*componentTypes)
+        }.toSet()
+    }
+
+    override fun update(deltaTime: Float) {
+        // Update component cache based on current entity state
+        updateComponentCache()
+
+        // Execute systems in dependency order
+        systemExecutionOrder.forEach { system ->
+            system.update(this, deltaTime)
+        }
+    }
+
+    /**
+     * Rebuild the component cache based on current entity components.
+     * Call this after components have been added/removed from entities.
+     */
+    private fun updateComponentCache() {
+        componentCache.clear()
+        entities.forEach { entity ->
+            entity.componentTypes().forEach { componentType ->
+                componentCache.getOrPut(componentType) { mutableSetOf() }.add(entity)
+            }
+        }
+    }
+
+    /**
+     * Build a topologically sorted execution order from system dependencies.
+     * Uses Kahn's algorithm for topological sorting.
+     */
+    private fun buildExecutionOrder(systems: List<System>): List<System> {
+        if (systems.isEmpty()) return emptyList()
+
+        val systemMap = systems.associateBy { it::class }
+        val inDegree = mutableMapOf<KClass<out System>, Int>()
+        val adjacencyList = mutableMapOf<KClass<out System>, MutableSet<KClass<out System>>>()
+
+        // 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>>()
+        val result = mutableListOf<System>()
+
+        // Add all systems with no dependencies to queue
+        inDegree.forEach { (systemClass, degree) ->
+            if (degree == 0) {
+                queue.add(systemClass)
+            }
+        }
+
+        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)
+                }
+            }
+        }
+
+        // Check for cycles
+        if (result.size != systems.size) {
+            throw IllegalArgumentException("Circular dependency detected in systems")
+        }
+
+        return result
+    }
+}