From b83bc2265b15a0a6ea17d743a406e6b725d2efa3 Mon Sep 17 00:00:00 2001 From: number Zero Date: Sun, 28 Jan 2018 01:49:39 +0300 Subject: Fix O(n^2) network traversal --- technic/machines/switching_station.lua | 24 +++++++++++++++--------- 1 file changed, 15 insertions(+), 9 deletions(-) diff --git a/technic/machines/switching_station.lua b/technic/machines/switching_station.lua index 86df293..18ce654 100644 --- a/technic/machines/switching_station.lua +++ b/technic/machines/switching_station.lua @@ -91,19 +91,22 @@ minetest.register_node("technic:switching_station",{ -------------------------------------------------- -- Functions to traverse the electrical network -------------------------------------------------- +local function flatten(map) + local list = {} + for key, value in map do + list[#list + 1] = value + end + return list +end -- Add a wire node to the LV/MV/HV network local add_new_cable_node = function(nodes, pos, network_id) - technic.cables[minetest.hash_node_position(pos)] = network_id - -- Ignore if the node has already been added - for i = 1, #nodes do - if pos.x == nodes[i].x and - pos.y == nodes[i].y and - pos.z == nodes[i].z then - return false - end + local node_id = minetest.hash_node_position(pos) + technic.cables[node_id] = network_id + if nodes[node_id] then + return false end - table.insert(nodes, {x=pos.x, y=pos.y, z=pos.z, visited=1}) + nodes[node_id] = pos return true end @@ -188,6 +191,9 @@ local get_network = function(sw_pos, pos1, tier) i, technic.machines[tier], tier, sw_pos, network_id) i = i + 1 until all_nodes[i] == nil + PR_nodes = flatten(PR_nodes) + BA_nodes = flatten(BA_nodes) + RE_nodes = flatten(BA_nodes) technic.networks[network_id] = {tier = tier, PR_nodes = PR_nodes, RE_nodes = RE_nodes, BA_nodes = BA_nodes} return PR_nodes, BA_nodes, RE_nodes end -- cgit v1.2.3