From 3f75c06a3bf80a4c50ccb0991b3664c491c0d523 Mon Sep 17 00:00:00 2001
From: DS <vorunbekannt75@web.de>
Date: Thu, 25 Mar 2021 16:53:51 +0100
Subject: Improve performance of mesecon.turnon and mesecon.turnoff (#556)
---
mesecons/fifo_queue.lua | 62 +++++++++++++++++++++++++++++++++++++++++++++++++
mesecons/internal.lua | 48 ++++++++++++++++++++++++--------------
2 files changed, 93 insertions(+), 17 deletions(-)
create mode 100644 mesecons/fifo_queue.lua
diff --git a/mesecons/fifo_queue.lua b/mesecons/fifo_queue.lua
new file mode 100644
index 0000000..a71c71b
--- /dev/null
+++ b/mesecons/fifo_queue.lua
@@ -0,0 +1,62 @@
+
+-- a simple first-in-first-out queue
+-- very similar to the one in https://github.com/minetest/minetest/pull/7683
+
+local fifo_queue = {}
+
+local metatable = {__index = fifo_queue}
+
+-- creates a new empty queue
+function fifo_queue.new()
+ local q = {n_in = 0, n_out = 0, i_out = 1, buf_in = {}, buf_out = {}}
+ setmetatable(q, metatable)
+ return q
+end
+
+-- adds an element to the queue
+function fifo_queue.add(self, v)
+ local n = self.n_in + 1
+ self.n_in = n
+ self.buf_in[n] = v
+end
+
+-- removes and returns the next element, or nil of empty
+function fifo_queue.take(self)
+ local i_out = self.i_out
+ if i_out <= self.n_out then
+ local v = self.buf_out[i_out]
+ self.i_out = i_out + 1
+ self.buf_out[i_out] = true
+ return v
+ end
+
+ -- buf_out is empty, try to swap
+ self.i_out = 1
+ self.n_out = 0
+ if self.n_in == 0 then
+ return nil -- empty
+ end
+
+ -- swap
+ self.n_out = self.n_in
+ self.n_in = 0
+ self.buf_out, self.buf_in = self.buf_in, self.buf_out
+
+ local v = self.buf_out[1]
+ self.i_out = 2
+ self.buf_out[1] = true
+ return v
+end
+
+-- returns whether the queue is empty
+function fifo_queue.is_empty(self)
+ return self.n_out == self.i_out + 1 and self.n_in == 0
+end
+
+-- returns stuff for iteration in a for loop, like pairs
+-- adding new elements while iterating is no problem
+function fifo_queue.iter(self)
+ return fifo_queue.take, self, nil
+end
+
+return fifo_queue
diff --git a/mesecons/internal.lua b/mesecons/internal.lua
index 044e3bf..93eccf9 100644
--- a/mesecons/internal.lua
+++ b/mesecons/internal.lua
@@ -11,7 +11,7 @@
-- RECEPTORS
-- mesecon.is_receptor(nodename) --> Returns true if nodename is a receptor
--- mesecon.is_receptor_on(nodename --> Returns true if nodename is an receptor with state = mesecon.state.on
+-- mesecon.is_receptor_on(nodename) --> Returns true if nodename is an receptor with state = mesecon.state.on
-- mesecon.is_receptor_off(nodename) --> Returns true if nodename is an receptor with state = mesecon.state.off
-- mesecon.receptor_get_rules(node) --> Returns the rules of the receptor (mesecon.rules.default if none specified)
@@ -46,6 +46,8 @@
-- mesecon.rotate_rules_down(rules)
-- These functions return rules that have been rotated in the specific direction
+local fifo_queue = dofile(minetest.get_modpath("mesecons").."/fifo_queue.lua")
+
-- General
function mesecon.get_effector(nodename)
if minetest.registered_nodes[nodename]
@@ -371,32 +373,39 @@ end
-- Follow all all conductor paths replacing conductors that were already
-- looked at, activating / changing all effectors along the way.
function mesecon.turnon(pos, link)
- local frontiers = {{pos = pos, link = link}}
+ local frontiers = fifo_queue.new()
+ frontiers:add({pos = pos, link = link})
+ local pos_can_be_skipped = {}
local depth = 1
- while frontiers[1] do
- local f = table.remove(frontiers, 1)
+ for f in frontiers:iter() do
local node = mesecon.get_node_force(f.pos)
if not node then
-- Area does not exist; do nothing
+ pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
elseif mesecon.is_conductor_off(node, f.link) then
local rules = mesecon.conductor_get_rules(node)
-- Call turnon on neighbors
for _, r in ipairs(mesecon.rule2meta(f.link, rules)) do
local np = vector.add(f.pos, r)
- for _, l in ipairs(mesecon.rules_link_rule_all(f.pos, r)) do
- table.insert(frontiers, {pos = np, link = l})
+ if not pos_can_be_skipped[minetest.hash_node_position(np)] then
+ for _, l in ipairs(mesecon.rules_link_rule_all(f.pos, r)) do
+ frontiers:add({pos = np, link = l})
+ end
end
end
mesecon.swap_node_force(f.pos, mesecon.get_conductor_on(node, f.link))
+ pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
elseif mesecon.is_effector(node.name) then
mesecon.changesignal(f.pos, node, f.link, mesecon.state.on, depth)
if mesecon.is_effector_off(node.name) then
mesecon.activate(f.pos, node, f.link, depth)
end
+ else
+ pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
end
depth = depth + 1
end
@@ -419,37 +428,40 @@ end
-- depth = indicates order in which signals wire fired, higher is later
-- }
function mesecon.turnoff(pos, link)
- local frontiers = {{pos = pos, link = link}}
+ local frontiers = fifo_queue.new()
+ frontiers:add({pos = pos, link = link})
local signals = {}
+ local pos_can_be_skipped = {}
local depth = 1
- while frontiers[1] do
- local f = table.remove(frontiers, 1)
+ for f in frontiers:iter() do
local node = mesecon.get_node_force(f.pos)
if not node then
-- Area does not exist; do nothing
+ pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
elseif mesecon.is_conductor_on(node, f.link) then
local rules = mesecon.conductor_get_rules(node)
for _, r in ipairs(mesecon.rule2meta(f.link, rules)) do
local np = vector.add(f.pos, r)
- -- Check if an onstate receptor is connected. If that is the case,
- -- abort this turnoff process by returning false. `receptor_off` will
- -- discard all the changes that we made in the voxelmanip:
- for _, l in ipairs(mesecon.rules_link_rule_all_inverted(f.pos, r)) do
+ if not pos_can_be_skipped[minetest.hash_node_position(np)] then
+ -- Check if an onstate receptor is connected. If that is the case,
+ -- abort this turnoff process by returning false. `receptor_off` will
+ -- discard all the changes that we made in the voxelmanip:
if mesecon.is_receptor_on(mesecon.get_node_force(np).name) then
return false
end
- end
- -- Call turnoff on neighbors
- for _, l in ipairs(mesecon.rules_link_rule_all(f.pos, r)) do
- table.insert(frontiers, {pos = np, link = l})
+ -- Call turnoff on neighbors
+ for _, l in ipairs(mesecon.rules_link_rule_all(f.pos, r)) do
+ frontiers:add({pos = np, link = l})
+ end
end
end
mesecon.swap_node_force(f.pos, mesecon.get_conductor_off(node, f.link))
+ pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
elseif mesecon.is_effector(node.name) then
table.insert(signals, {
pos = f.pos,
@@ -457,6 +469,8 @@ function mesecon.turnoff(pos, link)
link = f.link,
depth = depth
})
+ else
+ pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
end
depth = depth + 1
end
--
cgit v1.2.3