1 #include "Supply.h"
2
3 #include "EmpireManager.h"
4 #include "Empire.h"
5 #include "../universe/Universe.h"
6 #include "../universe/UniverseObject.h"
7 #include "../universe/System.h"
8 #include "../universe/Planet.h"
9 #include "../universe/Fleet.h"
10 #include "../universe/Enums.h"
11 #include "../universe/Predicates.h"
12 #include "../util/AppInterface.h"
13 #include "../util/Logger.h"
14
15 #include <boost/graph/connected_components.hpp>
16 #include <boost/graph/adjacency_list.hpp>
17 #include <boost/graph/connected_components.hpp>
18
19 namespace {
20 DeclareThreadSafeLogger(supply);
21 }
22
SupplyManager()23 SupplyManager::SupplyManager() :
24 m_supply_starlane_traversals(),
25 m_supply_starlane_obstructed_traversals(),
26 m_fleet_supplyable_system_ids(),
27 m_resource_supply_groups()
28 {}
29
operator =(const SupplyManager & rhs)30 SupplyManager& SupplyManager::operator=(const SupplyManager& rhs) {
31 m_supply_starlane_traversals = rhs.m_supply_starlane_traversals;
32 m_supply_starlane_obstructed_traversals = rhs.m_supply_starlane_obstructed_traversals;
33 m_fleet_supplyable_system_ids = rhs.m_fleet_supplyable_system_ids;
34 m_resource_supply_groups = rhs.m_resource_supply_groups;
35 return *this;
36 }
37
38 namespace {
39 static const std::set<int> EMPTY_INT_SET;
40 static const std::set<std::set<int>> EMPTY_INT_SET_SET;
41 static const std::set<std::pair<int, int>> EMPTY_INT_PAIR_SET;
42 static const std::map<int, float> EMPTY_INT_FLOAT_MAP;
43 }
44
SupplyStarlaneTraversals() const45 const std::map<int, std::set<std::pair<int, int>>>& SupplyManager::SupplyStarlaneTraversals() const
46 { return m_supply_starlane_traversals; }
47
SupplyStarlaneTraversals(int empire_id) const48 const std::set<std::pair<int, int>>& SupplyManager::SupplyStarlaneTraversals(int empire_id) const {
49 auto it = m_supply_starlane_traversals.find(empire_id);
50 if (it != m_supply_starlane_traversals.end())
51 return it->second;
52 return EMPTY_INT_PAIR_SET;
53 }
54
SupplyObstructedStarlaneTraversals() const55 const std::map<int, std::set<std::pair<int, int>>>& SupplyManager::SupplyObstructedStarlaneTraversals() const
56 { return m_supply_starlane_obstructed_traversals; }
57
SupplyObstructedStarlaneTraversals(int empire_id) const58 const std::set<std::pair<int, int>>& SupplyManager::SupplyObstructedStarlaneTraversals(int empire_id) const {
59 auto it = m_supply_starlane_obstructed_traversals.find(empire_id);
60 if (it != m_supply_starlane_obstructed_traversals.end())
61 return it->second;
62 return EMPTY_INT_PAIR_SET;
63 }
64
FleetSupplyableSystemIDs() const65 const std::map<int, std::set<int>>& SupplyManager::FleetSupplyableSystemIDs() const
66 { return m_fleet_supplyable_system_ids; }
67
FleetSupplyableSystemIDs(int empire_id) const68 const std::set<int>& SupplyManager::FleetSupplyableSystemIDs(int empire_id) const {
69 auto it = m_fleet_supplyable_system_ids.find(empire_id);
70 if (it != m_fleet_supplyable_system_ids.end())
71 return it->second;
72 return EMPTY_INT_SET;
73 }
74
FleetSupplyableSystemIDs(int empire_id,bool include_allies) const75 std::set<int> SupplyManager::FleetSupplyableSystemIDs(int empire_id, bool include_allies) const {
76 std::set<int> retval = FleetSupplyableSystemIDs(empire_id);
77 if (!include_allies)
78 return retval;
79
80 // add supplyable systems of all allies
81 for (auto empire_id_sys_id_set : m_fleet_supplyable_system_ids) {
82 int other_empire_id = empire_id_sys_id_set.first;
83 const std::set<int>& systems = empire_id_sys_id_set.second;
84 if (systems.empty() || Empires().GetDiplomaticStatus(empire_id, other_empire_id) != DIPLO_ALLIED)
85 continue;
86 retval.insert(systems.begin(), systems.end());
87 }
88 return retval;
89 }
90
EmpireThatCanSupplyAt(int system_id) const91 int SupplyManager::EmpireThatCanSupplyAt(int system_id) const {
92 for (const auto& entry : m_fleet_supplyable_system_ids) {
93 if (entry.second.count(system_id))
94 return entry.first;
95 }
96 return ALL_EMPIRES;
97 }
98
ResourceSupplyGroups() const99 const std::map<int, std::set<std::set<int>>>& SupplyManager::ResourceSupplyGroups() const
100 { return m_resource_supply_groups; }
101
ResourceSupplyGroups(int empire_id) const102 const std::set<std::set<int>>& SupplyManager::ResourceSupplyGroups(int empire_id) const {
103 auto it = m_resource_supply_groups.find(empire_id);
104 if (it != m_resource_supply_groups.end())
105 return it->second;
106 return EMPTY_INT_SET_SET;
107 }
108
PropagatedSupplyRanges() const109 const std::map<int, float>& SupplyManager::PropagatedSupplyRanges() const {
110 std::cout << "BLAAAAH" << std::endl;
111 return m_propagated_supply_ranges;
112 }
113
PropagatedSupplyRanges(int empire_id) const114 const std::map<int, float>& SupplyManager::PropagatedSupplyRanges(int empire_id) const {
115 auto emp_it = m_empire_propagated_supply_ranges.find(empire_id);
116 if (emp_it == m_empire_propagated_supply_ranges.end())
117 return EMPTY_INT_FLOAT_MAP;
118 return emp_it->second;
119 }
120
PropagatedSupplyDistances() const121 const std::map<int, float>& SupplyManager::PropagatedSupplyDistances() const
122 { return m_propagated_supply_distances; }
123
PropagatedSupplyDistances(int empire_id) const124 const std::map<int, float>& SupplyManager::PropagatedSupplyDistances(int empire_id) const {
125 auto emp_it = m_empire_propagated_supply_distances.find(empire_id);
126 if (emp_it == m_empire_propagated_supply_distances.end())
127 return EMPTY_INT_FLOAT_MAP;
128 return emp_it->second;
129 }
130
SystemHasFleetSupply(int system_id,int empire_id) const131 bool SupplyManager::SystemHasFleetSupply(int system_id, int empire_id) const {
132 if (system_id == INVALID_OBJECT_ID)
133 return false;
134 if (empire_id == ALL_EMPIRES)
135 return false;
136 auto it = m_fleet_supplyable_system_ids.find(empire_id);
137 if (it == m_fleet_supplyable_system_ids.end())
138 return false;
139 const std::set<int>& sys_set = it->second;
140 if (sys_set.count(system_id))
141 return true;
142 return false;
143 }
144
SystemHasFleetSupply(int system_id,int empire_id,bool include_allies) const145 bool SupplyManager::SystemHasFleetSupply(int system_id, int empire_id, bool include_allies) const {
146 if (!include_allies)
147 return SystemHasFleetSupply(system_id, empire_id);
148 if (system_id == INVALID_OBJECT_ID)
149 return false;
150 if (empire_id == ALL_EMPIRES)
151 return false;
152
153 std::set<int> empire_ids = Empires().GetEmpireIDsWithDiplomaticStatusWithEmpire(empire_id, DIPLO_ALLIED);
154 empire_ids.insert(empire_id);
155
156 for (auto id : empire_ids) {
157 auto sys_set_it = m_fleet_supplyable_system_ids.find(id);
158 if (sys_set_it == m_fleet_supplyable_system_ids.end())
159 continue;
160 auto sys_set = sys_set_it->second;
161 if (sys_set.count(system_id))
162 return true;
163 }
164
165 return false;
166 }
167
Dump(int empire_id) const168 std::string SupplyManager::Dump(int empire_id) const {
169 std::string retval;
170
171 try {
172 for (const auto& empire_supply : m_fleet_supplyable_system_ids) {
173 if (empire_id != ALL_EMPIRES && empire_supply.first != empire_id)
174 continue;
175 retval += "Supplyable systems for empire " + std::to_string(empire_supply.first) + "\n";
176 for (const auto& sys : Objects().find<System>(empire_supply.second)) {
177 if (!sys)
178 continue;
179 retval += "\n" + sys->PublicName(empire_id) + " (" + std::to_string(sys->ID()) + ") ";
180
181 retval += "\nTraversals from here to: ";
182
183 for (const auto& trav : m_supply_starlane_traversals.at(empire_supply.first)) {
184 if (trav.first == sys->ID()) {
185 auto obj = Objects().get(trav.second);
186 if (obj)
187 retval += obj->PublicName(empire_id) + " (" + std::to_string(obj->ID()) + ") ";
188 }
189 }
190 retval += "\n";
191
192 retval += "Traversals to here from: ";
193 for (const auto& trav : m_supply_starlane_traversals.at(empire_supply.first)) {
194 if (trav.second == sys->ID()) {
195 auto obj = Objects().get(trav.first);
196 if (obj)
197 retval += obj->PublicName(empire_id) + " (" + std::to_string(obj->ID()) + ") ";
198 }
199 }
200 retval += "\n";
201
202 retval += "Blocked Traversals from here to: ";
203 for (const auto& trav : m_supply_starlane_obstructed_traversals.at(empire_supply.first)) {
204 if (trav.first == sys->ID()) {
205 auto obj = Objects().get(trav.second);
206 if (obj)
207 retval += obj->PublicName(empire_id) + " (" + std::to_string(obj->ID()) + ") ";
208 }
209 }
210 retval += "\n";
211
212 retval += "Blocked Traversals to here from: ";
213 for (const auto& trav : m_supply_starlane_obstructed_traversals.at(empire_supply.first)) {
214 if (trav.second == sys->ID()) {
215 auto obj = Objects().get(trav.first);
216 if (obj)
217 retval += obj->PublicName(empire_id) + " (" + std::to_string(obj->ID()) + ") ";
218 }
219 }
220 retval += "\n";
221
222 }
223 retval += "\n\n";
224 }
225
226 for (const auto& empire_supply : m_resource_supply_groups) {
227 retval += "Supply groups for empire " + std::to_string(empire_supply.first) + "\n";
228 for (const auto& system_group : empire_supply.second) {
229 retval += "group: ";
230 for (const auto& sys : Objects().find<System>(system_group)) {
231 if (!sys)
232 continue;
233 retval += "\n" + sys->PublicName(empire_id) + " (" + std::to_string(sys->ID()) + ") ";
234 }
235 retval += "\n";
236 }
237 retval += "\n\n";
238 }
239 } catch (const std::exception& e) {
240 ErrorLogger() << "SupplyManager::Dump caught exception: " << e.what();
241 }
242
243 return retval;
244 }
245
246 namespace {
EmpireTotalSupplyRangeSumInSystem(int empire_id,int system_id)247 std::pair<float, float> EmpireTotalSupplyRangeSumInSystem(int empire_id, int system_id) {
248 if (empire_id == ALL_EMPIRES || system_id == INVALID_OBJECT_ID)
249 return {0.0f, 0.0f};
250 const auto sys = Objects().get<System>(system_id);
251 if (!sys)
252 return {0.0f, 0.0f};
253
254 float accumulator_current = 0.0f;
255 float accumulator_max = 0.0f;
256
257 for (auto obj : Objects().find(sys->ObjectIDs())) {
258 if (!obj || !obj->OwnedBy(empire_id))
259 continue;
260 if (const auto* m = obj->GetMeter(METER_SUPPLY))
261 accumulator_current += m->Current();
262 if (const auto* m = obj->GetMeter(METER_MAX_SUPPLY))
263 accumulator_max += m->Current();
264 }
265 return {accumulator_current, accumulator_max};
266 }
267
EmpireTotalSupplyRange(int empire_id)268 float EmpireTotalSupplyRange(int empire_id) {
269 if (empire_id == ALL_EMPIRES)
270 return 0.0f;
271
272 float accumulator_current = 0.0f;
273
274 for (auto obj : Objects().find(OwnedVisitor(empire_id))) {
275 if (!obj)
276 continue;
277 if (auto* m = obj->GetMeter(METER_SUPPLY))
278 accumulator_current += m->Current();
279 }
280 return accumulator_current;
281 }
282
DistanceBetweenObjects(int obj1_id,int obj2_id)283 float DistanceBetweenObjects(int obj1_id, int obj2_id) {
284 auto obj1 = Objects().get<System>(obj1_id);
285 if (!obj1)
286 return 0.0f;
287 auto obj2 = Objects().get<System>(obj2_id);
288 if (!obj2)
289 return 0.0f;
290 double dx = obj2->X() - obj1->X();
291 double dy = obj2->Y() - obj1->Y();
292 return static_cast<float>(std::sqrt(dx*dx + dy*dy));
293 }
294 }
295
Update()296 void SupplyManager::Update() {
297 m_supply_starlane_traversals.clear();
298 m_supply_starlane_obstructed_traversals.clear();
299 m_fleet_supplyable_system_ids.clear();
300 m_resource_supply_groups.clear();
301 m_propagated_supply_ranges.clear();
302
303 DebugLogger(supply) << "SupplyManager::Update";
304
305 // for each empire, need to get a set of sets of systems that can exchange
306 // resources. some sets may be just one system, in which resources can be
307 // exchanged between UniverseObjects producing or consuming them, but which
308 // can't exchange with any other systems.
309
310 // which systems can share resources depends on system supply ranges, which
311 // systems have obstructions to supply propagation for reach empire, and
312 // the ranges and obstructions of other empires' supply, as only one empire
313 // can supply each system or propagate along each starlane. one empire's
314 // propagating supply can push back another's, if the pusher's range is
315 // larger.
316
317 // map from empire id to map from system id to range (in starlane jumps)
318 // that supply can be propagated out of that system by that empire.
319 std::map<int, std::map<int, float>> empire_system_supply_ranges;
320 // map from empire id to which systems are obstructed for it for supply
321 // propagation
322 std::map<int, std::set<int>> empire_supply_unobstructed_systems;
323 // map from empire id to map from system id to pair of sum of supply source
324 // ranges and max ranges of objects owned by empire in that in system
325 std::map<int, std::map<int, std::pair<float, float>>> empire_system_supply_range_sums;
326 // map from empire id to total supply range sum of objects it owns
327 std::map<int, float> empire_total_supply_range_sums;
328
329 for (const auto& entry : Empires()) {
330 const Empire* empire = entry.second;
331 empire_system_supply_ranges[entry.first] = empire->SystemSupplyRanges();
332 empire_supply_unobstructed_systems[entry.first] = empire->SupplyUnobstructedSystems();
333
334 TraceLogger(supply) << "Empire " << empire->EmpireID() << " unobstructed systems: " << [&]() {
335 std::stringstream ss;
336 for (int system_id : empire_supply_unobstructed_systems[entry.first])
337 { ss << system_id << ", "; }
338 return ss.str();
339 }();
340 }
341 for (auto empire_id_pair : empire_system_supply_ranges) {
342 for (auto sys_id_pair : empire_id_pair.second) {
343 empire_system_supply_range_sums[empire_id_pair.first][sys_id_pair.first] =
344 EmpireTotalSupplyRangeSumInSystem(empire_id_pair.first, sys_id_pair.first);
345 }
346 empire_total_supply_range_sums[empire_id_pair.first] = EmpireTotalSupplyRange(empire_id_pair.first);
347 }
348
349
350 /////
351 // probably temporary: additional restriction here for supply propagation
352 // but not for general system obstruction as determind within Empire::UpdateSupplyUnobstructedSystems
353 /////
354 const auto fleets = GetUniverse().Objects().all<Fleet>();
355
356 for (const auto& entry : Empires()) {
357 int empire_id = entry.first;
358 const auto& known_destroyed_objects = GetUniverse().EmpireKnownDestroyedObjectIDs(empire_id);
359 std::set<int> systems_containing_friendly_fleets;
360
361 for (auto& fleet : fleets) {
362 int system_id = fleet->SystemID();
363 if (system_id == INVALID_OBJECT_ID || known_destroyed_objects.count(fleet->ID()))
364 continue;
365
366 if (fleet->HasArmedShips() && fleet->Aggressive()) {
367 if (fleet->OwnedBy(empire_id)) {
368 if (fleet->NextSystemID() == INVALID_OBJECT_ID || fleet->NextSystemID() == fleet->SystemID()) {
369 systems_containing_friendly_fleets.insert(system_id);
370 }
371 }
372 }
373 }
374
375 std::set<int> systems_where_others_have_supply_sources_and_current_empire_doesnt;
376 // add all systems where others have supply
377 for (auto& empire_supply : empire_system_supply_ranges) {
378 if (empire_supply.first == empire_id || empire_supply.first == ALL_EMPIRES)
379 continue;
380
381 for (const auto& supply_range : empire_supply.second) {
382 if (supply_range.second <= 0.0f)
383 continue;
384 systems_where_others_have_supply_sources_and_current_empire_doesnt.insert(supply_range.first);
385 }
386 }
387 // remove systems were this empire has supply
388 auto it = empire_system_supply_ranges.find(empire_id);
389 if (it != empire_system_supply_ranges.end()) {
390 for (const auto& supply_range : it->second) {
391 if (supply_range.second <= 0.0f)
392 continue;
393 systems_where_others_have_supply_sources_and_current_empire_doesnt.erase(supply_range.first);
394 }
395 }
396
397 // for systems where others have supply sources and this empire doesn't
398 // and where this empire has no fleets...
399 // supply is obstructed
400 for (int system_id : systems_where_others_have_supply_sources_and_current_empire_doesnt) {
401 if (!systems_containing_friendly_fleets.count(system_id))
402 empire_supply_unobstructed_systems[empire_id].erase(system_id);
403 }
404 }
405 /////
406 // end probably temporary...
407 /////
408
409
410 // system connections each empire can see / use for supply propagation
411 std::map<int, std::map<int, std::set<int>>> empire_visible_starlanes;
412 for (auto& entry : Empires()) {
413 const Empire* empire = entry.second;
414 empire_visible_starlanes[entry.first] = empire->KnownStarlanes();// VisibleStarlanes();
415
416 if (empire_visible_starlanes[entry.first].empty()) {
417 ErrorLogger(supply) << "Empire " << entry.first << " has no known starlanes?!";
418 }
419 }
420
421 std::set<int> systems_with_supply_in_them;
422
423 // store (supply range in jumps, and distance to supply source) of all
424 // unobstructed systems before propagation, and add to list of systems
425 // to propagate from.
426 std::map<int, std::map<int, std::pair<float, float>>> empire_propagating_supply_ranges;
427 float max_range = 0.0f;
428
429 for (const auto& empire_supply : empire_system_supply_ranges) {
430 int empire_id = empire_supply.first;
431 const std::set<int>& unobstructed_systems = empire_supply_unobstructed_systems[empire_id];
432
433 for (const auto& supply_range : empire_supply.second) {
434 int system_id = supply_range.first;
435 if (unobstructed_systems.count(system_id)) {
436 // stored: first -> source supply range. second -> distance to source (0 for the source itself)
437 empire_propagating_supply_ranges[empire_id][system_id] = {supply_range.second, 0.0f};
438 if (supply_range.second > max_range)
439 max_range = supply_range.second;
440 systems_with_supply_in_them.insert(system_id);
441 }
442 }
443 }
444
445 TraceLogger(supply) << "Propagating supply";
446 // spread supply out from sources by "diffusion" like process, along unobstructed
447 // starlanes, until the range is exhausted.
448 for (float range_to_spread = max_range; range_to_spread >= 0;
449 range_to_spread -= 1.0f)
450 {
451 TraceLogger(supply) << "Propagating at range " << range_to_spread;
452
453 // update systems that have supply in them
454 for (const auto& empire_supply : empire_propagating_supply_ranges) {
455 for (const auto& supply_range : empire_supply.second)
456 { systems_with_supply_in_them.insert(supply_range.first); }
457 }
458
459
460 // resolve supply fights between multiple empires in one system.
461 // pass over all empire-supplied systems, removing supply for all
462 // but the empire with the highest supply range in each system
463 for (const auto& sys : Objects().find<System>(systems_with_supply_in_them)) {
464 TraceLogger(supply) << "Determining top supply empire in system " << sys->Name() << " (" << sys->ID() << ")";
465 // sort empires by range in this system
466 std::map<float, std::set<int>> empire_ranges_here;
467 for (auto& empire_supply : empire_propagating_supply_ranges) {
468 int empire_id = empire_supply.first;
469 auto empire_supply_it = empire_supply.second.find(sys->ID());
470 // does this empire have any range in this system? if so, store it
471 if (empire_supply_it == empire_supply.second.end())
472 continue;
473
474 // stuff to break ties...
475 float bonus = 0.0f;
476
477 // empires with planets in system
478 bool has_outpost = false, has_colony = false;
479 for (auto& planet : Objects().find<Planet>(sys->PlanetIDs())) {
480 if (!planet)
481 continue;
482 if (!planet->OwnedBy(empire_id))
483 continue;
484 if (!planet->SpeciesName().empty())
485 has_colony = true;
486 else
487 has_outpost = true;
488 }
489 if (has_colony)
490 bonus += 0.5f;
491 else if (has_outpost)
492 bonus += 0.3f;
493
494 // sum of all supply sources in this system
495 bonus += empire_system_supply_range_sums[empire_id][sys->ID()].first / 1000.0f;
496 // sum of max supply of sourses in this system
497 bonus += empire_system_supply_range_sums[empire_id][sys->ID()].second / 100000.0f;
498 bonus += empire_total_supply_range_sums[empire_id] / 100000000.0f;
499
500 // distance to supply source from here
501 float propagated_distance_to_supply_source = std::max(1.0f, empire_supply_it->second.second);
502 bonus += propagated_distance_to_supply_source / 10000.0f;
503
504 // store ids of empires indexed by adjusted propgated range, in order to sort by range
505 float propagated_range = empire_supply_it->second.first;
506 empire_ranges_here[propagated_range + bonus].insert(empire_id);
507 }
508
509 if (empire_ranges_here.empty()) {
510 TraceLogger(supply) << " ... no empire has a range here";
511
512 } else if (empire_ranges_here.size() == 1) {
513 TraceLogger(supply) << " ... only empire here: " << *empire_ranges_here.begin()->second.begin() << " with range: " << empire_ranges_here.begin()->first;
514
515 } else {
516 TraceLogger(supply) << " ... ranges of empires: " << [&]() {
517 std::stringstream erss;
518 for (const auto& er : empire_ranges_here) {
519 erss << er.first << " : (";
520 for (const auto& eid : er.second)
521 erss << eid << " ";
522 erss << ") ";
523 }
524 return erss.str();
525 }();
526 }
527
528 if (empire_ranges_here.empty())
529 continue; // no empire has supply here?
530 if (empire_ranges_here.size() == 1 && empire_ranges_here.begin()->second.size() < 2)
531 continue; // only one empire has supply here
532
533 // at least two empires have supply sources here...
534 // check if one is stronger
535
536 // remove supply for all empires except the top-ranged empire here,
537 // or one of the empires at the top if all top empires are allies
538 auto range_empire_it = empire_ranges_here.rbegin();
539 int top_range_empire_id = ALL_EMPIRES;
540 if (range_empire_it->second.size() == 1) {
541 // if just one empire has the most range, it is the top empire
542 top_range_empire_id = *(range_empire_it->second.begin());
543
544 } else {
545 // if all empires that share the top range are allies, pick one
546 // to be the top empire
547 TraceLogger(supply) << " ... top empires are allied!";
548 const auto& top_empires = range_empire_it->second;
549 bool any_non_allied_pair = false;
550 for (auto id1 : top_empires) {
551 if (id1 == ALL_EMPIRES) continue;
552 for (auto id2 : top_empires) {
553 if (id2 == ALL_EMPIRES || id2 <= id1) continue;
554 if (Empires().GetDiplomaticStatus(id1, id2) != DIPLO_ALLIED) {
555 any_non_allied_pair = true;
556 break;
557 }
558 }
559 }
560 if (!any_non_allied_pair) {
561 // arbitrarily pick the lowest ID empire
562 top_range_empire_id = *(range_empire_it->second.begin());
563 }
564 }
565 TraceLogger(supply) << " ... top ranged empire here: " << top_range_empire_id << " with range: " << range_empire_it->first;
566
567
568 // remove range entries and traversals for all but the top empire
569 // (or all empires if there is no single top empire)
570 for (auto& empire_supply : empire_propagating_supply_ranges) {
571 int empire_id = empire_supply.first;
572 if (empire_id == top_range_empire_id)
573 continue; // this is the top empire, so leave as the sole empire supplying here
574
575 // remove from range entry...
576 auto& empire_ranges = empire_supply.second;
577 empire_ranges.erase(sys->ID());
578
579 TraceLogger(supply) << "... removed empire " << empire_id << " system " << sys->ID() << " supply.";
580
581 // Remove from unobstructed systems
582 empire_supply_unobstructed_systems[empire_id].erase(sys->ID());
583
584 auto& lane_traversals = m_supply_starlane_traversals[empire_id];
585 auto lane_traversals_initial = lane_traversals;
586 auto& obstructed_traversals = m_supply_starlane_obstructed_traversals[empire_id];
587 auto obstrcuted_traversals_initial = obstructed_traversals;
588
589 // remove from traversals departing from or going to this system for this empire,
590 // and set any traversals going to this system as obstructed
591 for (const auto& lane : lane_traversals_initial) {
592 if (lane.first == sys->ID()) {
593 lane_traversals.erase({sys->ID(), lane.second});
594 }
595 if (lane.second == sys->ID()) {
596 lane_traversals.erase({lane.first, sys->ID()});
597 obstructed_traversals.insert({lane.first, sys->ID()});
598 }
599 }
600
601 // remove obstructed traverals departing from this system
602 for (const auto& lane : obstrcuted_traversals_initial) {
603 if (lane.first == sys->ID())
604 obstructed_traversals.erase({lane.first, lane.second});
605 }
606 }
607
608 //// DEBUG
609 for (auto& empire_supply : empire_propagating_supply_ranges) {
610 auto& system_ranges = empire_supply.second;
611 auto range_it = system_ranges.find(sys->ID());
612 if (range_it != system_ranges.end())
613 TraceLogger(supply) << " ... after culling empires ranges at system " << sys->ID() << " : " << empire_supply.first << " : " << range_it->second.first;
614 }
615 //// END DEBUG
616 }
617
618 if (range_to_spread <= 0.0f)
619 break;
620
621 // initialize next iteration with current supply distribution
622 auto empire_propagating_supply_ranges_next = empire_propagating_supply_ranges;
623
624
625 // for sources of supply of at least the minimum range for this
626 // iteration that are in the current map, give adjacent systems one
627 // less supply in the next iteration (unless as much or more is already
628 // there)
629 for (const auto& empire_supply : empire_propagating_supply_ranges) {
630 int empire_id = empire_supply.first;
631 TraceLogger(supply) << ">-< Doing supply propagation for empire " << empire_id << " >-< at spread range: " << range_to_spread;
632 const auto& prev_sys_ranges = empire_supply.second;
633 const auto& unobstructed_systems = empire_supply_unobstructed_systems[empire_id];
634
635 for (const auto& supply_range : empire_supply.second) {
636 int system_id = supply_range.first;
637 float range = supply_range.second.first;
638 TraceLogger(supply) << " ... for system " << system_id << " with range: " << range;
639
640 // does the source system have the correct supply range to propagate outwards in this iteration?
641 if (std::floor(range) != range_to_spread)
642 continue;
643 float range_after_one_more_jump = range - 1.0f; // what to set adjacent systems' ranges to (at least)
644
645 // how far is this system from a source of supply for this empire?
646 float distance_to_supply_source = supply_range.second.second;
647
648 for (int lane_end_sys_id : empire_visible_starlanes[empire_id][system_id])
649 TraceLogger(supply) << "Propagating from system " << system_id << " to " << lane_end_sys_id
650 << " range: " << range << " and distance: " << distance_to_supply_source;
651
652 // attempt to propagate to all adjacent systems...
653 for (int lane_end_sys_id : empire_visible_starlanes[empire_id][system_id]) {
654 // is propagation to the adjacent system obstructed?
655 if (!unobstructed_systems.count(lane_end_sys_id)) {
656 // propagation obstructed!
657 TraceLogger(supply) << "Added obstructed traversal from " << system_id << " to " << lane_end_sys_id << " due to not being on unobstructed systems";
658 m_supply_starlane_obstructed_traversals[empire_id].insert({system_id, lane_end_sys_id});
659 continue;
660 }
661 // propagation not obstructed.
662 TraceLogger(supply) << "Propagation from " << system_id << " to " << lane_end_sys_id << " is unobstructed";
663
664 // does another empire already have as much or more supply here from a previous iteration?
665 float other_empire_biggest_range = -10000.0f; // arbitrary big numbeer
666 for (const auto& other_empire_supply : empire_propagating_supply_ranges) {
667 int other_empire_id = other_empire_supply.first;
668 if (other_empire_id == empire_id)
669 continue;
670 const auto& prev_other_empire_sys_ranges = other_empire_supply.second;
671 auto prev_other_empire_range_it = prev_other_empire_sys_ranges.find(lane_end_sys_id);
672 if (prev_other_empire_range_it == prev_other_empire_sys_ranges.end())
673 continue;
674 if (prev_other_empire_range_it->second.first > other_empire_biggest_range)
675 other_empire_biggest_range = prev_other_empire_range_it->second.first;
676 }
677
678 // if so, add a blocked traversal and continue
679 if (range_after_one_more_jump <= other_empire_biggest_range) {
680 m_supply_starlane_obstructed_traversals[empire_id].insert({system_id, lane_end_sys_id});
681 TraceLogger(supply) << "Added obstructed traversal from " << system_id << " to " << lane_end_sys_id << " due to other empire biggest range being " << other_empire_biggest_range;
682 continue;
683 }
684
685 // otherwise, propagate into system...
686 float lane_length = DistanceBetweenObjects(system_id, lane_end_sys_id);
687 float distance_to_supply_source_after_next_lane = lane_length + distance_to_supply_source;
688
689 TraceLogger(supply) << "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;
690
691 // if propagating supply would increase the range of the adjacent system,
692 // or decrease the distance to the adjacent system from a supply source...
693 auto prev_range_it = prev_sys_ranges.find(lane_end_sys_id);
694 if (prev_range_it == prev_sys_ranges.end()) {
695 empire_propagating_supply_ranges_next[empire_id][lane_end_sys_id] =
696 {range_after_one_more_jump, distance_to_supply_source_after_next_lane};
697 //TraceLogger(supply) << " ... default case: no previous entry.";
698
699 } else {
700 //TraceLogger(supply) << " ... previous entry values: " << prev_range_it->second.first << " and " << prev_range_it->second.second;
701
702 if (range_after_one_more_jump > prev_range_it->second.first) {
703 empire_propagating_supply_ranges_next[empire_id][lane_end_sys_id].first =
704 range_after_one_more_jump;
705 //TraceLogger(supply) << " ... range increased!";
706 }
707 if (distance_to_supply_source_after_next_lane < prev_range_it->second.second) {
708 empire_propagating_supply_ranges_next[empire_id][lane_end_sys_id].second =
709 distance_to_supply_source_after_next_lane;
710 //TraceLogger(supply) << " ... distance decreased!";
711 }
712 }
713 // always record a traversal, so connectivity is calculated properly
714 m_supply_starlane_traversals[empire_id].insert({system_id, lane_end_sys_id});
715 TraceLogger(supply) << "Added traversal from " << system_id << " to " << lane_end_sys_id;
716
717 // erase any previous obstructed traversal that just succeeded
718 if (m_supply_starlane_obstructed_traversals[empire_id].count({system_id, lane_end_sys_id}))
719 {
720 //TraceLogger(supply) << "Removed obstructed traversal from " << system_id << " to " << lane_end_sys_id;
721 m_supply_starlane_obstructed_traversals[empire_id].erase({system_id, lane_end_sys_id});
722 }
723 if (m_supply_starlane_obstructed_traversals[empire_id].count({lane_end_sys_id, system_id}))
724 {
725 //TraceLogger(supply) << "Removed obstructed traversal from " << lane_end_sys_id << " to " << system_id;
726 m_supply_starlane_obstructed_traversals[empire_id].erase({lane_end_sys_id, system_id});
727 }
728 }
729 }
730 }
731
732 // save propagated results for next iteration
733 empire_propagating_supply_ranges = std::move(empire_propagating_supply_ranges_next);
734 }
735
736 //// DEBUG
737 TraceLogger(supply) << "SupplyManager::Update: after removing conflicts, empires can provide supply to the following system ids (and ranges in jumps):";
738 for (auto& empire_supply : empire_propagating_supply_ranges) {
739 TraceLogger(supply) << " ... empire " << empire_supply.first << ": " << [&]() {
740 std::stringstream ss;
741 for (auto& supply_range : empire_supply.second)
742 ss << supply_range.first << " (" << supply_range.second.first << "), ";
743 return ss.str();
744 }();
745
746 }
747 //// END DEBUG
748
749 // record which systems are fleet supplyable by each empire (after resolving conflicts in each system)
750 for (const auto& empire_supply : empire_propagating_supply_ranges) {
751 int empire_id = empire_supply.first;
752 for (const auto& supply_range : empire_supply.second) {
753 if (supply_range.second.first < 0.0f)
754 continue; // negative supply doesn't count... zero does (it just reaches)
755 m_fleet_supplyable_system_ids[empire_id].insert(supply_range.first);
756
757 // should be only one empire per system at this point, but use max just to be safe...
758 m_propagated_supply_ranges[supply_range.first] =
759 std::max(supply_range.second.first, m_propagated_supply_ranges[supply_range.first]);
760 m_empire_propagated_supply_ranges[empire_id][supply_range.first] =
761 m_propagated_supply_ranges[supply_range.first];
762
763 // should be only one empire per system at this point, but use max just to be safe...
764 m_propagated_supply_distances[supply_range.first] =
765 std::max(supply_range.second.second, m_propagated_supply_distances[supply_range.first]);
766 m_empire_propagated_supply_distances[empire_id][supply_range.first] =
767 m_propagated_supply_distances[supply_range.first];
768 }
769
770 //TraceLogger(supply) << "For empire: " << empire_id << " system supply distances: ";
771 //for (auto entry : m_empire_propagated_supply_distances[empire_id]) {
772 // TraceLogger(supply) << entry.first << " : " << entry.second;
773 //}
774 }
775
776
777
778 auto ally_merged_supply_starlane_traversals = m_supply_starlane_traversals;
779
780 // add connections into allied empire systems when their obstructed lane
781 // traversals originate on either end of a starlane
782 for (auto& empire_set : m_supply_starlane_obstructed_traversals) {
783 // input:
784 const auto& empire_obstructed_traversals = empire_set.second;
785 // output:
786 auto& empire_supply_traversals = ally_merged_supply_starlane_traversals[empire_set.first];
787
788
789 std::set<int> allies_of_empire = Empires().GetEmpireIDsWithDiplomaticStatusWithEmpire(empire_set.first, DIPLO_ALLIED);
790 for (int ally_id : allies_of_empire) {
791 // input:
792 auto const& ally_obstructed_traversals = m_supply_starlane_obstructed_traversals[ally_id];
793
794 // find cases where outer loop empire has an obstructed traversal from A to B
795 // and inner loop empire has an obstructed traversal from B to A
796 for (auto const& empire_trav : empire_obstructed_traversals) {
797 for (auto const& ally_trav : ally_obstructed_traversals) {
798 if (empire_trav.first == ally_trav.second && empire_trav.second == ally_trav.first) {
799 empire_supply_traversals.insert({empire_trav.first, empire_trav.second});
800 empire_supply_traversals.insert({empire_trav.second, empire_trav.first});
801 }
802 }
803 }
804 }
805 }
806
807 // add allied supply starlane traversals to empires' traversals, so that
808 // allies can use eachothers' supply networks
809 for (auto& empire_set : ally_merged_supply_starlane_traversals) {
810 auto& output_empire_traversals = empire_set.second;
811 for (int ally_id : Empires().GetEmpireIDsWithDiplomaticStatusWithEmpire(empire_set.first, DIPLO_ALLIED)) {
812 // copy ally traversals into the output empire traversals set
813 for (const auto& traversal_pair : m_supply_starlane_traversals[ally_id])
814 output_empire_traversals.insert(traversal_pair);
815 }
816 }
817
818 // same for fleet supplyable system ids, as these are added to supplyable
819 // groups in following code
820 auto ally_merged_fleet_supplyable_system_ids = m_fleet_supplyable_system_ids;
821 for (auto& empire_set : ally_merged_fleet_supplyable_system_ids) {
822 std::set<int>& output_empire_ids = empire_set.second;
823 for (int ally_id : Empires().GetEmpireIDsWithDiplomaticStatusWithEmpire(empire_set.first, DIPLO_ALLIED)) {
824 // copy ally traversals into the output empire traversals set
825 for (int sys_id : m_fleet_supplyable_system_ids[ally_id])
826 output_empire_ids.insert(sys_id);
827 }
828 }
829
830
831
832 // determine supply-connected groups of systems for each empire.
833 // need to merge interconnected supply groups into as few sets of mutually-
834 // supply-exchanging systems as possible. This requires finding the
835 // connected components of an undirected graph, where the node
836 // adjacency are the directly-connected systems determined above.
837 for (const auto& empire_supply : empire_propagating_supply_ranges) {
838 int empire_id = empire_supply.first;
839
840 // assemble all direct connections between systems from remaining traversals
841 std::map<int, std::set<int>> supply_groups_map;
842 for (auto const& lane : ally_merged_supply_starlane_traversals[empire_id]) {
843 supply_groups_map[lane.first].insert(lane.second);
844 supply_groups_map[lane.second].insert(lane.first);
845 }
846
847 // also add connections from all fleet-supplyable systems to themselves, so that
848 // any fleet supplyable system with no connection to another system can still
849 // have resource sharing within itself
850 for (int system_id : ally_merged_fleet_supplyable_system_ids[empire_id])
851 supply_groups_map[system_id].insert(system_id);
852
853
854 if (supply_groups_map.empty())
855 continue;
856
857 TraceLogger(supply) << "Empire " << empire_id << " supply groups map before merging:";
858 for (auto const& q : supply_groups_map) {
859 TraceLogger(supply) << " ... src: " << q.first << " to: " << [&]() {
860 std::stringstream other_ids;
861 for (auto const& r : q.second)
862 { other_ids << r << ", "; }
863 return other_ids.str();
864 }();
865 }
866
867
868 // create graph
869 boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> graph;
870
871 // boost expects vertex labels to range from 0 to num vertices - 1, so need
872 // to map from system id to graph id and back when accessing vertices
873 std::vector<int> graph_id_to_sys_id;
874 graph_id_to_sys_id.reserve(supply_groups_map.size());
875
876 std::map<int, int> sys_id_to_graph_id;
877 int graph_id = 0;
878 for (auto& supply_group : supply_groups_map) {
879 int sys_id = supply_group.first;
880 boost::add_vertex(graph); // should add with index = graph_id
881
882 graph_id_to_sys_id.push_back(sys_id);
883 sys_id_to_graph_id[sys_id] = graph_id;
884 ++graph_id;
885 }
886
887 // add edges for all direct connections between systems
888 // and add edges from fleet supplyable systems to themselves
889 for (auto& supply_group : supply_groups_map) {
890 int start_graph_id = sys_id_to_graph_id[supply_group.first];
891 for (int system_id : supply_group.second) {
892 int end_graph_id = sys_id_to_graph_id[system_id];
893 boost::add_edge(start_graph_id, end_graph_id, graph);
894 }
895 }
896
897 // declare storage and fill with the component id (group id of connected systems)
898 // for each graph vertex
899 std::vector<int> components(boost::num_vertices(graph));
900 boost::connected_components(graph, &components[0]);
901
902 // convert results back from graph id to system id, and into desired output format
903 // output: std::map<int, std::set<std::set<int>>>& m_resource_supply_groups
904
905 // first, sort into a map from component id to set of system ids in component
906 std::map<int, std::set<int>> component_sets_map;
907 for (std::size_t comp_graph_id = 0; comp_graph_id != components.size(); ++comp_graph_id) {
908 int label = components[comp_graph_id];
909 int sys_id = graph_id_to_sys_id[comp_graph_id];
910 component_sets_map[label].insert(sys_id);
911 }
912
913 // copy sets in map into set of sets
914 for (auto& component_set : component_sets_map)
915 m_resource_supply_groups[empire_id].insert(component_set.second);
916 }
917
918 for (const auto& empire_pair : m_resource_supply_groups) {
919 DebugLogger(supply) << "Connected supply groups for empire " << empire_pair.first << ":";
920 for (const auto& group_set : empire_pair.second) {
921 DebugLogger(supply) << " ... " << [&]() {
922 std::stringstream ss;
923 for (const auto& sys : group_set)
924 ss << sys << ", ";
925 return ss.str();
926 }();
927 }
928 }
929 }
930