Fix O(n^2) network traversal

number Zero

2018-01-27 86fb981b445bc63d564f7903a9a0d48b87a12763

Fix O(n^2) network traversal

 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