widelands-dev team mailing list archive

[TiborB <tiborb95@xxxxxxxxx>]

TiborB has proposed merging lp:~widelands-dev/widelands/ai_roads_rework into lp:widelands.

Requested reviews:
  Widelands Developers (widelands-dev)

For more details, see:
https://code.launchpad.net/~widelands-dev/widelands/ai_roads_rework/+merge/288567

AI-only changes.

The main part of this branch is redesign of road logic. Most of logic was moved to ai_help_structs.*, but in addition to this overall logic was redesigned / simplified and improved, though the visual changes are not that much visible. 
Second, small changes to military sites
Third, redesigned the logic for building shipyards, now it needs at least two water-only fields in radius of 5
-- 
Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/ai_roads_rework into lp:widelands.

=== modified file 'src/ai/ai_help_structs.cc'
--- src/ai/ai_help_structs.cc	2016-02-18 17:58:54 +0000
+++ src/ai/ai_help_structs.cc	2016-03-09 20:23:58 +0000
@@ -137,17 +137,25 @@
 	return (fc.field->nodecaps() & BUILDCAPS_MINE) && (fc.field->get_resources() == res);
 }
 
-
 // Fishers and fishbreeders must be built near water
 FindNodeWater::FindNodeWater(const World& world) : world_(world) {}
 
-bool FindNodeWater::accept(const Map& /* map */, const FCoords& coord) const {
+bool FindNodeWater::accept(const Map& map, const FCoords& coord) const {
 	return (world_.terrain_descr(coord.field->terrain_d()).get_is() &
 			  TerrainDescription::Is::kWater) ||
-			 (world_.terrain_descr(coord.field->terrain_r()).get_is() &
+			 (world_.terrain_descr(map.get_neighbour(coord, WALK_W).field->terrain_r()).get_is() &
+			  TerrainDescription::Is::kWater) ||
+			 (world_.terrain_descr(map.get_neighbour(coord, WALK_NW).field->terrain_r()).get_is() &
 			  TerrainDescription::Is::kWater);
 }
 
+// Open water is field where all 6 adjacent triangles are water
+FindNodeOpenWater::FindNodeOpenWater(const World& world) : world_(world) {}
+
+bool FindNodeOpenWater::accept(const Map& /* map */, const FCoords& coord) const {
+	return !(coord.field->nodecaps() & MOVECAPS_WALK) && (coord.field->nodecaps() & MOVECAPS_SWIM);
+}
+
 // FindNodeWithFlagOrRoad
 bool FindNodeWithFlagOrRoad::accept(const Map&, FCoords fc) const {
 	if (upcast(PlayerImmovable const, pimm, fc.field->get_immovable()))
@@ -176,6 +184,7 @@
 	  // non-negative, water is not recaldulated
 	  rocks_nearby(1),
 	  water_nearby(-1),
+	  open_water_nearby(-1),
 	  distant_water(0),
 	  fish_nearby(-1),
 	  critters_nearby(-1),
@@ -300,6 +309,156 @@
 	return (blocked_fields_.count(coords.hash()) != 0);
 }
 
+
+FlagsForRoads::Candidate::Candidate(uint32_t cr, int32_t ad, bool de):
+	coords_hash(cr), air_distance(ad), different_economy(de) {
+		new_road_possible = false;
+		accessed_via_roads = false;
+		new_road_length = 1000;
+		current_roads_distance = 1000; // must be big enough
+		reduction_score = -air_distance; // allows reasonable ordering from the start
+		}
+
+bool FlagsForRoads::Candidate::operator<(const Candidate& other) const {
+	if (reduction_score == other.reduction_score) {
+		return coords_hash < other.coords_hash;
+	} else {
+		return reduction_score > other.reduction_score;
+	}
+}
+
+bool FlagsForRoads::Candidate::operator==(const Candidate& other) const {
+	return coords_hash == other.coords_hash;
+}
+
+void FlagsForRoads::Candidate::calculate_score() {
+	if (!new_road_possible) {
+		reduction_score = -1000 - air_distance; // to have at least some ordering preserved
+	} else if (different_economy) {
+		reduction_score = 10000 - air_distance - 2 * new_road_length;
+	} else if (!accessed_via_roads) {
+		if (air_distance + 6 > new_road_length) {
+			reduction_score = 1000 - air_distance - 2 * new_road_length;
+		} else {
+			reduction_score = -1000;
+		}
+	} else {
+		reduction_score = current_roads_distance - 2 * new_road_length;
+	}
+}
+
+void FlagsForRoads::print() { // this is for debuging and development purposes
+	for (auto& candidate_flag : 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_roads_distance - 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 orderd but some target flags are only estimations so we takes first such candidate_flag
+bool FlagsForRoads::get_best_uncalculated(uint32_t* winner) {
+	for (auto& candidate_flag : queue) {
+		if (!candidate_flag.new_road_possible) {
+			*winner = candidate_flag.coords_hash;
+			return true;
+		}
+	}
+	return false;
+}
+
+// We managed to calculate road from starting flag to this flag
+void  FlagsForRoads::road_possible(Widelands::Coords coords, uint32_t distance) {
+	// std::set does not allow updating
+	Candidate new_candidate_flag = Candidate(0, 0, false);
+	for (auto candidate_flag : queue) {
+		if (candidate_flag.coords_hash == coords.hash()) {
+			new_candidate_flag = candidate_flag;
+			assert (new_candidate_flag.coords_hash == candidate_flag.coords_hash);
+			queue.erase(candidate_flag);
+			break;
+		}
+	}
+
+	new_candidate_flag.new_road_length = distance;
+	new_candidate_flag.new_road_possible = true;
+	new_candidate_flag.calculate_score();
+	queue.insert(new_candidate_flag);
+}
+
+// Remove the flag from candidates as new road is not possible
+void FlagsForRoads::road_impossible(Widelands::Coords coords) {
+	const uint32_t hash = coords.hash();
+	for (auto candidate_flag : queue) {
+		if (candidate_flag.coords_hash == hash) {
+			queue.erase(candidate_flag);
+			return;
+		}
+	}
+}
+
+// Updating walking distance over existing roads
+// Queue does not allow modifying its members so we erase and then eventually insert modified member
+void FlagsForRoads::set_road_distance(Widelands::Coords coords, int32_t distance) {
+	const uint32_t hash = coords.hash();
+	Candidate new_candidate_flag = Candidate(0, 0, false);
+	bool replacing = false;
+	for (auto candidate_flag : queue) {
+		if (candidate_flag.coords_hash == hash) {
+			assert (!candidate_flag.different_economy);
+			if (distance < candidate_flag.current_roads_distance) {
+				new_candidate_flag = candidate_flag;
+				queue.erase(candidate_flag);
+				replacing = true;
+				break;
+			}
+		break;
+		}
+	}
+	if (replacing) {
+		new_candidate_flag.current_roads_distance = distance;
+		new_candidate_flag.accessed_via_roads = true;
+		new_candidate_flag.calculate_score();
+		queue.insert(new_candidate_flag);
+	}
+}
+
+bool FlagsForRoads::get_winner(uint32_t* winner_hash, uint32_t pos) {
+	assert (pos == 1 || pos == 2);
+	uint32_t counter = 1;
+	// 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 : queue) {
+		if (candidate_flag.reduction_score < min_reduction || !candidate_flag.new_road_possible) {
+			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 (counter == pos) {
+			return true;
+		} else if (counter < pos) {
+			counter += 1;
+		} else {
+			break;
+		}
+	}
+	if (has_winner) {
+		return true;
+	}
+	return false;
+}
+
 // This is an struct that stores strength of players, info on teams and provides some outputs from these data
 PlayersStrengths::PlayerStat::PlayerStat() {}
 PlayersStrengths::PlayerStat::PlayerStat(Widelands::TeamNumber tc, uint32_t pp) :

=== modified file 'src/ai/ai_help_structs.h'
--- src/ai/ai_help_structs.h	2016-02-25 19:20:21 +0000
+++ src/ai/ai_help_structs.h	2016-03-09 20:23:58 +0000
@@ -36,7 +36,6 @@
 #include "logic/map_objects/world/world.h"
 #include "logic/player.h"
 
-
 namespace Widelands {
 
 class ProductionSite;
@@ -173,6 +172,16 @@
 	const World& world_;
 };
 
+// Fishers and fishbreeders must be built near water
+struct FindNodeOpenWater {
+	FindNodeOpenWater(const World& world);
+
+	bool accept(const Map& /* map */, const FCoords& coord) const;
+
+private:
+	const World& world_;
+};
+
 struct FindNodeWithFlagOrRoad {
 	bool accept(const Map&, FCoords) const;
 };
@@ -233,6 +242,7 @@
 	uint8_t trees_nearby;
 	uint8_t rocks_nearby;
 	int16_t water_nearby;
+	int16_t open_water_nearby;
 	int16_t distant_water;
 	int8_t fish_nearby;
 	int8_t critters_nearby;
@@ -254,6 +264,8 @@
 	// stationed (manned) military buildings nearby
 	int16_t military_stationed;
 	// stationed (manned) military buildings nearby
+	//unconnected buildings nearby
+	bool unconnected_nearby;
 	int16_t military_unstationed;
 	bool is_portspace;
 	bool port_nearby;  // to increase priority if a port is nearby,
@@ -401,6 +413,7 @@
 	// when considering attack most military sites are inside territory and should be skipped during
 	// evaluation
 	bool enemies_nearby;
+	uint32_t built_time;
 };
 
 struct TrainingSiteObserver {
@@ -496,6 +509,54 @@
 	std::map<uint32_t, uint32_t> blocked_fields_;
 };
 
+// list of candidate flags to built roads, with some additional logic
+struct FlagsForRoads {
+
+	FlagsForRoads(int32_t mr) : min_reduction(mr) {};
+
+	struct Candidate {
+		Candidate();
+		Candidate(uint32_t cr, int32_t ad, bool de);
+
+		uint32_t coords_hash;
+		int32_t new_road_length;
+		int32_t current_roads_distance;
+		int32_t air_distance;
+		int32_t reduction_score;
+		bool different_economy;
+		bool new_road_possible;
+		bool accessed_via_roads;
+
+		bool operator<(const Candidate& other) const;
+		bool operator==(const Candidate& other) const;
+		void calculate_score();
+	};
+
+	int32_t min_reduction;
+	// This is the core of this object - candidate flags ordered by score
+	std::set<Candidate> queue;
+
+	void add_flag(Widelands::Coords coords, int32_t air_dist, bool diff_economy) {
+		queue.insert(Candidate(coords.hash(), air_dist, diff_economy));
+	}
+
+	uint32_t count() {
+		return queue.size();
+	}
+
+	// this is for debuging and development purposes
+	void print();
+	// during processing we need to pick first one uprocessed flags (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 distance);
+	void road_impossible(Widelands::Coords coords);
+	// updating walking distance over existing roads
+	void set_road_distance(Widelands::Coords coords, int32_t distance);
+	// Finally we query the flag that we will build a road to
+	bool get_winner(uint32_t* winner_hash, uint32_t pos);
+};
+
 // This is a struct that stores strength of players, info on teams and provides some outputs from these data
 struct PlayersStrengths {
 	struct PlayerStat {

=== modified file 'src/ai/defaultai.cc'
--- src/ai/defaultai.cc	2016-02-27 20:46:11 +0000
+++ src/ai/defaultai.cc	2016-03-09 20:23:58 +0000
@@ -122,6 +122,7 @@
      resource_necessity_water_needed_(false),
      military_last_dismantle_(0),
      military_last_build_(0),
+     last_road_dismantled_(0),
      seafaring_economy(false),
      expedition_ship_(kNoShip),
      spots_(0),
@@ -889,7 +890,6 @@
  * milliseconds if the area the computer owns is big.
  */
 void DefaultAI::update_all_buildable_fields(const uint32_t gametime) {
-
 	uint16_t i = 0;
 
 	// we test 40 fields that were update more than 1 seconds ago
@@ -972,10 +972,17 @@
  */
 void DefaultAI::update_all_not_buildable_fields() {
 	int32_t const pn = player_number();
+
+	// We are checking at least 5 unusable fields (or less if there are not 5 of them)
+	// at once, but not more then 200...
+	// The idea is to check each field at least once a minute, of cours with big maps
+	// it will take longer
 	uint32_t maxchecks = unusable_fields.size();
-
-	if (maxchecks > 50) {
-		maxchecks = 50;
+	if (maxchecks > 5) {
+		maxchecks = 5 + (unusable_fields.size() - 5) / 15;
+	}
+	if (maxchecks > 200) {
+		maxchecks = 200;
 	}
 
 	for (uint32_t i = 0; i < maxchecks; ++i) {
@@ -990,6 +997,7 @@
 			buildable_fields.push_back(new BuildableField(unusable_fields.front()));
 			unusable_fields.pop_front();
 			update_buildable_field(*buildable_fields.back());
+
 			continue;
 		}
 
@@ -997,6 +1005,7 @@
 			mineable_fields.push_back(new MineableField(unusable_fields.front()));
 			unusable_fields.pop_front();
 			update_mineable_field(*mineable_fields.back());
+
 			continue;
 		}
 
@@ -1115,6 +1124,7 @@
 		field.military_loneliness = 1000;  // instead of floats(v-
 		field.area_military_presence = 0;
 		field.military_stationed = 0;
+		field.unconnected_nearby = false;
 		field.trees_nearby = 0;
 		field.space_consumers_nearby = 0;
 		field.rangers_nearby = 0;
@@ -1124,19 +1134,25 @@
 		field.consumers_nearby.resize(wares.size());
 		field.supporters_nearby.clear();
 		field.supporters_nearby.resize(wares.size());
-		std::vector<Coords> water_list;
 		std::vector<Coords> resource_list;
 		std::vector<Bob*> critters_list;
 
 		if (field.water_nearby == kUncalculated) {
+			assert (field.open_water_nearby == kUncalculated);
 
 			FindNodeWater find_water(game().world());
-			map.find_fields(Area<FCoords>(field.coords, 5), &water_list, find_water);
-			field.water_nearby = water_list.size();
+			field.water_nearby =  map.find_fields(Area<FCoords>(field.coords, 5), nullptr, find_water);
+
+			if (field.water_nearby > 0) {
+				FindNodeOpenWater find_open_water(game().world());
+				field.open_water_nearby =
+					map.find_fields(Area<FCoords>(field.coords, 5), nullptr, find_open_water);
+			}
 
 			if (resource_necessity_water_needed_) {  // for atlanteans
-				map.find_fields(Area<FCoords>(field.coords, 14), &water_list, find_water);
-				field.distant_water = water_list.size() - field.water_nearby;
+				field.distant_water =
+					map.find_fields(Area<FCoords>(field.coords, 14), nullptr, find_water) - field.water_nearby;
+				assert (field.open_water_nearby <=  field.water_nearby);
 			}
 		}
 
@@ -1227,6 +1243,11 @@
 	field.area_military_capacity = 0;
 	field.military_loneliness = 1000;
 	field.area_military_presence = 0;
+	field.unconnected_nearby = false;
+
+	//we are interested in unconnected immovables, but we must be also close to connected ones
+	bool any_connected_imm = false;
+	bool any_unconnected_imm = false;
 
 	for (uint32_t i = 0; i < immovables.size(); ++i) {
 
@@ -1248,6 +1269,13 @@
 
 		// if we are here, immovable is ours
 		if (upcast(Building const, building, &base_immovable)) {
+
+			//connected to wh
+			bool connected = !building->get_economy()->warehouses().empty();
+			if (connected) {
+				any_connected_imm = true;
+			}
+
 			if (upcast(ConstructionSite const, constructionsite, building)) {
 				const BuildingDescr& target_descr = constructionsite->building();
 
@@ -1264,6 +1292,9 @@
 						field.military_in_constr_nearby += 1;
 					}
 				}
+			} else if (!connected) {
+				// we dont care about unconnected constructionsites
+				any_unconnected_imm = true;
 			}
 
 			if (upcast(MilitarySite const, militarysite, building)) {
@@ -1288,6 +1319,9 @@
 			}
 		}
 	}
+	if (any_unconnected_imm && any_connected_imm && field.military_in_constr_nearby == 0) {
+		field.unconnected_nearby = true;
+	}
 }
 
 /// Updates one mineable field
@@ -2080,9 +2114,9 @@
 
 					else if (bo.is_shipyard) {
 						// for now AI builds only one shipyard
-						if (bf->water_nearby > 3 && (bo.total_count() - bo.unconnected_count) == 0 &&
+						if (bf->open_water_nearby > 1 && (bo.total_count() - bo.unconnected_count) == 0 &&
 						    seafaring_economy) {
-							prio += productionsites.size() * 5 + bf->water_nearby;
+							prio += productionsites.size() * 5 + bf->open_water_nearby;
 						}
 					}
 
@@ -2167,6 +2201,7 @@
 					prio -= (bf->military_in_constr_nearby + bf->military_unstationed) * 150;
 					prio += (5 - bf->own_military_sites_nearby_()) * 15;
 				}
+				prio +=(bf->unconnected_nearby) * 50;
 				prio += bf->unowned_land_nearby * resource_necessity_territory_ / 100;
 				prio += bf->unowned_mines_spots_nearby * resource_necessity_mines_ / 100;
 				prio += ((bf->unowned_mines_spots_nearby > 0) ? 35 : 0) *
@@ -2570,14 +2605,16 @@
 		roads.push_back(roads.front());
 		roads.pop_front();
 
-		// occasionaly we test if the road can be dismounted
+		// Occasionaly (not more then once in 15 seconds) we test if the road can be dismounted
 		// if there is shortage of spots we do it always
-		if (gametime % 5 == 0 || spots_ < kSpotsTooLittle) {
-			const Road& road = *roads.front();
-			if (dispensable_road_test(*const_cast<Road*>(&road))) {
-				game().send_player_bulldoze(*const_cast<Road*>(&road));
-				return true;
-			}
+		if (last_road_dismantled_ + 15 * 1000 < gametime &&
+			(gametime % 5 == 0 || spots_ < kSpotsTooLittle)) {
+				const Road& road = *roads.front();
+				if (dispensable_road_test(*const_cast<Road*>(&road))) {
+					game().send_player_bulldoze(*const_cast<Road*>(&road));
+					last_road_dismantled_ =  gametime;
+					return true;
+				}
 		}
 	}
 
@@ -2616,7 +2653,9 @@
 	}
 
 	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;
@@ -2626,31 +2665,34 @@
 	// is connected to a warehouse?
 	const bool needs_warehouse = flag.get_economy()->warehouses().empty();
 
-	// needs to be connected
+	// Various tests to invoke building of a shortcut (new road)
 	if (flag.nr_of_roads() == 0 || needs_warehouse) {
-		create_shortcut_road(flag, 13, 22, gametime);
+		create_shortcut_road(flag, 17, 22, gametime);
 		inhibit_road_building_ = gametime + 800;
+	} else if (!has_building && flag.nr_of_roads() == 1) {
+		// This is end of road without any building, we do not initiate interconnection thus
+		return false;
 	} else if (flag.nr_of_roads() == 1 || gametime % 10 == 0) {
 		if (spots_ > kSpotsEnough) {
 			// This is the normal situation
-			create_shortcut_road(flag, 13, 22, gametime);
+			create_shortcut_road(flag, 15, 22, gametime);
 			inhibit_road_building_ = gametime + 800;
 		} else if (spots_ > kSpotsTooLittle)  {
 			// We are short of spots so shortening must be significant
-			create_shortcut_road(flag, 13, 35, gametime);
+			create_shortcut_road(flag, 15, 35, gametime);
 			inhibit_road_building_ = gametime + 800;
 		} else {
 			// We are very short of spots so shortening must be even bigger
-			create_shortcut_road(flag, 13, 50, gametime);
+			create_shortcut_road(flag, 15, 50, gametime);
 			inhibit_road_building_ = gametime + 800;
 		}
 		// a warehouse with 3 or less roads
 	} else if (is_warehouse && flag.nr_of_roads() <= 3) {
-		create_shortcut_road(flag, 9, -1, gametime);
+		create_shortcut_road(flag, 9, -5, gametime);
 		inhibit_road_building_ = gametime + 400;
 		// and when a flag is full with wares
 	} else if (spots_ > kSpotsEnough && flag.current_wares() > 5) {
-		create_shortcut_road(flag, 9, -2, gametime);
+		create_shortcut_road(flag, 9, -5, gametime);
 		inhibit_road_building_ = gametime + 400;
 	} else {
 		return false;
@@ -2681,11 +2723,11 @@
 	uint8_t pathcounts = 0;
 	uint8_t checkradius = 0;
 	if (spots_ > kSpotsEnough) {
-		checkradius = 8;
+		checkradius = 7;
 	} else if (spots_ > kSpotsTooLittle) {
-		checkradius = 12;
+		checkradius = 11;
 	} else {
-		checkradius = 16;
+		checkradius = 15;
 	}
 	Map& map = game().map();
 
@@ -2834,24 +2876,24 @@
 
 	Map& map = game().map();
 
-	// 1. first we collect all reachange points
-	std::vector<NearFlag> nearflags;
-	std::unordered_set<uint32_t> lookuptable;
-
-	FindNodeWithFlagOrRoad functor;
-	CheckStepRoadAI check(player_, MOVECAPS_WALK, true);
+	// initializing new object of FlagsForRoads, we will push there all candidate flags
+  	Widelands::FlagsForRoads RoadCandidates(min_reduction);
+
+  	FindNodeWithFlagOrRoad functor;
+ 	CheckStepRoadAI check(player_, MOVECAPS_WALK, true);
+
+	// get all flags within radius
 	std::vector<Coords> reachable;
-
-	// vector reachable now contains all suitable fields
-	const uint32_t reachable_fields_count = map.find_reachable_fields(
+  	map.find_reachable_fields(
 	   Area<FCoords>(map.get_fcoords(flag.get_position()), checkradius), &reachable, check, functor);
 
-	if (reachable_fields_count == 0) {
-		return false;
-	}
-
 	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())) {
 
@@ -2871,59 +2913,31 @@
 				continue;
 			}
 
-			// now make sure that this field has not been processed yet
-			const uint32_t hash = reachable_coords.hash();
-			if (lookuptable.count(hash) == 0) {
-				lookuptable.insert(hash);
-
-				// adding flag into NearFlags if road is possible
-				std::unique_ptr<Path> path2(new Path());
-
-				if (map.findpath(flag.get_position(), reachable_coords, 0, *path2, check) >= 0) {
-
-					// path is possible, but for now we presume connection
-					//'walking on existing roads' is not possible
-					// so we assign 'virtual distance'
-					int32_t virtual_distance = 0;
-					// the same economy, but connection not spotted above via "walking on roads"
-					// algorithm
-					if (player_immovable->get_economy() == flag.get_economy()) {
-						virtual_distance = 50;
-					} else  // and now different economies
-					{
-						virtual_distance = 100;
-					}
-
-					// distance as the crow flies
-					const int32_t dist = map.calc_distance(flag.get_position(), reachable_coords);
-
-					nearflags.push_back(
-					   NearFlag(*dynamic_cast<const Flag*>(map[reachable_coords].get_immovable()),
-					            virtual_distance,
-					            dist));
-				}
-			}
+			// 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);
+			RoadCandidates.add_flag(reachable_coords, air_distance, different_economy);
 		}
 	}
 
-	// now we walk over roads and if field is reachable by roads, we change distance asigned before
+	// now we walk over roads and if field is reachable by roads, we change distance asigned above
 	std::priority_queue<NearFlag> queue;
-	std::vector<NearFlag> nearflags_tmp;  // only used to collect flags reachable walk over roads
+	std::vector<NearFlag> nearflags;  // only used to collect flags reachable walk over roads
 	queue.push(NearFlag(flag, 0, 0));
 
 	// algorithm to walk on roads
 	while (!queue.empty()) {
 		std::vector<NearFlag>::iterator f =
-		   find(nearflags_tmp.begin(), nearflags_tmp.end(), queue.top().flag);
+		   find(nearflags.begin(), nearflags.end(), queue.top().flag);
 
-		if (f != nearflags_tmp.end()) {
+		if (f != nearflags.end()) {
 			queue.pop();
 			continue;
 		}
 
-		nearflags_tmp.push_back(queue.top());
+		nearflags.push_back(queue.top());
 		queue.pop();
-		NearFlag& nf = nearflags_tmp.back();
+		NearFlag& nf = nearflags.back();
 
 		for (uint8_t i = 1; i <= 6; ++i) {
 			Road* const road = nf.flag->get_road(i);
@@ -2940,7 +2954,7 @@
 
 			int32_t dist = map.calc_distance(flag.get_position(), endflag->get_position());
 
-			if (dist > checkradius) {  //  out of range of interest
+			if (dist > checkradius + 5) {  //  Testing bigger vicinity then checkradius....
 				continue;
 			}
 
@@ -2948,75 +2962,47 @@
 		}
 	}
 
-	// iterating over nearflags_tmp, each item in nearflags_tmp should be contained also in nearflags
-	// so for each corresponding field in nearflags we update "cost" (distance on existing roads)
-	// to actual value
-	for (std::vector<NearFlag>::iterator nf_walk_it = nearflags_tmp.begin();
-	     nf_walk_it != nearflags_tmp.end();
-	     ++nf_walk_it) {
-		uint32_t const hash_walk = nf_walk_it->flag->get_position().hash();
-		if (lookuptable.count(hash_walk) > 0) {
-			// iterating over nearflags
-			for (std::vector<NearFlag>::iterator nf_it = nearflags.begin(); nf_it != nearflags.end();
-			     ++nf_it) {
-				uint32_t const hash = nf_it->flag->get_position().hash();
-				if (hash == hash_walk) {
-					// decreasing "cost" (of walking via roads)
-					if (nf_it->cost > nf_walk_it->cost) {
-						nf_it->cost = nf_walk_it->cost;
-					}
-				}
-			}
-		}
-	}
-
-	// ordering nearflags
-	std::sort(nearflags.begin(), nearflags.end(), NearFlag::CompareShortening());
-
-	// this is just a random number, will be used later
-	int32_t random_gametime = game().get_gametime();
-
-	// the problem here is that send_player_build_road() does not return success/failed
-	// if it did, we would just test the first nearflag, then go on with further flags until
-	// a road is built or nearflags are exhausted
-	// but now we must just randomly pick one of nearflags
-	// probabililty of picking decreases with position in nearflags
-	for (uint32_t i = 0; i < nearflags.size() && i < 10; ++i) {
-		NearFlag& nf = nearflags.at(i);
-
-		// terminating looping if reduction is too low (nearflags are sorted by reduction)
-		if ((nf.cost - nf.distance) < min_reduction) {
-			return false;
-		}
-
-		// testing the nearflag
-		// usually we allow connecting only if both flags are closer then 'checkradius-2'
-		// with exeption the flag belongs to a small economy (typically a new building not connected
-		// yet)
-		if ((nf.cost - nf.distance) >= min_reduction && nf.distance >= 2 &&
-		    nf.distance < checkradius - 2) {
-
-			// sometimes the shortest road is not the buildable, even if map.findpath claims so
-			// best so we add some randomness
-			random_gametime /= 3;
-			if (random_gametime % 3 > 1) {
-				continue;
-			}
-
-			Path& path = *new Path();
-
-			// value of pathcost is not important, it just indicates, that the path can be built
-			const int32_t pathcost =
-			   map.findpath(flag.get_position(), nf.flag->get_position(), 0, path, check);
-
-			if (pathcost >= 0) {
-				if (static_cast<int32_t>(nf.cost - path.get_nsteps()) > min_reduction) {
-					game().send_player_build_road(player_number(), path);
-					return true;
-				}
-			}
-			delete &path;
-		}
+	// Sending calculated walking costs from nearflags to RoadCandidates to update info on
+	// Candidate flags/roads
+	for (auto& nf_walk : nearflags) {
+		if (map.calc_distance(flag.get_position(), nf_walk.flag->get_position()) <= checkradius) {
+			// nearflags contains also flags beyond the radius, so we skip these
+			RoadCandidates.set_road_distance(nf_walk.flag->get_position(), static_cast<int32_t>(nf_walk.cost));
+		}
+	}
+
+	// We do not calculate roads to all nearby flags, ideally we investigate 4 roads, but the number
+	// can be higher if a road cannot be built to considered flag. The logic is: 2 points for possible
+	// road, 1 for impossible, and count < 10 so in worst scenario we will calculate 10 impossible
+	// roads without finding any possible
+	uint32_t count = 0;
+	uint32_t current = 0; // hash of flag that we are going to calculate in the iteration
+	while (count < 10 && RoadCandidates.get_best_uncalculated(&current)) {
+		const Widelands::Coords coords = Coords::unhash(current);
+
+		Path& path = *new Path();
+
+		// value of pathcost is not important, it just indicates, that the path can be built
+		const int32_t pathcost =
+			map.findpath(flag.get_position(), coords, 0, path, check);
+		if (pathcost>=0) {
+			RoadCandidates.road_possible(coords,  path.get_nsteps());
+			count += 2;
+		} else {
+			RoadCandidates.road_impossible(coords);
+			count += 1;
+		}
+	}
+
+	// Well and finally building the winning road
+	uint32_t winner_hash = 0;
+	if (RoadCandidates.get_winner(&winner_hash, (gametime%4>0)? 1 : 2)) {
+		const Widelands::Coords target_coords=Coords::unhash(winner_hash);
+		Path& path = *new Path();
+		const int32_t pathcost =map.findpath(flag.get_position(), target_coords, 0, path, check);
+		assert (pathcost>=0);
+		game().send_player_build_road(player_number(), path);
+		return true;
 	}
 
 	// if all possible roads skipped
@@ -4568,6 +4554,7 @@
 				score += (bf.military_stationed > 2);
 				score -= size_penalty;
 				score += ((bf.unowned_land_nearby + allyOwnedFields) < 10);
+				score -= (mso.built_time + 10 * 60 * 1000 > gametime);
 
 				if (score >= 4) {
 					if (ms->get_playercaps() & Widelands::Building::PCap_Dismantle) {
@@ -5155,6 +5142,11 @@
 			militarysites.back().site = &dynamic_cast<MilitarySite&>(b);
 			militarysites.back().bo = &bo;
 			militarysites.back().checks = bo.desc->get_size();
+			if (found_on_load && gametime > 5 * 60 * 1000) {
+				militarysites.back().built_time = gametime - 5 * 60 * 1000;
+			} else {
+				militarysites.back().built_time = gametime;
+			}
 			militarysites.back().enemies_nearby = true;
 			msites_per_size[bo.desc->get_size()].finished += 1;
 			vacant_mil_positions_ += 2; // at least some indication that there are vacant positions

=== modified file 'src/ai/defaultai.h'
--- src/ai/defaultai.h	2016-02-25 19:20:21 +0000
+++ src/ai/defaultai.h	2016-03-09 20:23:58 +0000
@@ -309,6 +309,7 @@
 	uint16_t military_last_dismantle_;
 	uint32_t military_last_build_;  // sometimes expansions just stops, this is time of last military
 	                                // building build
+	uint32_t last_road_dismantled_; // uses to prevent to frequent road dismantling
 
 	bool seafaring_economy;          // false by default, until first port space is found
 	uint32_t expedition_ship_;