widelands-dev team mailing list archive

[TiborB <tiborb95@xxxxxxxxx>]

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

Requested reviews:
  Widelands Developers (widelands-dev)

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

This is mainly AI thing. First this contains extension to map::findpath function (now used only by AI) to be more sensitive about building capabilities of field where the road is going to lead. (To avoid them a bit)

Subsequently I did some changes to AI's road creating algorithm.
-- 
Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/findpath_modification into lp:widelands.

=== modified file 'src/ai/ai_help_structs.cc'
--- src/ai/ai_help_structs.cc	2017-11-24 09:19:52 +0000
+++ src/ai/ai_help_structs.cc	2018-02-02 22:36:27 +0000
@@ -191,8 +191,15 @@
 	return false;
 }
 
-NearFlag::NearFlag(const Flag& f, int32_t const c, int32_t const d)
-   : flag(&f), cost(c), distance(d) {
+NearFlag::NearFlag(const Flag& f, int32_t const c)
+   : flag(&f), current_road_distance(c) {
+	to_be_checked = true;
+}
+
+NearFlag::NearFlag() {
+	flag = nullptr;
+	current_road_distance = 0;
+	to_be_checked = true;
 }
 
 EventTimeQueue::EventTimeQueue() {
@@ -870,56 +877,38 @@
 	return (blocked_fields_.count(coords.hash()) != 0);
 }
 
-FlagsForRoads::Candidate::Candidate(uint32_t coords, int32_t distance, bool economy)
-   : coords_hash(coords), air_distance(distance), different_economy(economy) {
+// 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;
-	accessed_via_roads = false;
+	new_road_length = 200;
 	// Values are only very rough, and are dependant on the map size
-	new_road_length = 2 * Widelands::kMapDimensions.at(Widelands::kMapDimensions.size() - 1);
-	current_roads_distance = 2 * (Widelands::kMapDimensions.size() - 1);  // must be big enough
-	reduction_score = -air_distance;  // allows reasonable ordering from the start
+	current_road_length = (different_economy) ? 600 : 400;  // must be big enough
 }
 
+// Used when sorting cadidate flags from best one
 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;
-	}
+	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;
 }
 
-void FlagsForRoads::Candidate::calculate_score() {
-	if (!new_road_possible) {
-		reduction_score = kRoadNotFound - air_distance;  // to have at least some ordering preserved
-	} else if (different_economy) {
-		reduction_score = kRoadToDifferentEconomy - air_distance - 2 * new_road_length;
-	} else if (!accessed_via_roads) {
-		if (air_distance + 6 > new_road_length) {
-			reduction_score = kShortcutWithinSameEconomy - air_distance - 2 * new_road_length;
-		} else {
-			reduction_score = kRoadNotFound;
-		}
-	} else {
-		reduction_score = current_roads_distance - 2 * new_road_length;
-	}
-}
-
 void FlagsForRoads::print() {  // this is for debugging and development purposes
-	for (auto& candidate_flag : queue) {
+	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) ?
+		    (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.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.reduction_score(),
 		    (candidate_flag.new_road_possible) ? ", new road possible" : " ");
 	}
 }
@@ -927,7 +916,7 @@
 // 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 : queue) {
+	for (auto& candidate_flag : flags_queue) {
 		if (!candidate_flag.new_road_possible) {
 			*winner = candidate_flag.coords_hash;
 			return true;
@@ -937,77 +926,57 @@
 }
 
 // Road from starting flag to this flag can be built
-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 interconnecting 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);
-	}
-}
-
+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.current_roads_distance = current_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 : queue) {
-		if (candidate_flag.reduction_score < min_reduction || !candidate_flag.new_road_possible) {
+	for (auto candidate_flag : flags_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.reduction_score() >= min_reduction);
 		assert(candidate_flag.new_road_possible);
 		*winner_hash = candidate_flag.coords_hash;
 		has_winner = true;
 
-		if (std::rand() % 3 > 0) {
-			// with probability of 2/3 we accept this flag
+		if (std::rand() % 4 > 0) {
+			// with probability of 3/4 we accept this flag
 			return true;
 		}
 	}

=== modified file 'src/ai/ai_help_structs.h'
--- src/ai/ai_help_structs.h	2017-11-17 07:16:12 +0000
+++ src/ai/ai_help_structs.h	2018-02-02 22:36:27 +0000
@@ -255,14 +255,14 @@
 	// ordering nearflags by biggest reduction
 	struct CompareShortening {
 		bool operator()(const NearFlag& a, const NearFlag& b) const {
-			return (a.cost - a.distance) > (b.cost - b.distance);
+			return a.current_road_distance > b.current_road_distance;
 		}
 	};
-
-	NearFlag(const Flag& f, int32_t const c, int32_t const d);
+	NearFlag();
+	NearFlag(const Flag& f, int32_t const c);
 
 	bool operator<(const NearFlag& f) const {
-		return cost > f.cost;
+		return current_road_distance > f.current_road_distance;
 	}
 
 	bool operator==(Flag const* const f) const {
@@ -270,8 +270,8 @@
 	}
 
 	Flag const* flag;
-	int32_t cost;
-	int32_t distance;
+	bool to_be_checked;
+	uint32_t current_road_distance;
 };
 
 // FIFO like structure for pairs <gametime,id>, where id is optional
@@ -731,45 +731,44 @@
 
 	struct Candidate {
 		Candidate();
-		Candidate(uint32_t coords, int32_t distance, bool economy);
+		Candidate(uint32_t coords, int32_t distance, bool different_economy);
 
 		uint32_t coords_hash;
 		int32_t new_road_length;
-		int32_t current_roads_distance;
+		int32_t current_road_length;
 		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 reduction_score() const {return current_road_length - new_road_length - (new_road_length - air_distance) / 3;};
 	};
 
 	int32_t min_reduction;
-	// This is the core of this object - candidate flags ordered by score
-	std::set<Candidate> queue;
+	// This is the core of this object - candidate flags to be ordered by air_distance
+	std::deque<Candidate> flags_queue; //NOCOM
 
-	void add_flag(Widelands::Coords coords, int32_t air_dist, bool diff_economy) {
-		queue.insert(Candidate(coords.hash(), air_dist, diff_economy));
+	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 queue.size();
+		return flags_queue.size();
 	}
+	bool has_candidate(const 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 distance);
-	void road_impossible(Widelands::Coords coords);
+	void road_possible(Widelands::Coords coords, const uint32_t new_road);
 	// Updating walking distance over existing roads
-	void set_road_distance(Widelands::Coords coords, int32_t distance);
+	void set_cur_road_distance(Widelands::Coords coords, const 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

=== modified file 'src/ai/defaultai.cc'
--- src/ai/defaultai.cc	2018-01-30 11:44:48 +0000
+++ src/ai/defaultai.cc	2018-02-02 22:36:27 +0000
@@ -3280,7 +3280,7 @@
 
 	// Various tests to invoke building of a shortcut (new road)
 	if (flag.nr_of_roads() == 0 || needs_warehouse) {
-		create_shortcut_road(flag, 17, 22, gametime);
+		create_shortcut_road(flag, 22, 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
@@ -3288,7 +3288,7 @@
 	} else if (flag.nr_of_roads() == 1 || std::rand() % 10 == 0) {
 		if (spots_ > kSpotsEnough) {
 			// This is the normal situation
-			create_shortcut_road(flag, 15, 22, gametime);
+			create_shortcut_road(flag, 18, 22, gametime);
 			inhibit_road_building_ = gametime + 800;
 		} else if (spots_ > kSpotsTooLittle) {
 			// We are short of spots so shortening must be significant
@@ -3301,11 +3301,11 @@
 		}
 		// a warehouse with 3 or less roads
 	} else if (is_warehouse && flag.nr_of_roads() <= 3) {
-		create_shortcut_road(flag, 9, -10, gametime);
+		create_shortcut_road(flag, 15, -10, 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, -5, gametime);
+		create_shortcut_road(flag, 15, -5, gametime);
 		inhibit_road_building_ = gametime + 400;
 	} else {
 		return false;
@@ -3335,13 +3335,13 @@
 	std::priority_queue<NearFlag> queue;
 	// only used to collect flags reachable walking over roads
 	std::vector<NearFlag> reachableflags;
-	queue.push(NearFlag(roadstartflag, 0, 0));
+	queue.push(NearFlag(roadstartflag, 0));
 	uint8_t pathcounts = 0;
-	uint8_t checkradius = 0;
+	uint8_t checkradius = 15;
 	if (spots_ > kSpotsEnough) {
-		checkradius = 7;
+		checkradius = 10;
 	} else if (spots_ > kSpotsTooLittle) {
-		checkradius = 11;
+		checkradius = 12;
 	} else {
 		checkradius = 15;
 	}
@@ -3395,7 +3395,7 @@
 				continue;
 			}
 
-			queue.push(NearFlag(*endflag, 0, dist));
+			queue.push(NearFlag(*endflag, 0));
 		}
 	}
 	return false;
@@ -3403,6 +3403,17 @@
 
 // trying to connect the flag to another one, be it from own economy
 // or other economy
+// The procedure is:
+// - Collect all flags within checkradius into RoadCandidates, but first we dont even know if a road
+// can be built to them
+// - Walking over road network to collect info on flags that are accessible over road network
+// - Than merge info from NearFlags to RoadCandidates and consider roads to few best candidates from
+// RoadCandidates We use score named "reduction" that is basically diff between connection over
+// existing roads minus possible road from starting flag to candidate flag Of course there are two
+// special cases:
+// - the candidate flag does not belong to the same economy, so no road connection exists
+// - they are from same economy, but are connected beyond range of checkradius, so actual length of
+// connection is not known
 bool DefaultAI::create_shortcut_road(const Flag& flag,
                                      uint16_t checkradius,
                                      int16_t min_reduction,
@@ -3490,9 +3501,11 @@
 		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;
@@ -3532,32 +3545,41 @@
 			// 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);
+			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::priority_queue<NearFlag> queue;
-	std::vector<NearFlag> nearflags;  // only used to collect flags reachable walk over roads
-	queue.push(NearFlag(flag, 0, 0));
+	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
-	while (!queue.empty()) {
-		std::vector<NearFlag>::iterator f =
-		   find(nearflags.begin(), nearflags.end(), queue.top().flag);
-
-		if (f != nearflags.end()) {
-			queue.pop();
-			continue;
-		}
-
-		nearflags.push_back(queue.top());
-		queue.pop();
-		NearFlag& nf = nearflags.back();
-
+	// All nodes are marked as to_be_checked and under some conditions, the same node can be checked
+	// twice
+	while (true) {
+		// 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, so no node to be checked - quitting 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 = nf.flag->get_road(i);
+			Road* const road = nearflags[start_field].flag->get_road(i);
 
 			if (!road) {
 				continue;
@@ -3565,68 +3587,111 @@
 
 			Flag* endflag = &road->get_flag(Road::FlagStart);
 
-			if (endflag == nf.flag) {
+			if (endflag == nearflags[start_field].flag) {
 				endflag = &road->get_flag(Road::FlagEnd);
 			}
 
-			int32_t dist = map.calc_distance(flag.get_position(), endflag->get_position());
-
-			if (dist > checkradius + 5) {  //  Testing bigger vicinity then checkradius....
+			uint32_t endflag_hash = endflag->get_position().hash();
+
+			int32_t dist =
+			   map.calc_distance(nearflags[start_field].flag->get_position(), endflag->get_position());
+
+			if (dist > checkradius + 2) {  //  Testing bigger vicinity then checkradius....
 				continue;
 			}
 
-			queue.push(NearFlag(*endflag, nf.cost + road->get_path().get_nsteps(), dist));
+			// 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 {
+				// Were here
+				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) {
-		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));
+		// 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);
 		}
 	}
 
-	// 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;
+	// 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 = 5;
+	if (spots_ < kSpotsTooLittle) {
+		fields_necessity += 10;
+	}
+	if (map_allows_seafaring_ && num_ports == 0) {
+		fields_necessity += 10;
+	}
+	if (num_ports < 4) {
+		fields_necessity += 10;
+	}
+	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 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 (count < 10 && RoadCandidates.get_best_uncalculated(&current)) {
+	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
-		const int32_t pathcost = map.findpath(flag.get_position(), coords, 0, path, check);
+		// 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());
-			count += 2;
-		} else {
-			RoadCandidates.road_impossible(coords);
-			count += 1;
+			possible_roads_count += 1;
 		}
 	}
 
-	// Well and finally building the winning road
+	// re-sorting again, now by reduction score
+	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();
 #ifndef NDEBUG
-		const int32_t pathcost = map.findpath(flag.get_position(), target_coords, 0, path, check);
+		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);
+		map.findpath(flag.get_position(), target_coords, 0, path, check, 0, fields_necessity);
 #endif
 		game().send_player_build_road(player_number(), path);
 		return true;
 	}
-
 	// if all possible roads skipped
 	if (last_attempt_) {
 		Building* bld = flag.get_building();
@@ -3640,7 +3705,6 @@
 		game().send_player_bulldoze(*const_cast<Flag*>(&flag));
 		return true;
 	}
-
 	return false;
 }
 

=== modified file 'src/logic/map.cc'
--- src/logic/map.cc	2017-12-31 18:46:49 +0000
+++ src/logic/map.cc	2018-02-02 22:36:27 +0000
@@ -1612,7 +1612,8 @@
                       int32_t const persist,
                       Path& path,
                       const CheckStep& checkstep,
-                      uint32_t const flags) const {
+                      uint32_t const flags,
+	                  uint32_t const caps_sensitivity) const {
 	FCoords start;
 	FCoords end;
 	int32_t upper_cost_limit;
@@ -1695,6 +1696,15 @@
 			cost = curpf->real_cost + ((flags & fpBidiCost) ? calc_bidi_cost(cur, *direction) :
 			                                                  calc_cost(cur, *direction));
 
+			// If required (indicated by caps_sensitivity) we increase the path costs
+			// if the path is just crossing a field with building capabilities
+			if (caps_sensitivity > 0) {
+				int32_t buildcaps_score = neighb.field->get_caps() & BUILDCAPS_SIZEMASK;
+				buildcaps_score += (neighb.field->get_caps() & BUILDCAPS_MINE) ? 1 : 0;
+				buildcaps_score += (neighb.field->get_caps() & BUILDCAPS_PORT) ? 9 : 0;
+				cost += buildcaps_score * caps_sensitivity;
+			}
+
 			if (neighbpf.cycle != pathfields->cycle) {
 				// add to open list
 				neighbpf.cycle = pathfields->cycle;

=== modified file 'src/logic/map.h'
--- src/logic/map.h	2017-12-18 10:42:40 +0000
+++ src/logic/map.h	2018-02-02 22:36:27 +0000
@@ -354,7 +354,8 @@
 	                 const int32_t persist,
 	                 Path&,
 	                 const CheckStep&,
-	                 const uint32_t flags = 0) const;
+	                 const uint32_t flags = 0,
+	                 const uint32_t caps_sensitivity = 0) const;
 
 	/**
 	 * We can reach a field by water either if it has MOVECAPS_SWIM or if it has