1 /*
2 * Copyright (C) 2004-2020 by the Widelands Development Team
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 *
18 */
19
20 #include "economy/economy.h"
21
22 #include <memory>
23
24 #include "base/macros.h"
25 #include "base/wexception.h"
26 #include "economy/cmd_call_economy_balance.h"
27 #include "economy/flag.h"
28 #include "economy/request.h"
29 #include "economy/route.h"
30 #include "economy/routeastar.h"
31 #include "economy/router.h"
32 #include "economy/warehousesupply.h"
33 #include "logic/game.h"
34 #include "logic/map_objects/tribes/soldier.h"
35 #include "logic/map_objects/tribes/tribe_descr.h"
36 #include "logic/map_objects/tribes/warehouse.h"
37 #include "logic/player.h"
38
39 namespace Widelands {
40
41 Serial Economy::last_economy_serial_ = 0;
42
initialize_serial()43 void Economy::initialize_serial() {
44 log("Initializing economy serial\n");
45 last_economy_serial_ = 0;
46 }
47
Economy(Player & player,WareWorker wwtype)48 Economy::Economy(Player& player, WareWorker wwtype)
49 : Economy(player, last_economy_serial_++, wwtype) {
50 }
51
Economy(Player & player,Serial init_serial,WareWorker wwtype)52 Economy::Economy(Player& player, Serial init_serial, WareWorker wwtype)
53 : serial_(init_serial),
54 owner_(player),
55 type_(wwtype),
56 request_timerid_(0),
57 options_window_(nullptr) {
58 last_economy_serial_ = std::max(last_economy_serial_, serial_ + 1);
59 const TribeDescr& tribe = player.tribe();
60 DescriptionIndex const nr_wares_or_workers =
61 wwtype == wwWARE ? player.egbase().tribes().nrwares() : player.egbase().tribes().nrworkers();
62 wares_or_workers_.set_nrwares(nr_wares_or_workers);
63
64 target_quantities_ = new TargetQuantity[nr_wares_or_workers];
65 for (DescriptionIndex i = 0; i < nr_wares_or_workers; ++i) {
66 TargetQuantity tq;
67 switch (type_) {
68 case wwWARE:
69 if (tribe.has_ware(i)) {
70 tq.permanent = tribe.get_ware_descr(i)->default_target_quantity(tribe.name());
71 } else {
72 tq.permanent = 0;
73 }
74 break;
75 case wwWORKER:
76 tq.permanent = tribe.get_worker_descr(i)->default_target_quantity();
77 break;
78 }
79 tq.last_modified = 0;
80 target_quantities_[i] = tq;
81 }
82
83 router_.reset(new Router([this]() { reset_all_pathfinding_cycles(); }));
84 }
85
~Economy()86 Economy::~Economy() {
87 Notifications::publish(NoteEconomy{serial_, serial_, NoteEconomy::Action::kDeleted});
88
89 if (requests_.size())
90 log("Warning: Economy still has requests left on destruction\n");
91 if (flags_.size())
92 log("Warning: Economy still has flags left on destruction\n");
93 if (warehouses_.size())
94 log("Warning: Economy still has warehouses left on destruction\n");
95
96 delete[] target_quantities_;
97 }
98
99 /**
100 * \return an arbitrary flag in this economy.
101 */
get_arbitrary_flag()102 Flag* Economy::get_arbitrary_flag() {
103 if (flags_.empty())
104 return nullptr;
105
106 return flags_[0];
107 }
108
109 /**
110 * Two flags have been connected; check whether their economies should be
111 * merged.
112 * Since we could merge into both directions, we preserve the economy that is
113 * currently bigger (should be more efficient).
114 */
check_merge(Flag & f1,Flag & f2,WareWorker type)115 void Economy::check_merge(Flag& f1, Flag& f2, WareWorker type) {
116 Economy* e1 = f1.get_economy(type);
117 Economy* e2 = f2.get_economy(type);
118 if (e1 != e2) {
119 if (e1->get_nrflags() < e2->get_nrflags())
120 std::swap(e1, e2);
121 e1->merge(*e2);
122 }
123 }
124
125 /**
126 * Notify the economy that there may no longer be a connection between
127 * the given flags in the road and seafaring network.
128 */
check_split(Flag & f1,Flag & f2,WareWorker type)129 void Economy::check_split(Flag& f1, Flag& f2, WareWorker type) {
130 assert(&f1 != &f2);
131 assert(f1.get_economy(type) == f2.get_economy(type));
132
133 Economy* e = f1.get_economy(type);
134 // No economy in the editor.
135 if (!e)
136 return;
137
138 e->split_checks_.push_back(std::make_pair(OPtr<Flag>(&f1), OPtr<Flag>(&f2)));
139 e->rebalance_supply(); // the real split-checking is done during rebalance
140 }
141
check_splits()142 void Economy::check_splits() {
143 EditorGameBase& egbase = owner().egbase();
144 while (split_checks_.size()) {
145 Flag* f1 = split_checks_.back().first.get(egbase);
146 Flag* f2 = split_checks_.back().second.get(egbase);
147 split_checks_.pop_back();
148
149 if (!f1 || !f2) {
150 if (!f1 && !f2)
151 continue;
152 if (!f1)
153 f1 = f2;
154 if (f1->get_economy(type_) != this)
155 continue;
156
157 // Handle the case when two or more roads are removed simultaneously
158 RouteAStar<AStarZeroEstimator> astar(*router_, type_, AStarZeroEstimator());
159 astar.push(*f1);
160 std::set<OPtr<Flag>> reachable;
161 while (RoutingNode* current = astar.step()) {
162 reachable.insert(¤t->base_flag());
163 }
164 if (reachable.size() != flags_.size()) {
165 split(reachable);
166 }
167 continue;
168 }
169
170 // If one (or both) of the flags have already been split off, we do not need to re-check
171 if (f1->get_economy(type_) != this || f2->get_economy(type_) != this)
172 continue;
173
174 // Start an A-star searches from f1 with a heuristic bias towards f2,
175 // because we do not need to do anything if f1 is still connected to f2.
176 // If f2 is not reached by the search, split off all the nodes that have been
177 // reached from f1. These nodes induce a connected subgraph.
178 // This means that the newly created economy, which contains all the
179 // flags that have been split, is already connected.
180 RouteAStar<AStarEstimator> astar(*router_, type_, AStarEstimator(*egbase.mutable_map(), *f2));
181 astar.push(*f1);
182 std::set<OPtr<Flag>> reachable;
183
184 for (;;) {
185 RoutingNode* current = astar.step();
186 if (!current) {
187 split(reachable);
188 break;
189 } else if (current == f2) {
190 break;
191 }
192 reachable.insert(¤t->base_flag());
193 }
194 }
195 }
196
197 /**
198 * Calculate a route between two flags.
199 *
200 * This functionality has been moved to Router(). This is currently
201 * merely a delegator.
202 */
find_route(Flag & start,Flag & end,Route * const route,int32_t const cost_cutoff)203 bool Economy::find_route(Flag& start, Flag& end, Route* const route, int32_t const cost_cutoff) {
204 assert(start.get_economy(type_) == this);
205 assert(end.get_economy(type_) == this);
206 return router_->find_route(
207 start, end, route, type_, cost_cutoff, *owner().egbase().mutable_map());
208 }
209
210 struct ZeroEstimator {
operator ()Widelands::ZeroEstimator211 int32_t operator()(RoutingNode& /* node */) const {
212 return 0;
213 }
214 };
215
216 /**
217 * Find the warehouse closest to the given starting flag.
218 *
219 * If the search was successful and \p route is non-null,
220 * a route is also computed.
221 *
222 * \param start starting flag
223 * \param route if non-null, fill in a route to the warehouse
224 * \param cost_cutoff if positive, find paths of at most
225 * that length (in milliseconds)
226 */
find_closest_warehouse(Flag & start,Route * route,uint32_t cost_cutoff,const Economy::WarehouseAcceptFn & acceptfn)227 Warehouse* Economy::find_closest_warehouse(Flag& start,
228 Route* route,
229 uint32_t cost_cutoff,
230 const Economy::WarehouseAcceptFn& acceptfn) {
231 if (!warehouses().size())
232 return nullptr;
233
234 // A-star with zero estimator = Dijkstra
235 RouteAStar<ZeroEstimator> astar(*router_, type_);
236 astar.push(start);
237
238 while (RoutingNode* current = astar.step()) {
239 if (cost_cutoff &&
240 (type_ == wwWARE ? current->mpf_realcost_ware : current->mpf_realcost_worker) >
241 static_cast<int32_t>(cost_cutoff)) {
242 return nullptr;
243 }
244
245 Flag& flag = current->base_flag();
246 if (upcast(Warehouse, warehouse, flag.get_building())) {
247 if (!acceptfn || acceptfn(*warehouse)) {
248 if (route)
249 astar.routeto(flag, *route);
250 return warehouse;
251 }
252 }
253 }
254
255 return nullptr;
256 }
257
258 /**
259 * Add a flag to the flag array.
260 * Only call from Flag init and split/merger code!
261 */
add_flag(Flag & flag)262 void Economy::add_flag(Flag& flag) {
263 assert(flag.get_economy(type_) == nullptr);
264
265 flags_.push_back(&flag);
266 flag.set_economy(this, type_);
267
268 flag.reset_path_finding_cycle(type_);
269 }
270
271 /**
272 * Remove a flag from the flag array.
273 * Only call from Flag cleanup and split/merger code!
274 */
remove_flag(Flag & flag)275 void Economy::remove_flag(Flag& flag) {
276 assert(flag.get_economy(type_) == this);
277
278 do_remove_flag(flag);
279
280 // automatically delete the economy when it becomes empty.
281 if (flags_.empty()) {
282 owner_.remove_economy(serial_);
283 }
284 }
285
286 /**
287 * Remove the flag, but don't delete the economy automatically.
288 * This is called from the merge code.
289 */
do_remove_flag(Flag & flag)290 void Economy::do_remove_flag(Flag& flag) {
291 flag.set_economy(nullptr, type_);
292
293 // fast remove
294 for (Flags::iterator flag_iter = flags_.begin(); flag_iter != flags_.end(); ++flag_iter) {
295 if (*flag_iter == &flag) {
296 *flag_iter = *(flags_.end() - 1);
297 return flags_.pop_back();
298 }
299 }
300 throw wexception("trying to remove nonexistent flag");
301 }
302
303 /**
304 * Callback for the incredibly rare case that the \ref Router pathfinding
305 * cycle wraps around.
306 */
reset_all_pathfinding_cycles()307 void Economy::reset_all_pathfinding_cycles() {
308 for (Flag* flag : flags_) {
309 flag->reset_path_finding_cycle(type_);
310 }
311 }
312
313 /**
314 * Set the target quantities for the given DescriptionIndex to the
315 * numbers given in permanent. Also update the last
316 * modification time.
317 *
318 * This is called from Cmd_ResetTargetQuantity and Cmd_SetTargetQuantity
319 */
set_target_quantity(DescriptionIndex const ware_or_worker_type,Quantity const permanent,Time const mod_time)320 void Economy::set_target_quantity(DescriptionIndex const ware_or_worker_type,
321 Quantity const permanent,
322 Time const mod_time) {
323 #ifndef NDEBUG
324 if (type_ == wwWARE) {
325 assert(owner().egbase().tribes().ware_exists(ware_or_worker_type));
326 } else {
327 assert(owner().egbase().tribes().worker_exists(ware_or_worker_type));
328 }
329 #endif
330 TargetQuantity& tq = target_quantities_[ware_or_worker_type];
331 tq.permanent = permanent;
332 tq.last_modified = mod_time;
333 }
334
335 /**
336 * Call this whenever some entity created a ware, e.g. when a lumberjack
337 * has felled a tree.
338 * This is also called when a ware is added to the economy through trade or
339 * a merger.
340 * Also notifies the corresponding other-type economy, if desired,
341 * so it may check e.g. whether a worker for whom a tool was missing can now be created.
342 */
add_wares_or_workers(DescriptionIndex const id,Quantity const count,Economy * other_economy)343 void Economy::add_wares_or_workers(DescriptionIndex const id,
344 Quantity const count,
345 Economy* other_economy) {
346 wares_or_workers_.add(id, count);
347 start_request_timer();
348 if (other_economy) {
349 assert(other_economy->type() != type_);
350 other_economy->start_request_timer();
351 }
352
353 // TODO(unknown): add to global player inventory?
354 }
355
356 /**
357 * Call this whenever a ware is destroyed or consumed, e.g. food has been
358 * eaten or a warehouse has been destroyed.
359 * This is also called when a ware is removed from the economy through trade or
360 * a split of the Economy.
361 */
remove_wares_or_workers(DescriptionIndex const id,Quantity const count)362 void Economy::remove_wares_or_workers(DescriptionIndex const id, Quantity const count) {
363 #ifndef NDEBUG
364 if (type_ == wwWARE) {
365 assert(owner().egbase().tribes().ware_exists(id));
366 } else {
367 assert(owner().egbase().tribes().worker_exists(id));
368 }
369 #endif
370 wares_or_workers_.remove(id, count);
371
372 // TODO(unknown): remove from global player inventory?
373 }
374
375 /**
376 * Add the warehouse to our list of warehouses.
377 * This also adds the wares in the warehouse to the economy. However, if wares
378 * are added to the warehouse in the future, add_wares() must be called.
379 */
add_warehouse(Warehouse & wh)380 void Economy::add_warehouse(Warehouse& wh) {
381 warehouses_.push_back(&wh);
382 }
383
384 /**
385 * Remove the warehouse and its wares from the economy.
386 */
remove_warehouse(Warehouse & wh)387 void Economy::remove_warehouse(Warehouse& wh) {
388 for (size_t i = 0; i < warehouses_.size(); ++i)
389 if (warehouses_[i] == &wh) {
390 warehouses_[i] = *warehouses_.rbegin();
391 warehouses_.pop_back();
392 return;
393 }
394
395 // This assert was modified, since on loading, warehouses might try to
396 // remove themselves from their own economy, though they weren't added
397 // (since they weren't initialized)
398 assert(warehouses_.empty());
399 }
400
401 /**
402 * Consider the request, try to fulfill it immediately or queue it for later.
403 * Important: This must only be called by the \ref Request class.
404 */
add_request(Request & req)405 void Economy::add_request(Request& req) {
406 assert(req.is_open());
407 assert(!has_request(req));
408
409 assert(&owner());
410
411 requests_.push_back(&req);
412
413 // Try to fulfill the request
414 start_request_timer();
415 }
416
417 /**
418 * \return true if the given Request is registered with the \ref Economy, false
419 * otherwise
420 */
has_request(Request & req)421 bool Economy::has_request(Request& req) {
422 return std::find(requests_.begin(), requests_.end(), &req) != requests_.end();
423 }
424
425 /**
426 * Remove the request from this economy.
427 * Important: This must only be called by the \ref Request class.
428 */
remove_request(Request & req)429 void Economy::remove_request(Request& req) {
430 RequestList::iterator const it = std::find(requests_.begin(), requests_.end(), &req);
431
432 if (it == requests_.end()) {
433 FORMAT_WARNINGS_OFF
434 log("WARNING: remove_request(%p) not in list\n", &req);
435 FORMAT_WARNINGS_ON
436 return;
437 }
438
439 *it = *requests_.rbegin();
440
441 requests_.pop_back();
442 }
443
444 /**
445 * Add a supply to our list of supplies.
446 */
add_supply(Supply & supply)447 void Economy::add_supply(Supply& supply) {
448 supplies_.add_supply(supply);
449 start_request_timer();
450 }
451
452 /**
453 * Remove a supply from our list of supplies.
454 */
remove_supply(Supply & supply)455 void Economy::remove_supply(Supply& supply) {
456 supplies_.remove_supply(supply);
457 }
458
459 // Minimal invasive fix of bug 1236538 and issue #3794.
460 // It does not matter which tribe this soldier has, only that all training levels are 0.
461 std::unique_ptr<Worker> Economy::soldier_prototype_(nullptr);
462 // static
soldier_prototype(const WorkerDescr * d)463 Worker& Economy::soldier_prototype(const WorkerDescr* d) {
464 if (!soldier_prototype_) {
465 if (!d) {
466 throw wexception("soldier_prototype_ not initialized and no SoldierDescr provided");
467 }
468 assert(d->type() == MapObjectType::SOLDIER);
469 soldier_prototype_.reset(&static_cast<Worker&>(d->create_object()));
470 assert(soldier_prototype_->descr().type() == MapObjectType::SOLDIER);
471 }
472 return *soldier_prototype_;
473 }
474
needs_ware_or_worker(DescriptionIndex const ware_or_worker_type) const475 bool Economy::needs_ware_or_worker(DescriptionIndex const ware_or_worker_type) const {
476 Quantity const t = target_quantity(ware_or_worker_type).permanent;
477
478 // we have a target quantity set
479 if (t > 0) {
480 Quantity quantity = 0;
481 for (const Warehouse* wh : warehouses_) {
482 quantity += type_ == wwWARE ? wh->get_wares().stock(ware_or_worker_type) :
483 wh->get_workers().stock(ware_or_worker_type);
484 if (t <= quantity) {
485 return false;
486 }
487 }
488 return true;
489 } else {
490 // Target quantity is set to 0, we need to check if there is an open request.
491 // For soldier requests, do not recruit new rookies if only heroes are needed.
492 const bool is_soldier = type_ == wwWORKER && ware_or_worker_type == owner().tribe().soldier();
493 for (const Request* req : requests_) {
494 if (req->get_type() == type_ && req->get_index() == ware_or_worker_type &&
495 req->is_open() &&
496 (!is_soldier ||
497 req->get_requirements().check(soldier_prototype(
498 owner().egbase().tribes().get_worker_descr(ware_or_worker_type))))) {
499 return true;
500 }
501 }
502 return false;
503 }
504 }
505
506 /**
507 * Add e's flags to this economy.
508 *
509 * Also transfer all wares and wares request. Try to resolve the new ware
510 * requests if possible.
511 */
merge(Economy & e)512 void Economy::merge(Economy& e) {
513 assert(e.type() == type_);
514 for (const DescriptionIndex& w_index :
515 (type_ == wwWARE ? owner_.tribe().wares() : owner_.tribe().workers())) {
516 TargetQuantity other_tq = e.target_quantities_[w_index];
517 TargetQuantity& this_tq = target_quantities_[w_index];
518 if (this_tq.last_modified < other_tq.last_modified) {
519 this_tq = other_tq;
520 }
521 }
522
523 // If the options window for e is open, but not the one for this, the user
524 // should still have an options window after the merge.
525 if (e.get_options_window() && !get_options_window()) {
526 Notifications::publish(NoteEconomy{e.serial(), serial_, NoteEconomy::Action::kMerged});
527 }
528
529 for (std::vector<Flag*>::size_type i = e.get_nrflags() + 1; --i;) {
530 assert(i == e.get_nrflags());
531
532 Flag& flag = *e.flags_[0];
533
534 e.do_remove_flag(flag); // do not delete other economy yet!
535 add_flag(flag);
536 }
537
538 // Remember that the other economy may not have been connected before the merge
539 split_checks_.insert(split_checks_.end(), e.split_checks_.begin(), e.split_checks_.end());
540 owner_.remove_economy(e.serial());
541 }
542
543 /**
544 * Split the given set of flags off into a new economy.
545 */
split(const std::set<OPtr<Flag>> & flags)546 void Economy::split(const std::set<OPtr<Flag>>& flags) {
547 assert(!flags.empty());
548
549 Economy* e = owner_.create_economy(type_);
550
551 for (const DescriptionIndex& w_index :
552 (type_ == wwWARE ? owner_.tribe().wares() : owner_.tribe().workers())) {
553 e->target_quantities_[w_index] = target_quantities_[w_index];
554 }
555
556 for (const OPtr<Flag>& temp_flag : flags) {
557 Flag& flag = *temp_flag.get(owner().egbase());
558 assert(flags_.size() > 1); // We will not be deleted in remove_flag, right?
559 remove_flag(flag);
560 e->add_flag(flag);
561 }
562
563 // As long as rebalance commands are tied to specific flags, we
564 // need this, because the flag that rebalance commands for us were
565 // tied to might have been moved into the other economy
566 start_request_timer();
567 }
568
569 /**
570 * Make sure the request timer is running.
571 * We can skip this for flagless economies (expedition ships don't need economy balancing...).
572 */
start_request_timer(int32_t const delta)573 void Economy::start_request_timer(int32_t const delta) {
574 if (!flags_.empty()) {
575 if (upcast(Game, game, &owner_.egbase())) {
576 game->cmdqueue().enqueue(
577 new CmdCallEconomyBalance(game->get_gametime() + delta, this, request_timerid_));
578 }
579 }
580 }
581
582 /**
583 * Find the supply that is best suited to fulfill the given request.
584 * \return 0 if no supply is found, the best supply otherwise
585 */
find_best_supply(Game & game,const Request & req,int32_t & cost)586 Supply* Economy::find_best_supply(Game& game, const Request& req, int32_t& cost) {
587 assert(req.is_open());
588
589 Route buf_route0, buf_route1;
590 Supply* best_supply = nullptr;
591 Route* best_route = nullptr;
592 int32_t best_cost = -1;
593 Flag& target_flag = req.target_flag();
594
595 available_supplies_.clear();
596
597 for (size_t i = 0; i < supplies_.get_nrsupplies(); ++i) {
598 Supply& supp = supplies_[i];
599
600 // Just skip if supply does not provide required ware
601 if (!supp.nr_supplies(game, req))
602 continue;
603
604 const SupplyProviders provider = supp.provider_type(&game);
605
606 // We generally ignore disponible wares on ship as it is not possible to reliably
607 // calculate route (transportation time)
608 if (provider == SupplyProviders::kShip) {
609 continue;
610 }
611
612 const Widelands::Coords provider_position =
613 supp.get_position(game)->base_flag().get_position();
614
615 const uint32_t dist = game.map().calc_distance(target_flag.get_position(), provider_position);
616
617 UniqueDistance ud = {dist, supp.get_position(game)->serial(), provider};
618
619 // std::map quarantees uniqueness, practically it means that if more wares are on the same
620 // flag, only
621 // first one will be inserted into available_supplies
622 available_supplies_.insert(std::make_pair(ud, &supplies_[i]));
623 }
624
625 // Now available supplies have been sorted by distance to requestor
626 for (auto& supplypair : available_supplies_) {
627 Supply& supp = *supplypair.second;
628
629 Route* const route = best_route != &buf_route0 ? &buf_route0 : &buf_route1;
630 // will be cleared by find_route()
631
632 if (!find_route(supp.get_position(game)->base_flag(), target_flag, route, best_cost)) {
633 if (!best_route) {
634 log("Economy::find_best_supply: %s-Economy %u of player %u: Error, COULD NOT FIND A "
635 "ROUTE!",
636 type_ ? "WORKER" : "WARE", serial_, owner_.player_number());
637 // To help to debug this a bit:
638 log(" ... ware/worker at: %3dx%3d, requestor at: %3dx%3d! Item: %s.\n",
639 supp.get_position(game)->base_flag().get_position().x,
640 supp.get_position(game)->base_flag().get_position().y, target_flag.get_position().x,
641 target_flag.get_position().y,
642 type_ == wwWARE ? game.tribes().get_ware_descr(req.get_index())->name().c_str() :
643 game.tribes().get_worker_descr(req.get_index())->name().c_str());
644 }
645 continue;
646 }
647 best_supply = &supp;
648 best_route = route;
649 best_cost = route->get_totalcost();
650 }
651
652 if (!best_route)
653 return nullptr;
654
655 cost = best_cost;
656 return best_supply;
657 }
658
659 struct RequestSupplyPair {
660 TrackPtr<Request> request;
661 TrackPtr<Supply> supply;
662 int32_t priority;
663
664 /**
665 * pairid is an explicit tie-breaker for comparison.
666 *
667 * Without it, the pair priority queue would use an implicit, system
668 * dependent tie breaker, which in turn causes desyncs.
669 */
670 uint32_t pairid;
671
672 struct Compare {
operator ()Widelands::RequestSupplyPair::Compare673 bool operator()(const RequestSupplyPair& p1, const RequestSupplyPair& p2) {
674 return p1.priority == p2.priority ? p1.pairid < p2.pairid : p1.priority < p2.priority;
675 }
676 };
677 };
678
679 using RSPairQueue = std::priority_queue<RequestSupplyPair,
680 std::vector<RequestSupplyPair>,
681 RequestSupplyPair::Compare>;
682
683 struct RSPairStruct {
684 RSPairQueue queue;
685 uint32_t pairid;
686 int32_t nexttimer;
687
RSPairStructWidelands::RSPairStruct688 RSPairStruct() : pairid(0), nexttimer(0) {
689 }
690 };
691
692 /**
693 * Walk all Requests and find potential transfer candidates.
694 */
process_requests(Game & game,RSPairStruct * supply_pairs)695 void Economy::process_requests(Game& game, RSPairStruct* supply_pairs) {
696 // Algorithm can decide that wares are not to be delivered to constructionsite
697 // right now, therefore we need to shcedule next pairing
698 bool postponed_pairing_needed = false;
699 for (Request* temp_req : requests_) {
700 Request& req = *temp_req;
701
702 // We somehow get desynced request lists that don't trigger desync
703 // alerts, so add info to the sync stream here.
704 {
705 ::StreamWrite& ss = game.syncstream();
706 ss.unsigned_8(SyncEntry::kProcessRequests);
707 ss.unsigned_8(req.get_type());
708 ss.unsigned_8(req.get_index());
709 ss.unsigned_32(req.target().serial());
710 }
711
712 int32_t cost; // estimated time in milliseconds to fulfill Request
713 Supply* const supp = find_best_supply(game, req, cost);
714
715 if (!supp)
716 continue;
717
718 if (!supp->is_active()) {
719 // Calculate the time the building will be forced to idle waiting
720 // for the request
721 int32_t const idletime = game.get_gametime() + 15000 + 2 * cost - req.get_required_time();
722 // If the building wouldn't have to idle, we wait with the request
723 if (idletime < -200) {
724 if (supply_pairs->nexttimer < 0 || supply_pairs->nexttimer > -idletime)
725 supply_pairs->nexttimer = -idletime;
726
727 continue;
728 }
729 }
730
731 int32_t const priority = req.get_priority(cost);
732 if (priority < 0) {
733 // We dont "pair" the req with supply now, and dont set s.nexttimer right now
734 // but should not forget about this productionsite waiting for the building material
735 postponed_pairing_needed = true;
736 continue;
737 }
738
739 // Otherwise, consider this request/supply pair for queueing
740 RequestSupplyPair rsp;
741 rsp.request = &req;
742 rsp.supply = supp;
743 rsp.priority = priority;
744 rsp.pairid = ++supply_pairs->pairid;
745
746 supply_pairs->queue.push(rsp);
747 }
748 if (postponed_pairing_needed && supply_pairs->nexttimer < 0) {
749 // so no other pair set the timer, so we set them now for after 30 seconds
750 supply_pairs->nexttimer = 30 * 1000;
751 }
752 }
753
754 /**
755 * Try to fulfill open requests with available supplies.
756 */
balance_requestsupply(Game & game)757 void Economy::balance_requestsupply(Game& game) {
758 RSPairStruct rsps;
759 rsps.nexttimer = -1;
760
761 // Try to fulfill Requests.
762 process_requests(game, &rsps);
763
764 // Now execute request/supply pairs.
765 while (!rsps.queue.empty()) {
766 RequestSupplyPair rsp = rsps.queue.top();
767
768 rsps.queue.pop();
769
770 if (!rsp.request || !rsp.supply || !has_request(*rsp.request) ||
771 !rsp.supply->nr_supplies(game, *rsp.request)) {
772 rsps.nexttimer = 200;
773 continue;
774 }
775
776 rsp.request->start_transfer(game, *rsp.supply);
777 rsp.request->set_last_request_time(game.get_gametime());
778
779 // for multiple wares
780 if (rsp.request && has_request(*rsp.request))
781 rsps.nexttimer = 200;
782 }
783
784 if (rsps.nexttimer > 0) { // restart the timer, if necessary
785 start_request_timer(rsps.nexttimer);
786 }
787 }
788
789 /**
790 * Check whether there is a supply for the given request. If the request is a
791 * worker request without supply, attempt to create a new worker in a warehouse.
792 */
create_requested_worker(Game & game,DescriptionIndex index)793 void Economy::create_requested_worker(Game& game, DescriptionIndex index) {
794 assert(type_ == wwWORKER);
795
796 bool soldier_level_check;
797 const TribeDescr& tribe = owner().tribe();
798 const WorkerDescr& w_desc = *tribe.get_worker_descr(index);
799 // Request mapped to demand
800 std::map<Request*, uint32_t> open_requests;
801 uint32_t total_demand = 0;
802
803 // Make a dummy soldier, which should never be assigned to any economy
804 // Minimal invasive fix of bug 1236538: never create a rookie for a request
805 // that required a hero.
806 if (upcast(const SoldierDescr, s_desc, &w_desc)) {
807 soldier_prototype(s_desc); // init prototype
808 soldier_level_check = true;
809 } else {
810 soldier_level_check = false;
811 }
812
813 for (Request* temp_req : requests_) {
814 const Request& req = *temp_req;
815
816 if (req.get_type() != wwWORKER || req.get_index() != index)
817 continue;
818
819 // need to check for each request separately, because esp. soldier
820 // requests have different specific requirements
821 if (supplies_.have_supplies(game, req))
822 continue;
823
824 // Requests for heroes should not trigger the creation of more rookies
825 if (soldier_level_check) {
826 if (!(req.get_requirements().check(soldier_prototype()))) {
827 continue;
828 }
829 }
830
831 uint32_t current_demand = req.get_open_count();
832 if (current_demand > 0) {
833 open_requests.emplace(temp_req, current_demand);
834 total_demand += current_demand;
835 }
836 }
837
838 if (total_demand == 0) {
839 assert(open_requests.empty());
840 return;
841 }
842 assert(!open_requests.empty());
843
844 // We have worker demands that are not fulfilled by supplies.
845 // Find warehouses where we can create the required workers,
846 // and collect stats about existing build prerequisites.
847 // Since the wares may be in places belonging to a different worker economy,
848 // we will request their ware economies to bring them into warehouses belonging to this worker
849 // economy.
850 const WorkerDescr::Buildcost& cost = w_desc.buildcost();
851 Quantity total_planned = 0;
852 std::map<Economy*, std::map<DescriptionIndex, Quantity>> available_wares;
853
854 for (Warehouse* wh : warehouses_) {
855 uint32_t planned = wh->get_planned_workers(game, index);
856 total_planned += planned;
857
858 while (wh->can_create_worker(game, index)) {
859 wh->create_worker(game, index);
860 --open_requests.begin()->second;
861 --total_demand;
862 if (!open_requests.begin()->second) {
863 open_requests.erase(open_requests.begin());
864 }
865 if (total_demand == 0) {
866 assert(open_requests.empty());
867 return;
868 }
869 }
870
871 Economy* eco = wh->get_economy(wwWARE);
872 for (const auto& pair : cost) {
873 DescriptionIndex di = tribe.ware_index(pair.first);
874 if (tribe.has_ware(di)) {
875 available_wares[eco][di] += eco->get_wares_or_workers().stock(di);
876 }
877 }
878 }
879
880 // Couldn't create enough workers now. Adjust the warehouses' plans to bring the wares together.
881 for (const auto& pair : available_wares) {
882 uint32_t min_workers_createable = std::numeric_limits<Quantity>::max();
883 bool plan_at_least_one = false;
884 for (const auto& costpair : cost) {
885 DescriptionIndex di = tribe.ware_index(costpair.first);
886 if (tribe.has_ware(di)) {
887 min_workers_createable =
888 std::min(min_workers_createable, pair.second.at(di) / costpair.second);
889 plan_at_least_one |= pair.first->target_quantity(di).permanent == 0;
890 } else {
891 di = tribe.safe_worker_index(costpair.first);
892 assert(tribe.has_worker(di));
893 min_workers_createable = std::max(min_workers_createable, wares_or_workers_.stock(di));
894 // TODO(Nordfriese): As long as worker buildcosts contain only wares and carriers, this
895 // is fine. Revisit this function if we ever have a worker whose buildcost contains a
896 // worker with a buildcost.
897 }
898 }
899 for (Warehouse* wh : warehouses_) {
900 if (wh->get_economy(wwWARE) == pair.first) {
901 const uint32_t planned = wh->get_planned_workers(game, index);
902 assert(total_planned >= planned);
903 uint32_t nr_to_plan = planned;
904 if (total_planned > total_demand) {
905 // Cancel some excess plans
906 nr_to_plan -= std::min(nr_to_plan, total_planned - total_demand);
907 } else if (total_planned < total_demand) {
908 // Check how many we can plan
909 if (min_workers_createable > 0) {
910 uint32_t newly_planning =
911 std::min(min_workers_createable, total_demand - total_planned);
912 min_workers_createable -= newly_planning;
913 nr_to_plan += newly_planning;
914 } else if (plan_at_least_one) {
915 // Plan at least one worker somewhere if a target quantity is 0 to trigger tool
916 // production
917 nr_to_plan = std::max(nr_to_plan, 1u);
918 plan_at_least_one = false;
919 }
920 }
921 wh->plan_workers(game, index, nr_to_plan);
922 total_planned = total_planned + nr_to_plan - planned;
923 if (total_planned == total_demand) {
924 return;
925 }
926 }
927 }
928 }
929 }
930
931 /**
932 * Walk all Requests and find requests of workers than aren't supplied. Then
933 * try to create the worker at warehouses.
934 */
create_requested_workers(Game & game)935 void Economy::create_requested_workers(Game& game) {
936 if (type_ != wwWORKER || !warehouses().size())
937 return;
938
939 for (const DescriptionIndex& worker_index : owner().tribe().workers()) {
940 if (owner().is_worker_type_allowed(worker_index) &&
941 owner().tribe().get_worker_descr(worker_index)->is_buildable()) {
942 create_requested_worker(game, worker_index);
943 }
944 }
945 }
946
947 /**
948 * Helper function for \ref handle_active_supplies
949 */
accept_warehouse_if_policy(Warehouse & wh,WareWorker type,DescriptionIndex ware,StockPolicy policy)950 static bool accept_warehouse_if_policy(Warehouse& wh,
951 WareWorker type,
952 DescriptionIndex ware,
953 StockPolicy policy) {
954 return wh.get_stock_policy(type, ware) == policy;
955 }
956
957 /**
958 * Send all active supplies (wares that are outside on the road network without
959 * being sent to a specific request) to a warehouse.
960 */
handle_active_supplies(Game & game)961 void Economy::handle_active_supplies(Game& game) {
962 if (!warehouses().size())
963 return;
964
965 using Assignments = std::vector<std::pair<Supply*, Warehouse*>>;
966 Assignments assignments;
967
968 for (uint32_t idx = 0; idx < supplies_.get_nrsupplies(); ++idx) {
969 Supply& supply = supplies_[idx];
970 if (supply.has_storage())
971 continue;
972
973 WareWorker wwtype;
974 DescriptionIndex ware;
975 supply.get_ware_type(wwtype, ware);
976 assert(wwtype == type_);
977
978 bool haveprefer = false;
979 bool havenormal = false;
980
981 // One of preferred warehouses (if any) with lowest stock of ware/worker
982 Warehouse* preferred_wh = nullptr;
983 // Stock of particular ware in preferred warehouse
984 uint32_t preferred_wh_stock = std::numeric_limits<uint32_t>::max();
985
986 for (uint32_t nwh = 0; nwh < warehouses_.size(); ++nwh) {
987 Warehouse* wh = warehouses_[nwh];
988 StockPolicy policy = wh->get_stock_policy(type_, ware);
989 if (policy == StockPolicy::kPrefer) {
990 haveprefer = true;
991
992 // Getting count of worker/ware
993 uint32_t current_stock;
994 current_stock =
995 type_ == wwWARE ? wh->get_wares().stock(ware) : wh->get_workers().stock(ware);
996 // Stocks lower then in previous one?
997 if (current_stock < preferred_wh_stock) {
998 preferred_wh = wh;
999 preferred_wh_stock = current_stock;
1000 }
1001 } else if (policy == StockPolicy::kNormal) {
1002 havenormal = true;
1003 }
1004 }
1005 if (!havenormal && !haveprefer && type_ == wwWARE) {
1006 continue;
1007 }
1008
1009 // We either have one preferred warehouse picked up or walk on roads to find nearest one
1010 Warehouse* wh = nullptr;
1011 if (preferred_wh) {
1012 wh = preferred_wh;
1013 } else {
1014 wh = find_closest_warehouse(
1015 supply.get_position(game)->base_flag(), nullptr, 0,
1016 (!havenormal) ? WarehouseAcceptFn() : [this, ware](Warehouse& w) {
1017 return accept_warehouse_if_policy(w, type_, ware, StockPolicy::kNormal);
1018 });
1019 }
1020 if (!wh) {
1021 log("Warning: Economy::handle_active_supplies "
1022 "didn't find warehouse\n");
1023 return;
1024 }
1025
1026 assignments.push_back(std::make_pair(&supply, wh));
1027 }
1028
1029 // Actually start with the transfers in a separate second phase,
1030 // to avoid potential future problems caused by the supplies_ changing
1031 // under us in some way.
1032 ::StreamWrite& ss = game.syncstream();
1033 ss.unsigned_8(SyncEntry::kHandleActiveSupplies);
1034 ss.unsigned_32(assignments.size());
1035
1036 for (const auto& temp_assignment : assignments) {
1037 ss.unsigned_32(temp_assignment.first->get_position(game)->serial());
1038 ss.unsigned_32(temp_assignment.second->serial());
1039
1040 temp_assignment.first->send_to_storage(game, temp_assignment.second);
1041 }
1042 }
1043
1044 /**
1045 * Balance Requests and Supplies by collecting and weighing pairs, and
1046 * starting transfers for them.
1047 */
balance(uint32_t const timerid)1048 void Economy::balance(uint32_t const timerid) {
1049 if (request_timerid_ != timerid) {
1050 return;
1051 }
1052 ++request_timerid_;
1053
1054 Game& game = dynamic_cast<Game&>(owner().egbase());
1055
1056 check_splits();
1057
1058 create_requested_workers(game);
1059
1060 balance_requestsupply(game);
1061
1062 handle_active_supplies(game);
1063 }
1064 } // namespace Widelands
1065