Fix O(n^2) network traversal

number Zero

2018-01-27 86fb981b445bc63d564f7903a9a0d48b87a12763

 technic/machines/switching_station.lua

@@ -91,48 +91,57 @@
--------------------------------------------------
-- Functions to traverse the electrical network
--------------------------------------------------
local function flatten(map)
   local list = {}
   for key, value in pairs(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 function add_network_node(nodes, pos, network_id)
   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

local function add_cable_node(nodes, pos, network_id, queue)
   if add_network_node(nodes, pos, network_id) then
      queue[#queue + 1] = pos
   end
end

-- Generic function to add found connected nodes to the right classification array
local check_node_subp = function(PR_nodes, RE_nodes, BA_nodes, SP_nodes, all_nodes, pos, machines, tier, sw_pos, from_below, network_id)
local check_node_subp = function(PR_nodes, RE_nodes, BA_nodes, SP_nodes, all_nodes, pos, machines, tier, sw_pos, from_below, network_id, queue)
   technic.get_or_load_node(pos)
   local meta = minetest.get_meta(pos)
   local name = minetest.get_node(pos).name

   if technic.is_tier_cable(name, tier) then
      add_new_cable_node(all_nodes, pos,network_id)
      add_cable_node(all_nodes, pos,network_id, queue)
   elseif machines[name] then
      --dprint(name.." is a "..machines[name])
      meta:set_string(tier.."_network",minetest.pos_to_string(sw_pos))
      if     machines[name] == technic.producer then
         add_new_cable_node(PR_nodes, pos, network_id)
         add_network_node(PR_nodes, pos, network_id)
      elseif machines[name] == technic.receiver then
         add_new_cable_node(RE_nodes, pos, network_id)
         add_network_node(RE_nodes, pos, network_id)
      elseif machines[name] == technic.producer_receiver then
         add_new_cable_node(PR_nodes, pos, network_id)
         add_new_cable_node(RE_nodes, pos, network_id)
         add_network_node(PR_nodes, pos, network_id)
         add_network_node(RE_nodes, pos, network_id)
      elseif machines[name] == "SPECIAL" and
            (pos.x ~= sw_pos.x or pos.y ~= sw_pos.y or pos.z ~= sw_pos.z) and
            from_below then
         -- Another switching station -> disable it
         add_new_cable_node(SP_nodes, pos, network_id)
         add_network_node(SP_nodes, pos, network_id)
         meta:set_int("active", 0)
      elseif machines[name] == technic.battery then
         add_new_cable_node(BA_nodes, pos, network_id)
         add_network_node(BA_nodes, pos, network_id)
      end

      meta:set_int(tier.."_EU_timeout", 2) -- Touch node
@@ -140,8 +149,7 @@
end

-- Traverse a network given a list of machines and a cable type name
local traverse_network = function(PR_nodes, RE_nodes, BA_nodes, SP_nodes, all_nodes, i, machines, tier, sw_pos, network_id)
   local pos = all_nodes[i]
local traverse_network = function(PR_nodes, RE_nodes, BA_nodes, SP_nodes, all_nodes, pos, machines, tier, sw_pos, network_id, queue)
   local positions = {
      {x=pos.x+1, y=pos.y,   z=pos.z},
      {x=pos.x-1, y=pos.y,   z=pos.z},
@@ -149,9 +157,8 @@
      {x=pos.x,   y=pos.y-1, z=pos.z},
      {x=pos.x,   y=pos.y,   z=pos.z+1},
      {x=pos.x,   y=pos.y,   z=pos.z-1}}
   --print("ON")
   for i, cur_pos in pairs(positions) do
      check_node_subp(PR_nodes, RE_nodes, BA_nodes, SP_nodes, all_nodes, cur_pos, machines, tier, sw_pos, i == 3, network_id)
      check_node_subp(PR_nodes, RE_nodes, BA_nodes, SP_nodes, all_nodes, cur_pos, machines, tier, sw_pos, i == 3, network_id, queue)
   end
end

@@ -163,7 +170,8 @@
end

local get_network = function(sw_pos, pos1, tier)
   local cached = technic.networks[minetest.hash_node_position(pos1)]
   local network_id = minetest.hash_node_position(pos1)
   local cached = technic.networks[network_id]
   if cached and cached.tier == tier then
      touch_nodes(cached.PR_nodes, tier)
      touch_nodes(cached.BA_nodes, tier)
@@ -175,19 +183,28 @@
      end
      return cached.PR_nodes, cached.BA_nodes, cached.RE_nodes
   end
   local i = 1
   local PR_nodes = {}
   local BA_nodes = {}
   local RE_nodes = {}
   local SP_nodes = {}
   local all_nodes = {pos1}
   repeat
      traverse_network(PR_nodes, RE_nodes, BA_nodes, SP_nodes, all_nodes,
            i, technic.machines[tier], tier, sw_pos, minetest.hash_node_position(pos1))
      i = i + 1
   until all_nodes[i] == nil
   technic.networks[minetest.hash_node_position(pos1)] = {tier = tier, PR_nodes = PR_nodes,
         RE_nodes = RE_nodes, BA_nodes = BA_nodes, SP_nodes = SP_nodes, all_nodes = all_nodes}
   local all_nodes = {}
   local queue = {}
   add_cable_node(all_nodes, pos1, network_id, queue)
   while next(queue) do
      local to_visit = {}
      for _, pos in ipairs(queue) do
         traverse_network(PR_nodes, RE_nodes, BA_nodes, SP_nodes, all_nodes,
               pos, technic.machines[tier], tier, sw_pos, network_id, to_visit)
      end
      queue = to_visit
   end
   PR_nodes = flatten(PR_nodes)
   BA_nodes = flatten(BA_nodes)
   RE_nodes = flatten(RE_nodes)
   SP_nodes = flatten(SP_nodes)
   all_nodes = flatten(all_nodes)
   technic.networks[network_id] = {tier = tier, all_nodes = all_nodes, SP_nodes = SP_nodes,
         PR_nodes = PR_nodes, RE_nodes = RE_nodes, BA_nodes = BA_nodes}
   return PR_nodes, BA_nodes, RE_nodes
end