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
=== modified file 'src/ai/CMakeLists.txt'
--- src/ai/CMakeLists.txt 2017-11-22 19:00:09 +0000
+++ src/ai/CMakeLists.txt 2019-07-31 19:53:54 +0000
@@ -24,3 +24,4 @@
24 logic_map_objects24 logic_map_objects
25 scripting_lua_table25 scripting_lua_table
26)26)
27add_subdirectory(test)
2728
=== modified file 'src/ai/ai_help_structs.cc'
--- src/ai/ai_help_structs.cc 2019-04-09 16:43:49 +0000
+++ src/ai/ai_help_structs.cc 2019-07-31 19:53:54 +0000
@@ -19,6 +19,8 @@
1919
20#include "ai/ai_help_structs.h"20#include "ai/ai_help_structs.h"
2121
22#include <algorithm>
23
22#include "base/macros.h"24#include "base/macros.h"
23#include "base/time_string.h"25#include "base/time_string.h"
24#include "logic/ai_dna_handler.h"26#include "logic/ai_dna_handler.h"
@@ -27,10 +29,6 @@
2729
28namespace Widelands {30namespace Widelands {
2931
30// couple of constants for calculation of road interconnections
31constexpr int kRoadPossiblyBuildable = 200;
32constexpr int kConnectedByRoads = 400;
33constexpr int kNotConnectedByRoads = 600;
34constexpr int kNoAiTrainingMutation = 200;32constexpr int kNoAiTrainingMutation = 200;
35constexpr int kUpperDefaultMutationLimit = 150;33constexpr int kUpperDefaultMutationLimit = 150;
36constexpr int kLowerDefaultMutationLimit = 75;34constexpr int kLowerDefaultMutationLimit = 75;
@@ -307,7 +305,7 @@
307 // count of rocks can only decrease, so amount of rocks305 // count of rocks can only decrease, so amount of rocks
308 // is recalculated only when previous count is positive306 // is recalculated only when previous count is positive
309 // count of water fields are stable, so if the current count is307 // count of water fields are stable, so if the current count is
310 // non-negative, water is not recaldulated308 // non-negative, water is not recalculated
311 rocks_nearby(1),309 rocks_nearby(1),
312 water_nearby(-1),310 water_nearby(-1),
313 open_water_nearby(-1),311 open_water_nearby(-1),
@@ -974,120 +972,6 @@
974 return (blocked_fields_.count(coords.hash()) != 0);972 return (blocked_fields_.count(coords.hash()) != 0);
975}973}
976974
977// As a policy, we just set some default value, that will be updated later on
978FlagsForRoads::Candidate::Candidate(uint32_t coords, int32_t distance, bool different_economy)
979 : coords_hash(coords), air_distance(distance) {
980 new_road_possible = false;
981 // Just custom values
982 new_road_length = kRoadPossiblyBuildable;
983 current_road_length = (different_economy) ? kNotConnectedByRoads : kConnectedByRoads;
984}
985
986// Used when sorting cadidate flags from best one
987bool FlagsForRoads::Candidate::operator<(const Candidate& other) const {
988 const int32_t other_rs = other.reduction_score();
989 const int32_t this_rs = reduction_score();
990 return std::tie(other.new_road_possible, other_rs) < std::tie(new_road_possible, this_rs);
991}
992
993bool FlagsForRoads::Candidate::operator==(const Candidate& other) const {
994 return coords_hash == other.coords_hash;
995}
996
997int32_t FlagsForRoads::Candidate::reduction_score() const {
998 return current_road_length - new_road_length - (new_road_length - air_distance) / 3;
999}
1000
1001void FlagsForRoads::print() { // this is for debugging and development purposes
1002 for (auto& candidate_flag : flags_queue) {
1003 log(" %starget: %3dx%3d, saving: %5d (%3d), air distance: %3d, new road: %6d, score: %5d "
1004 "%s\n",
1005 (candidate_flag.reduction_score() >= min_reduction && candidate_flag.new_road_possible) ?
1006 "+" :
1007 " ",
1008 Coords::unhash(candidate_flag.coords_hash).x,
1009 Coords::unhash(candidate_flag.coords_hash).y,
1010 candidate_flag.current_road_length - candidate_flag.new_road_length, min_reduction,
1011 candidate_flag.air_distance, candidate_flag.new_road_length,
1012 candidate_flag.reduction_score(),
1013 (candidate_flag.new_road_possible) ? ", new road possible" : " ");
1014 }
1015}
1016
1017// Queue is ordered but some target flags are only estimations so we take such a candidate_flag
1018// first
1019bool FlagsForRoads::get_best_uncalculated(uint32_t* winner) {
1020 for (auto& candidate_flag : flags_queue) {
1021 if (!candidate_flag.new_road_possible) {
1022 *winner = candidate_flag.coords_hash;
1023 return true;
1024 }
1025 }
1026 return false;
1027}
1028
1029// Road from starting flag to this flag can be built
1030void FlagsForRoads::road_possible(Widelands::Coords coords, const uint32_t new_road) {
1031 for (auto& candidate_flag : flags_queue) {
1032 if (candidate_flag.coords_hash == coords.hash()) {
1033 candidate_flag.new_road_length = new_road;
1034 candidate_flag.new_road_possible = true;
1035 candidate_flag.reduction_score();
1036 return;
1037 }
1038 }
1039 NEVER_HERE();
1040}
1041
1042// find_reachable_fields returns duplicates so we deal with them
1043bool FlagsForRoads::has_candidate(const uint32_t hash) {
1044 for (auto& candidate_flag : flags_queue) {
1045 if (candidate_flag.coords_hash == hash) {
1046 return true;
1047 }
1048 }
1049 return false;
1050}
1051
1052// Updating walking distance into flags_queue
1053void FlagsForRoads::set_cur_road_distance(Widelands::Coords coords, int32_t cur_distance) {
1054 for (auto& candidate_flag : flags_queue) {
1055 if (candidate_flag.coords_hash == coords.hash()) {
1056 candidate_flag.current_road_length = cur_distance;
1057 candidate_flag.reduction_score();
1058 return;
1059 }
1060 }
1061}
1062
1063// Returns mostly best candidate, as a result of sorting
1064bool FlagsForRoads::get_winner(uint32_t* winner_hash) {
1065 // If AI can ask for 2nd position, but there is only one viable candidate
1066 // we return the first one of course
1067 bool has_winner = false;
1068 for (auto candidate_flag : flags_queue) {
1069 if (candidate_flag.reduction_score() < min_reduction || !candidate_flag.new_road_possible ||
1070 candidate_flag.new_road_length * 2 > candidate_flag.current_road_length) {
1071 continue;
1072 }
1073 assert(candidate_flag.air_distance > 0);
1074 assert(candidate_flag.reduction_score() >= min_reduction);
1075 assert(candidate_flag.new_road_possible);
1076 *winner_hash = candidate_flag.coords_hash;
1077 has_winner = true;
1078
1079 if (std::rand() % 4 > 0) {
1080 // with probability of 3/4 we accept this flag
1081 return true;
1082 }
1083 }
1084
1085 if (has_winner) {
1086 return true;
1087 }
1088 return false;
1089}
1090
1091PlayersStrengths::PlayersStrengths() : update_time(0) {975PlayersStrengths::PlayersStrengths() : update_time(0) {
1092}976}
1093977
@@ -1417,4 +1301,190 @@
1417 return update_time;1301 return update_time;
1418}1302}
14191303
1304FlagWarehouseDistances::FlagInfo::FlagInfo(const uint32_t gametime,
1305 const uint16_t dist,
1306 const uint32_t wh) {
1307 expiry_time = gametime + kFlagDistanceExpirationPeriod;
1308 soft_expiry_time = gametime + kFlagDistanceExpirationPeriod / 2;
1309 distance = dist;
1310 nearest_warehouse = wh;
1311 new_road_prohibited_till = 0;
1312}
1313FlagWarehouseDistances::FlagInfo::FlagInfo() {
1314 expiry_time = 0;
1315 distance = 1000;
1316 new_road_prohibited_till = 0;
1317}
1318
1319// We are updating the distance info, but not all the time.
1320// Always if after soft expiration period, but
1321// if below expiration period only when the new value is lower than current one
1322// In both cases new expiration times are calculated
1323bool FlagWarehouseDistances::FlagInfo::update(const uint32_t gametime,
1324 const uint16_t new_distance,
1325 const uint32_t nearest_wh) {
1326 const uint32_t new_expiry_time = gametime + kFlagDistanceExpirationPeriod;
1327
1328 if (gametime > soft_expiry_time) {
1329 distance = new_distance;
1330 expiry_time = new_expiry_time;
1331 soft_expiry_time = gametime + kFlagDistanceExpirationPeriod / 2;
1332 nearest_warehouse = nearest_wh;
1333 return true;
1334 } else if (new_distance < distance || (new_distance == distance &&
1335 expiry_time < new_expiry_time)) {
1336 distance = new_distance;
1337 expiry_time = new_expiry_time;
1338 nearest_warehouse = nearest_wh;
1339 return true;
1340 }
1341 return false;
1342}
1343
1344uint16_t FlagWarehouseDistances::FlagInfo::get(const uint32_t gametime, uint32_t* nw) const {
1345 *nw = nearest_warehouse;
1346 if (gametime <= expiry_time) {
1347 return distance;
1348 }
1349 return kFarButReachable;
1350}
1351
1352void FlagWarehouseDistances::FlagInfo::set_road_built(const uint32_t gametime) {
1353 // Prohibiting for next 60 seconds
1354 new_road_prohibited_till = gametime + 60 * 1000;
1355}
1356
1357bool FlagWarehouseDistances::FlagInfo::is_road_prohibited(const uint32_t gametime) const {
1358 return new_road_prohibited_till > gametime;
1359}
1360
1361bool FlagWarehouseDistances::set_distance(const uint32_t flag_coords,
1362 const uint16_t distance,
1363 uint32_t const gametime,
1364 uint32_t const nearest_warehouse) {
1365 if (flags_map.count(flag_coords) == 0) {
1366 flags_map[flag_coords] =
1367 FlagWarehouseDistances::FlagInfo(gametime, distance, nearest_warehouse);
1368 return true;
1369 }
1370 return flags_map[flag_coords].update(gametime, distance, nearest_warehouse);
1371}
1372
1373uint16_t FlagWarehouseDistances::count() const {
1374 return flags_map.size();
1375}
1376
1377int16_t
1378FlagWarehouseDistances::get_distance(const uint32_t flag_coords, uint32_t gametime, uint32_t* nw) {
1379 if (flags_map.count(flag_coords) == 0) {
1380 *nw = 0;
1381 return kFarButReachable; // this is to discourage to build second road from brand new flag...
1382 } else {
1383 return flags_map[flag_coords].get(gametime, nw);
1384 }
1385}
1386
1387void FlagWarehouseDistances::set_road_built(const uint32_t coords_hash, const uint32_t gametime) {
1388 if (flags_map.count(coords_hash) == 1) {
1389 flags_map[coords_hash].set_road_built(gametime);
1390 }
1391}
1392
1393bool FlagWarehouseDistances::is_road_prohibited(const uint32_t coords_hash,
1394 const uint32_t gametime) {
1395 if (flags_map.count(coords_hash) == 1) {
1396 return flags_map[coords_hash].is_road_prohibited(gametime);
1397 }
1398 return false;
1399}
1400
1401bool FlagWarehouseDistances::remove_old_flag(uint32_t gametime) {
1402 for (std::map<uint32_t, FlagWarehouseDistances::FlagInfo>::iterator it = flags_map.begin();
1403 it != flags_map.end(); it++) {
1404 if (it->second.expiry_time + kOldFlagRemoveTime < gametime) {
1405 it = flags_map.erase(it);
1406 return true;
1407 }
1408 }
1409 return false;
1410}
1411
1412// Returns pointer to winning road, provided that the treshold is exceeded
1413FlagCandidates::Candidate* FlagCandidates::get_winner(const int16_t threshold) {
1414 if (flags_.empty()) {
1415 return nullptr;
1416 }
1417 sort();
1418 if (flags_[0].score() < threshold) {
1419 return nullptr;
1420 }
1421 if (!flags_[0].is_buildable()) {
1422 return nullptr;
1423 }
1424 return &flags_[0];
1425}
1426
1427FlagCandidates::Candidate::Candidate(
1428 const uint32_t c_hash, bool different_eco, uint16_t start_f_dist, uint16_t act_dist_to_wh, uint16_t air_dst) {
1429 coords_hash = c_hash;
1430 different_economy = different_eco;
1431 start_flag_dist_to_wh = start_f_dist;
1432 flag_to_flag_road_distance = 0;
1433 possible_road_distance = kFarButReachable;
1434 cand_flag_distance_to_wh = act_dist_to_wh;
1435 air_distance = air_dst;
1436}
1437
1438int16_t FlagCandidates::Candidate::score() const {
1439 return different_economy * 2000 + (start_flag_dist_to_wh - cand_flag_distance_to_wh) +
1440 (flag_to_flag_road_distance - 2 * possible_road_distance);
1441}
1442
1443bool FlagCandidates::set_road_possible(const uint32_t coords_hash, const uint16_t steps) {
1444 for (auto& item : flags_) {
1445 if (item.coords_hash == coords_hash) {
1446 item.possible_road_distance = steps;
1447 return true;
1448 }
1449 }
1450 return false;
1451}
1452
1453bool FlagCandidates::set_cur_road_distance(const uint32_t coords, uint16_t dist) {
1454 for (auto& item : flags_) {
1455 if (item.coords_hash == coords) {
1456 item.flag_to_flag_road_distance = dist;
1457 return true;
1458 }
1459 }
1460 return false;
1461}
1462void FlagCandidates::sort() {
1463 std::sort(flags_.begin(), flags_.end());
1464}
1465
1466void FlagCandidates::sort_by_air_distance() {
1467 std::sort(flags_.begin(), flags_.end(),
1468 [](const FlagCandidates::Candidate& lf, const FlagCandidates::Candidate& rf) {
1469 return lf.air_distance < rf.air_distance;
1470 });
1471}
1472
1473void FlagCandidates::add_flag(const uint32_t coords,
1474 const bool different_economy,
1475 const uint16_t act_dist_to_wh,
1476 const uint16_t air_distance) {
1477 flags_.push_back(
1478 Candidate(coords, different_economy, start_flag_dist_to_wh, act_dist_to_wh, air_distance));
1479}
1480
1481bool FlagCandidates::has_candidate(const uint32_t coords_hash) const {
1482 for (auto& item : flags_) {
1483 if (item.coords_hash == coords_hash) {
1484 return true;
1485 }
1486 }
1487 return false;
1488}
1489
1420} // namespace Widelands1490} // namespace Widelands
14211491
=== modified file 'src/ai/ai_help_structs.h'
--- src/ai/ai_help_structs.h 2019-05-25 08:20:22 +0000
+++ src/ai/ai_help_structs.h 2019-07-31 19:53:54 +0000
@@ -20,6 +20,7 @@
20#ifndef WL_AI_AI_HELP_STRUCTS_H20#ifndef WL_AI_AI_HELP_STRUCTS_H
21#define WL_AI_AI_HELP_STRUCTS_H21#define WL_AI_AI_HELP_STRUCTS_H
2222
23#include <algorithm>
23#include <list>24#include <list>
24#include <queue>25#include <queue>
25#include <unordered_set>26#include <unordered_set>
@@ -107,6 +108,7 @@
107 kCheckEnemySites,108 kCheckEnemySites,
108 kManagementUpdate,109 kManagementUpdate,
109 kUpdateStats,110 kUpdateStats,
111 kWarehouseFlagDist,
110 kUnset112 kUnset
111};113};
112114
@@ -122,9 +124,20 @@
122// TODO(tiborb): this should be replaced by command line switch124// TODO(tiborb): this should be replaced by command line switch
123constexpr int kFNeuronBitSize = 32;125constexpr int kFNeuronBitSize = 32;
124constexpr int kMutationRatePosition = 42;126constexpr int kMutationRatePosition = 42;
127// This is expiration time for distance from a flag to nearest warehouse
128constexpr int kFlagDistanceExpirationPeriod = 120 * 1000;
129// If the distance of flag-warehouse was not updated for this time, we presume that the flag
130// does not exist anymore and remove it
131constexpr int kOldFlagRemoveTime = 5 * 60 * 1000;
125132
126constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();133constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();
127134
135constexpr uint32_t kNoField = std::numeric_limits<uint32_t>::max();
136
137constexpr uint32_t kOneMinute = 60 * 1000;
138
139constexpr uint16_t kFarButReachable = 1000;
140
128struct CheckStepRoadAI {141struct CheckStepRoadAI {
129 CheckStepRoadAI(Player* const pl, uint8_t const mc, bool const oe);142 CheckStepRoadAI(Player* const pl, uint8_t const mc, bool const oe);
130143
@@ -527,8 +540,10 @@
527};540};
528541
529struct WarehouseSiteObserver {542struct WarehouseSiteObserver {
543
530 Widelands::Warehouse* site;544 Widelands::Warehouse* site;
531 BuildingObserver* bo;545 BuildingObserver* bo;
546 uint32_t flag_distances_last_update;
532};547};
533548
534struct ShipObserver {549struct ShipObserver {
@@ -766,53 +781,6 @@
766 std::map<uint32_t, uint32_t> blocked_fields_;781 std::map<uint32_t, uint32_t> blocked_fields_;
767};782};
768783
769// list of candidate flags to build roads, with some additional logic
770struct FlagsForRoads {
771
772 explicit FlagsForRoads(int32_t mr) : min_reduction(mr) {
773 }
774
775 struct Candidate {
776 Candidate();
777 Candidate(uint32_t coords, int32_t distance, bool different_economy);
778
779 uint32_t coords_hash;
780 int32_t new_road_length;
781 int32_t current_road_length;
782 int32_t air_distance;
783
784 bool new_road_possible;
785
786 bool operator<(const Candidate& other) const;
787 bool operator==(const Candidate& other) const;
788 int32_t reduction_score() const;
789 };
790
791 int32_t min_reduction;
792 // This is the core of this object - candidate flags to be ordered by air_distance
793 std::deque<Candidate> flags_queue;
794
795 void add_flag(Widelands::Coords coords, int32_t air_dist, bool different_economy) {
796 flags_queue.push_back(Candidate(coords.hash(), air_dist, different_economy));
797 }
798
799 uint32_t count() {
800 return flags_queue.size();
801 }
802 bool has_candidate(uint32_t hash);
803
804 // This is for debugging and development purposes
805 void print();
806 // during processing we need to pick first one uprocessed flag (with best score so far)
807 bool get_best_uncalculated(uint32_t* winner);
808 // When we test candidate flag if road can be built to it, there are two possible outcomes:
809 void road_possible(Widelands::Coords coords, uint32_t new_road);
810 // Updating walking distance over existing roads
811 void set_cur_road_distance(Widelands::Coords coords, int32_t cur_distance);
812 // Finally we query the flag that we will build a road to
813 bool get_winner(uint32_t* winner_hash);
814};
815
816// This is a struct that stores strength of players, info on teams and provides some outputs from784// This is a struct that stores strength of players, info on teams and provides some outputs from
817// these data785// these data
818struct PlayersStrengths {786struct PlayersStrengths {
@@ -891,6 +859,97 @@
891 PlayerNumber this_player_number;859 PlayerNumber this_player_number;
892 PlayerNumber this_player_team;860 PlayerNumber this_player_team;
893};861};
862
863// This is a wrapper around map of <Flag coords hash:distance from flag to nearest warehouse>
864// Flags does not have observers so this stuct server like "lazy" substitution for this, where
865// keys are hash of flags positions
866// This "lives" during entire "session", and is not saved, but is easily recalulated
867struct FlagWarehouseDistances {
868private:
869 struct FlagInfo {
870 FlagInfo();
871 FlagInfo(uint32_t, uint16_t, uint32_t);
872 // Distance to a nearest warehouse expires, but in two stages
873 // This is complete expiration and such flag is treated as without distance to WH
874 uint32_t expiry_time;
875 // When recalculating new distance, if the current information is younger than
876 // soft_expiry_time it is only decreased if new value is smaller After soft_expiry_time is
877 // updated in any case
878 uint32_t soft_expiry_time;
879 uint16_t distance;
880 // This is coords hash of nearest warehouse, not used by now
881 uint32_t nearest_warehouse;
882 // after building of new road, the distance information is updated not immediately so
883 // we prohibit current flag from another road building...
884 uint32_t new_road_prohibited_till;
885
886 bool update(uint32_t, uint16_t, uint32_t);
887 // Saying the road was built and when
888 void set_road_built(uint32_t);
889 // Asking if road can be built from this flag (providing current gametime)
890 bool is_road_prohibited(uint32_t) const;
891 // get current distance (providing current gametime)
892 uint16_t get(uint32_t, uint32_t*) const;
893 };
894 std::map<uint32_t, FlagInfo> flags_map;
895
896public:
897 // All these function uses lookup in flags_map so first argument is usually flag coords hash
898 bool set_distance(uint32_t flag_coords, uint16_t distance, uint32_t gametime, uint32_t nearest_warehouse);
899 int16_t get_distance(uint32_t flag_coords, uint32_t gametime, uint32_t* nw);
900 void set_road_built(uint32_t coords_hash, uint32_t gametime);
901 bool is_road_prohibited(uint32_t coords_hash, uint32_t gametime);
902 uint16_t count() const;
903 bool remove_old_flag(uint32_t gametime);
904};
905
906// This is one-time structure - initiated and filled up when investigating possible roads to be
907// built to a flag. At the end the flags are scored based on gained info), ordered and if treshold is
908// achieved the road is to be built
909struct FlagCandidates {
910
911 explicit FlagCandidates(uint16_t wd) : start_flag_dist_to_wh(wd) {
912 }
913
914 struct Candidate {
915 Candidate() = delete;
916 Candidate(uint32_t, bool, uint16_t, uint16_t, uint16_t);
917 uint16_t air_distance;
918 uint32_t coords_hash;
919 bool different_economy;
920 uint16_t start_flag_dist_to_wh;
921 uint16_t flag_to_flag_road_distance;
922 uint16_t possible_road_distance;
923 uint16_t cand_flag_distance_to_wh;
924 // Scoring is considering multiple things
925 int16_t score() const;
926 bool is_buildable() {
927 return possible_road_distance > 0;
928 }
929 bool operator<(const Candidate& other) const {
930 return score() > other.score();
931 }
932 };
933
934private:
935 std::vector<Candidate> flags_;
936 uint16_t start_flag_dist_to_wh;
937
938public:
939 const std::vector<Candidate>& flags() const {
940 return flags_;
941 }
942 bool has_candidate(uint32_t) const;
943 void add_flag(uint32_t, bool, uint16_t, uint16_t);
944 bool set_cur_road_distance(uint32_t, uint16_t);
945 bool set_road_possible(uint32_t, uint16_t);
946 void sort();
947 void sort_by_air_distance();
948 uint32_t count() {
949 return flags_.size();
950 }
951 FlagCandidates::Candidate* get_winner(const int16_t = 0);
952};
894} // namespace Widelands953} // namespace Widelands
895954
896#endif // end of include guard: WL_AI_AI_HELP_STRUCTS_H955#endif // end of include guard: WL_AI_AI_HELP_STRUCTS_H
897956
=== modified file 'src/ai/defaultai.cc'
--- src/ai/defaultai.cc 2019-05-26 11:39:41 +0000
+++ src/ai/defaultai.cc 2019-07-31 19:53:54 +0000
@@ -331,7 +331,7 @@
331 set_taskpool_task_time(gametime + 1000, SchedulerTaskId::kRoadCheck);331 set_taskpool_task_time(gametime + 1000, SchedulerTaskId::kRoadCheck);
332 // testing 5 roads332 // testing 5 roads
333 {333 {
334 const int32_t roads_to_check = (roads.size() < 20) ? 1 : 3;334 const int32_t roads_to_check = roads.size() / 30 + 1;
335 for (int j = 0; j < roads_to_check; j += 1) {335 for (int j = 0; j < roads_to_check; j += 1) {
336 // improve_roads function will test one road and rotate roads vector336 // improve_roads function will test one road and rotate roads vector
337 if (improve_roads(gametime)) {337 if (improve_roads(gametime)) {
@@ -486,6 +486,10 @@
486 update_player_stat(gametime);486 update_player_stat(gametime);
487 set_taskpool_task_time(gametime + kStatUpdateInterval, SchedulerTaskId::kUpdateStats);487 set_taskpool_task_time(gametime + kStatUpdateInterval, SchedulerTaskId::kUpdateStats);
488 break;488 break;
489 case SchedulerTaskId::kWarehouseFlagDist:
490 check_flag_distances(gametime);
491 set_taskpool_task_time(gametime + kFlagWarehouseUpdInterval, SchedulerTaskId::kWarehouseFlagDist);
492 break;
489 case SchedulerTaskId::kUnset:493 case SchedulerTaskId::kUnset:
490 NEVER_HERE();494 NEVER_HERE();
491 }495 }
@@ -958,6 +962,9 @@
958 taskPool.push_back(SchedulerTask(962 taskPool.push_back(SchedulerTask(
959 std::max<uint32_t>(gametime, 10 * 1000), SchedulerTaskId::kUpdateStats, 15, "review"));963 std::max<uint32_t>(gametime, 10 * 1000), SchedulerTaskId::kUpdateStats, 15, "review"));
960964
965 taskPool.push_back(SchedulerTask(
966 std::max<uint32_t>(gametime, 10 * 1000), SchedulerTaskId::kWarehouseFlagDist, 5, "Flag-Warehouse Update"));
967
961 const Map& map = game().map();968 const Map& map = game().map();
962969
963 // here we scan entire map for own ships970 // here we scan entire map for own ships
@@ -1053,7 +1060,7 @@
1053 kExpeditionMinDuration +1060 kExpeditionMinDuration +
1054 static_cast<double>(off) * (kExpeditionMaxDuration - kExpeditionMinDuration) / scope;1061 static_cast<double>(off) * (kExpeditionMaxDuration - kExpeditionMinDuration) / scope;
1055 log(" %d: expedition max duration = %u (%u minutes), map area root: %u\n", player_number(),1062 log(" %d: expedition max duration = %u (%u minutes), map area root: %u\n", player_number(),
1056 expedition_max_duration / 1000, expedition_max_duration / 60000, map_area_root);1063 expedition_max_duration / 1000, expedition_max_duration / kOneMinute, map_area_root);
1057 assert(expedition_max_duration >= kExpeditionMinDuration);1064 assert(expedition_max_duration >= kExpeditionMinDuration);
1058 assert(expedition_max_duration <= kExpeditionMaxDuration);1065 assert(expedition_max_duration <= kExpeditionMaxDuration);
10591066
@@ -3422,6 +3429,70 @@
3422 return true;3429 return true;
3423}3430}
34243431
3432
3433// Re-calculating warehouse to flag distances
3434void DefaultAI::check_flag_distances(const uint32_t gametime) {
3435 for (WarehouseSiteObserver& wh_obs : warehousesites) {
3436 uint16_t checked_flags = 0;
3437 const uint32_t this_wh_hash = wh_obs.site->get_position().hash();
3438 uint32_t highest_distance_set = 0;
3439
3440 std::queue<Widelands::Flag*>
3441 remaining_flags; // only used to collect flags reachable walk over roads
3442 remaining_flags.push(&wh_obs.site->base_flag());
3443 flag_warehouse_distance.set_distance(
3444 wh_obs.site->base_flag().get_position().hash(), 0, gametime, this_wh_hash);
3445 uint32_t tmp_wh;
3446 assert(flag_warehouse_distance.get_distance(
3447 wh_obs.site->base_flag().get_position().hash(), gametime, &tmp_wh) == 0);
3448
3449 // Algorithm to walk on roads
3450 // All nodes are marked as to_be_checked == true first and once the node is checked it is
3451 // changed to false. Under some conditions, the same node can be checked twice, the
3452 // to_be_checked can be set back to true. Because less hoops (fewer flag-to-flag roads) does
3453 // not always mean shortest road.
3454 while (!remaining_flags.empty()) {
3455 ++checked_flags;
3456 // looking for a node with shortest existing road distance from starting flag and one that
3457 // has to be checked Now going over roads leading from this flag
3458 const uint16_t current_flag_distance = flag_warehouse_distance.get_distance(
3459 remaining_flags.front()->get_position().hash(), gametime, &tmp_wh);
3460 for (uint8_t i = 1; i <= 6; ++i) {
3461 Road* const road = remaining_flags.front()->get_road(i);
3462
3463 if (!road) {
3464 continue;
3465 }
3466
3467 Flag* endflag = &road->get_flag(Road::FlagStart);
3468
3469 if (endflag == remaining_flags.front()) {
3470 endflag = &road->get_flag(Road::FlagEnd);
3471 }
3472 const uint16_t steps_count = road->get_path().get_nsteps();
3473
3474 // Calculated distance can be used or ignored if f.e. longer than via other route
3475 bool const updated = flag_warehouse_distance.set_distance(
3476 endflag->get_position().hash(), current_flag_distance + steps_count, gametime,
3477 this_wh_hash);
3478
3479 if (highest_distance_set < current_flag_distance + steps_count) {
3480 highest_distance_set = current_flag_distance + steps_count;
3481 }
3482
3483 if (updated) {
3484 remaining_flags.push(endflag);
3485 }
3486 }
3487 remaining_flags.pop();
3488 }
3489
3490 }
3491
3492 // Now let do some lazy pruning - remove the flags that were not updated for long
3493 flag_warehouse_distance.remove_old_flag(gametime);
3494}
3495
3425// Here we pick about 25 roads and investigate them. If it is a dead end we dismantle it3496// Here we pick about 25 roads and investigate them. If it is a dead end we dismantle it
3426bool DefaultAI::dismantle_dead_ends() {3497bool DefaultAI::dismantle_dead_ends() {
3427 bool road_dismantled = false;3498 bool road_dismantled = false;
@@ -3538,50 +3609,36 @@
3538 }3609 }
35393610
3540 bool is_warehouse = false;3611 bool is_warehouse = false;
3541 bool has_building = false;
3542 if (Building* b = flag.get_building()) {3612 if (Building* b = flag.get_building()) {
3543 has_building = true;
3544 BuildingObserver& bo = get_building_observer(b->descr().name().c_str());3613 BuildingObserver& bo = get_building_observer(b->descr().name().c_str());
3545 if (bo.type == BuildingObserver::Type::kWarehouse) {3614 if (bo.type == BuildingObserver::Type::kWarehouse) {
3546 is_warehouse = true;3615 is_warehouse = true;
3547 }3616 }
3548 }3617 }
3618 const uint32_t flag_coords_hash = flag.get_position().hash();
35493619
3550 // is connected to a warehouse?3620 if (flag_warehouse_distance.is_road_prohibited(flag_coords_hash, gametime)) {return false;}
3551 const bool needs_warehouse = flag.get_economy()->warehouses().empty();3621 const bool needs_warehouse = flag.get_economy()->warehouses().empty();
35523622
3553 if (!has_building && flag.nr_of_roads() == 1) {3623 uint32_t tmp_wh;
3554 return false;3624
3555 } else if (is_warehouse && flag.nr_of_roads() <= 3) {3625 // when deciding if we attempt to build a road from here we use probability
3556 // Do nothing3626 uint16_t probability_score = 0;
3557 } else if (needs_warehouse) {3627 if (flag.nr_of_roads() == 1) {probability_score += 20;}
3558 // Do nothing3628 if (is_warehouse && flag.nr_of_roads() <= 3) {probability_score += 20;}
3559 } else if (flag.current_wares() > 5) {3629 probability_score += flag.current_wares() * 5;
3560 // Do nothing3630 if (needs_warehouse) {probability_score += 500;}
3561 } else if (has_building && std::rand() % 3 == 0) {3631 if (std::rand() % 10 == 0) {
3562 // Do nothing3632 probability_score += flag_warehouse_distance.get_distance(flag_coords_hash, gametime, &tmp_wh);
3563 } else if (std::rand() % 10 == 0) {3633 }
3564 // Do nothing3634
3565 } else {3635 if (std::rand() % 200 < probability_score) {
3566 return false;3636 create_shortcut_road(flag, 14, gametime);
3567 }3637 return true;
35683638 }
3569 int16_t expected_shortcut = 27;3639
3570 if (has_building) {3640 return false;
3571 expected_shortcut -= 3;3641
3572 }
3573 expected_shortcut -= flag.current_wares() * 3;
3574 if (is_warehouse) {
3575 expected_shortcut -= 10;
3576 }
3577 if (std::rand() % 5 == 0) {
3578 expected_shortcut -= 10;
3579 }
3580 expected_shortcut -= 2 * flag.nr_of_roads();
3581
3582 create_shortcut_road(flag, 14, expected_shortcut, gametime);
3583
3584 return true;
3585}3642}
35863643
3587// This function takes a road (road is smallest section of roads with two flags on the ends)3644// This function takes a road (road is smallest section of roads with two flags on the ends)
@@ -3756,318 +3813,339 @@
3756// connection is not known3813// connection is not known
3757bool DefaultAI::create_shortcut_road(const Flag& flag,3814bool DefaultAI::create_shortcut_road(const Flag& flag,
3758 uint16_t checkradius,3815 uint16_t checkradius,
3759 int16_t min_reduction,
3760 uint32_t gametime) {3816 uint32_t gametime) {
37613817
3762 // Increasing the failed_connection_tries counter3818 // Increasing the failed_connection_tries counter
3763 // At the same time it indicates a time an economy is without a warehouse3819 // At the same time it indicates a time an economy is without a warehouse
3764 EconomyObserver* eco = get_economy_observer(flag.economy());3820 EconomyObserver* eco = get_economy_observer(flag.economy());
3765 // if we passed grace time this will be last attempt and if it fails3821 // if we passed grace time this will be last attempt and if it fails
3766 // building is destroyes3822 // building is destroyed
3767 bool last_attempt_ = false;3823 bool last_attempt_ = false;
37683824
3769 // this should not happen, but if the economy has a warehouse and a dismantle3825 // this should not happen, but if the economy has a warehouse and a dismantle
3770 // grace time set, we must 'zero' the dismantle grace time3826 // grace time set, we must 'zero' the dismantle grace time
3771 if (!flag.get_economy()->warehouses().empty() &&3827 if (!flag.get_economy()->warehouses().empty() &&
3772 eco->dismantle_grace_time != std::numeric_limits<uint32_t>::max()) {3828 eco->dismantle_grace_time != kNever) {
3773 eco->dismantle_grace_time = std::numeric_limits<uint32_t>::max();3829 eco->dismantle_grace_time = kNever;
3774 }3830 }
37753831
3776 // first we deal with situations when this is economy with no warehouses3832 // first we deal with situations when this is economy with no warehouses
3777 // and this is a flag belonging to a building/constructionsite3833 // and this is a flag belonging to a building/constructionsite
3778 // such economy must get dismantle grace time (if not set yet)3834 // such economy must get dismantle grace time (if not set yet)
3779 // end sometimes extended checkradius3835 // end sometimes extended checkradius
3780 if (flag.get_economy()->warehouses().empty() && flag.get_building()) {3836 if (flag.get_economy()->warehouses().empty() && flag.get_building()) {
37813837
3782 // occupied military buildings get special treatment3838 // occupied military buildings get special treatment
3783 // (extended grace time + longer radius)3839 // (extended grace time + longer radius)
3784 bool occupied_military_ = false;3840 bool occupied_military_ = false;
3785 Building* b = flag.get_building();3841 Building* b = flag.get_building();
3786 if (upcast(MilitarySite, militb, b)) {3842 if (upcast(MilitarySite, militb, b)) {
3787 if (militb->soldier_control()->stationed_soldiers().size() > 0) {3843 if (militb->soldier_control()->stationed_soldiers().size() > 0) {
3788 occupied_military_ = true;3844 occupied_military_ = true;
3789 }3845 }
3790 }3846 }
37913847
3792 // check if we are within grace time, if not or gracetime unset we need to do something3848 // check if we are within grace time, if not or gracetime unset we need to do something
3793 // if we are within gracetime we do nothing (this loop is skipped)3849 // if we are within gracetime we do nothing (this loop is skipped)
37943850
3795 // if grace time is not set, this is probably first time without a warehouse and we must set3851 // if grace time is not set, this is probably first time without a warehouse and we must set
3796 // it3852 // it
3797 if (eco->dismantle_grace_time == std::numeric_limits<uint32_t>::max()) {3853 if (eco->dismantle_grace_time == kNever) {
37983854
3799 // constructionsites3855 // constructionsites
3800 if (upcast(ConstructionSite const, constructionsite, flag.get_building())) {3856 if (upcast(ConstructionSite const, constructionsite, flag.get_building())) {
3801 BuildingObserver& bo =3857 BuildingObserver& bo =
3802 get_building_observer(constructionsite->building().name().c_str());3858 get_building_observer(constructionsite->building().name().c_str());
3803 // first very special case - a port (in the phase of constructionsite)3859 // first very special case - a port (in the phase of constructionsite)
3804 // this might be a new colonization port3860 // this might be a new colonization port
3805 if (bo.is(BuildingAttribute::kPort)) {3861 if (bo.is(BuildingAttribute::kPort)) {
3806 eco->dismantle_grace_time = gametime + 60 * 60 * 1000; // one hour should be enough3862 eco->dismantle_grace_time = gametime + 60 * 60 * 1000; // one hour should be enough
3807 } else { // other constructionsites, usually new (standalone) constructionsites3863 } else { // other constructionsites, usually new (standalone) constructionsites
3808 eco->dismantle_grace_time =3864 eco->dismantle_grace_time =
3809 gametime + 30 * 1000 + // very shot time is enough3865 gametime + 30 * 1000 + // very shot time is enough
3810 (eco->flags.size() * 30 * 1000); // + 30 seconds for every flag in economy3866 (eco->flags.size() * 30 * 1000); // + 30 seconds for every flag in economy
3811 }3867 }
38123868
3813 // buildings3869 // buildings
3814 } else {3870 } else {
38153871
3816 if (occupied_military_) {3872 if (occupied_military_) {
3817 eco->dismantle_grace_time =3873 eco->dismantle_grace_time =
3818 (gametime + 90 * 60 * 1000) + (eco->flags.size() * 20 * 1000);3874 (gametime + 90 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
38193875
3820 } else { // for other normal buildings3876 } else { // for other normal buildings
3821 eco->dismantle_grace_time =3877 eco->dismantle_grace_time =
3822 gametime + (45 * 60 * 1000) + (eco->flags.size() * 20 * 1000);3878 gametime + (45 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
3823 }3879 }
3824 }3880 }
38253881
3826 // we have passed grace_time - it is time to dismantle3882 // we have passed grace_time - it is time to dismantle
3827 } else if (eco->dismantle_grace_time <= gametime) {3883 } else if (eco->dismantle_grace_time <= gametime) {
3828 last_attempt_ = true;3884 last_attempt_ = true;
3829 // we increase a check radius in last attempt3885 // we increase a check radius in last attempt
3830 checkradius += 2;3886 checkradius += 2;
3831 }3887 }
38323888
3833 // and bonus for occupied military buildings:3889 // and bonus for occupied military buildings:
3834 if (occupied_military_) {3890 if (occupied_military_) {
3835 checkradius += 4;3891 checkradius += 4;
3836 }3892 }
38373893
3838 // and generally increase radius for unconnected buildings3894 // and generally increase radius for unconnected buildings
3839 checkradius += 2;3895 checkradius += 2;
3840 }3896 }
38413897
3842 // Now own roadfinding stuff3898 // Now own roadfinding stuff
3843 const Map& map = game().map();3899 const Map& map = game().map();
38443900
3845 // initializing new object of FlagsForRoads, we will push there all candidate flags3901 // Initializing new object of FlagsForRoads, we will push there all candidate flags
3846 // First we dont even know if a road can be built there (from current flag)3902 // First we dont even know if a road can be built there (from current flag)
3847 Widelands::FlagsForRoads RoadCandidates(min_reduction);3903 // Adding also distance of this flag to nearest wh
38483904 uint32_t tmp_wh; // This information is not used, but we need it
3849 FindNodeWithFlagOrRoad functor;3905 const uint32_t current_flag_dist_to_wh = flag_warehouse_distance.
3850 CheckStepRoadAI check(player_, MOVECAPS_WALK, true);3906 get_distance(flag.get_position().hash(), gametime, &tmp_wh);
38513907
3852 // get all flags within radius3908 FlagCandidates flag_candidates(current_flag_dist_to_wh);
3853 std::vector<Coords> reachable;3909
3854 map.find_reachable_fields(3910 FindNodeWithFlagOrRoad functor;
3855 Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius), &reachable, check, functor);3911 CheckStepRoadAI check(player_, MOVECAPS_WALK, true);
38563912
3857 for (const Coords& reachable_coords : reachable) {3913 // get all flags within radius
38583914 std::vector<Coords> reachable;
3859 // ignore starting flag, of course3915 map.find_reachable_fields(
3860 if (reachable_coords == flag.get_position()) {3916 Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius), &reachable, check, functor);
3861 continue;3917
3862 }3918 for (const Coords& reachable_coords : reachable) {
38633919
3864 // first make sure there is an immovable (should be, but still)3920 // ignore starting flag, of course
3865 if (upcast(PlayerImmovable const, player_immovable, map[reachable_coords].get_immovable())) {3921 if (reachable_coords == flag.get_position()) {
38663922 continue;
3867 // if it is the road, make a flag there3923 }
3868 if (dynamic_cast<const Road*>(map[reachable_coords].get_immovable())) {3924
3869 game().send_player_build_flag(player_number(), reachable_coords);3925 const uint32_t reachable_coords_hash = reachable_coords.hash();
3870 }3926
38713927 // first make sure there is an immovable (should be, but still)
3872 // do not go on if it is not a flag3928 Widelands::BaseImmovable* this_immovable = map[reachable_coords].get_immovable();
3873 if (!dynamic_cast<const Flag*>(map[reachable_coords].get_immovable())) {3929 if (upcast(PlayerImmovable const, player_immovable, this_immovable)) {
3874 continue;3930
3875 }3931 // if it is the road, make a flag there
38763932 if (this_immovable->descr().type() == MapObjectType::ROAD) {
3877 // testing if a flag/road's economy has a warehouse, if not we are not3933 game().send_player_build_flag(player_number(), reachable_coords);
3878 // interested to connect to it3934 }
3879 if (player_immovable->economy().warehouses().size() == 0) {3935
3880 continue;3936 // do not go on if it is not a flag
3881 }3937 if (this_immovable->descr().type() != MapObjectType::FLAG) {
38823938 continue;
3883 // This is a candidate, sending all necessary info to RoadCandidates3939 }
3884 const bool different_economy = (player_immovable->get_economy() != flag.get_economy());3940
3885 const int32_t air_distance = map.calc_distance(flag.get_position(), reachable_coords);3941 // testing if a flag/road's economy has a warehouse, if not we are not
3886 if (!RoadCandidates.has_candidate(reachable_coords.hash())) {3942 // interested to connect to it
3887 RoadCandidates.add_flag(reachable_coords, air_distance, different_economy);3943 if (player_immovable->economy().warehouses().size() == 0) {
3888 }3944 continue;
3889 }3945 }
3890 }3946
38913947 // This is a candidate, sending all necessary info to RoadCandidates
3892 // now we walk over roads and if field is reachable by roads, we change the distance assigned3948 const bool is_different_economy = (player_immovable->get_economy() != flag.get_economy());
3893 // above3949 const uint16_t air_distance = map.calc_distance(flag.get_position(), reachable_coords);
3894 std::map<uint32_t, NearFlag> nearflags; // only used to collect flags reachable walk over roads3950
3895 nearflags[flag.get_position().hash()] = NearFlag(&flag, 0);3951 if (!flag_candidates.has_candidate(reachable_coords_hash) && !flag_warehouse_distance.is_road_prohibited(reachable_coords_hash, gametime)) {
38963952 flag_candidates.add_flag(reachable_coords_hash, is_different_economy,
3897 // Algorithm to walk on roads3953 flag_warehouse_distance.get_distance(reachable_coords_hash, gametime, &tmp_wh), air_distance);
3898 // All nodes are marked as to_be_checked == true first and once the node is checked it is changed3954 }
3899 // to false. Under some conditions, the same node can be checked twice, the to_be_checked can3955 }
3900 // be set back to true. Because less hoops (fewer flag-to-flag roads) does not always mean3956 }
3901 // shortest3957
3902 // road.3958 // now we walk over roads and if field is reachable by roads, we change the distance assigned
3903 for (;;) {3959 // above
3904 // looking for a node with shortest existing road distance from starting flag and one that has3960 std::map<uint32_t, NearFlag> nearflags; // only used to collect flags reachable walk over roads
3905 // to be checked3961 nearflags[flag.get_position().hash()] = NearFlag(&flag, 0);
3906 uint32_t start_field = std::numeric_limits<uint32_t>::max();3962
3907 uint32_t nearest_distance = 10000;3963 collect_nearflags(nearflags, flag, checkradius);
3908 for (auto item : nearflags) {3964
3909 if (item.second.current_road_distance < nearest_distance && item.second.to_be_checked) {3965 // Sending calculated walking costs from nearflags to RoadCandidates to update info on
3910 nearest_distance = item.second.current_road_distance;3966 // Candidate flags/roads
3911 start_field = item.first;3967 for (auto& nf_walk : nearflags) {
3912 }3968 const uint32_t nf_hash = nf_walk.second.flag->get_position().hash();
3913 }3969 // NearFlag contains also flags beyond check radius, these are not relevant for us
3914 // OK, we failed to find a NearFlag where to_be_checked == true, so quitting the loop now3970 if (flag_candidates.has_candidate(nf_hash)) {
3915 if (start_field == std::numeric_limits<uint32_t>::max()) {3971 flag_candidates.set_cur_road_distance(
3916 break;3972 nf_hash, nf_walk.second.current_road_distance);
3917 }3973 }
39183974 }
3919 nearflags[start_field].to_be_checked = false;3975
39203976 // Here we must consider how much are buildable fields lacking
3921 // Now going over roads leading from this flag3977 // the number will be transformed to a weight passed to findpath function
3922 for (uint8_t i = 1; i <= 6; ++i) {3978 int32_t fields_necessity = 0;
3923 Road* const road = nearflags[start_field].flag->get_road(i);3979 if (spots_ < kSpotsTooLittle) {
39243980 fields_necessity += 10;
3925 if (!road) {3981 }
3926 continue;3982 if (map_allows_seafaring_ && num_ports == 0) {
3927 }3983 fields_necessity += 10;
39283984 }
3929 Flag* endflag = &road->get_flag(Road::FlagStart);3985 if (num_ports < 4) {
39303986 fields_necessity += 5;
3931 if (endflag == nearflags[start_field].flag) {3987 }
3932 endflag = &road->get_flag(Road::FlagEnd);3988 if (spots_ < kSpotsEnough) {
3933 }3989 fields_necessity += 5;
39343990 }
3935 const uint32_t endflag_hash = endflag->get_position().hash();3991
39363992 fields_necessity *= std::abs(management_data.get_military_number_at(64)) * 5;
3937 const int32_t dist = map.calc_distance(flag.get_position(), endflag->get_position());3993
39383994 // Now we calculate roads from here to few best looking RoadCandidates....
3939 if (dist > checkradius + 2) { // Testing bigger vicinity then checkradius....3995 flag_candidates.sort_by_air_distance();
3940 continue;3996 uint32_t possible_roads_count = 0;
3941 }3997 for (const auto &flag_candidate : flag_candidates.flags()) {
39423998 if (possible_roads_count > 10) {break;}
3943 // There is few scenarios for this neighbour flag3999 const Widelands::Coords coords = Coords::unhash(flag_candidate.coords_hash);
3944 if (nearflags.count(endflag_hash) == 0) {4000 Path path;
3945 // This is brand new flag4001
3946 nearflags[endflag_hash] =4002 // value of pathcost is not important, it just indicates, that the path can be built
3947 NearFlag(endflag, nearflags[start_field].current_road_distance +4003 // We send this information to RoadCandidates, with length of possible road if applicable
3948 road->get_path().get_nsteps());4004 const int32_t pathcost =
3949 } else {4005 map.findpath(flag.get_position(), coords, 0, path, check, 0, fields_necessity);
3950 // We know about this flag already4006 if (pathcost >= 0) {
3951 if (nearflags[endflag_hash].current_road_distance >4007 flag_candidates.set_road_possible(flag_candidate.coords_hash, path.get_nsteps());
3952 nearflags[start_field].current_road_distance + road->get_path().get_nsteps()) {4008 ++possible_roads_count;
3953 // ..but this current connection is shorter than one found before4009 }
3954 nearflags[endflag_hash].current_road_distance =4010 }
3955 nearflags[start_field].current_road_distance + road->get_path().get_nsteps();4011
3956 // So let re-check neighbours once more4012 // re-sorting again now by default by a score
3957 nearflags[endflag_hash].to_be_checked = true;4013 flag_candidates.sort();
3958 }4014
3959 }4015
3960 }4016 // Well and finally building the winning road (if any)
3961 }4017 const int32_t winner_min_score = (spots_ < kSpotsTooLittle) ? 50 : 25;
39624018
3963 // Sending calculated walking costs from nearflags to RoadCandidates to update info on4019 FlagCandidates::Candidate* winner = flag_candidates.get_winner(winner_min_score);
3964 // Candidate flags/roads4020 if (winner) {
3965 for (auto& nf_walk : nearflags) {4021 const Widelands::Coords target_coords = Coords::unhash(winner->coords_hash);
3966 // NearFlag contains also flags beyond check radius, these are not relevent for us4022
3967 if (RoadCandidates.has_candidate(nf_walk.second.flag->get_position().hash())) {4023 // This is to prohibit the flag for some time but with exemption of warehouse
3968 RoadCandidates.set_cur_road_distance(4024 if (flag_warehouse_distance.get_distance(winner->coords_hash, gametime, &tmp_wh) > 0) {
3969 nf_walk.second.flag->get_position(), nf_walk.second.current_road_distance);4025 flag_warehouse_distance.set_road_built(winner->coords_hash, gametime);
3970 }4026 }
3971 }4027 // and we straight away set distance of future flag
39724028 flag_warehouse_distance.set_distance(flag.get_position().hash(), winner->start_flag_dist_to_wh + winner->possible_road_distance,
3973 // Here we must consider how much are buildable fields lacking4029 gametime, 0); // faking the warehouse
3974 // the number will be transformed to a weight passed to findpath function4030
3975 int32_t fields_necessity = 0;4031 Path& path = *new Path();
3976 if (spots_ < kSpotsTooLittle) {
3977 fields_necessity += 10;
3978 }
3979 if (map_allows_seafaring_ && num_ports == 0) {
3980 fields_necessity += 10;
3981 }
3982 if (num_ports < 4) {
3983 fields_necessity += 5;
3984 }
3985 if (spots_ < kSpotsEnough) {
3986 fields_necessity += 5;
3987 }
3988 fields_necessity *= std::abs(management_data.get_military_number_at(64)) * 5;
3989
3990 // We need to sort these flags somehow, because we are not going to investigate all of them
3991 // so sorting first by current road length (that might contain fake values for flags that were
3992 // not reached over roads) and secondary by air_distance (nearer flags first)
3993 std::sort(std::begin(RoadCandidates.flags_queue), std::end(RoadCandidates.flags_queue),
3994 [](const FlagsForRoads::Candidate& a, const FlagsForRoads::Candidate& b) {
3995 // Here we are doing a kind of bucketing
3996 const int32_t a_length = a.current_road_length / 50;
3997 const int32_t b_length = b.current_road_length / 50;
3998 return std::tie(b_length, a.air_distance) < std::tie(a_length, b.air_distance);
3999 });
4000
4001 // Now we calculate roads from here to few best looking RoadCandidates....
4002 uint32_t possible_roads_count = 0;
4003 uint32_t current = 0; // hash of flag that we are going to calculate in the iteration
4004 while (possible_roads_count < 5 && RoadCandidates.get_best_uncalculated(&current)) {
4005 const Widelands::Coords coords = Coords::unhash(current);
4006 Path path;
4007
4008 // value of pathcost is not important, it just indicates, that the path can be built
4009 // We send this information to RoadCandidates, with length of possible road if applicable
4010 const int32_t pathcost =
4011 map.findpath(flag.get_position(), coords, 0, path, check, 0, fields_necessity);
4012 if (pathcost >= 0) {
4013 RoadCandidates.road_possible(coords, path.get_nsteps());
4014 possible_roads_count += 1;
4015 }
4016 }
4017
4018 // re-sorting again, now by reduction score (custom operator specified in .h file)
4019 std::sort(std::begin(RoadCandidates.flags_queue), std::end(RoadCandidates.flags_queue));
4020
4021 // Well and finally building the winning road (if any)
4022 uint32_t winner_hash = 0;
4023 if (RoadCandidates.get_winner(&winner_hash)) {
4024 const Widelands::Coords target_coords = Coords::unhash(winner_hash);
4025 Path& path = *new Path();
4026#ifndef NDEBUG4032#ifndef NDEBUG
4027 const int32_t pathcost =4033 const int32_t pathcost =
4028 map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);4034 map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
4029 assert(pathcost >= 0);4035 assert(pathcost >= 0);
4030#else4036#else
4031 map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);4037 map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
4032#endif4038#endif
4033 game().send_player_build_road(player_number(), path);4039 game().send_player_build_road(player_number(), path);
4034 return true;4040 return true;
4035 }4041 }
4036 // We can't build a road so let's block the vicinity as an indication this area is not4042 // We can't build a road so let's block the vicinity as an indication this area is not
4037 // connectible4043 // connectible
4038 // Usually we block for 2 minutes, but if it is a last attempt we block for 10 minutes4044 // Usually we block for 2 minutes, but if it is a last attempt we block for 10 minutes
4039 // Note: we block the vicinity only if this economy (usually a sole flag with a building) is not4045 // Note: we block the vicinity only if this economy (usually a sole flag with a building) is not
4040 // connected to a warehouse4046 // connected to a warehouse
4041 if (flag.get_economy()->warehouses().empty()) {4047 if (flag.get_economy()->warehouses().empty()) {
40424048
4043 // blocking only if latest block was less then 60 seconds ago or it is last attempt4049 // blocking only if latest block was less then 60 seconds ago or it is last attempt
4044 if (eco->fields_block_last_time + 60000 < gametime || last_attempt_) {4050 if (eco->fields_block_last_time + kOneMinute < gametime || last_attempt_) {
4045 eco->fields_block_last_time = gametime;4051 eco->fields_block_last_time = gametime;
40464052
4047 const uint32_t block_time = last_attempt_ ? 10 * 60 * 1000 : 2 * 60 * 1000;4053 const uint32_t block_time = last_attempt_ ? 10 * kOneMinute : 2 * kOneMinute;
40484054
4049 FindNodeAcceptAll buildable_functor;4055 FindNodeAcceptAll buildable_functor;
4050 CheckStepOwnTerritory check_own(player_, MOVECAPS_WALK, true);4056 CheckStepOwnTerritory check_own(player_, MOVECAPS_WALK, true);
40514057
4052 // get all flags within radius4058 // get all flags within radius
4053 std::vector<Coords> reachable_to_block;4059 std::vector<Coords> reachable_to_block;
4054 map.find_reachable_fields(Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius),4060 map.find_reachable_fields(Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius),
4055 &reachable_to_block, check_own, buildable_functor);4061 &reachable_to_block, check_own, buildable_functor);
40564062
4057 for (auto coords : reachable_to_block) {4063 for (auto coords : reachable_to_block) {
4058 blocked_fields.add(coords, game().get_gametime() + block_time);4064 blocked_fields.add(coords, game().get_gametime() + block_time);
4059 }4065 }
4060 }4066 }
40614067
4062 // If it last attempt we also destroy the flag (with a building if any attached)4068 // If it last attempt we also destroy the flag (with a building if any attached)
4063 if (last_attempt_) {4069 if (last_attempt_) {
4064 remove_from_dqueue<Widelands::Flag>(eco->flags, &flag);4070 remove_from_dqueue<Widelands::Flag>(eco->flags, &flag);
4065 game().send_player_bulldoze(*const_cast<Flag*>(&flag));4071 game().send_player_bulldoze(*const_cast<Flag*>(&flag));
4066 dead_ends_check_ = true;4072 dead_ends_check_ = true;
4067 return true;4073 return true;
4068 }4074 }
4069 }4075 }
4070 return false;4076 return false;
4077}
4078
4079void DefaultAI::collect_nearflags(std::map<uint32_t, NearFlag> &nearflags, const Flag& flag, const uint16_t checkradius) {
4080 // Algorithm to walk on roads
4081 // All nodes are marked as to_be_checked == true first and once the node is checked it is changed
4082 // to false. Under some conditions, the same node can be checked twice, the to_be_checked can
4083 // be set back to true. Because less hoops (fewer flag-to-flag roads) does not always mean
4084 // shortest road.
4085
4086 const Map& map = game().map();
4087
4088 for (;;) {
4089 // looking for a node with shortest existing road distance from starting flag and one that has
4090 // to be checked
4091 uint32_t start_field = kNoField;
4092 uint32_t nearest_distance = 10000;
4093 for (auto item : nearflags) {
4094 if (item.second.current_road_distance < nearest_distance && item.second.to_be_checked) {
4095 nearest_distance = item.second.current_road_distance;
4096 start_field = item.first;
4097 }
4098 }
4099 // OK, we failed to find a NearFlag where to_be_checked == true, so quitting the loop now
4100 if (start_field == kNoField) {
4101 break;
4102 }
4103
4104 nearflags[start_field].to_be_checked = false;
4105
4106 // Now going over roads leading from this flag
4107 for (uint8_t i = 1; i <= 6; ++i) {
4108 Road* const road = nearflags[start_field].flag->get_road(i);
4109
4110 if (!road) {
4111 continue;
4112 }
4113
4114 Flag* endflag = &road->get_flag(Road::FlagStart);
4115
4116 if (endflag == nearflags[start_field].flag) {
4117 endflag = &road->get_flag(Road::FlagEnd);
4118 }
4119
4120 const uint32_t endflag_hash = endflag->get_position().hash();
4121
4122 const int32_t dist = map.calc_distance(flag.get_position(), endflag->get_position());
4123
4124 if (dist > checkradius + 2) { // Testing bigger vicinity then checkradius....
4125 continue;
4126 }
4127
4128 // There is few scenarios for this neighbour flag
4129 if (nearflags.count(endflag_hash) == 0) {
4130 // This is brand new flag
4131 // calculating diff how much closer we will get to the flag
4132 nearflags[endflag_hash] =
4133 NearFlag(endflag, nearflags[start_field].current_road_distance +
4134 road->get_path().get_nsteps());
4135 } else {
4136 // We know about this flag already
4137 if (nearflags[endflag_hash].current_road_distance >
4138 nearflags[start_field].current_road_distance + road->get_path().get_nsteps()) {
4139 // ..but this current connection is shorter than one found before
4140 nearflags[endflag_hash].current_road_distance =
4141 nearflags[start_field].current_road_distance + road->get_path().get_nsteps();
4142 // So let re-check neighbours once more
4143 nearflags[endflag_hash].to_be_checked = true;
4144 }
4145 }
4146 }
4147 }
4148
4071}4149}
40724150
4073/**4151/**
40744152
=== modified file 'src/ai/defaultai.h'
--- src/ai/defaultai.h 2019-05-15 06:29:24 +0000
+++ src/ai/defaultai.h 2019-07-31 19:53:54 +0000
@@ -148,6 +148,7 @@
148 static constexpr int32_t kSpotsTooLittle = 15;148 static constexpr int32_t kSpotsTooLittle = 15;
149 static constexpr int kManagementUpdateInterval = 10 * 60 * 1000;149 static constexpr int kManagementUpdateInterval = 10 * 60 * 1000;
150 static constexpr int kStatUpdateInterval = 60 * 1000;150 static constexpr int kStatUpdateInterval = 60 * 1000;
151 static constexpr int kFlagWarehouseUpdInterval = 15 * 1000;
151152
152 // For vision and scheduling153 // For vision and scheduling
153 static constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();154 static constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();
@@ -198,11 +199,14 @@
198 bool improve_roads(uint32_t);199 bool improve_roads(uint32_t);
199 bool create_shortcut_road(const Widelands::Flag&,200 bool create_shortcut_road(const Widelands::Flag&,
200 uint16_t maxcheckradius,201 uint16_t maxcheckradius,
201 int16_t minReduction,
202 const uint32_t gametime);202 const uint32_t gametime);
203 // trying to identify roads that might be removed203 // trying to identify roads that might be removed
204 bool dispensable_road_test(const Widelands::Road&);204 bool dispensable_road_test(const Widelands::Road&);
205 bool dismantle_dead_ends();205 bool dismantle_dead_ends();
206 void collect_nearflags(std::map<uint32_t, Widelands::NearFlag> &, const Widelands::Flag&, const uint16_t);
207 // calculating distances from local warehouse to flags
208 void check_flag_distances(uint32_t);
209 Widelands::FlagWarehouseDistances flag_warehouse_distance;
206210
207 bool check_economies();211 bool check_economies();
208 bool check_productionsites(uint32_t);212 bool check_productionsites(uint32_t);
@@ -272,6 +276,7 @@
272 bool check_ships(uint32_t);276 bool check_ships(uint32_t);
273 bool attempt_escape(Widelands::ShipObserver& so);277 bool attempt_escape(Widelands::ShipObserver& so);
274278
279
275 // finding and owner280 // finding and owner
276 Widelands::PlayerNumber get_land_owner(const Widelands::Map&, uint32_t);281 Widelands::PlayerNumber get_land_owner(const Widelands::Map&, uint32_t);
277282
278283
=== added directory 'src/ai/test'
=== added file 'src/ai/test/CMakeLists.txt'
--- src/ai/test/CMakeLists.txt 1970-01-01 00:00:00 +0000
+++ src/ai/test/CMakeLists.txt 2019-07-31 19:53:54 +0000
@@ -0,0 +1,9 @@
1wl_test(test_ai
2 SRCS
3 ai_test_main.cc
4 test_ai.cc
5 DEPENDS
6 base_log
7 base_macros
8 ai
9)
010
=== added file 'src/ai/test/ai_test_main.cc'
--- src/ai/test/ai_test_main.cc 1970-01-01 00:00:00 +0000
+++ src/ai/test/ai_test_main.cc 2019-07-31 19:53:54 +0000
@@ -0,0 +1,21 @@
1/*
2 * Copyright (C) 2007-2019 by the Widelands Development Team
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 *
18 */
19
20#define BOOST_TEST_MODULE AI
21#include <boost/test/unit_test.hpp>
022
=== added file 'src/ai/test/test_ai.cc'
--- src/ai/test/test_ai.cc 1970-01-01 00:00:00 +0000
+++ src/ai/test/test_ai.cc 2019-07-31 19:53:54 +0000
@@ -0,0 +1,228 @@
1/*
2 * Copyright (C) 2007-2019 by the Widelands Development Team
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 *
18 */
19
20#include <exception>
21
22#include <boost/test/unit_test.hpp>
23
24#ifdef _WIN32
25#include "base/log.h"
26#endif
27#include "ai/ai_help_structs.h"
28#include "base/macros.h"
29
30// Triggered by BOOST_AUTO_TEST_CASE
31CLANG_DIAG_OFF("-Wdisabled-macro-expansion")
32
33namespace Widelands { // Needed?
34class World;
35} // namespace Widelands
36
37using namespace Widelands;
38
39BOOST_AUTO_TEST_SUITE(ai)
40
41BOOST_AUTO_TEST_CASE(flag_distance_soft_expiry) {
42 FlagWarehouseDistances fw;
43 uint32_t tmp_wh;
44 BOOST_CHECK_EQUAL(fw.get_distance(0, 0, &tmp_wh), 1000);
45 BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
46 BOOST_CHECK_EQUAL(fw.get_distance(1, 2, &tmp_wh), 2); // distance now 2
47 BOOST_CHECK_EQUAL(tmp_wh, 3);
48
49 // setting longer distance below soft_expiry time
50 BOOST_CHECK_EQUAL(fw.set_distance(1, 3, kFlagDistanceExpirationPeriod / 3, 4), false);
51 // distance to 3 not updated
52 BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod / 3, &tmp_wh), 2);
53 BOOST_CHECK_EQUAL(tmp_wh, 3);
54
55 // now setting after soft expiry
56 BOOST_CHECK_EQUAL(
57 fw.set_distance(1, 1, kFlagDistanceExpirationPeriod / 3, 6), true); // distance set to 1
58 BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod / 3, &tmp_wh), 1);
59 BOOST_CHECK_EQUAL(tmp_wh, 6);
60}
61BOOST_AUTO_TEST_CASE(flag_distance_below_expiry)
62/* Compare with void free_test_function() */
63{
64 FlagWarehouseDistances fw;
65 uint32_t tmp_wh;
66 BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
67
68 // setting longer distance after soft but below expiry time
69 BOOST_CHECK_EQUAL(fw.set_distance(1, 3, kFlagDistanceExpirationPeriod * 2 / 3, 5), true);
70 BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod * 2 / 3, &tmp_wh), 3);
71 BOOST_CHECK_EQUAL(tmp_wh, 5);
72}
73
74BOOST_AUTO_TEST_CASE(flag_distance_after_expiry)
75/* Compare with void free_test_function() */
76{
77 FlagWarehouseDistances fw;
78 uint32_t tmp_wh;
79 BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
80
81 // setting longer distance below expiry time
82 BOOST_CHECK_EQUAL(fw.set_distance(1, 3, 2 * kFlagDistanceExpirationPeriod, 5), true);
83 BOOST_CHECK_EQUAL(fw.get_distance(1, 3, &tmp_wh), 3);
84 BOOST_CHECK_EQUAL(tmp_wh, 5);
85}
86
87BOOST_AUTO_TEST_CASE(flag_distance_expiration_extension)
88/* setting the same distance restart the expiry_period */
89{
90 FlagWarehouseDistances fw;
91 uint32_t tmp_wh;
92 BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
93 BOOST_CHECK_EQUAL(
94 fw.set_distance(1, 2, 0, 3), false); // cannot reset the same distance in the same time
95
96 // Now we are after expiration time
97 BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod + 3, &tmp_wh), 1000);
98
99 // setting distance 2 time shortly one after another
100 BOOST_CHECK_EQUAL(fw.set_distance(1, 2, kFlagDistanceExpirationPeriod + 3, 5), true);
101 BOOST_CHECK_EQUAL(fw.set_distance(1, 2, kFlagDistanceExpirationPeriod + 10, 5), true);
102 // current expiry_time should be 2*kFlagDistanceExpirationPeriod + 10
103 BOOST_CHECK_EQUAL(fw.get_distance(1, 2 * kFlagDistanceExpirationPeriod, &tmp_wh), 2);
104 BOOST_CHECK_EQUAL(tmp_wh, 5);
105 BOOST_CHECK_EQUAL(fw.get_distance(1, 2 * kFlagDistanceExpirationPeriod + 15, &tmp_wh), 1000);
106}
107
108BOOST_AUTO_TEST_CASE(flag_distance_road_builtexpiration_extension)
109/* setting the same distance restart the expiry_period */
110{
111 FlagWarehouseDistances fw;
112 // No road built on fresh flag
113 BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
114 // get_distance(const uint32_t flag_coords, uint32_t gametime, uint32_t* nw)
115
116 // setting road we dont know about
117 fw.set_road_built(1, 0);
118 BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
119
120 // let fw knows about it
121 fw.set_distance(1, 2, 0, 3);
122 fw.set_road_built(1, 0);
123 BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), true);
124 BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 59999), true);
125 BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 60001), false);
126
127 BOOST_CHECK_EQUAL(fw.is_road_prohibited(2, 60001), false);
128}
129
130BOOST_AUTO_TEST_CASE(flag_distance_old_removal)
131/* setting the same distance restart the expiry_period */
132{
133 FlagWarehouseDistances fw;
134 fw.set_distance(1, 2, 0, 3);
135 BOOST_CHECK_EQUAL(fw.count(), 1);
136 BOOST_CHECK_EQUAL(fw.remove_old_flag(kOldFlagRemoveTime + kFlagDistanceExpirationPeriod), false);
137 BOOST_CHECK_EQUAL(fw.count(), 1);
138 BOOST_CHECK_EQUAL(
139 fw.remove_old_flag(kOldFlagRemoveTime + kFlagDistanceExpirationPeriod + 2), true);
140 BOOST_CHECK_EQUAL(fw.count(), 0);
141}
142
143BOOST_AUTO_TEST_CASE(new_flag_road_not_prohibited)
144/* setting the same distance restart the expiry_period */
145{
146 FlagWarehouseDistances fw;
147 // let fw knows about it
148 BOOST_CHECK_EQUAL(fw.count(), 0);
149 fw.set_distance(1, 2, 0, 3);
150 BOOST_CHECK_EQUAL(fw.count(), 1);
151 BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
152}
153
154BOOST_AUTO_TEST_CASE(flag_candidate_init)
155/* setting the same distance restart the expiry_period */
156{
157 FlagCandidates fc = FlagCandidates(10);
158 BOOST_CHECK_EQUAL(fc.count(), 0);
159}
160
161BOOST_AUTO_TEST_CASE(flag_candidate_winner_score) {
162 const uint16_t kCurFlDistToWh = 3;
163 const uint16_t kStartFlagToWh = 10;
164
165 const uint16_t kPosRoadDist = 5;
166 const uint16_t kCurRoadDistFlToFl = 17;
167
168 const uint32_t kTestedCoords = 11;
169
170 FlagCandidates fc = FlagCandidates(kStartFlagToWh);
171
172 // coord, different economy, distance to wh
173 fc.add_flag(kTestedCoords, false, kCurFlDistToWh, 1);
174 // setting coords, dist
175 BOOST_CHECK_EQUAL(fc.set_cur_road_distance(kTestedCoords, kCurRoadDistFlToFl), true);
176 BOOST_CHECK_EQUAL(
177 fc.set_cur_road_distance(1, 5), false); // we cannot set distance to unknown flag
178 BOOST_CHECK(!fc.get_winner()); // road not possible
179 // set length of possible road
180 BOOST_CHECK_EQUAL(fc.set_road_possible(kTestedCoords, kPosRoadDist), true);
181 BOOST_VERIFY(fc.get_winner());
182 BOOST_CHECK_EQUAL(fc.get_winner()->start_flag_dist_to_wh, kStartFlagToWh);
183 BOOST_CHECK_EQUAL(fc.get_winner()->cand_flag_distance_to_wh, kCurFlDistToWh);
184 BOOST_CHECK_EQUAL(fc.get_winner()->flag_to_flag_road_distance, kCurRoadDistFlToFl);
185 BOOST_CHECK_EQUAL(fc.get_winner()->possible_road_distance, kPosRoadDist);
186 BOOST_CHECK_EQUAL(fc.get_winner()->coords_hash, kTestedCoords);
187 BOOST_CHECK_EQUAL(fc.get_winner()->different_economy, false);
188
189 BOOST_CHECK_EQUAL(fc.get_winner()->score(),
190 +(kStartFlagToWh - kCurFlDistToWh) + (kCurRoadDistFlToFl - 2 * kPosRoadDist));
191}
192BOOST_AUTO_TEST_CASE(flag_candidates_sorting) {
193 FlagCandidates fc = FlagCandidates(10);
194
195 fc.add_flag(0, false, 10, 1);
196 fc.add_flag(1, false, 10, 1);
197 fc.add_flag(2, false, 10, 1);
198 BOOST_CHECK_EQUAL(fc.set_cur_road_distance(0, 5), true);
199 BOOST_CHECK_EQUAL(fc.set_cur_road_distance(1, 5), true);
200 BOOST_CHECK_EQUAL(fc.set_cur_road_distance(2, 5), true);
201 BOOST_CHECK_EQUAL(fc.set_road_possible(0, 4), true);
202 BOOST_CHECK_EQUAL(fc.set_road_possible(1, 2), true);
203 BOOST_CHECK_EQUAL(fc.set_road_possible(2, 3), true);
204 BOOST_CHECK_EQUAL(fc.get_winner()->coords_hash, 1); // sorted done automatically
205 BOOST_CHECK_EQUAL(fc.count(), 3);
206}
207
208BOOST_AUTO_TEST_CASE(flag_sort_by_air_distance) {
209 FlagCandidates fc = FlagCandidates(10);
210
211 fc.add_flag(0, false, 10, 4);
212 fc.add_flag(1, false, 10, 1);
213 fc.add_flag(2, false, 10, 2);
214 fc.sort_by_air_distance();
215 BOOST_CHECK_EQUAL(fc.flags()[0].air_distance, 1);
216}
217
218BOOST_AUTO_TEST_CASE(flag_has_candidate) {
219 FlagCandidates fc = FlagCandidates(10);
220
221 fc.add_flag(0, false, 10, 4);
222 fc.add_flag(1, false, 10, 1);
223 fc.add_flag(2, false, 10, 2);
224 BOOST_CHECK_EQUAL(fc.has_candidate(1), true);
225 BOOST_CHECK_EQUAL(fc.has_candidate(3), false);
226}
227
228BOOST_AUTO_TEST_SUITE_END()

Subscribers

People subscribed via source and target branches

to status/vote changes: