Merge lp:~widelands-dev/widelands/ai_flag_warehouse_distance into lp:widelands

Proposed by TiborB on 2019-06-07
Status: Merged
Merged at revision: 9172
Proposed branch: lp:~widelands-dev/widelands/ai_flag_warehouse_distance
Merge into: lp:widelands
Diff against target: 1700 lines (+982/-511)
8 files modified
src/ai/CMakeLists.txt (+1/-0)
src/ai/ai_help_structs.cc (+189/-119)
src/ai/ai_help_structs.h (+106/-47)
src/ai/defaultai.cc (+422/-344)
src/ai/defaultai.h (+6/-1)
src/ai/test/CMakeLists.txt (+9/-0)
src/ai/test/ai_test_main.cc (+21/-0)
src/ai/test/test_ai.cc (+228/-0)
To merge this branch: bzr merge lp:~widelands-dev/widelands/ai_flag_warehouse_distance
Reviewer Review Type Date Requested Status
hessenfarmer 2019-06-07 Approve on 2019-07-07
Review via email: mp+368544@code.launchpad.net

Commit message

Not ready for merge

Description of the change

This is just to trigger the build process

To post a comment you must log in.
9132. By TiborB on 2019-06-07

trunk merged

TiborB (tiborb95) wrote :

I dont see any build here, why?

hessenfarmer (stephan-lutz) wrote :

The appveyor builds failed you need to merge trunk first.

TiborB (tiborb95) wrote :

currently there is no new revision in trunk, so nothing to merge for now..

hessenfarmer (stephan-lutz) wrote :

Sorry overlooked you already did the merge. Seems as if Bunnybot is down again.

bunnybot (widelandsofficial) wrote :

Continuous integration builds have changed state:

Travis build 5169. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/542793848.
Appveyor build 4951. State: failed. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ai_flag_warehouse_distance-4951.

bunnybot (widelandsofficial) wrote :

Continuous integration builds have changed state:

Travis build 5174. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/544757949.
Appveyor build 4952. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ai_flag_warehouse_distance-4952.

9133. By TiborB on 2019-06-14

trunk merged

hessenfarmer (stephan-lutz) wrote :

hi, I finally found some time to test this and I believe it to be an improvement over the previous code. So I would like to see it in the game.

review: Approve
GunChleoc (gunchleoc) wrote :

I have done a preliminary code review - everything just small nits. Can you clean up the NOCOMs too and set a commit message?

9134. By TiborB on 2019-07-10

review comments incorporated

bunnybot (widelandsofficial) wrote :

Continuous integration builds have changed state:

Travis build 5261. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/556957444.
Appveyor build 5038. State: failed. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ai_flag_warehouse_distance-5038.

TiborB (tiborb95) wrote :

I forgot some comments, so another try tonight...

9135. By TiborB on 2019-07-11

further cleaning

9136. By TiborB on 2019-07-12

trunk merged

9137. By TiborB on 2019-07-12

one nocom removed

9138. By TiborB on 2019-07-22

trunk merged

bunnybot (widelandsofficial) wrote :

Continuous integration builds have changed state:

Travis build 5278. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/562425929.
Appveyor build 5053. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ai_flag_warehouse_distance-5053.

9139. By TiborB on 2019-07-24

another round of compilation issues fixes

bunnybot (widelandsofficial) wrote :

Continuous integration builds have changed state:

Travis build 5280. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/563253114.
Appveyor build 5055. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ai_flag_warehouse_distance-5055.

TiborB (tiborb95) wrote :

Failed only because of some network issues

hessenfarmer (stephan-lutz) wrote :

Technically I already approved this but I believe a C++ experet should do the final Code review. GunChleoc would be probably best to do this as she did the first round

TiborB (tiborb95) wrote :

OK, let wait then...

GunChleoc (gunchleoc) wrote :

Code review done. Mostly small tweaks to names and some efficiency stuff, and 1 real question.

TiborB (tiborb95) wrote :

See my answer.

9140. By TiborB on 2019-07-31

comments incorporated

9141. By TiborB on 2019-07-31

trunk merged

TiborB (tiborb95) wrote :

Comments implemented except one 'const', where compiler complained, probably because one of arguments was a pointer

GunChleoc (gunchleoc) wrote :

Looking good, let's have it :)

@bunnybot merge

bunnybot (widelandsofficial) wrote :

Refusing to merge, since Travis is not green. Use @bunnybot merge force for merging anyways.

Travis build 5295. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/566169834.

hessenfarmer (stephan-lutz) wrote :

transient failure on travis

@bunnybot merge force

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'src/ai/CMakeLists.txt'
2--- src/ai/CMakeLists.txt 2017-11-22 19:00:09 +0000
3+++ src/ai/CMakeLists.txt 2019-07-31 19:53:54 +0000
4@@ -24,3 +24,4 @@
5 logic_map_objects
6 scripting_lua_table
7 )
8+add_subdirectory(test)
9
10=== modified file 'src/ai/ai_help_structs.cc'
11--- src/ai/ai_help_structs.cc 2019-04-09 16:43:49 +0000
12+++ src/ai/ai_help_structs.cc 2019-07-31 19:53:54 +0000
13@@ -19,6 +19,8 @@
14
15 #include "ai/ai_help_structs.h"
16
17+#include <algorithm>
18+
19 #include "base/macros.h"
20 #include "base/time_string.h"
21 #include "logic/ai_dna_handler.h"
22@@ -27,10 +29,6 @@
23
24 namespace Widelands {
25
26-// couple of constants for calculation of road interconnections
27-constexpr int kRoadPossiblyBuildable = 200;
28-constexpr int kConnectedByRoads = 400;
29-constexpr int kNotConnectedByRoads = 600;
30 constexpr int kNoAiTrainingMutation = 200;
31 constexpr int kUpperDefaultMutationLimit = 150;
32 constexpr int kLowerDefaultMutationLimit = 75;
33@@ -307,7 +305,7 @@
34 // count of rocks can only decrease, so amount of rocks
35 // is recalculated only when previous count is positive
36 // count of water fields are stable, so if the current count is
37- // non-negative, water is not recaldulated
38+ // non-negative, water is not recalculated
39 rocks_nearby(1),
40 water_nearby(-1),
41 open_water_nearby(-1),
42@@ -974,120 +972,6 @@
43 return (blocked_fields_.count(coords.hash()) != 0);
44 }
45
46-// As a policy, we just set some default value, that will be updated later on
47-FlagsForRoads::Candidate::Candidate(uint32_t coords, int32_t distance, bool different_economy)
48- : coords_hash(coords), air_distance(distance) {
49- new_road_possible = false;
50- // Just custom values
51- new_road_length = kRoadPossiblyBuildable;
52- current_road_length = (different_economy) ? kNotConnectedByRoads : kConnectedByRoads;
53-}
54-
55-// Used when sorting cadidate flags from best one
56-bool FlagsForRoads::Candidate::operator<(const Candidate& other) const {
57- const int32_t other_rs = other.reduction_score();
58- const int32_t this_rs = reduction_score();
59- return std::tie(other.new_road_possible, other_rs) < std::tie(new_road_possible, this_rs);
60-}
61-
62-bool FlagsForRoads::Candidate::operator==(const Candidate& other) const {
63- return coords_hash == other.coords_hash;
64-}
65-
66-int32_t FlagsForRoads::Candidate::reduction_score() const {
67- return current_road_length - new_road_length - (new_road_length - air_distance) / 3;
68-}
69-
70-void FlagsForRoads::print() { // this is for debugging and development purposes
71- for (auto& candidate_flag : flags_queue) {
72- log(" %starget: %3dx%3d, saving: %5d (%3d), air distance: %3d, new road: %6d, score: %5d "
73- "%s\n",
74- (candidate_flag.reduction_score() >= min_reduction && candidate_flag.new_road_possible) ?
75- "+" :
76- " ",
77- Coords::unhash(candidate_flag.coords_hash).x,
78- Coords::unhash(candidate_flag.coords_hash).y,
79- candidate_flag.current_road_length - candidate_flag.new_road_length, min_reduction,
80- candidate_flag.air_distance, candidate_flag.new_road_length,
81- candidate_flag.reduction_score(),
82- (candidate_flag.new_road_possible) ? ", new road possible" : " ");
83- }
84-}
85-
86-// Queue is ordered but some target flags are only estimations so we take such a candidate_flag
87-// first
88-bool FlagsForRoads::get_best_uncalculated(uint32_t* winner) {
89- for (auto& candidate_flag : flags_queue) {
90- if (!candidate_flag.new_road_possible) {
91- *winner = candidate_flag.coords_hash;
92- return true;
93- }
94- }
95- return false;
96-}
97-
98-// Road from starting flag to this flag can be built
99-void FlagsForRoads::road_possible(Widelands::Coords coords, const uint32_t new_road) {
100- for (auto& candidate_flag : flags_queue) {
101- if (candidate_flag.coords_hash == coords.hash()) {
102- candidate_flag.new_road_length = new_road;
103- candidate_flag.new_road_possible = true;
104- candidate_flag.reduction_score();
105- return;
106- }
107- }
108- NEVER_HERE();
109-}
110-
111-// find_reachable_fields returns duplicates so we deal with them
112-bool FlagsForRoads::has_candidate(const uint32_t hash) {
113- for (auto& candidate_flag : flags_queue) {
114- if (candidate_flag.coords_hash == hash) {
115- return true;
116- }
117- }
118- return false;
119-}
120-
121-// Updating walking distance into flags_queue
122-void FlagsForRoads::set_cur_road_distance(Widelands::Coords coords, int32_t cur_distance) {
123- for (auto& candidate_flag : flags_queue) {
124- if (candidate_flag.coords_hash == coords.hash()) {
125- candidate_flag.current_road_length = cur_distance;
126- candidate_flag.reduction_score();
127- return;
128- }
129- }
130-}
131-
132-// Returns mostly best candidate, as a result of sorting
133-bool FlagsForRoads::get_winner(uint32_t* winner_hash) {
134- // If AI can ask for 2nd position, but there is only one viable candidate
135- // we return the first one of course
136- bool has_winner = false;
137- for (auto candidate_flag : flags_queue) {
138- if (candidate_flag.reduction_score() < min_reduction || !candidate_flag.new_road_possible ||
139- candidate_flag.new_road_length * 2 > candidate_flag.current_road_length) {
140- continue;
141- }
142- assert(candidate_flag.air_distance > 0);
143- assert(candidate_flag.reduction_score() >= min_reduction);
144- assert(candidate_flag.new_road_possible);
145- *winner_hash = candidate_flag.coords_hash;
146- has_winner = true;
147-
148- if (std::rand() % 4 > 0) {
149- // with probability of 3/4 we accept this flag
150- return true;
151- }
152- }
153-
154- if (has_winner) {
155- return true;
156- }
157- return false;
158-}
159-
160 PlayersStrengths::PlayersStrengths() : update_time(0) {
161 }
162
163@@ -1417,4 +1301,190 @@
164 return update_time;
165 }
166
167+FlagWarehouseDistances::FlagInfo::FlagInfo(const uint32_t gametime,
168+ const uint16_t dist,
169+ const uint32_t wh) {
170+ expiry_time = gametime + kFlagDistanceExpirationPeriod;
171+ soft_expiry_time = gametime + kFlagDistanceExpirationPeriod / 2;
172+ distance = dist;
173+ nearest_warehouse = wh;
174+ new_road_prohibited_till = 0;
175+}
176+FlagWarehouseDistances::FlagInfo::FlagInfo() {
177+ expiry_time = 0;
178+ distance = 1000;
179+ new_road_prohibited_till = 0;
180+}
181+
182+// We are updating the distance info, but not all the time.
183+// Always if after soft expiration period, but
184+// if below expiration period only when the new value is lower than current one
185+// In both cases new expiration times are calculated
186+bool FlagWarehouseDistances::FlagInfo::update(const uint32_t gametime,
187+ const uint16_t new_distance,
188+ const uint32_t nearest_wh) {
189+ const uint32_t new_expiry_time = gametime + kFlagDistanceExpirationPeriod;
190+
191+ if (gametime > soft_expiry_time) {
192+ distance = new_distance;
193+ expiry_time = new_expiry_time;
194+ soft_expiry_time = gametime + kFlagDistanceExpirationPeriod / 2;
195+ nearest_warehouse = nearest_wh;
196+ return true;
197+ } else if (new_distance < distance || (new_distance == distance &&
198+ expiry_time < new_expiry_time)) {
199+ distance = new_distance;
200+ expiry_time = new_expiry_time;
201+ nearest_warehouse = nearest_wh;
202+ return true;
203+ }
204+ return false;
205+}
206+
207+uint16_t FlagWarehouseDistances::FlagInfo::get(const uint32_t gametime, uint32_t* nw) const {
208+ *nw = nearest_warehouse;
209+ if (gametime <= expiry_time) {
210+ return distance;
211+ }
212+ return kFarButReachable;
213+}
214+
215+void FlagWarehouseDistances::FlagInfo::set_road_built(const uint32_t gametime) {
216+ // Prohibiting for next 60 seconds
217+ new_road_prohibited_till = gametime + 60 * 1000;
218+}
219+
220+bool FlagWarehouseDistances::FlagInfo::is_road_prohibited(const uint32_t gametime) const {
221+ return new_road_prohibited_till > gametime;
222+}
223+
224+bool FlagWarehouseDistances::set_distance(const uint32_t flag_coords,
225+ const uint16_t distance,
226+ uint32_t const gametime,
227+ uint32_t const nearest_warehouse) {
228+ if (flags_map.count(flag_coords) == 0) {
229+ flags_map[flag_coords] =
230+ FlagWarehouseDistances::FlagInfo(gametime, distance, nearest_warehouse);
231+ return true;
232+ }
233+ return flags_map[flag_coords].update(gametime, distance, nearest_warehouse);
234+}
235+
236+uint16_t FlagWarehouseDistances::count() const {
237+ return flags_map.size();
238+}
239+
240+int16_t
241+FlagWarehouseDistances::get_distance(const uint32_t flag_coords, uint32_t gametime, uint32_t* nw) {
242+ if (flags_map.count(flag_coords) == 0) {
243+ *nw = 0;
244+ return kFarButReachable; // this is to discourage to build second road from brand new flag...
245+ } else {
246+ return flags_map[flag_coords].get(gametime, nw);
247+ }
248+}
249+
250+void FlagWarehouseDistances::set_road_built(const uint32_t coords_hash, const uint32_t gametime) {
251+ if (flags_map.count(coords_hash) == 1) {
252+ flags_map[coords_hash].set_road_built(gametime);
253+ }
254+}
255+
256+bool FlagWarehouseDistances::is_road_prohibited(const uint32_t coords_hash,
257+ const uint32_t gametime) {
258+ if (flags_map.count(coords_hash) == 1) {
259+ return flags_map[coords_hash].is_road_prohibited(gametime);
260+ }
261+ return false;
262+}
263+
264+bool FlagWarehouseDistances::remove_old_flag(uint32_t gametime) {
265+ for (std::map<uint32_t, FlagWarehouseDistances::FlagInfo>::iterator it = flags_map.begin();
266+ it != flags_map.end(); it++) {
267+ if (it->second.expiry_time + kOldFlagRemoveTime < gametime) {
268+ it = flags_map.erase(it);
269+ return true;
270+ }
271+ }
272+ return false;
273+}
274+
275+// Returns pointer to winning road, provided that the treshold is exceeded
276+FlagCandidates::Candidate* FlagCandidates::get_winner(const int16_t threshold) {
277+ if (flags_.empty()) {
278+ return nullptr;
279+ }
280+ sort();
281+ if (flags_[0].score() < threshold) {
282+ return nullptr;
283+ }
284+ if (!flags_[0].is_buildable()) {
285+ return nullptr;
286+ }
287+ return &flags_[0];
288+}
289+
290+FlagCandidates::Candidate::Candidate(
291+ const uint32_t c_hash, bool different_eco, uint16_t start_f_dist, uint16_t act_dist_to_wh, uint16_t air_dst) {
292+ coords_hash = c_hash;
293+ different_economy = different_eco;
294+ start_flag_dist_to_wh = start_f_dist;
295+ flag_to_flag_road_distance = 0;
296+ possible_road_distance = kFarButReachable;
297+ cand_flag_distance_to_wh = act_dist_to_wh;
298+ air_distance = air_dst;
299+}
300+
301+int16_t FlagCandidates::Candidate::score() const {
302+ return different_economy * 2000 + (start_flag_dist_to_wh - cand_flag_distance_to_wh) +
303+ (flag_to_flag_road_distance - 2 * possible_road_distance);
304+}
305+
306+bool FlagCandidates::set_road_possible(const uint32_t coords_hash, const uint16_t steps) {
307+ for (auto& item : flags_) {
308+ if (item.coords_hash == coords_hash) {
309+ item.possible_road_distance = steps;
310+ return true;
311+ }
312+ }
313+ return false;
314+}
315+
316+bool FlagCandidates::set_cur_road_distance(const uint32_t coords, uint16_t dist) {
317+ for (auto& item : flags_) {
318+ if (item.coords_hash == coords) {
319+ item.flag_to_flag_road_distance = dist;
320+ return true;
321+ }
322+ }
323+ return false;
324+}
325+void FlagCandidates::sort() {
326+ std::sort(flags_.begin(), flags_.end());
327+}
328+
329+void FlagCandidates::sort_by_air_distance() {
330+ std::sort(flags_.begin(), flags_.end(),
331+ [](const FlagCandidates::Candidate& lf, const FlagCandidates::Candidate& rf) {
332+ return lf.air_distance < rf.air_distance;
333+ });
334+}
335+
336+void FlagCandidates::add_flag(const uint32_t coords,
337+ const bool different_economy,
338+ const uint16_t act_dist_to_wh,
339+ const uint16_t air_distance) {
340+ flags_.push_back(
341+ Candidate(coords, different_economy, start_flag_dist_to_wh, act_dist_to_wh, air_distance));
342+}
343+
344+bool FlagCandidates::has_candidate(const uint32_t coords_hash) const {
345+ for (auto& item : flags_) {
346+ if (item.coords_hash == coords_hash) {
347+ return true;
348+ }
349+ }
350+ return false;
351+}
352+
353 } // namespace Widelands
354
355=== modified file 'src/ai/ai_help_structs.h'
356--- src/ai/ai_help_structs.h 2019-05-25 08:20:22 +0000
357+++ src/ai/ai_help_structs.h 2019-07-31 19:53:54 +0000
358@@ -20,6 +20,7 @@
359 #ifndef WL_AI_AI_HELP_STRUCTS_H
360 #define WL_AI_AI_HELP_STRUCTS_H
361
362+#include <algorithm>
363 #include <list>
364 #include <queue>
365 #include <unordered_set>
366@@ -107,6 +108,7 @@
367 kCheckEnemySites,
368 kManagementUpdate,
369 kUpdateStats,
370+ kWarehouseFlagDist,
371 kUnset
372 };
373
374@@ -122,9 +124,20 @@
375 // TODO(tiborb): this should be replaced by command line switch
376 constexpr int kFNeuronBitSize = 32;
377 constexpr int kMutationRatePosition = 42;
378+// This is expiration time for distance from a flag to nearest warehouse
379+constexpr int kFlagDistanceExpirationPeriod = 120 * 1000;
380+// If the distance of flag-warehouse was not updated for this time, we presume that the flag
381+// does not exist anymore and remove it
382+constexpr int kOldFlagRemoveTime = 5 * 60 * 1000;
383
384 constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();
385
386+constexpr uint32_t kNoField = std::numeric_limits<uint32_t>::max();
387+
388+constexpr uint32_t kOneMinute = 60 * 1000;
389+
390+constexpr uint16_t kFarButReachable = 1000;
391+
392 struct CheckStepRoadAI {
393 CheckStepRoadAI(Player* const pl, uint8_t const mc, bool const oe);
394
395@@ -527,8 +540,10 @@
396 };
397
398 struct WarehouseSiteObserver {
399+
400 Widelands::Warehouse* site;
401 BuildingObserver* bo;
402+ uint32_t flag_distances_last_update;
403 };
404
405 struct ShipObserver {
406@@ -766,53 +781,6 @@
407 std::map<uint32_t, uint32_t> blocked_fields_;
408 };
409
410-// list of candidate flags to build roads, with some additional logic
411-struct FlagsForRoads {
412-
413- explicit FlagsForRoads(int32_t mr) : min_reduction(mr) {
414- }
415-
416- struct Candidate {
417- Candidate();
418- Candidate(uint32_t coords, int32_t distance, bool different_economy);
419-
420- uint32_t coords_hash;
421- int32_t new_road_length;
422- int32_t current_road_length;
423- int32_t air_distance;
424-
425- bool new_road_possible;
426-
427- bool operator<(const Candidate& other) const;
428- bool operator==(const Candidate& other) const;
429- int32_t reduction_score() const;
430- };
431-
432- int32_t min_reduction;
433- // This is the core of this object - candidate flags to be ordered by air_distance
434- std::deque<Candidate> flags_queue;
435-
436- void add_flag(Widelands::Coords coords, int32_t air_dist, bool different_economy) {
437- flags_queue.push_back(Candidate(coords.hash(), air_dist, different_economy));
438- }
439-
440- uint32_t count() {
441- return flags_queue.size();
442- }
443- bool has_candidate(uint32_t hash);
444-
445- // This is for debugging and development purposes
446- void print();
447- // during processing we need to pick first one uprocessed flag (with best score so far)
448- bool get_best_uncalculated(uint32_t* winner);
449- // When we test candidate flag if road can be built to it, there are two possible outcomes:
450- void road_possible(Widelands::Coords coords, uint32_t new_road);
451- // Updating walking distance over existing roads
452- void set_cur_road_distance(Widelands::Coords coords, int32_t cur_distance);
453- // Finally we query the flag that we will build a road to
454- bool get_winner(uint32_t* winner_hash);
455-};
456-
457 // This is a struct that stores strength of players, info on teams and provides some outputs from
458 // these data
459 struct PlayersStrengths {
460@@ -891,6 +859,97 @@
461 PlayerNumber this_player_number;
462 PlayerNumber this_player_team;
463 };
464+
465+// This is a wrapper around map of <Flag coords hash:distance from flag to nearest warehouse>
466+// Flags does not have observers so this stuct server like "lazy" substitution for this, where
467+// keys are hash of flags positions
468+// This "lives" during entire "session", and is not saved, but is easily recalulated
469+struct FlagWarehouseDistances {
470+private:
471+ struct FlagInfo {
472+ FlagInfo();
473+ FlagInfo(uint32_t, uint16_t, uint32_t);
474+ // Distance to a nearest warehouse expires, but in two stages
475+ // This is complete expiration and such flag is treated as without distance to WH
476+ uint32_t expiry_time;
477+ // When recalculating new distance, if the current information is younger than
478+ // soft_expiry_time it is only decreased if new value is smaller After soft_expiry_time is
479+ // updated in any case
480+ uint32_t soft_expiry_time;
481+ uint16_t distance;
482+ // This is coords hash of nearest warehouse, not used by now
483+ uint32_t nearest_warehouse;
484+ // after building of new road, the distance information is updated not immediately so
485+ // we prohibit current flag from another road building...
486+ uint32_t new_road_prohibited_till;
487+
488+ bool update(uint32_t, uint16_t, uint32_t);
489+ // Saying the road was built and when
490+ void set_road_built(uint32_t);
491+ // Asking if road can be built from this flag (providing current gametime)
492+ bool is_road_prohibited(uint32_t) const;
493+ // get current distance (providing current gametime)
494+ uint16_t get(uint32_t, uint32_t*) const;
495+ };
496+ std::map<uint32_t, FlagInfo> flags_map;
497+
498+public:
499+ // All these function uses lookup in flags_map so first argument is usually flag coords hash
500+ bool set_distance(uint32_t flag_coords, uint16_t distance, uint32_t gametime, uint32_t nearest_warehouse);
501+ int16_t get_distance(uint32_t flag_coords, uint32_t gametime, uint32_t* nw);
502+ void set_road_built(uint32_t coords_hash, uint32_t gametime);
503+ bool is_road_prohibited(uint32_t coords_hash, uint32_t gametime);
504+ uint16_t count() const;
505+ bool remove_old_flag(uint32_t gametime);
506+};
507+
508+// This is one-time structure - initiated and filled up when investigating possible roads to be
509+// built to a flag. At the end the flags are scored based on gained info), ordered and if treshold is
510+// achieved the road is to be built
511+struct FlagCandidates {
512+
513+ explicit FlagCandidates(uint16_t wd) : start_flag_dist_to_wh(wd) {
514+ }
515+
516+ struct Candidate {
517+ Candidate() = delete;
518+ Candidate(uint32_t, bool, uint16_t, uint16_t, uint16_t);
519+ uint16_t air_distance;
520+ uint32_t coords_hash;
521+ bool different_economy;
522+ uint16_t start_flag_dist_to_wh;
523+ uint16_t flag_to_flag_road_distance;
524+ uint16_t possible_road_distance;
525+ uint16_t cand_flag_distance_to_wh;
526+ // Scoring is considering multiple things
527+ int16_t score() const;
528+ bool is_buildable() {
529+ return possible_road_distance > 0;
530+ }
531+ bool operator<(const Candidate& other) const {
532+ return score() > other.score();
533+ }
534+ };
535+
536+private:
537+ std::vector<Candidate> flags_;
538+ uint16_t start_flag_dist_to_wh;
539+
540+public:
541+ const std::vector<Candidate>& flags() const {
542+ return flags_;
543+ }
544+ bool has_candidate(uint32_t) const;
545+ void add_flag(uint32_t, bool, uint16_t, uint16_t);
546+ bool set_cur_road_distance(uint32_t, uint16_t);
547+ bool set_road_possible(uint32_t, uint16_t);
548+ void sort();
549+ void sort_by_air_distance();
550+ uint32_t count() {
551+ return flags_.size();
552+ }
553+ FlagCandidates::Candidate* get_winner(const int16_t = 0);
554+};
555 } // namespace Widelands
556
557 #endif // end of include guard: WL_AI_AI_HELP_STRUCTS_H
558
559=== modified file 'src/ai/defaultai.cc'
560--- src/ai/defaultai.cc 2019-05-26 11:39:41 +0000
561+++ src/ai/defaultai.cc 2019-07-31 19:53:54 +0000
562@@ -331,7 +331,7 @@
563 set_taskpool_task_time(gametime + 1000, SchedulerTaskId::kRoadCheck);
564 // testing 5 roads
565 {
566- const int32_t roads_to_check = (roads.size() < 20) ? 1 : 3;
567+ const int32_t roads_to_check = roads.size() / 30 + 1;
568 for (int j = 0; j < roads_to_check; j += 1) {
569 // improve_roads function will test one road and rotate roads vector
570 if (improve_roads(gametime)) {
571@@ -486,6 +486,10 @@
572 update_player_stat(gametime);
573 set_taskpool_task_time(gametime + kStatUpdateInterval, SchedulerTaskId::kUpdateStats);
574 break;
575+ case SchedulerTaskId::kWarehouseFlagDist:
576+ check_flag_distances(gametime);
577+ set_taskpool_task_time(gametime + kFlagWarehouseUpdInterval, SchedulerTaskId::kWarehouseFlagDist);
578+ break;
579 case SchedulerTaskId::kUnset:
580 NEVER_HERE();
581 }
582@@ -958,6 +962,9 @@
583 taskPool.push_back(SchedulerTask(
584 std::max<uint32_t>(gametime, 10 * 1000), SchedulerTaskId::kUpdateStats, 15, "review"));
585
586+ taskPool.push_back(SchedulerTask(
587+ std::max<uint32_t>(gametime, 10 * 1000), SchedulerTaskId::kWarehouseFlagDist, 5, "Flag-Warehouse Update"));
588+
589 const Map& map = game().map();
590
591 // here we scan entire map for own ships
592@@ -1053,7 +1060,7 @@
593 kExpeditionMinDuration +
594 static_cast<double>(off) * (kExpeditionMaxDuration - kExpeditionMinDuration) / scope;
595 log(" %d: expedition max duration = %u (%u minutes), map area root: %u\n", player_number(),
596- expedition_max_duration / 1000, expedition_max_duration / 60000, map_area_root);
597+ expedition_max_duration / 1000, expedition_max_duration / kOneMinute, map_area_root);
598 assert(expedition_max_duration >= kExpeditionMinDuration);
599 assert(expedition_max_duration <= kExpeditionMaxDuration);
600
601@@ -3422,6 +3429,70 @@
602 return true;
603 }
604
605+
606+// Re-calculating warehouse to flag distances
607+void DefaultAI::check_flag_distances(const uint32_t gametime) {
608+ for (WarehouseSiteObserver& wh_obs : warehousesites) {
609+ uint16_t checked_flags = 0;
610+ const uint32_t this_wh_hash = wh_obs.site->get_position().hash();
611+ uint32_t highest_distance_set = 0;
612+
613+ std::queue<Widelands::Flag*>
614+ remaining_flags; // only used to collect flags reachable walk over roads
615+ remaining_flags.push(&wh_obs.site->base_flag());
616+ flag_warehouse_distance.set_distance(
617+ wh_obs.site->base_flag().get_position().hash(), 0, gametime, this_wh_hash);
618+ uint32_t tmp_wh;
619+ assert(flag_warehouse_distance.get_distance(
620+ wh_obs.site->base_flag().get_position().hash(), gametime, &tmp_wh) == 0);
621+
622+ // Algorithm to walk on roads
623+ // All nodes are marked as to_be_checked == true first and once the node is checked it is
624+ // changed to false. Under some conditions, the same node can be checked twice, the
625+ // to_be_checked can be set back to true. Because less hoops (fewer flag-to-flag roads) does
626+ // not always mean shortest road.
627+ while (!remaining_flags.empty()) {
628+ ++checked_flags;
629+ // looking for a node with shortest existing road distance from starting flag and one that
630+ // has to be checked Now going over roads leading from this flag
631+ const uint16_t current_flag_distance = flag_warehouse_distance.get_distance(
632+ remaining_flags.front()->get_position().hash(), gametime, &tmp_wh);
633+ for (uint8_t i = 1; i <= 6; ++i) {
634+ Road* const road = remaining_flags.front()->get_road(i);
635+
636+ if (!road) {
637+ continue;
638+ }
639+
640+ Flag* endflag = &road->get_flag(Road::FlagStart);
641+
642+ if (endflag == remaining_flags.front()) {
643+ endflag = &road->get_flag(Road::FlagEnd);
644+ }
645+ const uint16_t steps_count = road->get_path().get_nsteps();
646+
647+ // Calculated distance can be used or ignored if f.e. longer than via other route
648+ bool const updated = flag_warehouse_distance.set_distance(
649+ endflag->get_position().hash(), current_flag_distance + steps_count, gametime,
650+ this_wh_hash);
651+
652+ if (highest_distance_set < current_flag_distance + steps_count) {
653+ highest_distance_set = current_flag_distance + steps_count;
654+ }
655+
656+ if (updated) {
657+ remaining_flags.push(endflag);
658+ }
659+ }
660+ remaining_flags.pop();
661+ }
662+
663+ }
664+
665+ // Now let do some lazy pruning - remove the flags that were not updated for long
666+ flag_warehouse_distance.remove_old_flag(gametime);
667+}
668+
669 // Here we pick about 25 roads and investigate them. If it is a dead end we dismantle it
670 bool DefaultAI::dismantle_dead_ends() {
671 bool road_dismantled = false;
672@@ -3538,50 +3609,36 @@
673 }
674
675 bool is_warehouse = false;
676- bool has_building = false;
677 if (Building* b = flag.get_building()) {
678- has_building = true;
679 BuildingObserver& bo = get_building_observer(b->descr().name().c_str());
680 if (bo.type == BuildingObserver::Type::kWarehouse) {
681 is_warehouse = true;
682 }
683 }
684+ const uint32_t flag_coords_hash = flag.get_position().hash();
685
686- // is connected to a warehouse?
687+ if (flag_warehouse_distance.is_road_prohibited(flag_coords_hash, gametime)) {return false;}
688 const bool needs_warehouse = flag.get_economy()->warehouses().empty();
689
690- if (!has_building && flag.nr_of_roads() == 1) {
691- return false;
692- } else if (is_warehouse && flag.nr_of_roads() <= 3) {
693- // Do nothing
694- } else if (needs_warehouse) {
695- // Do nothing
696- } else if (flag.current_wares() > 5) {
697- // Do nothing
698- } else if (has_building && std::rand() % 3 == 0) {
699- // Do nothing
700- } else if (std::rand() % 10 == 0) {
701- // Do nothing
702- } else {
703- return false;
704- }
705-
706- int16_t expected_shortcut = 27;
707- if (has_building) {
708- expected_shortcut -= 3;
709- }
710- expected_shortcut -= flag.current_wares() * 3;
711- if (is_warehouse) {
712- expected_shortcut -= 10;
713- }
714- if (std::rand() % 5 == 0) {
715- expected_shortcut -= 10;
716- }
717- expected_shortcut -= 2 * flag.nr_of_roads();
718-
719- create_shortcut_road(flag, 14, expected_shortcut, gametime);
720-
721- return true;
722+ uint32_t tmp_wh;
723+
724+ // when deciding if we attempt to build a road from here we use probability
725+ uint16_t probability_score = 0;
726+ if (flag.nr_of_roads() == 1) {probability_score += 20;}
727+ if (is_warehouse && flag.nr_of_roads() <= 3) {probability_score += 20;}
728+ probability_score += flag.current_wares() * 5;
729+ if (needs_warehouse) {probability_score += 500;}
730+ if (std::rand() % 10 == 0) {
731+ probability_score += flag_warehouse_distance.get_distance(flag_coords_hash, gametime, &tmp_wh);
732+ }
733+
734+ if (std::rand() % 200 < probability_score) {
735+ create_shortcut_road(flag, 14, gametime);
736+ return true;
737+ }
738+
739+ return false;
740+
741 }
742
743 // This function takes a road (road is smallest section of roads with two flags on the ends)
744@@ -3756,318 +3813,339 @@
745 // connection is not known
746 bool DefaultAI::create_shortcut_road(const Flag& flag,
747 uint16_t checkradius,
748- int16_t min_reduction,
749 uint32_t gametime) {
750
751- // Increasing the failed_connection_tries counter
752- // At the same time it indicates a time an economy is without a warehouse
753- EconomyObserver* eco = get_economy_observer(flag.economy());
754- // if we passed grace time this will be last attempt and if it fails
755- // building is destroyes
756- bool last_attempt_ = false;
757-
758- // this should not happen, but if the economy has a warehouse and a dismantle
759- // grace time set, we must 'zero' the dismantle grace time
760- if (!flag.get_economy()->warehouses().empty() &&
761- eco->dismantle_grace_time != std::numeric_limits<uint32_t>::max()) {
762- eco->dismantle_grace_time = std::numeric_limits<uint32_t>::max();
763- }
764-
765- // first we deal with situations when this is economy with no warehouses
766- // and this is a flag belonging to a building/constructionsite
767- // such economy must get dismantle grace time (if not set yet)
768- // end sometimes extended checkradius
769- if (flag.get_economy()->warehouses().empty() && flag.get_building()) {
770-
771- // occupied military buildings get special treatment
772- // (extended grace time + longer radius)
773- bool occupied_military_ = false;
774- Building* b = flag.get_building();
775- if (upcast(MilitarySite, militb, b)) {
776- if (militb->soldier_control()->stationed_soldiers().size() > 0) {
777- occupied_military_ = true;
778- }
779- }
780-
781- // check if we are within grace time, if not or gracetime unset we need to do something
782- // if we are within gracetime we do nothing (this loop is skipped)
783-
784- // if grace time is not set, this is probably first time without a warehouse and we must set
785- // it
786- if (eco->dismantle_grace_time == std::numeric_limits<uint32_t>::max()) {
787-
788- // constructionsites
789- if (upcast(ConstructionSite const, constructionsite, flag.get_building())) {
790- BuildingObserver& bo =
791- get_building_observer(constructionsite->building().name().c_str());
792- // first very special case - a port (in the phase of constructionsite)
793- // this might be a new colonization port
794- if (bo.is(BuildingAttribute::kPort)) {
795- eco->dismantle_grace_time = gametime + 60 * 60 * 1000; // one hour should be enough
796- } else { // other constructionsites, usually new (standalone) constructionsites
797- eco->dismantle_grace_time =
798- gametime + 30 * 1000 + // very shot time is enough
799- (eco->flags.size() * 30 * 1000); // + 30 seconds for every flag in economy
800- }
801-
802- // buildings
803- } else {
804-
805- if (occupied_military_) {
806- eco->dismantle_grace_time =
807- (gametime + 90 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
808-
809- } else { // for other normal buildings
810- eco->dismantle_grace_time =
811- gametime + (45 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
812- }
813- }
814-
815- // we have passed grace_time - it is time to dismantle
816- } else if (eco->dismantle_grace_time <= gametime) {
817- last_attempt_ = true;
818- // we increase a check radius in last attempt
819- checkradius += 2;
820- }
821-
822- // and bonus for occupied military buildings:
823- if (occupied_military_) {
824- checkradius += 4;
825- }
826-
827- // and generally increase radius for unconnected buildings
828- checkradius += 2;
829- }
830-
831- // Now own roadfinding stuff
832- const Map& map = game().map();
833-
834- // initializing new object of FlagsForRoads, we will push there all candidate flags
835- // First we dont even know if a road can be built there (from current flag)
836- Widelands::FlagsForRoads RoadCandidates(min_reduction);
837-
838- FindNodeWithFlagOrRoad functor;
839- CheckStepRoadAI check(player_, MOVECAPS_WALK, true);
840-
841- // get all flags within radius
842- std::vector<Coords> reachable;
843- map.find_reachable_fields(
844- Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius), &reachable, check, functor);
845-
846- for (const Coords& reachable_coords : reachable) {
847-
848- // ignore starting flag, of course
849- if (reachable_coords == flag.get_position()) {
850- continue;
851- }
852-
853- // first make sure there is an immovable (should be, but still)
854- if (upcast(PlayerImmovable const, player_immovable, map[reachable_coords].get_immovable())) {
855-
856- // if it is the road, make a flag there
857- if (dynamic_cast<const Road*>(map[reachable_coords].get_immovable())) {
858- game().send_player_build_flag(player_number(), reachable_coords);
859- }
860-
861- // do not go on if it is not a flag
862- if (!dynamic_cast<const Flag*>(map[reachable_coords].get_immovable())) {
863- continue;
864- }
865-
866- // testing if a flag/road's economy has a warehouse, if not we are not
867- // interested to connect to it
868- if (player_immovable->economy().warehouses().size() == 0) {
869- continue;
870- }
871-
872- // This is a candidate, sending all necessary info to RoadCandidates
873- const bool different_economy = (player_immovable->get_economy() != flag.get_economy());
874- const int32_t air_distance = map.calc_distance(flag.get_position(), reachable_coords);
875- if (!RoadCandidates.has_candidate(reachable_coords.hash())) {
876- RoadCandidates.add_flag(reachable_coords, air_distance, different_economy);
877- }
878- }
879- }
880-
881- // now we walk over roads and if field is reachable by roads, we change the distance assigned
882- // above
883- std::map<uint32_t, NearFlag> nearflags; // only used to collect flags reachable walk over roads
884- nearflags[flag.get_position().hash()] = NearFlag(&flag, 0);
885-
886- // Algorithm to walk on roads
887- // All nodes are marked as to_be_checked == true first and once the node is checked it is changed
888- // to false. Under some conditions, the same node can be checked twice, the to_be_checked can
889- // be set back to true. Because less hoops (fewer flag-to-flag roads) does not always mean
890- // shortest
891- // road.
892- for (;;) {
893- // looking for a node with shortest existing road distance from starting flag and one that has
894- // to be checked
895- uint32_t start_field = std::numeric_limits<uint32_t>::max();
896- uint32_t nearest_distance = 10000;
897- for (auto item : nearflags) {
898- if (item.second.current_road_distance < nearest_distance && item.second.to_be_checked) {
899- nearest_distance = item.second.current_road_distance;
900- start_field = item.first;
901- }
902- }
903- // OK, we failed to find a NearFlag where to_be_checked == true, so quitting the loop now
904- if (start_field == std::numeric_limits<uint32_t>::max()) {
905- break;
906- }
907-
908- nearflags[start_field].to_be_checked = false;
909-
910- // Now going over roads leading from this flag
911- for (uint8_t i = 1; i <= 6; ++i) {
912- Road* const road = nearflags[start_field].flag->get_road(i);
913-
914- if (!road) {
915- continue;
916- }
917-
918- Flag* endflag = &road->get_flag(Road::FlagStart);
919-
920- if (endflag == nearflags[start_field].flag) {
921- endflag = &road->get_flag(Road::FlagEnd);
922- }
923-
924- const uint32_t endflag_hash = endflag->get_position().hash();
925-
926- const int32_t dist = map.calc_distance(flag.get_position(), endflag->get_position());
927-
928- if (dist > checkradius + 2) { // Testing bigger vicinity then checkradius....
929- continue;
930- }
931-
932- // There is few scenarios for this neighbour flag
933- if (nearflags.count(endflag_hash) == 0) {
934- // This is brand new flag
935- nearflags[endflag_hash] =
936- NearFlag(endflag, nearflags[start_field].current_road_distance +
937- road->get_path().get_nsteps());
938- } else {
939- // We know about this flag already
940- if (nearflags[endflag_hash].current_road_distance >
941- nearflags[start_field].current_road_distance + road->get_path().get_nsteps()) {
942- // ..but this current connection is shorter than one found before
943- nearflags[endflag_hash].current_road_distance =
944- nearflags[start_field].current_road_distance + road->get_path().get_nsteps();
945- // So let re-check neighbours once more
946- nearflags[endflag_hash].to_be_checked = true;
947- }
948- }
949- }
950- }
951-
952- // Sending calculated walking costs from nearflags to RoadCandidates to update info on
953- // Candidate flags/roads
954- for (auto& nf_walk : nearflags) {
955- // NearFlag contains also flags beyond check radius, these are not relevent for us
956- if (RoadCandidates.has_candidate(nf_walk.second.flag->get_position().hash())) {
957- RoadCandidates.set_cur_road_distance(
958- nf_walk.second.flag->get_position(), nf_walk.second.current_road_distance);
959- }
960- }
961-
962- // Here we must consider how much are buildable fields lacking
963- // the number will be transformed to a weight passed to findpath function
964- int32_t fields_necessity = 0;
965- if (spots_ < kSpotsTooLittle) {
966- fields_necessity += 10;
967- }
968- if (map_allows_seafaring_ && num_ports == 0) {
969- fields_necessity += 10;
970- }
971- if (num_ports < 4) {
972- fields_necessity += 5;
973- }
974- if (spots_ < kSpotsEnough) {
975- fields_necessity += 5;
976- }
977- fields_necessity *= std::abs(management_data.get_military_number_at(64)) * 5;
978-
979- // We need to sort these flags somehow, because we are not going to investigate all of them
980- // so sorting first by current road length (that might contain fake values for flags that were
981- // not reached over roads) and secondary by air_distance (nearer flags first)
982- std::sort(std::begin(RoadCandidates.flags_queue), std::end(RoadCandidates.flags_queue),
983- [](const FlagsForRoads::Candidate& a, const FlagsForRoads::Candidate& b) {
984- // Here we are doing a kind of bucketing
985- const int32_t a_length = a.current_road_length / 50;
986- const int32_t b_length = b.current_road_length / 50;
987- return std::tie(b_length, a.air_distance) < std::tie(a_length, b.air_distance);
988- });
989-
990- // Now we calculate roads from here to few best looking RoadCandidates....
991- uint32_t possible_roads_count = 0;
992- uint32_t current = 0; // hash of flag that we are going to calculate in the iteration
993- while (possible_roads_count < 5 && RoadCandidates.get_best_uncalculated(&current)) {
994- const Widelands::Coords coords = Coords::unhash(current);
995- Path path;
996-
997- // value of pathcost is not important, it just indicates, that the path can be built
998- // We send this information to RoadCandidates, with length of possible road if applicable
999- const int32_t pathcost =
1000- map.findpath(flag.get_position(), coords, 0, path, check, 0, fields_necessity);
1001- if (pathcost >= 0) {
1002- RoadCandidates.road_possible(coords, path.get_nsteps());
1003- possible_roads_count += 1;
1004- }
1005- }
1006-
1007- // re-sorting again, now by reduction score (custom operator specified in .h file)
1008- std::sort(std::begin(RoadCandidates.flags_queue), std::end(RoadCandidates.flags_queue));
1009-
1010- // Well and finally building the winning road (if any)
1011- uint32_t winner_hash = 0;
1012- if (RoadCandidates.get_winner(&winner_hash)) {
1013- const Widelands::Coords target_coords = Coords::unhash(winner_hash);
1014- Path& path = *new Path();
1015+ // Increasing the failed_connection_tries counter
1016+ // At the same time it indicates a time an economy is without a warehouse
1017+ EconomyObserver* eco = get_economy_observer(flag.economy());
1018+ // if we passed grace time this will be last attempt and if it fails
1019+ // building is destroyed
1020+ bool last_attempt_ = false;
1021+
1022+ // this should not happen, but if the economy has a warehouse and a dismantle
1023+ // grace time set, we must 'zero' the dismantle grace time
1024+ if (!flag.get_economy()->warehouses().empty() &&
1025+ eco->dismantle_grace_time != kNever) {
1026+ eco->dismantle_grace_time = kNever;
1027+ }
1028+
1029+ // first we deal with situations when this is economy with no warehouses
1030+ // and this is a flag belonging to a building/constructionsite
1031+ // such economy must get dismantle grace time (if not set yet)
1032+ // end sometimes extended checkradius
1033+ if (flag.get_economy()->warehouses().empty() && flag.get_building()) {
1034+
1035+ // occupied military buildings get special treatment
1036+ // (extended grace time + longer radius)
1037+ bool occupied_military_ = false;
1038+ Building* b = flag.get_building();
1039+ if (upcast(MilitarySite, militb, b)) {
1040+ if (militb->soldier_control()->stationed_soldiers().size() > 0) {
1041+ occupied_military_ = true;
1042+ }
1043+ }
1044+
1045+ // check if we are within grace time, if not or gracetime unset we need to do something
1046+ // if we are within gracetime we do nothing (this loop is skipped)
1047+
1048+ // if grace time is not set, this is probably first time without a warehouse and we must set
1049+ // it
1050+ if (eco->dismantle_grace_time == kNever) {
1051+
1052+ // constructionsites
1053+ if (upcast(ConstructionSite const, constructionsite, flag.get_building())) {
1054+ BuildingObserver& bo =
1055+ get_building_observer(constructionsite->building().name().c_str());
1056+ // first very special case - a port (in the phase of constructionsite)
1057+ // this might be a new colonization port
1058+ if (bo.is(BuildingAttribute::kPort)) {
1059+ eco->dismantle_grace_time = gametime + 60 * 60 * 1000; // one hour should be enough
1060+ } else { // other constructionsites, usually new (standalone) constructionsites
1061+ eco->dismantle_grace_time =
1062+ gametime + 30 * 1000 + // very shot time is enough
1063+ (eco->flags.size() * 30 * 1000); // + 30 seconds for every flag in economy
1064+ }
1065+
1066+ // buildings
1067+ } else {
1068+
1069+ if (occupied_military_) {
1070+ eco->dismantle_grace_time =
1071+ (gametime + 90 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
1072+
1073+ } else { // for other normal buildings
1074+ eco->dismantle_grace_time =
1075+ gametime + (45 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
1076+ }
1077+ }
1078+
1079+ // we have passed grace_time - it is time to dismantle
1080+ } else if (eco->dismantle_grace_time <= gametime) {
1081+ last_attempt_ = true;
1082+ // we increase a check radius in last attempt
1083+ checkradius += 2;
1084+ }
1085+
1086+ // and bonus for occupied military buildings:
1087+ if (occupied_military_) {
1088+ checkradius += 4;
1089+ }
1090+
1091+ // and generally increase radius for unconnected buildings
1092+ checkradius += 2;
1093+ }
1094+
1095+ // Now own roadfinding stuff
1096+ const Map& map = game().map();
1097+
1098+ // Initializing new object of FlagsForRoads, we will push there all candidate flags
1099+ // First we dont even know if a road can be built there (from current flag)
1100+ // Adding also distance of this flag to nearest wh
1101+ uint32_t tmp_wh; // This information is not used, but we need it
1102+ const uint32_t current_flag_dist_to_wh = flag_warehouse_distance.
1103+ get_distance(flag.get_position().hash(), gametime, &tmp_wh);
1104+
1105+ FlagCandidates flag_candidates(current_flag_dist_to_wh);
1106+
1107+ FindNodeWithFlagOrRoad functor;
1108+ CheckStepRoadAI check(player_, MOVECAPS_WALK, true);
1109+
1110+ // get all flags within radius
1111+ std::vector<Coords> reachable;
1112+ map.find_reachable_fields(
1113+ Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius), &reachable, check, functor);
1114+
1115+ for (const Coords& reachable_coords : reachable) {
1116+
1117+ // ignore starting flag, of course
1118+ if (reachable_coords == flag.get_position()) {
1119+ continue;
1120+ }
1121+
1122+ const uint32_t reachable_coords_hash = reachable_coords.hash();
1123+
1124+ // first make sure there is an immovable (should be, but still)
1125+ Widelands::BaseImmovable* this_immovable = map[reachable_coords].get_immovable();
1126+ if (upcast(PlayerImmovable const, player_immovable, this_immovable)) {
1127+
1128+ // if it is the road, make a flag there
1129+ if (this_immovable->descr().type() == MapObjectType::ROAD) {
1130+ game().send_player_build_flag(player_number(), reachable_coords);
1131+ }
1132+
1133+ // do not go on if it is not a flag
1134+ if (this_immovable->descr().type() != MapObjectType::FLAG) {
1135+ continue;
1136+ }
1137+
1138+ // testing if a flag/road's economy has a warehouse, if not we are not
1139+ // interested to connect to it
1140+ if (player_immovable->economy().warehouses().size() == 0) {
1141+ continue;
1142+ }
1143+
1144+ // This is a candidate, sending all necessary info to RoadCandidates
1145+ const bool is_different_economy = (player_immovable->get_economy() != flag.get_economy());
1146+ const uint16_t air_distance = map.calc_distance(flag.get_position(), reachable_coords);
1147+
1148+ if (!flag_candidates.has_candidate(reachable_coords_hash) && !flag_warehouse_distance.is_road_prohibited(reachable_coords_hash, gametime)) {
1149+ flag_candidates.add_flag(reachable_coords_hash, is_different_economy,
1150+ flag_warehouse_distance.get_distance(reachable_coords_hash, gametime, &tmp_wh), air_distance);
1151+ }
1152+ }
1153+ }
1154+
1155+ // now we walk over roads and if field is reachable by roads, we change the distance assigned
1156+ // above
1157+ std::map<uint32_t, NearFlag> nearflags; // only used to collect flags reachable walk over roads
1158+ nearflags[flag.get_position().hash()] = NearFlag(&flag, 0);
1159+
1160+ collect_nearflags(nearflags, flag, checkradius);
1161+
1162+ // Sending calculated walking costs from nearflags to RoadCandidates to update info on
1163+ // Candidate flags/roads
1164+ for (auto& nf_walk : nearflags) {
1165+ const uint32_t nf_hash = nf_walk.second.flag->get_position().hash();
1166+ // NearFlag contains also flags beyond check radius, these are not relevant for us
1167+ if (flag_candidates.has_candidate(nf_hash)) {
1168+ flag_candidates.set_cur_road_distance(
1169+ nf_hash, nf_walk.second.current_road_distance);
1170+ }
1171+ }
1172+
1173+ // Here we must consider how much are buildable fields lacking
1174+ // the number will be transformed to a weight passed to findpath function
1175+ int32_t fields_necessity = 0;
1176+ if (spots_ < kSpotsTooLittle) {
1177+ fields_necessity += 10;
1178+ }
1179+ if (map_allows_seafaring_ && num_ports == 0) {
1180+ fields_necessity += 10;
1181+ }
1182+ if (num_ports < 4) {
1183+ fields_necessity += 5;
1184+ }
1185+ if (spots_ < kSpotsEnough) {
1186+ fields_necessity += 5;
1187+ }
1188+
1189+ fields_necessity *= std::abs(management_data.get_military_number_at(64)) * 5;
1190+
1191+ // Now we calculate roads from here to few best looking RoadCandidates....
1192+ flag_candidates.sort_by_air_distance();
1193+ uint32_t possible_roads_count = 0;
1194+ for (const auto &flag_candidate : flag_candidates.flags()) {
1195+ if (possible_roads_count > 10) {break;}
1196+ const Widelands::Coords coords = Coords::unhash(flag_candidate.coords_hash);
1197+ Path path;
1198+
1199+ // value of pathcost is not important, it just indicates, that the path can be built
1200+ // We send this information to RoadCandidates, with length of possible road if applicable
1201+ const int32_t pathcost =
1202+ map.findpath(flag.get_position(), coords, 0, path, check, 0, fields_necessity);
1203+ if (pathcost >= 0) {
1204+ flag_candidates.set_road_possible(flag_candidate.coords_hash, path.get_nsteps());
1205+ ++possible_roads_count;
1206+ }
1207+ }
1208+
1209+ // re-sorting again now by default by a score
1210+ flag_candidates.sort();
1211+
1212+
1213+ // Well and finally building the winning road (if any)
1214+ const int32_t winner_min_score = (spots_ < kSpotsTooLittle) ? 50 : 25;
1215+
1216+ FlagCandidates::Candidate* winner = flag_candidates.get_winner(winner_min_score);
1217+ if (winner) {
1218+ const Widelands::Coords target_coords = Coords::unhash(winner->coords_hash);
1219+
1220+ // This is to prohibit the flag for some time but with exemption of warehouse
1221+ if (flag_warehouse_distance.get_distance(winner->coords_hash, gametime, &tmp_wh) > 0) {
1222+ flag_warehouse_distance.set_road_built(winner->coords_hash, gametime);
1223+ }
1224+ // and we straight away set distance of future flag
1225+ flag_warehouse_distance.set_distance(flag.get_position().hash(), winner->start_flag_dist_to_wh + winner->possible_road_distance,
1226+ gametime, 0); // faking the warehouse
1227+
1228+ Path& path = *new Path();
1229 #ifndef NDEBUG
1230- const int32_t pathcost =
1231- map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
1232- assert(pathcost >= 0);
1233+ const int32_t pathcost =
1234+ map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
1235+ assert(pathcost >= 0);
1236 #else
1237- map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
1238+ map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
1239 #endif
1240- game().send_player_build_road(player_number(), path);
1241- return true;
1242- }
1243- // We can't build a road so let's block the vicinity as an indication this area is not
1244- // connectible
1245- // Usually we block for 2 minutes, but if it is a last attempt we block for 10 minutes
1246- // Note: we block the vicinity only if this economy (usually a sole flag with a building) is not
1247- // connected to a warehouse
1248- if (flag.get_economy()->warehouses().empty()) {
1249-
1250- // blocking only if latest block was less then 60 seconds ago or it is last attempt
1251- if (eco->fields_block_last_time + 60000 < gametime || last_attempt_) {
1252- eco->fields_block_last_time = gametime;
1253-
1254- const uint32_t block_time = last_attempt_ ? 10 * 60 * 1000 : 2 * 60 * 1000;
1255-
1256- FindNodeAcceptAll buildable_functor;
1257- CheckStepOwnTerritory check_own(player_, MOVECAPS_WALK, true);
1258-
1259- // get all flags within radius
1260- std::vector<Coords> reachable_to_block;
1261- map.find_reachable_fields(Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius),
1262- &reachable_to_block, check_own, buildable_functor);
1263-
1264- for (auto coords : reachable_to_block) {
1265- blocked_fields.add(coords, game().get_gametime() + block_time);
1266- }
1267- }
1268-
1269- // If it last attempt we also destroy the flag (with a building if any attached)
1270- if (last_attempt_) {
1271- remove_from_dqueue<Widelands::Flag>(eco->flags, &flag);
1272- game().send_player_bulldoze(*const_cast<Flag*>(&flag));
1273- dead_ends_check_ = true;
1274- return true;
1275- }
1276- }
1277- return false;
1278+ game().send_player_build_road(player_number(), path);
1279+ return true;
1280+ }
1281+ // We can't build a road so let's block the vicinity as an indication this area is not
1282+ // connectible
1283+ // Usually we block for 2 minutes, but if it is a last attempt we block for 10 minutes
1284+ // Note: we block the vicinity only if this economy (usually a sole flag with a building) is not
1285+ // connected to a warehouse
1286+ if (flag.get_economy()->warehouses().empty()) {
1287+
1288+ // blocking only if latest block was less then 60 seconds ago or it is last attempt
1289+ if (eco->fields_block_last_time + kOneMinute < gametime || last_attempt_) {
1290+ eco->fields_block_last_time = gametime;
1291+
1292+ const uint32_t block_time = last_attempt_ ? 10 * kOneMinute : 2 * kOneMinute;
1293+
1294+ FindNodeAcceptAll buildable_functor;
1295+ CheckStepOwnTerritory check_own(player_, MOVECAPS_WALK, true);
1296+
1297+ // get all flags within radius
1298+ std::vector<Coords> reachable_to_block;
1299+ map.find_reachable_fields(Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius),
1300+ &reachable_to_block, check_own, buildable_functor);
1301+
1302+ for (auto coords : reachable_to_block) {
1303+ blocked_fields.add(coords, game().get_gametime() + block_time);
1304+ }
1305+ }
1306+
1307+ // If it last attempt we also destroy the flag (with a building if any attached)
1308+ if (last_attempt_) {
1309+ remove_from_dqueue<Widelands::Flag>(eco->flags, &flag);
1310+ game().send_player_bulldoze(*const_cast<Flag*>(&flag));
1311+ dead_ends_check_ = true;
1312+ return true;
1313+ }
1314+ }
1315+ return false;
1316+}
1317+
1318+void DefaultAI::collect_nearflags(std::map<uint32_t, NearFlag> &nearflags, const Flag& flag, const uint16_t checkradius) {
1319+ // Algorithm to walk on roads
1320+ // All nodes are marked as to_be_checked == true first and once the node is checked it is changed
1321+ // to false. Under some conditions, the same node can be checked twice, the to_be_checked can
1322+ // be set back to true. Because less hoops (fewer flag-to-flag roads) does not always mean
1323+ // shortest road.
1324+
1325+ const Map& map = game().map();
1326+
1327+ for (;;) {
1328+ // looking for a node with shortest existing road distance from starting flag and one that has
1329+ // to be checked
1330+ uint32_t start_field = kNoField;
1331+ uint32_t nearest_distance = 10000;
1332+ for (auto item : nearflags) {
1333+ if (item.second.current_road_distance < nearest_distance && item.second.to_be_checked) {
1334+ nearest_distance = item.second.current_road_distance;
1335+ start_field = item.first;
1336+ }
1337+ }
1338+ // OK, we failed to find a NearFlag where to_be_checked == true, so quitting the loop now
1339+ if (start_field == kNoField) {
1340+ break;
1341+ }
1342+
1343+ nearflags[start_field].to_be_checked = false;
1344+
1345+ // Now going over roads leading from this flag
1346+ for (uint8_t i = 1; i <= 6; ++i) {
1347+ Road* const road = nearflags[start_field].flag->get_road(i);
1348+
1349+ if (!road) {
1350+ continue;
1351+ }
1352+
1353+ Flag* endflag = &road->get_flag(Road::FlagStart);
1354+
1355+ if (endflag == nearflags[start_field].flag) {
1356+ endflag = &road->get_flag(Road::FlagEnd);
1357+ }
1358+
1359+ const uint32_t endflag_hash = endflag->get_position().hash();
1360+
1361+ const int32_t dist = map.calc_distance(flag.get_position(), endflag->get_position());
1362+
1363+ if (dist > checkradius + 2) { // Testing bigger vicinity then checkradius....
1364+ continue;
1365+ }
1366+
1367+ // There is few scenarios for this neighbour flag
1368+ if (nearflags.count(endflag_hash) == 0) {
1369+ // This is brand new flag
1370+ // calculating diff how much closer we will get to the flag
1371+ nearflags[endflag_hash] =
1372+ NearFlag(endflag, nearflags[start_field].current_road_distance +
1373+ road->get_path().get_nsteps());
1374+ } else {
1375+ // We know about this flag already
1376+ if (nearflags[endflag_hash].current_road_distance >
1377+ nearflags[start_field].current_road_distance + road->get_path().get_nsteps()) {
1378+ // ..but this current connection is shorter than one found before
1379+ nearflags[endflag_hash].current_road_distance =
1380+ nearflags[start_field].current_road_distance + road->get_path().get_nsteps();
1381+ // So let re-check neighbours once more
1382+ nearflags[endflag_hash].to_be_checked = true;
1383+ }
1384+ }
1385+ }
1386+ }
1387+
1388 }
1389
1390 /**
1391
1392=== modified file 'src/ai/defaultai.h'
1393--- src/ai/defaultai.h 2019-05-15 06:29:24 +0000
1394+++ src/ai/defaultai.h 2019-07-31 19:53:54 +0000
1395@@ -148,6 +148,7 @@
1396 static constexpr int32_t kSpotsTooLittle = 15;
1397 static constexpr int kManagementUpdateInterval = 10 * 60 * 1000;
1398 static constexpr int kStatUpdateInterval = 60 * 1000;
1399+ static constexpr int kFlagWarehouseUpdInterval = 15 * 1000;
1400
1401 // For vision and scheduling
1402 static constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();
1403@@ -198,11 +199,14 @@
1404 bool improve_roads(uint32_t);
1405 bool create_shortcut_road(const Widelands::Flag&,
1406 uint16_t maxcheckradius,
1407- int16_t minReduction,
1408 const uint32_t gametime);
1409 // trying to identify roads that might be removed
1410 bool dispensable_road_test(const Widelands::Road&);
1411 bool dismantle_dead_ends();
1412+ void collect_nearflags(std::map<uint32_t, Widelands::NearFlag> &, const Widelands::Flag&, const uint16_t);
1413+ // calculating distances from local warehouse to flags
1414+ void check_flag_distances(uint32_t);
1415+ Widelands::FlagWarehouseDistances flag_warehouse_distance;
1416
1417 bool check_economies();
1418 bool check_productionsites(uint32_t);
1419@@ -272,6 +276,7 @@
1420 bool check_ships(uint32_t);
1421 bool attempt_escape(Widelands::ShipObserver& so);
1422
1423+
1424 // finding and owner
1425 Widelands::PlayerNumber get_land_owner(const Widelands::Map&, uint32_t);
1426
1427
1428=== added directory 'src/ai/test'
1429=== added file 'src/ai/test/CMakeLists.txt'
1430--- src/ai/test/CMakeLists.txt 1970-01-01 00:00:00 +0000
1431+++ src/ai/test/CMakeLists.txt 2019-07-31 19:53:54 +0000
1432@@ -0,0 +1,9 @@
1433+wl_test(test_ai
1434+ SRCS
1435+ ai_test_main.cc
1436+ test_ai.cc
1437+ DEPENDS
1438+ base_log
1439+ base_macros
1440+ ai
1441+)
1442
1443=== added file 'src/ai/test/ai_test_main.cc'
1444--- src/ai/test/ai_test_main.cc 1970-01-01 00:00:00 +0000
1445+++ src/ai/test/ai_test_main.cc 2019-07-31 19:53:54 +0000
1446@@ -0,0 +1,21 @@
1447+/*
1448+ * Copyright (C) 2007-2019 by the Widelands Development Team
1449+ *
1450+ * This program is free software; you can redistribute it and/or
1451+ * modify it under the terms of the GNU General Public License
1452+ * as published by the Free Software Foundation; either version 2
1453+ * of the License, or (at your option) any later version.
1454+ *
1455+ * This program is distributed in the hope that it will be useful,
1456+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
1457+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1458+ * GNU General Public License for more details.
1459+ *
1460+ * You should have received a copy of the GNU General Public License
1461+ * along with this program; if not, write to the Free Software
1462+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
1463+ *
1464+ */
1465+
1466+#define BOOST_TEST_MODULE AI
1467+#include <boost/test/unit_test.hpp>
1468
1469=== added file 'src/ai/test/test_ai.cc'
1470--- src/ai/test/test_ai.cc 1970-01-01 00:00:00 +0000
1471+++ src/ai/test/test_ai.cc 2019-07-31 19:53:54 +0000
1472@@ -0,0 +1,228 @@
1473+/*
1474+ * Copyright (C) 2007-2019 by the Widelands Development Team
1475+ *
1476+ * This program is free software; you can redistribute it and/or
1477+ * modify it under the terms of the GNU General Public License
1478+ * as published by the Free Software Foundation; either version 2
1479+ * of the License, or (at your option) any later version.
1480+ *
1481+ * This program is distributed in the hope that it will be useful,
1482+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
1483+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1484+ * GNU General Public License for more details.
1485+ *
1486+ * You should have received a copy of the GNU General Public License
1487+ * along with this program; if not, write to the Free Software
1488+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
1489+ *
1490+ */
1491+
1492+#include <exception>
1493+
1494+#include <boost/test/unit_test.hpp>
1495+
1496+#ifdef _WIN32
1497+#include "base/log.h"
1498+#endif
1499+#include "ai/ai_help_structs.h"
1500+#include "base/macros.h"
1501+
1502+// Triggered by BOOST_AUTO_TEST_CASE
1503+CLANG_DIAG_OFF("-Wdisabled-macro-expansion")
1504+
1505+namespace Widelands { // Needed?
1506+class World;
1507+} // namespace Widelands
1508+
1509+using namespace Widelands;
1510+
1511+BOOST_AUTO_TEST_SUITE(ai)
1512+
1513+BOOST_AUTO_TEST_CASE(flag_distance_soft_expiry) {
1514+ FlagWarehouseDistances fw;
1515+ uint32_t tmp_wh;
1516+ BOOST_CHECK_EQUAL(fw.get_distance(0, 0, &tmp_wh), 1000);
1517+ BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
1518+ BOOST_CHECK_EQUAL(fw.get_distance(1, 2, &tmp_wh), 2); // distance now 2
1519+ BOOST_CHECK_EQUAL(tmp_wh, 3);
1520+
1521+ // setting longer distance below soft_expiry time
1522+ BOOST_CHECK_EQUAL(fw.set_distance(1, 3, kFlagDistanceExpirationPeriod / 3, 4), false);
1523+ // distance to 3 not updated
1524+ BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod / 3, &tmp_wh), 2);
1525+ BOOST_CHECK_EQUAL(tmp_wh, 3);
1526+
1527+ // now setting after soft expiry
1528+ BOOST_CHECK_EQUAL(
1529+ fw.set_distance(1, 1, kFlagDistanceExpirationPeriod / 3, 6), true); // distance set to 1
1530+ BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod / 3, &tmp_wh), 1);
1531+ BOOST_CHECK_EQUAL(tmp_wh, 6);
1532+}
1533+BOOST_AUTO_TEST_CASE(flag_distance_below_expiry)
1534+/* Compare with void free_test_function() */
1535+{
1536+ FlagWarehouseDistances fw;
1537+ uint32_t tmp_wh;
1538+ BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
1539+
1540+ // setting longer distance after soft but below expiry time
1541+ BOOST_CHECK_EQUAL(fw.set_distance(1, 3, kFlagDistanceExpirationPeriod * 2 / 3, 5), true);
1542+ BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod * 2 / 3, &tmp_wh), 3);
1543+ BOOST_CHECK_EQUAL(tmp_wh, 5);
1544+}
1545+
1546+BOOST_AUTO_TEST_CASE(flag_distance_after_expiry)
1547+/* Compare with void free_test_function() */
1548+{
1549+ FlagWarehouseDistances fw;
1550+ uint32_t tmp_wh;
1551+ BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
1552+
1553+ // setting longer distance below expiry time
1554+ BOOST_CHECK_EQUAL(fw.set_distance(1, 3, 2 * kFlagDistanceExpirationPeriod, 5), true);
1555+ BOOST_CHECK_EQUAL(fw.get_distance(1, 3, &tmp_wh), 3);
1556+ BOOST_CHECK_EQUAL(tmp_wh, 5);
1557+}
1558+
1559+BOOST_AUTO_TEST_CASE(flag_distance_expiration_extension)
1560+/* setting the same distance restart the expiry_period */
1561+{
1562+ FlagWarehouseDistances fw;
1563+ uint32_t tmp_wh;
1564+ BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
1565+ BOOST_CHECK_EQUAL(
1566+ fw.set_distance(1, 2, 0, 3), false); // cannot reset the same distance in the same time
1567+
1568+ // Now we are after expiration time
1569+ BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod + 3, &tmp_wh), 1000);
1570+
1571+ // setting distance 2 time shortly one after another
1572+ BOOST_CHECK_EQUAL(fw.set_distance(1, 2, kFlagDistanceExpirationPeriod + 3, 5), true);
1573+ BOOST_CHECK_EQUAL(fw.set_distance(1, 2, kFlagDistanceExpirationPeriod + 10, 5), true);
1574+ // current expiry_time should be 2*kFlagDistanceExpirationPeriod + 10
1575+ BOOST_CHECK_EQUAL(fw.get_distance(1, 2 * kFlagDistanceExpirationPeriod, &tmp_wh), 2);
1576+ BOOST_CHECK_EQUAL(tmp_wh, 5);
1577+ BOOST_CHECK_EQUAL(fw.get_distance(1, 2 * kFlagDistanceExpirationPeriod + 15, &tmp_wh), 1000);
1578+}
1579+
1580+BOOST_AUTO_TEST_CASE(flag_distance_road_builtexpiration_extension)
1581+/* setting the same distance restart the expiry_period */
1582+{
1583+ FlagWarehouseDistances fw;
1584+ // No road built on fresh flag
1585+ BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
1586+ // get_distance(const uint32_t flag_coords, uint32_t gametime, uint32_t* nw)
1587+
1588+ // setting road we dont know about
1589+ fw.set_road_built(1, 0);
1590+ BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
1591+
1592+ // let fw knows about it
1593+ fw.set_distance(1, 2, 0, 3);
1594+ fw.set_road_built(1, 0);
1595+ BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), true);
1596+ BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 59999), true);
1597+ BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 60001), false);
1598+
1599+ BOOST_CHECK_EQUAL(fw.is_road_prohibited(2, 60001), false);
1600+}
1601+
1602+BOOST_AUTO_TEST_CASE(flag_distance_old_removal)
1603+/* setting the same distance restart the expiry_period */
1604+{
1605+ FlagWarehouseDistances fw;
1606+ fw.set_distance(1, 2, 0, 3);
1607+ BOOST_CHECK_EQUAL(fw.count(), 1);
1608+ BOOST_CHECK_EQUAL(fw.remove_old_flag(kOldFlagRemoveTime + kFlagDistanceExpirationPeriod), false);
1609+ BOOST_CHECK_EQUAL(fw.count(), 1);
1610+ BOOST_CHECK_EQUAL(
1611+ fw.remove_old_flag(kOldFlagRemoveTime + kFlagDistanceExpirationPeriod + 2), true);
1612+ BOOST_CHECK_EQUAL(fw.count(), 0);
1613+}
1614+
1615+BOOST_AUTO_TEST_CASE(new_flag_road_not_prohibited)
1616+/* setting the same distance restart the expiry_period */
1617+{
1618+ FlagWarehouseDistances fw;
1619+ // let fw knows about it
1620+ BOOST_CHECK_EQUAL(fw.count(), 0);
1621+ fw.set_distance(1, 2, 0, 3);
1622+ BOOST_CHECK_EQUAL(fw.count(), 1);
1623+ BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
1624+}
1625+
1626+BOOST_AUTO_TEST_CASE(flag_candidate_init)
1627+/* setting the same distance restart the expiry_period */
1628+{
1629+ FlagCandidates fc = FlagCandidates(10);
1630+ BOOST_CHECK_EQUAL(fc.count(), 0);
1631+}
1632+
1633+BOOST_AUTO_TEST_CASE(flag_candidate_winner_score) {
1634+ const uint16_t kCurFlDistToWh = 3;
1635+ const uint16_t kStartFlagToWh = 10;
1636+
1637+ const uint16_t kPosRoadDist = 5;
1638+ const uint16_t kCurRoadDistFlToFl = 17;
1639+
1640+ const uint32_t kTestedCoords = 11;
1641+
1642+ FlagCandidates fc = FlagCandidates(kStartFlagToWh);
1643+
1644+ // coord, different economy, distance to wh
1645+ fc.add_flag(kTestedCoords, false, kCurFlDistToWh, 1);
1646+ // setting coords, dist
1647+ BOOST_CHECK_EQUAL(fc.set_cur_road_distance(kTestedCoords, kCurRoadDistFlToFl), true);
1648+ BOOST_CHECK_EQUAL(
1649+ fc.set_cur_road_distance(1, 5), false); // we cannot set distance to unknown flag
1650+ BOOST_CHECK(!fc.get_winner()); // road not possible
1651+ // set length of possible road
1652+ BOOST_CHECK_EQUAL(fc.set_road_possible(kTestedCoords, kPosRoadDist), true);
1653+ BOOST_VERIFY(fc.get_winner());
1654+ BOOST_CHECK_EQUAL(fc.get_winner()->start_flag_dist_to_wh, kStartFlagToWh);
1655+ BOOST_CHECK_EQUAL(fc.get_winner()->cand_flag_distance_to_wh, kCurFlDistToWh);
1656+ BOOST_CHECK_EQUAL(fc.get_winner()->flag_to_flag_road_distance, kCurRoadDistFlToFl);
1657+ BOOST_CHECK_EQUAL(fc.get_winner()->possible_road_distance, kPosRoadDist);
1658+ BOOST_CHECK_EQUAL(fc.get_winner()->coords_hash, kTestedCoords);
1659+ BOOST_CHECK_EQUAL(fc.get_winner()->different_economy, false);
1660+
1661+ BOOST_CHECK_EQUAL(fc.get_winner()->score(),
1662+ +(kStartFlagToWh - kCurFlDistToWh) + (kCurRoadDistFlToFl - 2 * kPosRoadDist));
1663+}
1664+BOOST_AUTO_TEST_CASE(flag_candidates_sorting) {
1665+ FlagCandidates fc = FlagCandidates(10);
1666+
1667+ fc.add_flag(0, false, 10, 1);
1668+ fc.add_flag(1, false, 10, 1);
1669+ fc.add_flag(2, false, 10, 1);
1670+ BOOST_CHECK_EQUAL(fc.set_cur_road_distance(0, 5), true);
1671+ BOOST_CHECK_EQUAL(fc.set_cur_road_distance(1, 5), true);
1672+ BOOST_CHECK_EQUAL(fc.set_cur_road_distance(2, 5), true);
1673+ BOOST_CHECK_EQUAL(fc.set_road_possible(0, 4), true);
1674+ BOOST_CHECK_EQUAL(fc.set_road_possible(1, 2), true);
1675+ BOOST_CHECK_EQUAL(fc.set_road_possible(2, 3), true);
1676+ BOOST_CHECK_EQUAL(fc.get_winner()->coords_hash, 1); // sorted done automatically
1677+ BOOST_CHECK_EQUAL(fc.count(), 3);
1678+}
1679+
1680+BOOST_AUTO_TEST_CASE(flag_sort_by_air_distance) {
1681+ FlagCandidates fc = FlagCandidates(10);
1682+
1683+ fc.add_flag(0, false, 10, 4);
1684+ fc.add_flag(1, false, 10, 1);
1685+ fc.add_flag(2, false, 10, 2);
1686+ fc.sort_by_air_distance();
1687+ BOOST_CHECK_EQUAL(fc.flags()[0].air_distance, 1);
1688+}
1689+
1690+BOOST_AUTO_TEST_CASE(flag_has_candidate) {
1691+ FlagCandidates fc = FlagCandidates(10);
1692+
1693+ fc.add_flag(0, false, 10, 4);
1694+ fc.add_flag(1, false, 10, 1);
1695+ fc.add_flag(2, false, 10, 2);
1696+ BOOST_CHECK_EQUAL(fc.has_candidate(1), true);
1697+ BOOST_CHECK_EQUAL(fc.has_candidate(3), false);
1698+}
1699+
1700+BOOST_AUTO_TEST_SUITE_END()