refactor systems to use cleaner dependency resolution

1 files changed, 105 insertions, 31 deletions

diff --git a/honey/ecs/ecs.lua b/honey/ecs/ecs.lua
index dda99cb..d7eb4ac 100644
--- a/honey/ecs/ecs.lua
+++ b/honey/ecs/ecs.lua
@@ -1,6 +1,6 @@
 math.randomseed(os.time())
 
-local glm = require 'honey.glm'
+local testing, glm = pcall(require, 'honey.glm')
 
 local module = {}
 setmetatable(module, {__index=_G})
@@ -87,9 +87,11 @@ function EntityDb.load(self, filename)
 			self:createEntity(id)
 			self:addComponents(id, components)
 		end,
-		Vec3 = glm.Vec3,
-		Mat4 = glm.Mat4,
 	}
+	if not testing then
+		env.Vec3 = glm.Vec3
+		env.Mat4 = glm.Mat4
+	end
 	local f, err = loadfile(filename)
 	if not f then error(err) end
 	setfenv(f, env)
@@ -209,6 +211,35 @@ function EntityDb.deleteEntity(self, id)
 end
 
 
+--===== Systems =====--
+
+System = {}
+System.__index = System
+
+function System.new(_, name, f)
+	local self = {
+		name = name,
+		f = f,
+		dependencies = {},
+	}
+	setmetatable(self, System)
+	return self
+end
+setmetatable(System, {__call=System.new})
+
+function System.addDependency(self, system)
+	self.dependencies[system.name] = true
+	return self
+end
+
+function System.addDependencies(self, systems)
+	for _, system in ipairs(systems) do
+		self:addDependency(system)
+	end
+	return self
+end
+
+
 --===== SystemDb =====--
 
 SystemDb = {}
@@ -218,7 +249,9 @@ SystemDb.__index = SystemDb
 function SystemDb.new(_, entityDb)
 	local self = {
 		systems = {},
-		sorted = {},
+		params = {},
+		sort = {},
+		dangling = {},
 		entityDb = entityDb,
 	}
 	setmetatable(self, SystemDb)
@@ -227,49 +260,90 @@ end
 setmetatable(SystemDb, {__call=SystemDb.new})
 
 
-local function systemId()
-	local template = "xx:xx:xx"
-	return string.gsub(template, "x", function(c)
-		return string.format("%x", random(0, 0xf))
-	end)
-end
+-- depth-first topological sort
+-- thank god for wikipedia
+local function tsort(systems)
+	local graph = {}
+	local count = 0
+	for _, system in pairs(systems) do
+		graph[system.name] = { name=system.name, dependencies=system.dependencies, tmark=false, pmark=false }
+		count = count+1
+	end
 
+	local sort = {}
+	local dangling = {}
 
-function SystemDb.addSystem(self, systemFunc, params)
-	local system
-	if type(systemFunc) == "table" then
-		system = systemFunc
-	else
-		local params = params or {}
-		params.db = self.entityDb
-		system = systemFunc(params)
+	local visit
+	visit = function(node)
+		if node == nil then
+			-- dangling dependency, ignore for now
+			return true
+		end
+		if node.pmark then return false end
+		if node.tmark then error("dependency cycle detected") end
+
+		node.tmark = true
+
+		for name in pairs(node.dependencies) do
+			local dangle = visit(graph[name])
+			if dangle then
+				dangling[name] = true
+			end
+		end
+
+		node.tmark = false
+		node.pmark = true
+		count = count-1
+		table.insert(sort, node.name)
 	end
 
-	local id = systemId()
-	self.systems[id] = system
-	table.insert(self.sorted, id)
-	self:sort()
-	return id
+	for _, node in pairs(graph) do
+		visit(node)
+		if count == 0 then break end
+	end
+
+	return sort, dangling
 end
 
 
-function SystemDb.sort(self)
-	table.sort(self.sorted, function(a, b) return (self.systems[a].priority or 100) < (self.systems[b].priority or 100) end)
+function SystemDb.addSystems(self, systems, params)
+	for _, system in ipairs(systems) do
+		self.systems[system.name] = system
+		self.params[system.name] = params
+	end
+	self.sort, self.dangling = tsort(self.systems)
+	return self
 end
 
 
 function SystemDb.update(self, dt)
-	for _, system in ipairs(self.sorted) do
-		self.systems[system]:update(dt)
+	-- check for dangling dependencies
+	local dangle = ""
+	for dependency in pairs(self.dangling) do
+		print(dependency)
+		dangle = dangle .. string.format(
+			"unresolved dangling dependency: %s\n",
+			dependency
+		)
+	end
+	if dangle ~= "" then
+		error(dangle)
+	end
+
+
+	for _, name in ipairs(self.sort) do
+		local system = self.systems[name]
+		local params = self.params[name]
+		system.f(self.db, dt, params)
 	end
 end
 
 
-function SystemDb.removeSystem(self, id)
-	self.systems[id] = nil
-	for i=#self.sorted,1,-1 do
-		if self.sorted[i] == id then table.remove(self.sorted, i) end
+function SystemDb.removeSystems(self, systems)
+	for _, system in pairs(systems) do
+		self.systems[system.name] = nil
 	end
+	self.sort, self.dangling = tsort(self.systems)
 end