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

Proposed by TiborB
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 Approve
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

trunk merged

Revision history for this message
TiborB (tiborb95) wrote :

I dont see any build here, why?

Revision history for this message
hessenfarmer (stephan-lutz) wrote :

The appveyor builds failed you need to merge trunk first.

Revision history for this message
TiborB (tiborb95) wrote :

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

Revision history for this message
hessenfarmer (stephan-lutz) wrote :

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

Revision history for this message
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.

Revision history for this message
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

trunk merged

Revision history for this message
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
Revision history for this message
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

review comments incorporated

Revision history for this message
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.

Revision history for this message
TiborB (tiborb95) wrote :

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

9135. By TiborB

further cleaning

9136. By TiborB

trunk merged

9137. By TiborB

one nocom removed

9138. By TiborB

trunk merged

Revision history for this message
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

another round of compilation issues fixes

Revision history for this message
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.

Revision history for this message
TiborB (tiborb95) wrote :

Failed only because of some network issues

Revision history for this message
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

Revision history for this message
TiborB (tiborb95) wrote :

OK, let wait then...

Revision history for this message
GunChleoc (gunchleoc) wrote :

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

Revision history for this message
TiborB (tiborb95) wrote :

See my answer.

9140. By TiborB

comments incorporated

9141. By TiborB

trunk merged

Revision history for this message
TiborB (tiborb95) wrote :

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

Revision history for this message
GunChleoc (gunchleoc) wrote :

Looking good, let's have it :)

@bunnybot merge

Revision history for this message
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.

Revision history for this message
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()

Subscribers

People subscribed via source and target branches

to status/vote changes: