Supply.cpp

#include "Supply.h"

#include "EmpireManager.h"
#include "Empire.h"
#include "../universe/Universe.h"
#include "../universe/UniverseObject.h"
#include "../universe/System.h"
#include "../universe/Planet.h"
#include "../universe/Fleet.h"
#include "../universe/Enums.h"
#include "../universe/Predicates.h"
#include "../util/AppInterface.h"
#include "../util/Logger.h"

#include <boost/graph/connected_components.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

SupplyManager::SupplyManager() :
    m_supply_starlane_traversals(),
    m_supply_starlane_obstructed_traversals(),
    m_fleet_supplyable_system_ids(),
    m_resource_supply_groups()
{}

SupplyManager& SupplyManager::operator=(const SupplyManager& rhs) {
    m_supply_starlane_traversals =              rhs.m_supply_starlane_traversals;
    m_supply_starlane_obstructed_traversals =   rhs.m_supply_starlane_obstructed_traversals;
    m_fleet_supplyable_system_ids =             rhs.m_fleet_supplyable_system_ids;
    m_resource_supply_groups =                  rhs.m_resource_supply_groups;
    return *this;
}

namespace {
    static const std::set<int> EMPTY_INT_SET;
    static const std::set<std::set<int>> EMPTY_INT_SET_SET;
    static const std::set<std::pair<int, int>> EMPTY_INT_PAIR_SET;
    static const std::map<int, float> EMPTY_INT_FLOAT_MAP;
}

const std::map<int, std::set<std::pair<int, int>>>& SupplyManager::SupplyStarlaneTraversals() const
{ return m_supply_starlane_traversals; }

const std::set<std::pair<int, int>>& SupplyManager::SupplyStarlaneTraversals(int empire_id) const {
    auto it = m_supply_starlane_traversals.find(empire_id);
    if (it != m_supply_starlane_traversals.end())
        return it->second;
    return EMPTY_INT_PAIR_SET;
}

const std::map<int, std::set<std::pair<int, int>>>& SupplyManager::SupplyObstructedStarlaneTraversals() const
{ return m_supply_starlane_obstructed_traversals; }

const std::set<std::pair<int, int>>& SupplyManager::SupplyObstructedStarlaneTraversals(int empire_id) const {
    auto it = m_supply_starlane_obstructed_traversals.find(empire_id);
    if (it != m_supply_starlane_obstructed_traversals.end())
        return it->second;
    return EMPTY_INT_PAIR_SET;
}

const std::map<int, std::set<int>>& SupplyManager::FleetSupplyableSystemIDs() const
{ return m_fleet_supplyable_system_ids; }

const std::set<int>& SupplyManager::FleetSupplyableSystemIDs(int empire_id) const {
    auto it = m_fleet_supplyable_system_ids.find(empire_id);
    if (it != m_fleet_supplyable_system_ids.end())
        return it->second;
    return EMPTY_INT_SET;
}

std::set<int> SupplyManager::FleetSupplyableSystemIDs(int empire_id, bool include_allies) const {
    std::set<int> retval = FleetSupplyableSystemIDs(empire_id);
    if (!include_allies)
        return retval;

    // add supplyable systems of all allies
    for (auto empire_id_sys_id_set : m_fleet_supplyable_system_ids) {
        int other_empire_id = empire_id_sys_id_set.first;
        const std::set<int>& systems = empire_id_sys_id_set.second;
        if (systems.empty() || Empires().GetDiplomaticStatus(empire_id, other_empire_id) != DIPLO_ALLIED)
            continue;
        retval.insert(systems.begin(), systems.end());
    }
    return retval;
}

int SupplyManager::EmpireThatCanSupplyAt(int system_id) const {
    for (const auto& entry : m_fleet_supplyable_system_ids) {
        if (entry.second.count(system_id))
            return entry.first;
    }
    return ALL_EMPIRES;
}

const std::map<int, std::set<std::set<int>>>& SupplyManager::ResourceSupplyGroups() const
{ return m_resource_supply_groups; }

const std::set<std::set<int>>& SupplyManager::ResourceSupplyGroups(int empire_id) const {
    auto it = m_resource_supply_groups.find(empire_id);
    if (it != m_resource_supply_groups.end())
        return it->second;
    return EMPTY_INT_SET_SET;
}

const std::map<int, float>& SupplyManager::PropagatedSupplyRanges() const {
    std::cout << "BLAAAAH" << std::endl;
    return m_propagated_supply_ranges;
}

const std::map<int, float>& SupplyManager::PropagatedSupplyRanges(int empire_id) const
{
    auto emp_it = m_empire_propagated_supply_ranges.find(empire_id);
    if (emp_it == m_empire_propagated_supply_ranges.end())
        return EMPTY_INT_FLOAT_MAP;
    return emp_it->second;
}

const std::map<int, float>& SupplyManager::PropagatedSupplyDistances() const {
    std::cout << "GLAARB" << std::endl;
    return m_propagated_supply_distances;
}

const std::map<int, float>& SupplyManager::PropagatedSupplyDistances(int empire_id) const {
    auto emp_it = m_empire_propagated_supply_distances.find(empire_id);
    if (emp_it == m_empire_propagated_supply_distances.end())
        return EMPTY_INT_FLOAT_MAP;
    return emp_it->second;
}

bool SupplyManager::SystemHasFleetSupply(int system_id, int empire_id) const {
    if (system_id == INVALID_OBJECT_ID)
        return false;
    if (empire_id == ALL_EMPIRES)
        return false;
    auto it = m_fleet_supplyable_system_ids.find(empire_id);
    if (it == m_fleet_supplyable_system_ids.end())
        return false;
    const std::set<int>& sys_set = it->second;
    if (sys_set.count(system_id))
        return true;
    return false;
}

bool SupplyManager::SystemHasFleetSupply(int system_id, int empire_id, bool include_allies) const {
    if (!include_allies)
        return SystemHasFleetSupply(system_id, empire_id);
    if (system_id == INVALID_OBJECT_ID)
        return false;
    if (empire_id == ALL_EMPIRES)
        return false;

    std::set<int> empire_ids = Empires().GetEmpireIDsWithDiplomaticStatusWithEmpire(empire_id, DIPLO_ALLIED);
    empire_ids.insert(empire_id);

    for (auto id : empire_ids) {
        auto sys_set_it = m_fleet_supplyable_system_ids.find(id);
        if (sys_set_it == m_fleet_supplyable_system_ids.end())
            continue;
        auto sys_set = sys_set_it->second;
        if (sys_set.count(system_id))
            return true;
    }

    return false;
}

std::string SupplyManager::Dump(int empire_id) const {
    std::string retval;

    try {
        for (const auto& empire_supply : m_fleet_supplyable_system_ids) {
            if (empire_id != ALL_EMPIRES && empire_supply.first != empire_id)
                continue;
            retval += "Supplyable systems for empire " + std::to_string(empire_supply.first) + "\n";
            for (int system_id : empire_supply.second) {
                auto sys = GetSystem(system_id);
                if (!sys)
                    continue;
                retval += "\n" + sys->PublicName(empire_id) + " (" + std::to_string(sys->ID()) + ") ";

                retval += "\nTraversals from here to: ";

                for (const auto& trav : m_supply_starlane_traversals.at(empire_supply.first)) {
                    if (trav.first == sys->ID()) {
                        auto obj = GetUniverseObject(trav.second);
                        if (obj)
                            retval += obj->PublicName(empire_id) + " (" + std::to_string(obj->ID()) + ")  ";
                    }
                }
                retval += "\n";

                retval += "Traversals to here from: ";
                for (const auto& trav : m_supply_starlane_traversals.at(empire_supply.first)) {
                    if (trav.second == sys->ID()) {
                        auto obj = GetUniverseObject(trav.first);
                        if (obj)
                            retval += obj->PublicName(empire_id) + " (" + std::to_string(obj->ID()) + ")  ";
                    }
                }
                retval += "\n";

                retval += "Blocked Traversals from here to: ";
                for (const auto& trav : m_supply_starlane_obstructed_traversals.at(empire_supply.first)) {
                    if (trav.first == sys->ID()) {
                        auto obj = GetUniverseObject(trav.second);
                        if (obj)
                            retval += obj->PublicName(empire_id) + " (" + std::to_string(obj->ID()) + ")  ";
                    }
                }
                retval += "\n";

                retval += "Blocked Traversals to here from: ";
                for (const auto& trav : m_supply_starlane_obstructed_traversals.at(empire_supply.first)) {
                    if (trav.second == sys->ID()) {
                        auto obj = GetUniverseObject(trav.first);
                        if (obj)
                            retval += obj->PublicName(empire_id) + " (" + std::to_string(obj->ID()) + ")  ";
                    }
                }
                retval += "\n";

            }
            retval += "\n\n";
        }

        for (const auto& empire_supply : m_resource_supply_groups) {
            retval += "Supply groups for empire " + std::to_string(empire_supply.first) + "\n";
            for (const auto& system_group : empire_supply.second) {
                retval += "group: ";
                for (int system_id : system_group) {
                    auto sys = GetSystem(system_id);
                    if (!sys)
                        continue;
                    retval += "\n" + sys->PublicName(empire_id) + " (" + std::to_string(sys->ID()) + ") ";
                }
                retval += "\n";
            }
            retval += "\n\n";
        }
    } catch (const std::exception& e) {
        ErrorLogger() << "SupplyManager::Dump caught exception: " << e.what();
    }

    return retval;
}

namespace {
    std::pair<float, float> EmpireTotalSupplyRangeSumInSystem(int empire_id, int system_id) {
        if (empire_id == ALL_EMPIRES || system_id == INVALID_OBJECT_ID)
            return {0.0f, 0.0f};
        const auto sys = GetSystem(system_id);
        if (!sys)
            return {0.0f, 0.0f};

        float accumulator_current = 0.0f;
        float accumulator_max = 0.0f;

        for (auto obj : Objects().FindObjects(sys->ObjectIDs())) {
            if (!obj || !obj->OwnedBy(empire_id))
                continue;
            if (obj->Meters().count(METER_SUPPLY) > 0)
                accumulator_current += obj->CurrentMeterValue(METER_SUPPLY);
            if (obj->Meters().count(METER_MAX_SUPPLY) > 0)
                accumulator_max += obj->CurrentMeterValue(METER_MAX_SUPPLY);
        }
        return {accumulator_current, accumulator_max};
    }

    float EmpireTotalSupplyRange(int empire_id) {
        if (empire_id == ALL_EMPIRES)
            return 0.0f;

        float accumulator_current = 0.0f;

        for (auto obj : Objects().FindObjects(OwnedVisitor<UniverseObject>(empire_id))) {
            if (!obj || !obj->OwnedBy(empire_id))
                continue;
            if (obj->Meters().count(METER_SUPPLY) > 0)
                accumulator_current += obj->CurrentMeterValue(METER_SUPPLY);
        }
        return accumulator_current;
    }

    float DistanceBetweenObjects(int obj1_id, int obj2_id) {
        auto obj1 = GetSystem(obj1_id);
        if (!obj1)
            return 0.0f;
        auto obj2 = GetSystem(obj2_id);
        if (!obj2)
            return 0.0f;
        double dx = obj2->X() - obj1->X();
        double dy = obj2->Y() - obj1->Y();
        return static_cast<float>(std::sqrt(dx*dx + dy*dy));
    }
}

void SupplyManager::Update() {
    m_supply_starlane_traversals.clear();
    m_supply_starlane_obstructed_traversals.clear();
    m_fleet_supplyable_system_ids.clear();
    m_resource_supply_groups.clear();
    m_propagated_supply_ranges.clear();

    // for each empire, need to get a set of sets of systems that can exchange
    // resources.  some sets may be just one system, in which resources can be
    // exchanged between UniverseObjects producing or consuming them, but which
    // can't exchange with any other systems.

    // which systems can share resources depends on system supply ranges, which
    // systems have obstructions to supply propagation for reach empire, and
    // the ranges and obstructions of other empires' supply, as only one empire
    // can supply each system or propagate along each starlane. one empire's
    // propagating supply can push back another's, if the pusher's range is
    // larger.

    // map from empire id to map from system id to range (in starlane jumps)
    // that supply can be propagated out of that system by that empire.
    std::map<int, std::map<int, float>> empire_system_supply_ranges;
    // map from empire id to which systems are obstructed for it for supply
    // propagation
    std::map<int, std::set<int>> empire_supply_unobstructed_systems;
    // map from empire id to map from system id to pair of sum of supply source
    // ranges and max ranges of objects owned by empire in that in system
    std::map<int, std::map<int, std::pair<float, float>>> empire_system_supply_range_sums;
    // map from empire id to total supply range sum of objects it owns
    std::map<int, float> empire_total_supply_range_sums;

    for (const auto& entry : Empires()) {
        const Empire* empire = entry.second;
        empire_system_supply_ranges[entry.first] = empire->SystemSupplyRanges();
        empire_supply_unobstructed_systems[entry.first] = empire->SupplyUnobstructedSystems();

        //std::stringstream ss;
        //for (int system_id : empire_supply_unobstructed_systems[entry.first])
        //{ ss << system_id << ", "; }
        //DebugLogger() << "Empire " << empire->EmpireID() << " unobstructed systems: " << ss.str();
    }
    for (auto empire_id_pair : empire_system_supply_ranges) {
        for (auto sys_id_pair : empire_id_pair.second) {
            empire_system_supply_range_sums[empire_id_pair.first][sys_id_pair.first] =
                EmpireTotalSupplyRangeSumInSystem(empire_id_pair.first, sys_id_pair.first);
        }
        empire_total_supply_range_sums[empire_id_pair.first] = EmpireTotalSupplyRange(empire_id_pair.first);
    }


    /////
    // probably temporary: additional restriction here for supply propagation
    // but not for general system obstruction as determind within Empire::UpdateSupplyUnobstructedSystems
    /////
    const auto fleets = GetUniverse().Objects().FindObjects<Fleet>();

    for (const auto& entry : Empires()) {
        int empire_id = entry.first;
        const auto& known_destroyed_objects = GetUniverse().EmpireKnownDestroyedObjectIDs(empire_id);
        std::set<int> systems_containing_friendly_fleets;

        for (auto& fleet : fleets) {
            int system_id = fleet->SystemID();
            if (system_id == INVALID_OBJECT_ID || known_destroyed_objects.count(fleet->ID()))
                continue;

            if (fleet->HasArmedShips() && fleet->Aggressive()) {
                if (fleet->OwnedBy(empire_id)) {
                    if (fleet->NextSystemID() == INVALID_OBJECT_ID || fleet->NextSystemID() == fleet->SystemID()) {
                        systems_containing_friendly_fleets.insert(system_id);
                    }
                }
            }
        }

        std::set<int> systems_where_others_have_supply_sources_and_current_empire_doesnt;
        // add all systems where others have supply
        for (auto& empire_supply : empire_system_supply_ranges) {
            if (empire_supply.first == empire_id || empire_supply.first == ALL_EMPIRES)
                continue;

            for (const auto& supply_range : empire_supply.second) {
                if (supply_range.second <= 0.0f)
                    continue;
                systems_where_others_have_supply_sources_and_current_empire_doesnt.insert(supply_range.first);
            }
        }
        // remove systems were this empire has supply
        auto it = empire_system_supply_ranges.find(empire_id);
        if (it != empire_system_supply_ranges.end()) {
            for (const auto& supply_range : it->second) {
                if (supply_range.second <= 0.0f)
                    continue;
                systems_where_others_have_supply_sources_and_current_empire_doesnt.erase(supply_range.first);
            }
        }

        // for systems where others have supply sources and this empire doesn't
        // and where this empire has no fleets...
        // supply is obstructed
        for (int system_id : systems_where_others_have_supply_sources_and_current_empire_doesnt) {
            if (!systems_containing_friendly_fleets.count(system_id))
                empire_supply_unobstructed_systems[empire_id].erase(system_id);
        }
    }
    /////
    // end probably temporary...
    /////


    // system connections each empire can see / use for supply propagation
    std::map<int, std::map<int, std::set<int>>> empire_visible_starlanes;
    for (auto& entry : Empires()) {
        const Empire* empire = entry.second;
        empire_visible_starlanes[entry.first] = empire->KnownStarlanes();//  VisibleStarlanes();
    }

    std::set<int> systems_with_supply_in_them;

    // store (supply range in jumps, and distance to supply source) of all
    // unobstructed systems before propagation, and add to list of systems
    // to propagate from.
    std::map<int, std::map<int, std::pair<float, float>>> empire_propagating_supply_ranges;
    float max_range = 0.0f;

    for (const auto& empire_supply : empire_system_supply_ranges) {
        int empire_id = empire_supply.first;
        const std::set<int>& unobstructed_systems = empire_supply_unobstructed_systems[empire_id];

        for (const auto& supply_range : empire_supply.second) {
            int system_id = supply_range.first;
            if (unobstructed_systems.count(system_id)) {
                // stored: first -> source supply range.  second -> distance to source (0 for the source itself)
                empire_propagating_supply_ranges[empire_id][system_id] = {supply_range.second, 0.0f};
                if (supply_range.second > max_range)
                    max_range = supply_range.second;
                systems_with_supply_in_them.insert(system_id);
            }
        }
    }


    // spread supply out from sources by "diffusion" like process, along unobstructed
    // starlanes, until the range is exhausted.
    for (float range_to_spread = max_range; range_to_spread >= 0;
         range_to_spread -= 1.0f)
    {
        //DebugLogger() << "!!!! Reduced spreading range to " << range_to_spread;

        // update systems that have supply in them
        for (const auto& empire_supply : empire_propagating_supply_ranges) {
            for (const auto& supply_range : empire_supply.second)
            { systems_with_supply_in_them.insert(supply_range.first); }
        }


        // resolve supply fights between multiple empires in one system.
        // pass over all empire-supplied systems, removing supply for all
        // but the empire with the highest supply range in each system
        for (int sys_id : systems_with_supply_in_them) {
            // sort empires by range in this system
            std::map<float, std::set<int>> empire_ranges_here;
            for (auto& empire_supply : empire_propagating_supply_ranges) {
                int empire_id = empire_supply.first;
                auto empire_supply_it = empire_supply.second.find(sys_id);
                // does this empire have any range in this system? if so, store it
                if (empire_supply_it == empire_supply.second.end())
                    continue;

                // stuff to break ties...
                float bonus = 0.0f;

                // empires with planets in system
                bool has_outpost = false, has_colony = false;
                if (auto sys = GetSystem(sys_id)) {
                    std::vector<int> obj_ids;
                    std::copy(sys->ContainedObjectIDs().begin(), sys->ContainedObjectIDs().end(), std::back_inserter(obj_ids));
                    for (auto& obj : Objects().FindObjects(obj_ids)) {
                        if (!obj)
                            continue;
                        if (!obj->OwnedBy(empire_id))
                            continue;
                        if (obj->ObjectType() == OBJ_PLANET) {
                            if (auto planet = std::dynamic_pointer_cast<Planet>(obj)) {
                                if (!planet->SpeciesName().empty())
                                    has_colony = true;
                                else
                                    has_outpost = true;
                                continue;
                            }
                        }
                    }
                }
                if (has_colony)
                    bonus += 0.5f;
                else if (has_outpost)
                    bonus += 0.3f;

                // sum of all supply sources in this system
                bonus += empire_system_supply_range_sums[empire_id][sys_id].first / 1000.0f;
                // sum of max supply of sourses in this system
                bonus += empire_system_supply_range_sums[empire_id][sys_id].second / 100000.0f;
                bonus += empire_total_supply_range_sums[empire_id] / 100000000.0f;

                // distance to supply source from here
                float propagated_distance_to_supply_source = std::max(1.0f, empire_supply_it->second.second);
                bonus += propagated_distance_to_supply_source / 10000.0f;

                // store ids of empires indexed by adjusted propgated range, in order to sort by range
                float propagated_range = empire_supply_it->second.first;
                empire_ranges_here[propagated_range + bonus].insert(empire_id);
            }

            if (empire_ranges_here.empty())
                continue;   // no empire has supply here?
            if (empire_ranges_here.size() == 1 && empire_ranges_here.begin()->second.size() < 2)
                continue;   // only one empire has supply here

            // at least two empires have supply sources here...
            // check if one is stronger

            // remove supply for all empires except the top-ranged empire here,
            // or one of the empires at the top if all top empires are allies
            auto range_empire_it = empire_ranges_here.rbegin();
            int top_range_empire_id = ALL_EMPIRES;
            if (range_empire_it->second.size() == 1) {
                // if just one empire has the most range, it is the top empire
                top_range_empire_id = *(range_empire_it->second.begin());
            } else {
                // if all empires that share the top range are allies, pick one
                // to be the top empire
                const auto& top_empires = range_empire_it->second;
                bool any_non_allied_pair = false;
                for (auto id1 : top_empires) {
                    if (id1 == ALL_EMPIRES) continue;
                    for (auto id2 : top_empires) {
                        if (id2 == ALL_EMPIRES || id2 <= id1) continue;
                        if (Empires().GetDiplomaticStatus(id1, id2) != DIPLO_ALLIED) {
                            any_non_allied_pair = true;
                            break;
                        }
                    }
                }
                if (!any_non_allied_pair) {
                    // arbitrarily pick the lowest ID empire
                    top_range_empire_id = *(range_empire_it->second.begin());
                }
            }
            //DebugLogger() << "top ranged empire here: " << top_range_empire_id;


            // remove range entries and traversals for all but the top empire
            // (or all empires if there is no single top empire)
            for (auto& empire_supply : empire_propagating_supply_ranges) {
                int empire_id = empire_supply.first;
                if (empire_id == top_range_empire_id)
                    continue;   // this is the top empire, so leave as the sole empire supplying here

                // remove from range entry...
                auto& empire_ranges = empire_supply.second;
                empire_ranges.erase(sys_id);

                //DebugLogger() << "... removed empire " << empire_id << " system " << sys_id << " supply.";

                // Remove from unobstructed systems
                empire_supply_unobstructed_systems[empire_id].erase(sys_id);

                auto& lane_traversals = m_supply_starlane_traversals[empire_id];
                auto lane_traversals_initial = lane_traversals;
                auto& obstructed_traversals = m_supply_starlane_obstructed_traversals[empire_id];
                auto obstrcuted_traversals_initial = obstructed_traversals;

                // remove from traversals departing from or going to this system for this empire,
                // and set any traversals going to this system as obstructed
                for (const auto& lane : lane_traversals_initial) {
                    if (lane.first == sys_id) {
                        lane_traversals.erase({sys_id, lane.second});
                    }
                    if (lane.second == sys_id) {
                        lane_traversals.erase({lane.first, sys_id});
                        obstructed_traversals.insert({lane.first, sys_id});
                    }
                }

                // remove obstructed traverals departing from this system
                for (const auto& lane : obstrcuted_traversals_initial) {
                    if (lane.first == sys_id)
                        obstructed_traversals.erase({lane.first, lane.second});
                }
            }

            //// DEBUG
            //DebugLogger() << "after culling empires ranges at system " << sys_id << ":";
            //for (auto& empire_supply : empire_propagating_supply_ranges) {
            //    auto& system_ranges = empire_supply.second;
            //    auto range_it = system_ranges.find(sys_id);
            //    if (range_it != system_ranges.end())
            //        DebugLogger() << empire_supply.first << " : " << range_it->second;
            //}
            //// END DEBUG
        }

        if (range_to_spread <= 0)
            break;

        // initialize next iteration with current supply distribution
        auto empire_propagating_supply_ranges_next = empire_propagating_supply_ranges;


        // for sources of supply of at least the minimum range for this
        // iteration that are in the current map, give adjacent systems one
        // less supply in the next iteration (unless as much or more is already
        // there)
        for (const auto& empire_supply : empire_propagating_supply_ranges) {
            int empire_id = empire_supply.first;
            //DebugLogger() << ">-< Doing supply propagation for empire " << empire_id << " >-<";
            const auto& prev_sys_ranges = empire_supply.second;
            const auto& unobstructed_systems = empire_supply_unobstructed_systems[empire_id];

            for (const auto& supply_range : empire_supply.second) {
                // does the source system have enough supply range to propagate outwards?
                float range = supply_range.second.first;
                if (range != range_to_spread)
                    continue;
                float range_after_one_more_jump = range - 1.0f; // what to set adjacent systems' ranges to (at least)

                // how far is this system from a source of supply for this empire?
                float distance_to_supply_source = supply_range.second.second;

                // what starlanes can be used to propagate supply?
                int system_id = supply_range.first;

                //DebugLogger() << "propagating from system " << system_id << " which has range: " << range << " and distance: " << distance_to_supply_source;

                // attempt to propagate to all adjacent systems...
                for (int lane_end_sys_id : empire_visible_starlanes[empire_id][system_id]) {
                    // is propagation to the adjacent system obstructed?
                    if (!unobstructed_systems.count(lane_end_sys_id)) {
                        // propagation obstructed!
                        //DebugLogger() << "Added obstructed traversal from " << system_id << " to " << lane_end_sys_id << " due to not being on unobstructed systems";
                        m_supply_starlane_obstructed_traversals[empire_id].insert({system_id, lane_end_sys_id});
                        continue;
                    }
                    // propagation not obstructed.


                    // does another empire already have as much or more supply here from a previous iteration?
                    float other_empire_biggest_range = -10000.0f;   // arbitrary big numbeer
                    for (const auto& other_empire_supply : empire_propagating_supply_ranges) {
                        int other_empire_id = other_empire_supply.first;
                        if (other_empire_id == empire_id)
                            continue;
                        const auto& prev_other_empire_sys_ranges = other_empire_supply.second;
                        auto prev_other_empire_range_it = prev_other_empire_sys_ranges.find(lane_end_sys_id);
                        if (prev_other_empire_range_it == prev_other_empire_sys_ranges.end())
                            continue;
                        if (prev_other_empire_range_it->second.first > other_empire_biggest_range)
                            other_empire_biggest_range = prev_other_empire_range_it->second.first;
                    }

                    // if so, add a blocked traversal and continue
                    if (range_after_one_more_jump <= other_empire_biggest_range) {
                        m_supply_starlane_obstructed_traversals[empire_id].insert({system_id, lane_end_sys_id});
                        //DebugLogger() << "Added obstructed traversal from " << system_id << " to " << lane_end_sys_id << " due to other empire biggest range being " << other_empire_biggest_range;
                        continue;
                    }

                    // otherwise, propagate into system...
                    float lane_length = DistanceBetweenObjects(system_id, lane_end_sys_id);
                    float distance_to_supply_source_after_next_lane = lane_length + distance_to_supply_source;

                    //DebugLogger() << "Attempting to propagate into system: " << lane_end_sys_id << " the new range: " << range_after_one_more_jump << " and distance: " << distance_to_supply_source_after_next_lane;

                    // if propagating supply would increase the range of the adjacent system,
                    // or decrease the distance to the adjacent system from a supply source...
                    auto prev_range_it = prev_sys_ranges.find(lane_end_sys_id);
                    if (prev_range_it == prev_sys_ranges.end()) {
                        empire_propagating_supply_ranges_next[empire_id][lane_end_sys_id] =
                            {range_after_one_more_jump, distance_to_supply_source_after_next_lane};
                        //DebugLogger() << " ... default case: no previous entry.";

                    } else {
                        //DebugLogger() << " ... previous entry values: " << prev_range_it->second.first << " and " << prev_range_it->second.second;

                        if (range_after_one_more_jump > prev_range_it->second.first) {
                            empire_propagating_supply_ranges_next[empire_id][lane_end_sys_id].first =
                                range_after_one_more_jump;
                            //DebugLogger() << " ... range increased!";
                        }
                        if (distance_to_supply_source_after_next_lane < prev_range_it->second.second) {
                            empire_propagating_supply_ranges_next[empire_id][lane_end_sys_id].second =
                                distance_to_supply_source_after_next_lane;
                            //DebugLogger() << " ... distance decreased!";
                        }
                    }
                    // always record a traversal, so connectivity is calculated properly
                    m_supply_starlane_traversals[empire_id].insert({system_id, lane_end_sys_id});
                    //DebugLogger() << "Added traversal from " << system_id << " to " << lane_end_sys_id;

                    // erase any previous obstructed traversal that just succeeded
                    if (m_supply_starlane_obstructed_traversals[empire_id].count({system_id, lane_end_sys_id}))
                    {
                        //DebugLogger() << "Removed obstructed traversal from " << system_id << " to " << lane_end_sys_id;
                        m_supply_starlane_obstructed_traversals[empire_id].erase({system_id, lane_end_sys_id});
                    }
                    if (m_supply_starlane_obstructed_traversals[empire_id].count({lane_end_sys_id, system_id}))
                    {
                        //DebugLogger() << "Removed obstructed traversal from " << lane_end_sys_id << " to " << system_id;
                        m_supply_starlane_obstructed_traversals[empire_id].erase({lane_end_sys_id, system_id});
                    }
                }
            }
        }

        // save propagated results for next iteration
        empire_propagating_supply_ranges = std::move(empire_propagating_supply_ranges_next);
    }

    //// DEBUG
    //DebugLogger() << "SuppolyManager::Update: after removing conflicts, empires can provide supply to the following system ids:";
    //for (auto& empire_supply : empire_propagating_supply_ranges) {
    //    int empire_id = empire_supply.first;
    //    std::stringstream ss;
    //    for (auto& supply_range : empire_supply.second) {
    //        ss << supply_range.first << " (" << supply_range.second << "),  ";
    //    }
    //    DebugLogger() << "empire: " << empire_id << ":  " << ss.str();
    //}
    //// END DEBUG

    // record which systems are fleet supplyable by each empire (after resolving conflicts in each system)
    for (const auto& empire_supply : empire_propagating_supply_ranges) {
        int empire_id = empire_supply.first;
        for (const auto& supply_range : empire_supply.second) {
            if (supply_range.second.first < 0.0f)
                continue;   // negative supply doesn't count... zero does (it just reaches)
            m_fleet_supplyable_system_ids[empire_id].insert(supply_range.first);

            // should be only one empire per system at this point, but use max just to be safe...
            m_propagated_supply_ranges[supply_range.first] =
                std::max(supply_range.second.first, m_propagated_supply_ranges[supply_range.first]);
            m_empire_propagated_supply_ranges[empire_id][supply_range.first] =
                m_propagated_supply_ranges[supply_range.first];

            // should be only one empire per system at this point, but use max just to be safe...
            m_propagated_supply_distances[supply_range.first] =
                std::max(supply_range.second.second, m_propagated_supply_distances[supply_range.first]);
            m_empire_propagated_supply_distances[empire_id][supply_range.first] =
                m_propagated_supply_distances[supply_range.first];
        }

        //DebugLogger() << "For empire: " << empire_id << " system supply distances: ";
        //for (auto entry : m_empire_propagated_supply_distances[empire_id]) {
        //    DebugLogger() << entry.first << " : " << entry.second;
        //}
    }



    auto ally_merged_supply_starlane_traversals = m_supply_starlane_traversals;

    // add connections into allied empire systems when their obstructed lane
    // traversals originate on either end of a starlane
    for (auto& empire_set : m_supply_starlane_obstructed_traversals) {
        // input:
        const auto& empire_obstructed_traversals = empire_set.second;
        // output:
        auto& empire_supply_traversals = ally_merged_supply_starlane_traversals[empire_set.first];


        std::set<int> allies_of_empire = Empires().GetEmpireIDsWithDiplomaticStatusWithEmpire(empire_set.first, DIPLO_ALLIED);
        for (int ally_id : allies_of_empire) {
            // input:
            auto const& ally_obstructed_traversals = m_supply_starlane_obstructed_traversals[ally_id];

            // find cases where outer loop empire has an obstructed traversal from A to B
            // and inner loop empire has an obstructed traversal from B to A
            for (auto const& empire_trav : empire_obstructed_traversals) {
                for (auto const& ally_trav : ally_obstructed_traversals) {
                    if (empire_trav.first == ally_trav.second && empire_trav.second == ally_trav.first) {
                        empire_supply_traversals.insert({empire_trav.first, empire_trav.second});
                        empire_supply_traversals.insert({empire_trav.second, empire_trav.first});
                    }
                }
            }
        }
    }

    // add allied supply starlane traversals to empires' traversals, so that
    // allies can use eachothers' supply networks
    for (auto& empire_set : ally_merged_supply_starlane_traversals) {
        auto& output_empire_traversals = empire_set.second;
        for (int ally_id : Empires().GetEmpireIDsWithDiplomaticStatusWithEmpire(empire_set.first, DIPLO_ALLIED)) {
            // copy ally traversals into the output empire traversals set
            for (const auto& traversal_pair : m_supply_starlane_traversals[ally_id])
                output_empire_traversals.insert(traversal_pair);
        }
    }

    // same for fleet supplyable system ids, as these are added to supplyable
    // groups in following code
    auto ally_merged_fleet_supplyable_system_ids = m_fleet_supplyable_system_ids;
    for (auto& empire_set : ally_merged_fleet_supplyable_system_ids) {
        std::set<int>& output_empire_ids = empire_set.second;
        for (int ally_id : Empires().GetEmpireIDsWithDiplomaticStatusWithEmpire(empire_set.first, DIPLO_ALLIED)) {
            // copy ally traversals into the output empire traversals set
            for (int sys_id : m_fleet_supplyable_system_ids[ally_id])
                output_empire_ids.insert(sys_id);
        }
    }



    // determine supply-connected groups of systems for each empire.
    // need to merge interconnected supply groups into as few sets of mutually-
    // supply-exchanging systems as possible.  This requires finding the
    // connected components of an undirected graph, where the node
    // adjacency are the directly-connected systems determined above.
    for (const auto& empire_supply : empire_propagating_supply_ranges) {
        int empire_id = empire_supply.first;

        // assemble all direct connections between systems from remaining traversals
        std::map<int, std::set<int>> supply_groups_map;
        for (auto const& lane : ally_merged_supply_starlane_traversals[empire_id]) {
            supply_groups_map[lane.first].insert(lane.second);
            supply_groups_map[lane.second].insert(lane.first);
        }

        // also add connections from all fleet-supplyable systems to themselves, so that
        // any fleet supply able system with no connection to another system can still
        // have resource sharing within tiself
        for (int system_id : ally_merged_fleet_supplyable_system_ids[empire_id])
            supply_groups_map[system_id].insert(system_id);


        if (supply_groups_map.empty())
            continue;

        //DebugLogger() << "Empire " << empire_id << " supply groups map:";
        //for (auto const& q : supply_groups_map) {
        //    int source_id = q.first;

        //    std::stringstream other_ids;
        //    for (auto const& r : q.second)
        //    { other_ids << r << ", "; }

        //    DebugLogger() << " ... src: " << source_id << " to: " << other_ids.str();
        //}


        // create graph
        boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> graph;

        // boost expects vertex labels to range from 0 to num vertices - 1, so need
        // to map from system id to graph id and back when accessing vertices
        std::vector<int> graph_id_to_sys_id;
        graph_id_to_sys_id.reserve(supply_groups_map.size());

        std::map<int, int> sys_id_to_graph_id;
        int graph_id = 0;
        for (auto& supply_group : supply_groups_map) {
            int sys_id = supply_group.first;
            boost::add_vertex(graph);   // should add with index = graph_id

            graph_id_to_sys_id.push_back(sys_id);
            sys_id_to_graph_id[sys_id] = graph_id;
            ++graph_id;
        }

        // add edges for all direct connections between systems
        // and add edges from fleet supplyable systems to themselves
        for (auto& supply_group : supply_groups_map) {
            int start_graph_id = sys_id_to_graph_id[supply_group.first];
            for (int system_id : supply_group.second) {
                int end_graph_id = sys_id_to_graph_id[system_id];
                boost::add_edge(start_graph_id, end_graph_id, graph);
            }
        }

        // declare storage and fill with the component id (group id of connected systems)
        // for each graph vertex
        std::vector<int> components(boost::num_vertices(graph));
        boost::connected_components(graph, &components[0]);

        // convert results back from graph id to system id, and into desired output format
        // output: std::map<int, std::set<std::set<int>>>& m_resource_supply_groups

        // first, sort into a map from component id to set of system ids in component
        std::map<int, std::set<int>> component_sets_map;
        for (std::size_t comp_graph_id = 0; comp_graph_id != components.size(); ++comp_graph_id) {
            int label = components[comp_graph_id];
            int sys_id = graph_id_to_sys_id[comp_graph_id];
            component_sets_map[label].insert(sys_id);
        }

        // copy sets in map into set of sets
        for (auto& component_set : component_sets_map)
            m_resource_supply_groups[empire_id].insert(component_set.second);
    }
}