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

[TiborB]

Not ready for merge

This is just to trigger the build process

[TiborB (tiborb95)]

I dont see any build here, why?

[hessenfarmer (stephan-lutz)]

The appveyor builds failed you need to merge trunk first.

[TiborB (tiborb95)]

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

[hessenfarmer (stephan-lutz)]

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

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

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

[bunnybot (widelandsofficial)]

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.

[hessenfarmer (stephan-lutz)]

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

review: Approve

[GunChleoc (gunchleoc)]

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

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

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

[TiborB (tiborb95)]

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

[bunnybot (widelandsofficial)]

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.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

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

[TiborB (tiborb95)]

Failed only because of some network issues

[hessenfarmer (stephan-lutz)]

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

[TiborB (tiborb95)]

OK, let wait then...

[GunChleoc (gunchleoc)]

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

[TiborB (tiborb95)]

See my answer.

[TiborB (tiborb95)]

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

[GunChleoc (gunchleoc)]

Looking good, let's have it :)

@bunnybot merge

[bunnybot (widelandsofficial)]

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

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

[hessenfarmer (stephan-lutz)]

transient failure on travis

@bunnybot merge force

=== 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 @@
     logic_map_objects
     scripting_lua_table
 )
+add_subdirectory(test)

=== 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 @@
 
 #include "ai/ai_help_structs.h"
 
+#include <algorithm>
+
 #include "base/macros.h"
 #include "base/time_string.h"
 #include "logic/ai_dna_handler.h"
@@ -27,10 +29,6 @@
 
 namespace Widelands {
 
-// couple of constants for calculation of road interconnections
-constexpr int kRoadPossiblyBuildable = 200;
-constexpr int kConnectedByRoads = 400;
-constexpr int kNotConnectedByRoads = 600;
 constexpr int kNoAiTrainingMutation = 200;
 constexpr int kUpperDefaultMutationLimit = 150;
 constexpr int kLowerDefaultMutationLimit = 75;
@@ -307,7 +305,7 @@
      // count of rocks can only decrease, so  amount of rocks
      // is recalculated only when previous count is positive
      // count of water fields are stable, so if the current count is
-     // non-negative, water is not recaldulated
+     // non-negative, water is not recalculated
      rocks_nearby(1),
      water_nearby(-1),
      open_water_nearby(-1),
@@ -974,120 +972,6 @@
 	return (blocked_fields_.count(coords.hash()) != 0);
 }
 
-// As a policy, we just set some default value, that will be updated later on
-FlagsForRoads::Candidate::Candidate(uint32_t coords, int32_t distance, bool different_economy)
-   : coords_hash(coords), air_distance(distance) {
-	new_road_possible = false;
-	// Just custom values
-	new_road_length = kRoadPossiblyBuildable;
-	current_road_length = (different_economy) ? kNotConnectedByRoads : kConnectedByRoads;
-}
-
-// Used when sorting cadidate flags from best one
-bool FlagsForRoads::Candidate::operator<(const Candidate& other) const {
-	const int32_t other_rs = other.reduction_score();
-	const int32_t this_rs = reduction_score();
-	return std::tie(other.new_road_possible, other_rs) < std::tie(new_road_possible, this_rs);
-}
-
-bool FlagsForRoads::Candidate::operator==(const Candidate& other) const {
-	return coords_hash == other.coords_hash;
-}
-
-int32_t FlagsForRoads::Candidate::reduction_score() const {
-	return current_road_length - new_road_length - (new_road_length - air_distance) / 3;
-}
-
-void FlagsForRoads::print() {  // this is for debugging and development purposes
-	for (auto& candidate_flag : flags_queue) {
-		log("   %starget: %3dx%3d, saving: %5d (%3d), air distance: %3d, new road: %6d, score: %5d "
-		    "%s\n",
-		    (candidate_flag.reduction_score() >= min_reduction && candidate_flag.new_road_possible) ?
-		       "+" :
-		       " ",
-		    Coords::unhash(candidate_flag.coords_hash).x,
-		    Coords::unhash(candidate_flag.coords_hash).y,
-		    candidate_flag.current_road_length - candidate_flag.new_road_length, min_reduction,
-		    candidate_flag.air_distance, candidate_flag.new_road_length,
-		    candidate_flag.reduction_score(),
-		    (candidate_flag.new_road_possible) ? ", new road possible" : " ");
-	}
-}
-
-// Queue is ordered but some target flags are only estimations so we take such a candidate_flag
-// first
-bool FlagsForRoads::get_best_uncalculated(uint32_t* winner) {
-	for (auto& candidate_flag : flags_queue) {
-		if (!candidate_flag.new_road_possible) {
-			*winner = candidate_flag.coords_hash;
-			return true;
-		}
-	}
-	return false;
-}
-
-// Road from starting flag to this flag can be built
-void FlagsForRoads::road_possible(Widelands::Coords coords, const uint32_t new_road) {
-	for (auto& candidate_flag : flags_queue) {
-		if (candidate_flag.coords_hash == coords.hash()) {
-			candidate_flag.new_road_length = new_road;
-			candidate_flag.new_road_possible = true;
-			candidate_flag.reduction_score();
-			return;
-		}
-	}
-	NEVER_HERE();
-}
-
-// find_reachable_fields returns duplicates so we deal with them
-bool FlagsForRoads::has_candidate(const uint32_t hash) {
-	for (auto& candidate_flag : flags_queue) {
-		if (candidate_flag.coords_hash == hash) {
-			return true;
-		}
-	}
-	return false;
-}
-
-// Updating walking distance into flags_queue
-void FlagsForRoads::set_cur_road_distance(Widelands::Coords coords, int32_t cur_distance) {
-	for (auto& candidate_flag : flags_queue) {
-		if (candidate_flag.coords_hash == coords.hash()) {
-			candidate_flag.current_road_length = cur_distance;
-			candidate_flag.reduction_score();
-			return;
-		}
-	}
-}
-
-// Returns mostly best candidate, as a result of sorting
-bool FlagsForRoads::get_winner(uint32_t* winner_hash) {
-	// If AI can ask for 2nd position, but there is only one viable candidate
-	// we return the first one of course
-	bool has_winner = false;
-	for (auto candidate_flag : flags_queue) {
-		if (candidate_flag.reduction_score() < min_reduction || !candidate_flag.new_road_possible ||
-		    candidate_flag.new_road_length * 2 > candidate_flag.current_road_length) {
-			continue;
-		}
-		assert(candidate_flag.air_distance > 0);
-		assert(candidate_flag.reduction_score() >= min_reduction);
-		assert(candidate_flag.new_road_possible);
-		*winner_hash = candidate_flag.coords_hash;
-		has_winner = true;
-
-		if (std::rand() % 4 > 0) {
-			// with probability of 3/4 we accept this flag
-			return true;
-		}
-	}
-
-	if (has_winner) {
-		return true;
-	}
-	return false;
-}
-
 PlayersStrengths::PlayersStrengths() : update_time(0) {
 }
 
@@ -1417,4 +1301,190 @@
 	return update_time;
 }
 
+FlagWarehouseDistances::FlagInfo::FlagInfo(const uint32_t gametime,
+                                           const uint16_t dist,
+                                           const uint32_t wh) {
+	expiry_time = gametime + kFlagDistanceExpirationPeriod;
+	soft_expiry_time = gametime + kFlagDistanceExpirationPeriod / 2;
+	distance = dist;
+	nearest_warehouse = wh;
+	new_road_prohibited_till = 0;
+}
+FlagWarehouseDistances::FlagInfo::FlagInfo() {
+	expiry_time = 0;
+	distance = 1000;
+	new_road_prohibited_till = 0;
+}
+
+// We are updating the distance info, but not all the time.
+// Always if after soft expiration period, but
+// if below expiration period only when the new value is lower than current one
+// In both cases new expiration times are calculated
+bool FlagWarehouseDistances::FlagInfo::update(const uint32_t gametime,
+                                              const uint16_t new_distance,
+                                              const uint32_t nearest_wh) {
+	const uint32_t new_expiry_time = gametime + kFlagDistanceExpirationPeriod;
+
+	if (gametime > soft_expiry_time) {
+		distance = new_distance;
+		expiry_time = new_expiry_time;
+		soft_expiry_time = gametime + kFlagDistanceExpirationPeriod / 2;
+		nearest_warehouse = nearest_wh;
+		return true;
+	} else if (new_distance < distance || (new_distance == distance &&
+	                                       expiry_time < new_expiry_time)) {
+		distance = new_distance;
+		expiry_time = new_expiry_time;
+		nearest_warehouse = nearest_wh;
+		return true;
+	}
+	return false;
+}
+
+uint16_t FlagWarehouseDistances::FlagInfo::get(const uint32_t gametime, uint32_t* nw) const {
+	*nw = nearest_warehouse;
+	if (gametime <= expiry_time) {
+		return distance;
+	}
+	return kFarButReachable;
+}
+
+void FlagWarehouseDistances::FlagInfo::set_road_built(const uint32_t gametime) {
+	// Prohibiting for next 60 seconds
+	new_road_prohibited_till = gametime + 60 * 1000;
+}
+
+bool FlagWarehouseDistances::FlagInfo::is_road_prohibited(const uint32_t gametime) const {
+	return new_road_prohibited_till > gametime;
+}
+
+bool FlagWarehouseDistances::set_distance(const uint32_t flag_coords,
+                                          const uint16_t distance,
+                                          uint32_t const gametime,
+                                          uint32_t const nearest_warehouse) {
+	if (flags_map.count(flag_coords) == 0) {
+		flags_map[flag_coords] =
+		   FlagWarehouseDistances::FlagInfo(gametime, distance, nearest_warehouse);
+		return true;
+	}
+	return flags_map[flag_coords].update(gametime, distance, nearest_warehouse);
+}
+
+uint16_t FlagWarehouseDistances::count() const {
+	return flags_map.size();
+}
+
+int16_t
+FlagWarehouseDistances::get_distance(const uint32_t flag_coords, uint32_t gametime, uint32_t* nw) {
+	if (flags_map.count(flag_coords) == 0) {
+		*nw = 0;
+		return kFarButReachable;  // this is to discourage to build second road from brand new flag...
+	} else {
+		return flags_map[flag_coords].get(gametime, nw);
+	}
+}
+
+void FlagWarehouseDistances::set_road_built(const uint32_t coords_hash, const uint32_t gametime) {
+	if (flags_map.count(coords_hash) == 1) {
+		flags_map[coords_hash].set_road_built(gametime);
+	}
+}
+
+bool FlagWarehouseDistances::is_road_prohibited(const uint32_t coords_hash,
+                                                 const uint32_t gametime) {
+	if (flags_map.count(coords_hash) == 1) {
+		return flags_map[coords_hash].is_road_prohibited(gametime);
+	}
+	return false;
+}
+
+bool FlagWarehouseDistances::remove_old_flag(uint32_t gametime) {
+	for (std::map<uint32_t, FlagWarehouseDistances::FlagInfo>::iterator it = flags_map.begin();
+	     it != flags_map.end(); it++) {
+		if (it->second.expiry_time + kOldFlagRemoveTime < gametime) {
+			it = flags_map.erase(it);
+			return true;
+		}
+	}
+	return false;
+}
+
+// Returns pointer to winning road, provided that the treshold is exceeded
+FlagCandidates::Candidate* FlagCandidates::get_winner(const int16_t threshold) {
+	if (flags_.empty()) {
+		return nullptr;
+	}
+	sort();
+	if (flags_[0].score() < threshold) {
+		return nullptr;
+	}
+	if (!flags_[0].is_buildable()) {
+		return nullptr;
+	}
+	return &flags_[0];
+}
+
+FlagCandidates::Candidate::Candidate(
+   const uint32_t c_hash, bool different_eco, uint16_t start_f_dist, uint16_t act_dist_to_wh, uint16_t air_dst) {
+	coords_hash = c_hash;
+	different_economy = different_eco;
+	start_flag_dist_to_wh = start_f_dist;
+	flag_to_flag_road_distance = 0;
+	possible_road_distance = kFarButReachable;
+	cand_flag_distance_to_wh = act_dist_to_wh;
+	air_distance = air_dst;
+}
+
+int16_t FlagCandidates::Candidate::score() const {
+	return different_economy * 2000 + (start_flag_dist_to_wh - cand_flag_distance_to_wh) +
+	       (flag_to_flag_road_distance - 2 * possible_road_distance);
+}
+
+bool FlagCandidates::set_road_possible(const uint32_t coords_hash, const uint16_t steps) {
+	for (auto& item : flags_) {
+		if (item.coords_hash == coords_hash) {
+			item.possible_road_distance = steps;
+			return true;
+		}
+	}
+	return false;
+}
+
+bool FlagCandidates::set_cur_road_distance(const uint32_t coords, uint16_t dist) {
+	for (auto& item : flags_) {
+		if (item.coords_hash == coords) {
+			item.flag_to_flag_road_distance = dist;
+			return true;
+		}
+	}
+	return false;
+}
+void FlagCandidates::sort() {
+	std::sort(flags_.begin(), flags_.end());
+}
+
+void FlagCandidates::sort_by_air_distance() {
+	std::sort(flags_.begin(), flags_.end(),
+	          [](const FlagCandidates::Candidate& lf, const FlagCandidates::Candidate& rf) {
+		          return lf.air_distance < rf.air_distance;
+	          });
+}
+
+void FlagCandidates::add_flag(const uint32_t coords,
+                              const bool different_economy,
+                              const uint16_t act_dist_to_wh,
+                              const uint16_t air_distance) {
+	flags_.push_back(
+	   Candidate(coords, different_economy, start_flag_dist_to_wh, act_dist_to_wh, air_distance));
+}
+
+bool FlagCandidates::has_candidate(const uint32_t coords_hash) const {
+	for (auto& item : flags_) {
+		if (item.coords_hash == coords_hash) {
+			return true;
+		}
+	}
+	return false;
+}
+
 }  // namespace Widelands

=== 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 @@
 #ifndef WL_AI_AI_HELP_STRUCTS_H
 #define WL_AI_AI_HELP_STRUCTS_H
 
+#include <algorithm>
 #include <list>
 #include <queue>
 #include <unordered_set>
@@ -107,6 +108,7 @@
 	kCheckEnemySites,
 	kManagementUpdate,
 	kUpdateStats,
+	kWarehouseFlagDist,
 	kUnset
 };
 
@@ -122,9 +124,20 @@
 // TODO(tiborb): this should be replaced by command line switch
 constexpr int kFNeuronBitSize = 32;
 constexpr int kMutationRatePosition = 42;
+// This is expiration time for distance from a flag to nearest warehouse
+constexpr int kFlagDistanceExpirationPeriod = 120 * 1000;
+// If the distance of flag-warehouse was not updated for this time, we presume that the flag
+// does not exist anymore and remove it
+constexpr int kOldFlagRemoveTime = 5 * 60 * 1000;
 
 constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();
 
+constexpr uint32_t kNoField = std::numeric_limits<uint32_t>::max();
+
+constexpr uint32_t kOneMinute = 60 * 1000;
+
+constexpr uint16_t kFarButReachable = 1000;
+
 struct CheckStepRoadAI {
 	CheckStepRoadAI(Player* const pl, uint8_t const mc, bool const oe);
 
@@ -527,8 +540,10 @@
 };
 
 struct WarehouseSiteObserver {
+
 	Widelands::Warehouse* site;
 	BuildingObserver* bo;
+	uint32_t flag_distances_last_update;
 };
 
 struct ShipObserver {
@@ -766,53 +781,6 @@
 	std::map<uint32_t, uint32_t> blocked_fields_;
 };
 
-// list of candidate flags to build roads, with some additional logic
-struct FlagsForRoads {
-
-	explicit FlagsForRoads(int32_t mr) : min_reduction(mr) {
-	}
-
-	struct Candidate {
-		Candidate();
-		Candidate(uint32_t coords, int32_t distance, bool different_economy);
-
-		uint32_t coords_hash;
-		int32_t new_road_length;
-		int32_t current_road_length;
-		int32_t air_distance;
-
-		bool new_road_possible;
-
-		bool operator<(const Candidate& other) const;
-		bool operator==(const Candidate& other) const;
-		int32_t reduction_score() const;
-	};
-
-	int32_t min_reduction;
-	// This is the core of this object - candidate flags to be ordered by air_distance
-	std::deque<Candidate> flags_queue;
-
-	void add_flag(Widelands::Coords coords, int32_t air_dist, bool different_economy) {
-		flags_queue.push_back(Candidate(coords.hash(), air_dist, different_economy));
-	}
-
-	uint32_t count() {
-		return flags_queue.size();
-	}
-	bool has_candidate(uint32_t hash);
-
-	// This is for debugging and development purposes
-	void print();
-	// during processing we need to pick first one uprocessed flag (with best score so far)
-	bool get_best_uncalculated(uint32_t* winner);
-	// When we test candidate flag if road can be built to it, there are two possible outcomes:
-	void road_possible(Widelands::Coords coords, uint32_t new_road);
-	// Updating walking distance over existing roads
-	void set_cur_road_distance(Widelands::Coords coords, int32_t cur_distance);
-	// Finally we query the flag that we will build a road to
-	bool get_winner(uint32_t* winner_hash);
-};
-
 // This is a struct that stores strength of players, info on teams and provides some outputs from
 // these data
 struct PlayersStrengths {
@@ -891,6 +859,97 @@
 	PlayerNumber this_player_number;
 	PlayerNumber this_player_team;
 };
+
+// This is a wrapper around map of <Flag coords hash:distance from flag to nearest warehouse>
+// Flags does not have observers so this stuct server like "lazy" substitution for this, where
+// keys are hash of flags positions
+// This "lives" during entire "session", and is not saved, but is easily recalulated
+struct FlagWarehouseDistances {
+private:
+	struct FlagInfo {
+		FlagInfo();
+		FlagInfo(uint32_t, uint16_t, uint32_t);
+		// Distance to a nearest warehouse expires, but in two stages
+		// This is complete expiration and such flag is treated as without distance to WH
+		uint32_t expiry_time;
+		// When recalculating new distance, if the current information is younger than
+		// soft_expiry_time it is only decreased if new value is smaller After soft_expiry_time is
+		// updated in any case
+		uint32_t soft_expiry_time;
+		uint16_t distance;
+		// This is coords hash of nearest warehouse, not used by now
+		uint32_t nearest_warehouse;
+		// after building of new road, the distance information is updated not immediately so
+		// we prohibit current flag from another road building...
+		uint32_t new_road_prohibited_till;
+
+		bool update(uint32_t, uint16_t, uint32_t);
+		// Saying the road was built and when
+		void set_road_built(uint32_t);
+		// Asking if road can be built from this flag (providing current gametime)
+		bool is_road_prohibited(uint32_t) const;
+		// get current distance (providing current gametime)
+		uint16_t get(uint32_t, uint32_t*) const;
+	};
+	std::map<uint32_t, FlagInfo> flags_map;
+
+public:
+	// All these function uses lookup in flags_map so first argument is usually flag coords hash
+	bool set_distance(uint32_t flag_coords, uint16_t distance, uint32_t gametime, uint32_t nearest_warehouse);
+	int16_t get_distance(uint32_t flag_coords, uint32_t gametime, uint32_t* nw);
+	void set_road_built(uint32_t coords_hash, uint32_t gametime);
+	bool is_road_prohibited(uint32_t coords_hash, uint32_t gametime);
+	uint16_t count() const;
+	bool remove_old_flag(uint32_t gametime);
+};
+
+// This is one-time structure - initiated and filled up when investigating possible roads to be
+// built to a flag. At the end the flags are scored based on gained info), ordered and if treshold is
+// achieved the road is to be built
+struct FlagCandidates {
+
+	explicit FlagCandidates(uint16_t wd) : start_flag_dist_to_wh(wd) {
+	}
+
+	struct Candidate {
+		Candidate() = delete;
+		Candidate(uint32_t, bool, uint16_t, uint16_t, uint16_t);
+		uint16_t air_distance;
+		uint32_t coords_hash;
+		bool different_economy;
+		uint16_t start_flag_dist_to_wh;
+		uint16_t flag_to_flag_road_distance;
+		uint16_t possible_road_distance;
+		uint16_t cand_flag_distance_to_wh;
+		// Scoring is considering multiple things
+		int16_t score() const;
+		bool is_buildable() {
+			return possible_road_distance > 0;
+		}
+		bool operator<(const Candidate& other) const {
+			return score() > other.score();
+		}
+	};
+
+private:
+	std::vector<Candidate> flags_;
+	uint16_t start_flag_dist_to_wh;
+
+public:
+	const std::vector<Candidate>& flags() const {
+		return flags_;
+	}
+	bool has_candidate(uint32_t) const;
+	void add_flag(uint32_t, bool, uint16_t, uint16_t);
+	bool set_cur_road_distance(uint32_t, uint16_t);
+	bool set_road_possible(uint32_t, uint16_t);
+	void sort();
+	void sort_by_air_distance();
+	uint32_t count() {
+		return flags_.size();
+	}
+	FlagCandidates::Candidate* get_winner(const int16_t = 0);
+};
 }  // namespace Widelands
 
 #endif  // end of include guard: WL_AI_AI_HELP_STRUCTS_H

=== 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 @@
 			set_taskpool_task_time(gametime + 1000, SchedulerTaskId::kRoadCheck);
 			// testing 5 roads
 			{
-				const int32_t roads_to_check = (roads.size() < 20) ? 1 : 3;
+				const int32_t roads_to_check = roads.size() / 30 + 1;
 				for (int j = 0; j < roads_to_check; j += 1) {
 					// improve_roads function will test one road and rotate roads vector
 					if (improve_roads(gametime)) {
@@ -486,6 +486,10 @@
 			update_player_stat(gametime);
 			set_taskpool_task_time(gametime + kStatUpdateInterval, SchedulerTaskId::kUpdateStats);
 			break;
+		case SchedulerTaskId::kWarehouseFlagDist:
+			check_flag_distances(gametime);
+			set_taskpool_task_time(gametime + kFlagWarehouseUpdInterval, SchedulerTaskId::kWarehouseFlagDist);
+			break;
 		case SchedulerTaskId::kUnset:
 			NEVER_HERE();
 		}
@@ -958,6 +962,9 @@
 	taskPool.push_back(SchedulerTask(
 	   std::max<uint32_t>(gametime, 10 * 1000), SchedulerTaskId::kUpdateStats, 15, "review"));
 
+	taskPool.push_back(SchedulerTask(
+	   std::max<uint32_t>(gametime, 10 * 1000), SchedulerTaskId::kWarehouseFlagDist, 5, "Flag-Warehouse Update"));
+
 	const Map& map = game().map();
 
 	// here we scan entire map for own ships
@@ -1053,7 +1060,7 @@
 	   kExpeditionMinDuration +
 	   static_cast<double>(off) * (kExpeditionMaxDuration - kExpeditionMinDuration) / scope;
 	log(" %d: expedition max duration = %u (%u minutes), map area root: %u\n", player_number(),
-	    expedition_max_duration / 1000, expedition_max_duration / 60000, map_area_root);
+	    expedition_max_duration / 1000, expedition_max_duration / kOneMinute, map_area_root);
 	assert(expedition_max_duration >= kExpeditionMinDuration);
 	assert(expedition_max_duration <= kExpeditionMaxDuration);
 
@@ -3422,6 +3429,70 @@
 	return true;
 }
 
+
+// Re-calculating warehouse to flag distances
+void DefaultAI::check_flag_distances(const uint32_t gametime) {
+	for (WarehouseSiteObserver& wh_obs : warehousesites) {
+		uint16_t checked_flags = 0;
+		const uint32_t this_wh_hash = wh_obs.site->get_position().hash();
+		uint32_t highest_distance_set = 0;
+
+		std::queue<Widelands::Flag*>
+		   remaining_flags;  // only used to collect flags reachable walk over roads
+		remaining_flags.push(&wh_obs.site->base_flag());
+		flag_warehouse_distance.set_distance(
+		   wh_obs.site->base_flag().get_position().hash(), 0, gametime, this_wh_hash);
+		uint32_t tmp_wh;
+		assert(flag_warehouse_distance.get_distance(
+		          wh_obs.site->base_flag().get_position().hash(), gametime, &tmp_wh) == 0);
+
+		// Algorithm to walk on roads
+		// All nodes are marked as to_be_checked == true first and once the node is checked it is
+		// changed to false. Under some conditions, the same node can be checked twice, the
+		// to_be_checked can be set back to true. Because less hoops (fewer flag-to-flag roads) does
+		// not always mean shortest road.
+		while (!remaining_flags.empty()) {
+			++checked_flags;
+			// looking for a node with shortest existing road distance from starting flag and one that
+			// has to be checked Now going over roads leading from this flag
+			const uint16_t current_flag_distance = flag_warehouse_distance.get_distance(
+			   remaining_flags.front()->get_position().hash(), gametime, &tmp_wh);
+			for (uint8_t i = 1; i <= 6; ++i) {
+				Road* const road = remaining_flags.front()->get_road(i);
+
+				if (!road) {
+					continue;
+				}
+
+				Flag* endflag = &road->get_flag(Road::FlagStart);
+
+				if (endflag == remaining_flags.front()) {
+					endflag = &road->get_flag(Road::FlagEnd);
+				}
+				const uint16_t steps_count = road->get_path().get_nsteps();
+
+				// Calculated distance can be used or ignored if f.e. longer than via other route
+				bool const updated = flag_warehouse_distance.set_distance(
+				   endflag->get_position().hash(), current_flag_distance + steps_count, gametime,
+				   this_wh_hash);
+
+				if (highest_distance_set < current_flag_distance + steps_count) {
+					highest_distance_set = current_flag_distance + steps_count;
+				}
+
+				if (updated) {
+					remaining_flags.push(endflag);
+				}
+			}
+			remaining_flags.pop();
+		}
+
+	}
+
+	// Now let do some lazy pruning - remove the flags that were not updated for long
+	flag_warehouse_distance.remove_old_flag(gametime);
+}
+
 // Here we pick about 25 roads and investigate them. If it is a dead end we dismantle it
 bool DefaultAI::dismantle_dead_ends() {
 	bool road_dismantled = false;
@@ -3538,50 +3609,36 @@
 	}
 
 	bool is_warehouse = false;
-	bool has_building = false;
 	if (Building* b = flag.get_building()) {
-		has_building = true;
 		BuildingObserver& bo = get_building_observer(b->descr().name().c_str());
 		if (bo.type == BuildingObserver::Type::kWarehouse) {
 			is_warehouse = true;
 		}
 	}
+	const uint32_t flag_coords_hash = flag.get_position().hash();
 
-	// is connected to a warehouse?
+	if (flag_warehouse_distance.is_road_prohibited(flag_coords_hash, gametime)) {return false;}
 	const bool needs_warehouse = flag.get_economy()->warehouses().empty();
 
-	if (!has_building && flag.nr_of_roads() == 1) {
-		return false;
-	} else if (is_warehouse && flag.nr_of_roads() <= 3) {
-		// Do nothing
-	} else if (needs_warehouse) {
-		// Do nothing
-	} else if (flag.current_wares() > 5) {
-		// Do nothing
-	} else if (has_building && std::rand() % 3 == 0) {
-		// Do nothing
-	} else if (std::rand() % 10 == 0) {
-		// Do nothing
-	} else {
-		return false;
-	}
-
-	int16_t expected_shortcut = 27;
-	if (has_building) {
-		expected_shortcut -= 3;
-	}
-	expected_shortcut -= flag.current_wares() * 3;
-	if (is_warehouse) {
-		expected_shortcut -= 10;
-	}
-	if (std::rand() % 5 == 0) {
-		expected_shortcut -= 10;
-	}
-	expected_shortcut -= 2 * flag.nr_of_roads();
-
-	create_shortcut_road(flag, 14, expected_shortcut, gametime);
-
-	return true;
+	uint32_t tmp_wh;
+
+	// when deciding if we attempt to build a road from here we use probability
+	uint16_t probability_score = 0;
+	if (flag.nr_of_roads() == 1) {probability_score += 20;}
+	if (is_warehouse && flag.nr_of_roads() <= 3) {probability_score += 20;}
+	probability_score += flag.current_wares() * 5;
+	if (needs_warehouse) {probability_score += 500;}
+	if (std::rand() % 10 == 0) {
+	probability_score += flag_warehouse_distance.get_distance(flag_coords_hash, gametime, &tmp_wh);
+	}
+
+	if (std::rand() % 200 < probability_score) {
+		create_shortcut_road(flag, 14, gametime);
+		return true;
+	}
+
+	return false;
+
 }
 
 // This function takes a road (road is smallest section of roads with two flags on the ends)
@@ -3756,318 +3813,339 @@
 // connection is not known
 bool DefaultAI::create_shortcut_road(const Flag& flag,
                                      uint16_t checkradius,
-                                     int16_t min_reduction,
                                      uint32_t gametime) {
 
-	// Increasing the failed_connection_tries counter
-	// At the same time it indicates a time an economy is without a warehouse
-	EconomyObserver* eco = get_economy_observer(flag.economy());
-	// if we passed grace time this will be last attempt and if it fails
-	// building is destroyes
-	bool last_attempt_ = false;
-
-	// this should not happen, but if the economy has a warehouse and a dismantle
-	// grace time set, we must 'zero' the dismantle grace time
-	if (!flag.get_economy()->warehouses().empty() &&
-	    eco->dismantle_grace_time != std::numeric_limits<uint32_t>::max()) {
-		eco->dismantle_grace_time = std::numeric_limits<uint32_t>::max();
-	}
-
-	// first we deal with situations when this is economy with no warehouses
-	// and this is a flag belonging to a building/constructionsite
-	// such economy must get dismantle grace time (if not set yet)
-	// end sometimes extended checkradius
-	if (flag.get_economy()->warehouses().empty() && flag.get_building()) {
-
-		// occupied military buildings get special treatment
-		// (extended grace time + longer radius)
-		bool occupied_military_ = false;
-		Building* b = flag.get_building();
-		if (upcast(MilitarySite, militb, b)) {
-			if (militb->soldier_control()->stationed_soldiers().size() > 0) {
-				occupied_military_ = true;
-			}
-		}
-
-		// check if we are within grace time, if not or gracetime unset we need to do something
-		// if we are within gracetime we do nothing (this loop is skipped)
-
-		// if grace time is not set, this is probably first time without a warehouse and we must set
-		// it
-		if (eco->dismantle_grace_time == std::numeric_limits<uint32_t>::max()) {
-
-			// constructionsites
-			if (upcast(ConstructionSite const, constructionsite, flag.get_building())) {
-				BuildingObserver& bo =
-				   get_building_observer(constructionsite->building().name().c_str());
-				// first very special case - a port (in the phase of constructionsite)
-				// this might be a new colonization port
-				if (bo.is(BuildingAttribute::kPort)) {
-					eco->dismantle_grace_time = gametime + 60 * 60 * 1000;  // one hour should be enough
-				} else {  // other constructionsites, usually new (standalone) constructionsites
-					eco->dismantle_grace_time =
-					   gametime + 30 * 1000 +            // very shot time is enough
-					   (eco->flags.size() * 30 * 1000);  // + 30 seconds for every flag in economy
-				}
-
-				// buildings
-			} else {
-
-				if (occupied_military_) {
-					eco->dismantle_grace_time =
-					   (gametime + 90 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
-
-				} else {  // for other normal buildings
-					eco->dismantle_grace_time =
-					   gametime + (45 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
-				}
-			}
-
-			// we have passed grace_time - it is time to dismantle
-		} else if (eco->dismantle_grace_time <= gametime) {
-			last_attempt_ = true;
-			// we increase a check radius in last attempt
-			checkradius += 2;
-		}
-
-		// and bonus for occupied military buildings:
-		if (occupied_military_) {
-			checkradius += 4;
-		}
-
-		// and generally increase radius for unconnected buildings
-		checkradius += 2;
-	}
-
-	// Now own roadfinding stuff
-	const Map& map = game().map();
-
-	// initializing new object of FlagsForRoads, we will push there all candidate flags
-	// First we dont even know if a road can be built there (from current flag)
-	Widelands::FlagsForRoads RoadCandidates(min_reduction);
-
-	FindNodeWithFlagOrRoad functor;
-	CheckStepRoadAI check(player_, MOVECAPS_WALK, true);
-
-	// get all flags within radius
-	std::vector<Coords> reachable;
-	map.find_reachable_fields(
-	   Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius), &reachable, check, functor);
-
-	for (const Coords& reachable_coords : reachable) {
-
-		// ignore starting flag, of course
-		if (reachable_coords == flag.get_position()) {
-			continue;
-		}
-
-		// first make sure there is an immovable (should be, but still)
-		if (upcast(PlayerImmovable const, player_immovable, map[reachable_coords].get_immovable())) {
-
-			// if it is the road, make a flag there
-			if (dynamic_cast<const Road*>(map[reachable_coords].get_immovable())) {
-				game().send_player_build_flag(player_number(), reachable_coords);
-			}
-
-			// do not go on if it is not a flag
-			if (!dynamic_cast<const Flag*>(map[reachable_coords].get_immovable())) {
-				continue;
-			}
-
-			// testing if a flag/road's economy has a warehouse, if not we are not
-			// interested to connect to it
-			if (player_immovable->economy().warehouses().size() == 0) {
-				continue;
-			}
-
-			// This is a candidate, sending all necessary info to RoadCandidates
-			const bool different_economy = (player_immovable->get_economy() != flag.get_economy());
-			const int32_t air_distance = map.calc_distance(flag.get_position(), reachable_coords);
-			if (!RoadCandidates.has_candidate(reachable_coords.hash())) {
-				RoadCandidates.add_flag(reachable_coords, air_distance, different_economy);
-			}
-		}
-	}
-
-	// now we walk over roads and if field is reachable by roads, we change the distance assigned
-	// above
-	std::map<uint32_t, NearFlag> nearflags;  // only used to collect flags reachable walk over roads
-	nearflags[flag.get_position().hash()] = NearFlag(&flag, 0);
-
-	// Algorithm to walk on roads
-	// All nodes are marked as to_be_checked == true first and once the node is checked it is changed
-	// to false. Under some conditions, the same node can be checked twice, the to_be_checked can
-	// be set back to true. Because less hoops (fewer flag-to-flag roads) does not always mean
-	// shortest
-	// road.
-	for (;;) {
-		// looking for a node with shortest existing road distance from starting flag and one that has
-		// to be checked
-		uint32_t start_field = std::numeric_limits<uint32_t>::max();
-		uint32_t nearest_distance = 10000;
-		for (auto item : nearflags) {
-			if (item.second.current_road_distance < nearest_distance && item.second.to_be_checked) {
-				nearest_distance = item.second.current_road_distance;
-				start_field = item.first;
-			}
-		}
-		// OK, we failed to find a NearFlag where to_be_checked == true, so quitting the loop now
-		if (start_field == std::numeric_limits<uint32_t>::max()) {
-			break;
-		}
-
-		nearflags[start_field].to_be_checked = false;
-
-		// Now going over roads leading from this flag
-		for (uint8_t i = 1; i <= 6; ++i) {
-			Road* const road = nearflags[start_field].flag->get_road(i);
-
-			if (!road) {
-				continue;
-			}
-
-			Flag* endflag = &road->get_flag(Road::FlagStart);
-
-			if (endflag == nearflags[start_field].flag) {
-				endflag = &road->get_flag(Road::FlagEnd);
-			}
-
-			const uint32_t endflag_hash = endflag->get_position().hash();
-
-			const int32_t dist = map.calc_distance(flag.get_position(), endflag->get_position());
-
-			if (dist > checkradius + 2) {  //  Testing bigger vicinity then checkradius....
-				continue;
-			}
-
-			// There is few scenarios for this neighbour flag
-			if (nearflags.count(endflag_hash) == 0) {
-				// This is brand new flag
-				nearflags[endflag_hash] =
-				   NearFlag(endflag, nearflags[start_field].current_road_distance +
-				                        road->get_path().get_nsteps());
-			} else {
-				// We know about this flag already
-				if (nearflags[endflag_hash].current_road_distance >
-				    nearflags[start_field].current_road_distance + road->get_path().get_nsteps()) {
-					// ..but this current connection is shorter than one found before
-					nearflags[endflag_hash].current_road_distance =
-					   nearflags[start_field].current_road_distance + road->get_path().get_nsteps();
-					// So let re-check neighbours once more
-					nearflags[endflag_hash].to_be_checked = true;
-				}
-			}
-		}
-	}
-
-	// Sending calculated walking costs from nearflags to RoadCandidates to update info on
-	// Candidate flags/roads
-	for (auto& nf_walk : nearflags) {
-		// NearFlag contains also flags beyond check radius, these are not relevent for us
-		if (RoadCandidates.has_candidate(nf_walk.second.flag->get_position().hash())) {
-			RoadCandidates.set_cur_road_distance(
-			   nf_walk.second.flag->get_position(), nf_walk.second.current_road_distance);
-		}
-	}
-
-	// Here we must consider how much are buildable fields lacking
-	// the number will be transformed to a weight passed to findpath function
-	int32_t fields_necessity = 0;
-	if (spots_ < kSpotsTooLittle) {
-		fields_necessity += 10;
-	}
-	if (map_allows_seafaring_ && num_ports == 0) {
-		fields_necessity += 10;
-	}
-	if (num_ports < 4) {
-		fields_necessity += 5;
-	}
-	if (spots_ < kSpotsEnough) {
-		fields_necessity += 5;
-	}
-	fields_necessity *= std::abs(management_data.get_military_number_at(64)) * 5;
-
-	// We need to sort these flags somehow, because we are not going to investigate all of them
-	// so sorting first by current road length (that might contain fake values for flags that were
-	// not reached over roads) and secondary by air_distance (nearer flags first)
-	std::sort(std::begin(RoadCandidates.flags_queue), std::end(RoadCandidates.flags_queue),
-	          [](const FlagsForRoads::Candidate& a, const FlagsForRoads::Candidate& b) {
-		          // Here we are doing a kind of bucketing
-		          const int32_t a_length = a.current_road_length / 50;
-		          const int32_t b_length = b.current_road_length / 50;
-		          return std::tie(b_length, a.air_distance) < std::tie(a_length, b.air_distance);
-	          });
-
-	// Now we calculate roads from here to few best looking RoadCandidates....
-	uint32_t possible_roads_count = 0;
-	uint32_t current = 0;  // hash of flag that we are going to calculate in the iteration
-	while (possible_roads_count < 5 && RoadCandidates.get_best_uncalculated(&current)) {
-		const Widelands::Coords coords = Coords::unhash(current);
-		Path path;
-
-		// value of pathcost is not important, it just indicates, that the path can be built
-		// We send this information to RoadCandidates, with length of possible road if applicable
-		const int32_t pathcost =
-		   map.findpath(flag.get_position(), coords, 0, path, check, 0, fields_necessity);
-		if (pathcost >= 0) {
-			RoadCandidates.road_possible(coords, path.get_nsteps());
-			possible_roads_count += 1;
-		}
-	}
-
-	// re-sorting again, now by reduction score (custom operator specified in .h file)
-	std::sort(std::begin(RoadCandidates.flags_queue), std::end(RoadCandidates.flags_queue));
-
-	// Well and finally building the winning road (if any)
-	uint32_t winner_hash = 0;
-	if (RoadCandidates.get_winner(&winner_hash)) {
-		const Widelands::Coords target_coords = Coords::unhash(winner_hash);
-		Path& path = *new Path();
+    // Increasing the failed_connection_tries counter
+    // At the same time it indicates a time an economy is without a warehouse
+    EconomyObserver* eco = get_economy_observer(flag.economy());
+    // if we passed grace time this will be last attempt and if it fails
+    // building is destroyed
+    bool last_attempt_ = false;
+
+    // this should not happen, but if the economy has a warehouse and a dismantle
+    // grace time set, we must 'zero' the dismantle grace time
+    if (!flag.get_economy()->warehouses().empty() &&
+        eco->dismantle_grace_time != kNever) {
+        eco->dismantle_grace_time = kNever;
+    }
+
+    // first we deal with situations when this is economy with no warehouses
+    // and this is a flag belonging to a building/constructionsite
+    // such economy must get dismantle grace time (if not set yet)
+    // end sometimes extended checkradius
+    if (flag.get_economy()->warehouses().empty() && flag.get_building()) {
+
+        // occupied military buildings get special treatment
+        // (extended grace time + longer radius)
+        bool occupied_military_ = false;
+        Building* b = flag.get_building();
+        if (upcast(MilitarySite, militb, b)) {
+            if (militb->soldier_control()->stationed_soldiers().size() > 0) {
+                occupied_military_ = true;
+            }
+        }
+
+        // check if we are within grace time, if not or gracetime unset we need to do something
+        // if we are within gracetime we do nothing (this loop is skipped)
+
+        // if grace time is not set, this is probably first time without a warehouse and we must set
+        // it
+        if (eco->dismantle_grace_time == kNever) {
+
+            // constructionsites
+            if (upcast(ConstructionSite const, constructionsite, flag.get_building())) {
+                BuildingObserver& bo =
+                   get_building_observer(constructionsite->building().name().c_str());
+                // first very special case - a port (in the phase of constructionsite)
+                // this might be a new colonization port
+                if (bo.is(BuildingAttribute::kPort)) {
+                    eco->dismantle_grace_time = gametime + 60 * 60 * 1000;  // one hour should be enough
+                } else {  // other constructionsites, usually new (standalone) constructionsites
+                    eco->dismantle_grace_time =
+                       gametime + 30 * 1000 +            // very shot time is enough
+                       (eco->flags.size() * 30 * 1000);  // + 30 seconds for every flag in economy
+                }
+
+                // buildings
+            } else {
+
+                if (occupied_military_) {
+                    eco->dismantle_grace_time =
+                       (gametime + 90 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
+
+                } else {  // for other normal buildings
+                    eco->dismantle_grace_time =
+                       gametime + (45 * 60 * 1000) + (eco->flags.size() * 20 * 1000);
+                }
+            }
+
+            // we have passed grace_time - it is time to dismantle
+        } else if (eco->dismantle_grace_time <= gametime) {
+            last_attempt_ = true;
+            // we increase a check radius in last attempt
+            checkradius += 2;
+        }
+
+        // and bonus for occupied military buildings:
+        if (occupied_military_) {
+            checkradius += 4;
+        }
+
+        // and generally increase radius for unconnected buildings
+        checkradius += 2;
+    }
+
+    // Now own roadfinding stuff
+    const Map& map = game().map();
+
+    // Initializing new object of FlagsForRoads, we will push there all candidate flags
+    // First we dont even know if a road can be built there (from current flag)
+    // Adding also distance of this flag to nearest wh
+    uint32_t tmp_wh; // This information is not used, but we need it
+    const uint32_t current_flag_dist_to_wh = flag_warehouse_distance.
+            get_distance(flag.get_position().hash(), gametime, &tmp_wh);
+
+    FlagCandidates flag_candidates(current_flag_dist_to_wh);
+
+    FindNodeWithFlagOrRoad functor;
+    CheckStepRoadAI check(player_, MOVECAPS_WALK, true);
+
+    // get all flags within radius
+    std::vector<Coords> reachable;
+    map.find_reachable_fields(
+       Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius), &reachable, check, functor);
+
+    for (const Coords& reachable_coords : reachable) {
+
+        // ignore starting flag, of course
+        if (reachable_coords == flag.get_position()) {
+            continue;
+        }
+
+        const uint32_t reachable_coords_hash = reachable_coords.hash();
+
+        // first make sure there is an immovable (should be, but still)
+        Widelands::BaseImmovable* this_immovable = map[reachable_coords].get_immovable();
+        if (upcast(PlayerImmovable const, player_immovable, this_immovable)) {
+
+            // if it is the road, make a flag there
+            if (this_immovable->descr().type() == MapObjectType::ROAD) {
+                game().send_player_build_flag(player_number(), reachable_coords);
+            }
+
+            // do not go on if it is not a flag
+            if (this_immovable->descr().type() != MapObjectType::FLAG) {
+                continue;
+            }
+
+            // testing if a flag/road's economy has a warehouse, if not we are not
+            // interested to connect to it
+            if (player_immovable->economy().warehouses().size() == 0) {
+                continue;
+            }
+
+            // This is a candidate, sending all necessary info to RoadCandidates
+            const bool is_different_economy = (player_immovable->get_economy() != flag.get_economy());
+			const uint16_t air_distance = map.calc_distance(flag.get_position(), reachable_coords);
+
+            if (!flag_candidates.has_candidate(reachable_coords_hash) && !flag_warehouse_distance.is_road_prohibited(reachable_coords_hash, gametime)) {
+                flag_candidates.add_flag(reachable_coords_hash, is_different_economy,
+                flag_warehouse_distance.get_distance(reachable_coords_hash, gametime, &tmp_wh), air_distance);
+            }
+        }
+    }
+
+    // now we walk over roads and if field is reachable by roads, we change the distance assigned
+    // above
+    std::map<uint32_t, NearFlag> nearflags;  // only used to collect flags reachable walk over roads
+    nearflags[flag.get_position().hash()] = NearFlag(&flag, 0);
+
+    collect_nearflags(nearflags, flag, checkradius);
+
+    // Sending calculated walking costs from nearflags to RoadCandidates to update info on
+    // Candidate flags/roads
+    for (auto& nf_walk : nearflags) {
+		const uint32_t nf_hash = nf_walk.second.flag->get_position().hash();
+        // NearFlag contains also flags beyond check radius, these are not relevant for us
+        if (flag_candidates.has_candidate(nf_hash)) {
+            flag_candidates.set_cur_road_distance(
+               nf_hash, nf_walk.second.current_road_distance);
+        }
+    }
+
+    // Here we must consider how much are buildable fields lacking
+    // the number will be transformed to a weight passed to findpath function
+    int32_t fields_necessity = 0;
+    if (spots_ < kSpotsTooLittle) {
+        fields_necessity += 10;
+    }
+    if (map_allows_seafaring_ && num_ports == 0) {
+        fields_necessity += 10;
+    }
+    if (num_ports < 4) {
+        fields_necessity += 5;
+    }
+    if (spots_ < kSpotsEnough) {
+        fields_necessity += 5;
+    }
+
+    fields_necessity *= std::abs(management_data.get_military_number_at(64)) * 5;
+
+    // Now we calculate roads from here to few best looking RoadCandidates....
+    flag_candidates.sort_by_air_distance();
+    uint32_t possible_roads_count = 0;
+    for (const auto &flag_candidate : flag_candidates.flags()) {
+        if (possible_roads_count > 10) {break;}
+        const Widelands::Coords coords = Coords::unhash(flag_candidate.coords_hash);
+        Path path;
+
+        // value of pathcost is not important, it just indicates, that the path can be built
+        // We send this information to RoadCandidates, with length of possible road if applicable
+        const int32_t pathcost =
+           map.findpath(flag.get_position(), coords, 0, path, check, 0, fields_necessity);
+        if (pathcost >= 0) {
+            flag_candidates.set_road_possible(flag_candidate.coords_hash, path.get_nsteps());
+            ++possible_roads_count;
+        }
+    }
+
+    // re-sorting again now by default by a score
+    flag_candidates.sort();
+
+
+    // Well and finally building the winning road (if any)
+    const int32_t winner_min_score = (spots_ < kSpotsTooLittle) ? 50 : 25;
+
+    FlagCandidates::Candidate* winner = flag_candidates.get_winner(winner_min_score);
+    if (winner) {
+        const Widelands::Coords target_coords = Coords::unhash(winner->coords_hash);
+
+		// This is to prohibit the flag for some time but with exemption of warehouse
+		if (flag_warehouse_distance.get_distance(winner->coords_hash, gametime, &tmp_wh) > 0) {
+			flag_warehouse_distance.set_road_built(winner->coords_hash, gametime);
+		}
+		// and we straight away set distance of future flag
+		flag_warehouse_distance.set_distance(flag.get_position().hash(), winner->start_flag_dist_to_wh + winner->possible_road_distance,
+		gametime, 0); // faking the warehouse
+
+        Path& path = *new Path();
 #ifndef NDEBUG
-		const int32_t pathcost =
-		   map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
-		assert(pathcost >= 0);
+        const int32_t pathcost =
+           map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
+        assert(pathcost >= 0);
 #else
-		map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
+        map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
 #endif
-		game().send_player_build_road(player_number(), path);
-		return true;
-	}
-	// We can't build a road so let's block the vicinity as an indication this area is not
-	// connectible
-	// Usually we block for 2 minutes, but if it is a last attempt we block for 10 minutes
-	// Note: we block the vicinity only if this economy (usually a sole flag with a building) is not
-	// connected to a warehouse
-	if (flag.get_economy()->warehouses().empty()) {
-
-		// blocking only if latest block was less then 60 seconds ago or it is last attempt
-		if (eco->fields_block_last_time + 60000 < gametime || last_attempt_) {
-			eco->fields_block_last_time = gametime;
-
-			const uint32_t block_time = last_attempt_ ? 10 * 60 * 1000 : 2 * 60 * 1000;
-
-			FindNodeAcceptAll buildable_functor;
-			CheckStepOwnTerritory check_own(player_, MOVECAPS_WALK, true);
-
-			// get all flags within radius
-			std::vector<Coords> reachable_to_block;
-			map.find_reachable_fields(Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius),
-			                          &reachable_to_block, check_own, buildable_functor);
-
-			for (auto coords : reachable_to_block) {
-				blocked_fields.add(coords, game().get_gametime() + block_time);
-			}
-		}
-
-		// If it last attempt we also destroy the flag (with a building if any attached)
-		if (last_attempt_) {
-			remove_from_dqueue<Widelands::Flag>(eco->flags, &flag);
-			game().send_player_bulldoze(*const_cast<Flag*>(&flag));
-			dead_ends_check_ = true;
-			return true;
-		}
-	}
-	return false;
+        game().send_player_build_road(player_number(), path);
+        return true;
+    }
+    // We can't build a road so let's block the vicinity as an indication this area is not
+    // connectible
+    // Usually we block for 2 minutes, but if it is a last attempt we block for 10 minutes
+    // Note: we block the vicinity only if this economy (usually a sole flag with a building) is not
+    // connected to a warehouse
+    if (flag.get_economy()->warehouses().empty()) {
+
+        // blocking only if latest block was less then 60 seconds ago or it is last attempt
+        if (eco->fields_block_last_time + kOneMinute < gametime || last_attempt_) {
+            eco->fields_block_last_time = gametime;
+
+            const uint32_t block_time = last_attempt_ ? 10 * kOneMinute : 2 * kOneMinute;
+
+            FindNodeAcceptAll buildable_functor;
+            CheckStepOwnTerritory check_own(player_, MOVECAPS_WALK, true);
+
+            // get all flags within radius
+            std::vector<Coords> reachable_to_block;
+            map.find_reachable_fields(Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius),
+                                      &reachable_to_block, check_own, buildable_functor);
+
+            for (auto coords : reachable_to_block) {
+                blocked_fields.add(coords, game().get_gametime() + block_time);
+            }
+        }
+
+        // If it last attempt we also destroy the flag (with a building if any attached)
+        if (last_attempt_) {
+            remove_from_dqueue<Widelands::Flag>(eco->flags, &flag);
+            game().send_player_bulldoze(*const_cast<Flag*>(&flag));
+            dead_ends_check_ = true;
+            return true;
+        }
+    }
+    return false;
+}
+
+void DefaultAI::collect_nearflags(std::map<uint32_t, NearFlag> &nearflags, const Flag& flag, const uint16_t checkradius) {
+    // Algorithm to walk on roads
+    // All nodes are marked as to_be_checked == true first and once the node is checked it is changed
+    // to false. Under some conditions, the same node can be checked twice, the to_be_checked can
+    // be set back to true. Because less hoops (fewer flag-to-flag roads) does not always mean
+    // shortest road.
+
+	const Map& map = game().map();
+
+    for (;;) {
+        // looking for a node with shortest existing road distance from starting flag and one that has
+        // to be checked
+        uint32_t start_field = kNoField;
+        uint32_t nearest_distance = 10000;
+        for (auto item : nearflags) {
+            if (item.second.current_road_distance < nearest_distance && item.second.to_be_checked) {
+                nearest_distance = item.second.current_road_distance;
+                start_field = item.first;
+            }
+        }
+        // OK, we failed to find a NearFlag where to_be_checked == true, so quitting the loop now
+        if (start_field == kNoField) {
+            break;
+        }
+
+        nearflags[start_field].to_be_checked = false;
+
+        // Now going over roads leading from this flag
+        for (uint8_t i = 1; i <= 6; ++i) {
+            Road* const road = nearflags[start_field].flag->get_road(i);
+
+            if (!road) {
+                continue;
+            }
+
+            Flag* endflag = &road->get_flag(Road::FlagStart);
+
+            if (endflag == nearflags[start_field].flag) {
+                endflag = &road->get_flag(Road::FlagEnd);
+            }
+
+            const uint32_t endflag_hash = endflag->get_position().hash();
+
+            const int32_t dist = map.calc_distance(flag.get_position(), endflag->get_position());
+
+            if (dist > checkradius + 2) {  //  Testing bigger vicinity then checkradius....
+                continue;
+            }
+
+            // There is few scenarios for this neighbour flag
+            if (nearflags.count(endflag_hash) == 0) {
+                // This is brand new flag
+                // calculating diff how much closer we will get to the flag
+                nearflags[endflag_hash] =
+                   NearFlag(endflag, nearflags[start_field].current_road_distance +
+                                        road->get_path().get_nsteps());
+            } else {
+                // We know about this flag already
+                if (nearflags[endflag_hash].current_road_distance >
+                    nearflags[start_field].current_road_distance + road->get_path().get_nsteps()) {
+                    // ..but this current connection is shorter than one found before
+                    nearflags[endflag_hash].current_road_distance =
+                       nearflags[start_field].current_road_distance + road->get_path().get_nsteps();
+                    // So let re-check neighbours once more
+                    nearflags[endflag_hash].to_be_checked = true;
+                }
+            }
+        }
+    }
+
 }
 
 /**

=== 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 @@
 	static constexpr int32_t kSpotsTooLittle = 15;
 	static constexpr int kManagementUpdateInterval = 10 * 60 * 1000;
 	static constexpr int kStatUpdateInterval = 60 * 1000;
+	static constexpr int kFlagWarehouseUpdInterval = 15 * 1000;
 
 	// For vision and scheduling
 	static constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();
@@ -198,11 +199,14 @@
 	bool improve_roads(uint32_t);
 	bool create_shortcut_road(const Widelands::Flag&,
 	                          uint16_t maxcheckradius,
-	                          int16_t minReduction,
 	                          const uint32_t gametime);
 	// trying to identify roads that might be removed
 	bool dispensable_road_test(const Widelands::Road&);
 	bool dismantle_dead_ends();
+	void collect_nearflags(std::map<uint32_t, Widelands::NearFlag> &, const Widelands::Flag&, const uint16_t);
+	// calculating distances from local warehouse to flags
+	void check_flag_distances(uint32_t);
+	Widelands::FlagWarehouseDistances flag_warehouse_distance;
 
 	bool check_economies();
 	bool check_productionsites(uint32_t);
@@ -272,6 +276,7 @@
 	bool check_ships(uint32_t);
 	bool attempt_escape(Widelands::ShipObserver& so);
 
+
 	// finding and owner
 	Widelands::PlayerNumber get_land_owner(const Widelands::Map&, uint32_t);
 

=== 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 @@
+wl_test(test_ai
+  SRCS
+    ai_test_main.cc
+    test_ai.cc
+  DEPENDS
+    base_log
+    base_macros
+    ai
+)

=== 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 @@
+/*
+ * Copyright (C) 2007-2019 by the Widelands Development Team
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+ *
+ */
+
+#define BOOST_TEST_MODULE AI
+#include <boost/test/unit_test.hpp>

=== 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 @@
+/*
+ * Copyright (C) 2007-2019 by the Widelands Development Team
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+ *
+ */
+
+#include <exception>
+
+#include <boost/test/unit_test.hpp>
+
+#ifdef _WIN32
+#include "base/log.h"
+#endif
+#include "ai/ai_help_structs.h"
+#include "base/macros.h"
+
+// Triggered by BOOST_AUTO_TEST_CASE
+CLANG_DIAG_OFF("-Wdisabled-macro-expansion")
+
+namespace Widelands {  // Needed?
+class World;
+}  // namespace Widelands
+
+using namespace Widelands;
+
+BOOST_AUTO_TEST_SUITE(ai)
+
+BOOST_AUTO_TEST_CASE(flag_distance_soft_expiry) {
+	FlagWarehouseDistances fw;
+	uint32_t tmp_wh;
+	BOOST_CHECK_EQUAL(fw.get_distance(0, 0, &tmp_wh), 1000);
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
+	BOOST_CHECK_EQUAL(fw.get_distance(1, 2, &tmp_wh), 2);  // distance now 2
+	BOOST_CHECK_EQUAL(tmp_wh, 3);
+
+	// setting longer distance below soft_expiry time
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 3, kFlagDistanceExpirationPeriod / 3, 4), false);
+	// distance to 3 not updated
+	BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod / 3, &tmp_wh), 2);
+	BOOST_CHECK_EQUAL(tmp_wh, 3);
+
+	// now setting after soft expiry
+	BOOST_CHECK_EQUAL(
+	   fw.set_distance(1, 1, kFlagDistanceExpirationPeriod / 3, 6), true);  // distance set to 1
+	BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod / 3, &tmp_wh), 1);
+	BOOST_CHECK_EQUAL(tmp_wh, 6);
+}
+BOOST_AUTO_TEST_CASE(flag_distance_below_expiry)
+/* Compare with void free_test_function() */
+{
+	FlagWarehouseDistances fw;
+	uint32_t tmp_wh;
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
+
+	// setting longer distance after soft but below expiry time
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 3, kFlagDistanceExpirationPeriod * 2 / 3, 5), true);
+	BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod * 2 / 3, &tmp_wh), 3);
+	BOOST_CHECK_EQUAL(tmp_wh, 5);
+}
+
+BOOST_AUTO_TEST_CASE(flag_distance_after_expiry)
+/* Compare with void free_test_function() */
+{
+	FlagWarehouseDistances fw;
+	uint32_t tmp_wh;
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
+
+	// setting longer distance below expiry time
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 3, 2 * kFlagDistanceExpirationPeriod, 5), true);
+	BOOST_CHECK_EQUAL(fw.get_distance(1, 3, &tmp_wh), 3);
+	BOOST_CHECK_EQUAL(tmp_wh, 5);
+}
+
+BOOST_AUTO_TEST_CASE(flag_distance_expiration_extension)
+/* setting the same distance restart the expiry_period */
+{
+	FlagWarehouseDistances fw;
+	uint32_t tmp_wh;
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 2, 0, 3), true);
+	BOOST_CHECK_EQUAL(
+	   fw.set_distance(1, 2, 0, 3), false);  // cannot reset the same distance in the same time
+
+	// Now we are after expiration time
+	BOOST_CHECK_EQUAL(fw.get_distance(1, kFlagDistanceExpirationPeriod + 3, &tmp_wh), 1000);
+
+	// setting distance 2 time shortly one after another
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 2, kFlagDistanceExpirationPeriod + 3, 5), true);
+	BOOST_CHECK_EQUAL(fw.set_distance(1, 2, kFlagDistanceExpirationPeriod + 10, 5), true);
+	// current expiry_time should be 2*kFlagDistanceExpirationPeriod + 10
+	BOOST_CHECK_EQUAL(fw.get_distance(1, 2 * kFlagDistanceExpirationPeriod, &tmp_wh), 2);
+	BOOST_CHECK_EQUAL(tmp_wh, 5);
+	BOOST_CHECK_EQUAL(fw.get_distance(1, 2 * kFlagDistanceExpirationPeriod + 15, &tmp_wh), 1000);
+}
+
+BOOST_AUTO_TEST_CASE(flag_distance_road_builtexpiration_extension)
+/* setting the same distance restart the expiry_period */
+{
+	FlagWarehouseDistances fw;
+	// No road built on fresh flag
+	BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
+	// get_distance(const uint32_t flag_coords, uint32_t gametime, uint32_t* nw)
+
+	// setting road we dont know about
+	fw.set_road_built(1, 0);
+	BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
+
+	// let fw knows about it
+	fw.set_distance(1, 2, 0, 3);
+	fw.set_road_built(1, 0);
+	BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), true);
+	BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 59999), true);
+	BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 60001), false);
+
+	BOOST_CHECK_EQUAL(fw.is_road_prohibited(2, 60001), false);
+}
+
+BOOST_AUTO_TEST_CASE(flag_distance_old_removal)
+/* setting the same distance restart the expiry_period */
+{
+	FlagWarehouseDistances fw;
+	fw.set_distance(1, 2, 0, 3);
+	BOOST_CHECK_EQUAL(fw.count(), 1);
+	BOOST_CHECK_EQUAL(fw.remove_old_flag(kOldFlagRemoveTime + kFlagDistanceExpirationPeriod), false);
+	BOOST_CHECK_EQUAL(fw.count(), 1);
+	BOOST_CHECK_EQUAL(
+	   fw.remove_old_flag(kOldFlagRemoveTime + kFlagDistanceExpirationPeriod + 2), true);
+	BOOST_CHECK_EQUAL(fw.count(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(new_flag_road_not_prohibited)
+/* setting the same distance restart the expiry_period */
+{
+	FlagWarehouseDistances fw;
+	// let fw knows about it
+	BOOST_CHECK_EQUAL(fw.count(), 0);
+	fw.set_distance(1, 2, 0, 3);
+	BOOST_CHECK_EQUAL(fw.count(), 1);
+	BOOST_CHECK_EQUAL(fw.is_road_prohibited(1, 1), false);
+}
+
+BOOST_AUTO_TEST_CASE(flag_candidate_init)
+/* setting the same distance restart the expiry_period */
+{
+	FlagCandidates fc = FlagCandidates(10);
+	BOOST_CHECK_EQUAL(fc.count(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(flag_candidate_winner_score) {
+	const uint16_t kCurFlDistToWh = 3;
+	const uint16_t kStartFlagToWh = 10;
+
+	const uint16_t kPosRoadDist = 5;
+	const uint16_t kCurRoadDistFlToFl = 17;
+
+	const uint32_t kTestedCoords = 11;
+
+	FlagCandidates fc = FlagCandidates(kStartFlagToWh);
+
+	// coord, different economy, distance to wh
+	fc.add_flag(kTestedCoords, false, kCurFlDistToWh, 1);
+	// setting coords, dist
+	BOOST_CHECK_EQUAL(fc.set_cur_road_distance(kTestedCoords, kCurRoadDistFlToFl), true);
+	BOOST_CHECK_EQUAL(
+	   fc.set_cur_road_distance(1, 5), false);    // we cannot set distance to unknown flag
+	BOOST_CHECK(!fc.get_winner());  // road not possible
+	// set length of possible road
+	BOOST_CHECK_EQUAL(fc.set_road_possible(kTestedCoords, kPosRoadDist), true);
+	BOOST_VERIFY(fc.get_winner());
+	BOOST_CHECK_EQUAL(fc.get_winner()->start_flag_dist_to_wh, kStartFlagToWh);
+	BOOST_CHECK_EQUAL(fc.get_winner()->cand_flag_distance_to_wh, kCurFlDistToWh);
+	BOOST_CHECK_EQUAL(fc.get_winner()->flag_to_flag_road_distance, kCurRoadDistFlToFl);
+	BOOST_CHECK_EQUAL(fc.get_winner()->possible_road_distance, kPosRoadDist);
+	BOOST_CHECK_EQUAL(fc.get_winner()->coords_hash, kTestedCoords);
+	BOOST_CHECK_EQUAL(fc.get_winner()->different_economy, false);
+
+	BOOST_CHECK_EQUAL(fc.get_winner()->score(),
+	                  +(kStartFlagToWh - kCurFlDistToWh) + (kCurRoadDistFlToFl - 2 * kPosRoadDist));
+}
+BOOST_AUTO_TEST_CASE(flag_candidates_sorting) {
+	FlagCandidates fc = FlagCandidates(10);
+
+	fc.add_flag(0, false, 10, 1);
+	fc.add_flag(1, false, 10, 1);
+	fc.add_flag(2, false, 10, 1);
+	BOOST_CHECK_EQUAL(fc.set_cur_road_distance(0, 5), true);
+	BOOST_CHECK_EQUAL(fc.set_cur_road_distance(1, 5), true);
+	BOOST_CHECK_EQUAL(fc.set_cur_road_distance(2, 5), true);
+	BOOST_CHECK_EQUAL(fc.set_road_possible(0, 4), true);
+	BOOST_CHECK_EQUAL(fc.set_road_possible(1, 2), true);
+	BOOST_CHECK_EQUAL(fc.set_road_possible(2, 3), true);
+	BOOST_CHECK_EQUAL(fc.get_winner()->coords_hash, 1);  // sorted done automatically
+	BOOST_CHECK_EQUAL(fc.count(), 3);
+}
+
+BOOST_AUTO_TEST_CASE(flag_sort_by_air_distance) {
+	FlagCandidates fc = FlagCandidates(10);
+
+	fc.add_flag(0, false, 10, 4);
+	fc.add_flag(1, false, 10, 1);
+	fc.add_flag(2, false, 10, 2);
+	fc.sort_by_air_distance();
+	BOOST_CHECK_EQUAL(fc.flags()[0].air_distance, 1);
+}
+
+BOOST_AUTO_TEST_CASE(flag_has_candidate) {
+	FlagCandidates fc = FlagCandidates(10);
+
+	fc.add_flag(0, false, 10, 4);
+	fc.add_flag(1, false, 10, 1);
+	fc.add_flag(2, false, 10, 2);
+	BOOST_CHECK_EQUAL(fc.has_candidate(1), true);
+	BOOST_CHECK_EQUAL(fc.has_candidate(3), false);
+}
+
+BOOST_AUTO_TEST_SUITE_END()