Use iterative algorithm for mesecon.find_receptor_on, major performance improvement for large

Jeija · Jeija · commit d19e97595546 · 2014-11-22T17:12:48.000+01:00
circuits.
This also fixes a crash introduced with the previous commit that occured when placing a wire
crossing.
diff --git a/mesecons/internal.lua b/mesecons/internal.lua
@@ -39,7 +39,7 @@
 -- mesecon.is_power_off(pos)            --> Returns true if pos does not emit power in any way
 -- mesecon.turnon(pos, rulename)        --> Returns true  whatever there is at pos. Calls itself for connected nodes (if pos is a conductor) --> recursive, the rulename is the name of the input rule that caused calling turnon; Uses third parameter recdepth internally to determine how far away the current node is from the initial pos as it uses recursion
 -- mesecon.turnoff(pos, rulename)       --> Turns off whatever there is at pos. Calls itself for connected nodes (if pos is a conductor) --> recursive, the rulename is the name of the input rule that caused calling turnoff; Uses third parameter recdepth internally to determine how far away the current node is from the initial pos as it uses recursion
--- mesecon.connected_to_receptor(pos)   --> Returns true if pos is connected to a receptor directly or via conductors; calls itself if pos is a conductor --> recursive
+-- mesecon.connected_to_receptor(pos, link)   --> Returns true if pos is connected to a receptor directly or via conductors; calls itself if pos is a conductor --> recursive
 -- mesecon.rules_link(output, input, dug_outputrules) --> Returns true if outputposition + outputrules = inputposition and inputposition + inputrules = outputposition (if the two positions connect)
 -- mesecon.rules_link_anydir(outp., inp., d_outpr.)   --> Same as rules mesecon.rules_link but also returns true if output and input are swapped
 -- mesecon.is_powered(pos)              --> Returns true if pos is powered by a receptor or a conductor
@@ -179,8 +179,8 @@ end
 
 -- Activation:
 mesecon.queue:add_function("activate", function (pos, rulename)
-	node = minetest.get_node(pos)
-	effector = mesecon.get_effector(node.name)
+	local node = minetest.get_node(pos)
+	local effector = mesecon.get_effector(node.name)
 
 	if effector and effector.action_on then
 		effector.action_on(pos, node, rulename)
@@ -446,18 +446,18 @@ mesecon.queue:add_function("turnoff", function (pos, rulename, recdepth)
 end)
 
 
-function mesecon.connected_to_receptor(pos, rulename)
+function mesecon.connected_to_receptor(pos, link)
 	local node = minetest.get_node(pos)
 
 	-- Check if conductors around are connected
 	local rules = mesecon.get_any_inputrules(node)
 	if not rules then return false end
 
-	for _, rule in ipairs(mesecon.rule2meta(rulename, rules)) do
-		local rulenames = mesecon.rules_link_rule_all_inverted(pos, rule)
-		for _, rname in ipairs(rulenames) do
-			local np = mesecon.addPosRule(pos, rname)
-			if mesecon.find_receptor_on(np, {}, mesecon.invertRule(rname)) then
+	for _, rule in ipairs(mesecon.rule2meta(link, rules)) do
+		local links = mesecon.rules_link_rule_all_inverted(pos, rule)
+		for _, l in ipairs(links) do
+			local np = mesecon.addPosRule(pos, l)
+			if mesecon.find_receptor_on(np, mesecon.invertRule(l)) then
 				return true
 			end
 		end
@@ -466,49 +466,36 @@ function mesecon.connected_to_receptor(pos, rulename)
 	return false
 end
 
-function mesecon.find_receptor_on(pos, checked, rulename, recdepth)
-	recdepth = recdepth or 2
-	if (recdepth > STACK_SIZE) then return true end -- ignore request
-	local node = minetest.get_node(pos)
+function mesecon.find_receptor_on(pos, link)
+	local frontiers = {{pos = pos, link = link}}
+	local checked = {}
 
-	if mesecon.is_receptor_on(node.name) then
-		-- add current position to checked
-		table.insert(checked, {x=pos.x, y=pos.y, z=pos.z})
-		return true
-	end
+	-- List of positions that have been searched for onstate receptors
+	local depth = 1
+	while frontiers[depth] do
+		local f = frontiers[depth]
+		local node = minetest.get_node_or_nil(f.pos)
 
-	if mesecon.is_conductor(node.name) then
-		local rules = mesecon.conductor_get_rules(node)
-		local metaindex = mesecon.rule2metaindex(rulename, rules)
-		-- find out if node has already been checked (to prevent from endless loop)
-		for _, cp in ipairs(checked) do
-			if mesecon.cmpPos(cp, pos) and cp.metaindex == metaindex then
-				return false, checked
-			end
-		end
-		-- add current position to checked
-		table.insert(checked, {x=pos.x, y=pos.y, z=pos.z, metaindex = metaindex})
-		for _, rule in ipairs(mesecon.rule2meta(rulename, rules)) do
-			local rulenames = mesecon.rules_link_rule_all_inverted(pos, rule)
-			for _, rname in ipairs(rulenames) do
-				local np = mesecon.addPosRule(pos, rname)
-				if mesecon.find_receptor_on(np, checked, mesecon.invertRule(rname),
-					recdepth + 1) then
-					return true
+		if mesecon.is_receptor_on(node.name) then return true end
+		if mesecon.is_conductor_on(node, f.link) then
+			local rules = mesecon.conductor_get_rules(node)
+
+			-- call turnoff on neighbors: normal rules
+			for _, r in ipairs(mesecon.rule2meta(f.link, rules)) do
+				local np = mesecon.addPosRule(f.pos, r)
+
+				local links = mesecon.rules_link_rule_all_inverted(f.pos, r)
+				for _, l in ipairs(links) do
+					if not checked[f.pos.x .. f.pos.y .. f.pos.z] then
+						table.insert(frontiers, {pos = np, link = l})
+						checked[f.pos.x .. f.pos.y .. f.pos.z] = true
+					end
 				end
 			end
+			
 		end
-	else
-		-- find out if node has already been checked (to prevent from endless loop)
-		for _, cp in ipairs(checked) do
-			if mesecon.cmpPos(cp, pos) then
-				return false, checked
-			end
-		end
-		table.insert(checked, {x=pos.x, y=pos.y, z=pos.z})
+		depth = depth + 1
 	end
-
-	return false
 end
 
 function mesecon.rules_link(output, input, dug_outputrules) --output/input are positions (outputrules optional, used if node has been dug), second return value: the name of the affected input rule
@@ -551,7 +538,7 @@ function mesecon.rules_link_rule_all(output, rule)
 		if  mesecon.cmpPos(mesecon.addPosRule(input, inputrule), output) then
 			if inputrule.sx == nil or rule.sx == nil
 			or mesecon.cmpSpecial(inputrule, rule) then
-				rules[#rules+1] = inputrule
+				table.insert(rules, inputrule)
 			end
 		end
 	end
@@ -572,7 +559,7 @@ function mesecon.rules_link_rule_all_inverted(input, rule)
 		if  mesecon.cmpPos(mesecon.addPosRule(output, outputrule), input) then
 			if outputrule.sx == nil or rule.sx == nil
 			or mesecon.cmpSpecial(outputrule, rule) then
-				rules[#rules+1] = mesecon.invertRule(outputrule)
+				table.insert(rules, mesecon.invertRule(outputrule))
 			end
 		end
 	end
diff --git a/mesecons/presets.lua b/mesecons/presets.lua
@@ -15,8 +15,7 @@ mesecon.rules.default =
  {x=0,  y=1,  z=-1},
  {x=0,  y=-1, z=-1}}
 
-mesecon.rules.pplate = {{x=0, y=-2, z=0}}
-mesecon.mergetable(mesecon.rules.default, mesecon.rules.pplate)
+mesecon.rules.pplate = mesecon.mergetable(mesecon.rules.default, {{x=0, y=-2, z=0}})
 
 mesecon.rules.buttonlike =
 {{x = 1,  y = 0, z = 0},
diff --git a/mesecons/util.lua b/mesecons/util.lua
@@ -196,20 +196,23 @@ end
 
 -- does not overwrite values; number keys (ipairs) are appended, not overwritten
 mesecon.mergetable = function(source, dest)
+	local rval = mesecon.tablecopy(dest)
+
 	for k, v in pairs(source) do
-		dest[k] = dest[k] or v
+		rval[k] = dest[k] or mesecon.tablecopy(v)
 	end
-
 	for i, v in ipairs(source) do
-		table.insert(dest, v)
+		table.insert(rval, mesecon.tablecopy(v))
 	end
+
+	return rval
 end
 
 mesecon.register_node = function(name, spec_common, spec_off, spec_on)
 	spec_common.drop = spec_common.drop or name .. "_off"
 
-	mesecon.mergetable(spec_common, spec_on);
-	mesecon.mergetable(spec_common, spec_off);
+	spec_on = mesecon.mergetable(spec_common, spec_on);
+	spec_off = mesecon.mergetable(spec_common, spec_off);
 
 	minetest.register_node(name .. "_on", spec_on)
 	minetest.register_node(name .. "_off", spec_off)
diff --git a/mesecons/wires.lua b/mesecons/wires.lua
@@ -19,7 +19,7 @@ local wire_getconnect = function (from_pos, self_pos)
 			rules = mesecon.rules.default
 		else
 			rules = mesecon.get_any_inputrules(node) or {}
-			mesecon.mergetable(mesecon.get_any_outputrules(node) or {}, rules)
+			rules = mesecon.mergetable(mesecon.get_any_outputrules(node) or {}, rules)
 		end
 
 		for _, r in ipairs(mesecon.flattenrules(rules)) do
@@ -80,7 +80,7 @@ local update_on_place_dig = function (pos, node)
 		rules = mesecon.rules.default
 	else
 		rules = mesecon.get_any_inputrules(node) or {}
-		mesecon.mergetable(mesecon.get_any_outputrules(node) or {}, rules)
+		rules = mesecon.mergetable(mesecon.get_any_outputrules(node) or {}, rules)
 	end
 	if (not rules) then return end
 
