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

[TiborB]

AI tweak - better identification of unconnectable regions based on walking algorithm. Used to keep AI from wasting attempts to build there something.

This improves behavior related to blocked_fields (list of fields temporarily blocked for construction of new buildable fields). Now it better calculates the region that is temporarily unconnectable and consider these blocked fields more. However, visible difference is quite small.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 3294. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/354043229.
Appveyor build 3102. State: failed. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ai_blocked_fields_tweaks-3102.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 3295. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/354209658.
Appveyor build 3103. State: failed. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ai_blocked_fields_tweaks-3103.

[GunChleoc (gunchleoc)]

Looks good to me - just some minor nits. Please feel free to merge once you have addressed those to your liking. Don't forget to set the commit message above ;)

review: Approve

[TiborB (tiborb95)]

@Gun
How can I use imm->descr().type() to say if an immovable is PlayerImmovable?

[TiborB (tiborb95)]

Do you mean this:
https://bazaar.launchpad.net/~widelands-dev/widelands/trunk/view/head:/src/logic/map_objects/map_object.h#L58
?

Is it guaranteed that type >= 40 is player immovable?

[TiborB (tiborb95)]

Got it!
It can go once the CI is green

[GunChleoc (gunchleoc)]

Please set a commit message on the top of this page.

[TiborB (tiborb95)]

Sorry, I forgot, done now.....

[GunChleoc (gunchleoc)]

Great, thanks!

@bunnybot merge

review: Approve

=== modified file 'src/ai/ai_help_structs.cc'
--- src/ai/ai_help_structs.cc	2018-02-16 20:42:21 +0000
+++ src/ai/ai_help_structs.cc	2018-03-25 16:41:13 +0000
@@ -42,7 +42,7 @@
 
 bool CheckStepRoadAI::allowed(
    const Map& map, FCoords start, FCoords end, int32_t, CheckStep::StepId const id) const {
-	uint8_t endcaps = player->get_buildcaps(end);
+	const uint8_t endcaps = player->get_buildcaps(end);
 
 	// we should not cross fields with road or flags (or any other immovable)
 	if ((map.get_immovable(start)) && !(id == CheckStep::stepFirst)) {
@@ -83,6 +83,57 @@
 	return true;
 }
 
+
+// CheckStepOwnTerritory
+CheckStepOwnTerritory::CheckStepOwnTerritory(Player* const pl, uint8_t const mc, bool const oe)
+   : player(pl), movecaps(mc), open_end(oe) {
+}
+
+// Defines when movement is allowed:
+// 1. startfield is walkable (or it is the first step)
+// And endfield either:
+// 2a. is walkable
+// 2b. has our PlayerImmovable (building or flag)
+bool CheckStepOwnTerritory::allowed(
+   const Map& map, FCoords start, FCoords end, int32_t, CheckStep::StepId const id) const {
+	const uint8_t endcaps = player->get_buildcaps(end);
+	const uint8_t startcaps = player->get_buildcaps(start);
+
+	// We should not cross fields with road or flags (or any other immovable)
+	// Or rather we can step on it, but not go on from such field
+	if ((map.get_immovable(start)) && !(id == CheckStep::stepFirst)) {
+		return false;
+	}
+
+	// Start field must be walkable
+	if (!(startcaps & movecaps)) {
+		return false;
+	}
+
+	// Endfield can not be water
+	if (endcaps & MOVECAPS_SWIM) {
+		return false;
+	}
+
+	return true;
+}
+
+// We accept either walkable territory or field with own immovable
+bool CheckStepOwnTerritory::reachable_dest(const Map& map, const FCoords& dest) const {
+	const uint8_t endcaps = player->get_buildcaps(dest);
+	if (BaseImmovable const* const imm = map.get_immovable(dest)) {
+		if (imm->descr().type() >= MapObjectType::FLAG) {
+			return true;
+		} else {
+			return false;
+		}
+	}
+	if (endcaps & MOVECAPS_WALK) {
+		return true;
+	}
+	return false;
+}
+
 // We are looking for fields we can walk on
 // and owned by hostile player.
 FindNodeEnemy::FindNodeEnemy(Player* p, Game& g) : player(p), game(g) {
@@ -296,7 +347,8 @@
 }
 
 EconomyObserver::EconomyObserver(Widelands::Economy& e) : economy(e) {
-	dismantle_grace_time = std::numeric_limits<int32_t>::max();
+	dismantle_grace_time = std::numeric_limits<uint32_t>::max();
+	fields_block_last_time = 0;
 }
 
 int32_t BuildingObserver::total_count() const {
 
=== modified file 'src/ai/ai_help_structs.h'
--- src/ai/ai_help_structs.h	2018-03-03 20:46:01 +0000
+++ src/ai/ai_help_structs.h	2018-03-25 16:41:13 +0000
@@ -133,6 +133,21 @@
 	Player* player;
 	uint8_t movecaps;
 	bool open_end;
+
+};
+
+// Used to walk ower own territory, on fields that are walkable (or as given by mc)
+// plus one step more to a field with own immovable. So that also flags and buildings are
+// included in resulting list
+struct CheckStepOwnTerritory {
+	CheckStepOwnTerritory(Player* const pl, uint8_t const mc, bool const oe);
+
+	bool allowed(const Map&, FCoords start, FCoords end, int32_t dir, CheckStep::StepId) const;
+	bool reachable_dest(const Map&, const FCoords& dest) const;
+
+	Player* player;
+	uint8_t movecaps;
+	bool open_end;
 };
 
 // We are looking for fields we can walk on
@@ -249,6 +264,11 @@
 	bool accept(const Map&, FCoords) const;
 };
 
+// Accepts any field
+struct FindNodeAcceptAll {
+	bool accept(const Map&, FCoords) const {return true;};
+};
+
 struct NearFlag {
 	// ordering nearflags by biggest reduction
 	struct CompareShortening {
@@ -387,7 +407,8 @@
 
 	Widelands::Economy& economy;
 	std::deque<Widelands::Flag const*> flags;
-	int32_t dismantle_grace_time;
+	uint32_t dismantle_grace_time;
+	uint32_t fields_block_last_time;
 };
 
 struct BuildingObserver {
 
=== modified file 'src/ai/defaultai.cc'
--- src/ai/defaultai.cc	2018-03-03 20:46:01 +0000
+++ src/ai/defaultai.cc	2018-03-25 16:41:13 +0000
@@ -2069,9 +2069,15 @@
 	for (int32_t i = 0; i < 4; ++i)
 		spots_avail.at(i) = 0;
 
+	// We calculate owned buildable spots, of course ignoring ones that are blocked
+	// for now
 	for (std::deque<BuildableField*>::iterator i = buildable_fields.begin();
-	     i != buildable_fields.end(); ++i)
+	     i != buildable_fields.end(); ++i) {
+			 if (blocked_fields.is_blocked((*i)->coords)) {
+				 continue;
+			 }
 		++spots_avail.at((*i)->coords.field->nodecaps() & BUILDCAPS_SIZEMASK);
+	}
 
 	spots_ = spots_avail.at(BUILDCAPS_SMALL);
 	spots_ += spots_avail.at(BUILDCAPS_MEDIUM);
@@ -3549,7 +3555,7 @@
 bool DefaultAI::create_shortcut_road(const Flag& flag,
                                      uint16_t checkradius,
                                      int16_t min_reduction,
-                                     int32_t gametime) {
+                                     uint32_t gametime) {
 
 	// Increasing the failed_connection_tries counter
 	// At the same time it indicates a time an economy is without a warehouse
@@ -3561,8 +3567,8 @@
 	// 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<int32_t>::max()) {
-		eco->dismantle_grace_time = std::numeric_limits<int32_t>::max();
+	    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
@@ -3583,12 +3589,12 @@
 
 		// if we are within grace time, it is OK, just go on
 		if (eco->dismantle_grace_time > gametime &&
-		    eco->dismantle_grace_time != std::numeric_limits<int32_t>::max()) {
+		    eco->dismantle_grace_time != std::numeric_limits<uint32_t>::max()) {
 			;
 
 			// if grace time is not set, this is probably first time without a warehouse and we must
 			// set it
-		} else if (eco->dismantle_grace_time == std::numeric_limits<int32_t>::max()) {
+		} else if (eco->dismantle_grace_time == std::numeric_limits<uint32_t>::max()) {
 
 			// constructionsites
 			if (upcast(ConstructionSite const, constructionsite, flag.get_building())) {
@@ -3827,19 +3833,38 @@
 		game().send_player_build_road(player_number(), path);
 		return true;
 	}
-	// if all possible roads skipped
-	if (last_attempt_) {
-		Building* bld = flag.get_building();
-		// first we block the field and vicinity for 15 minutes, probably it is not a good place to
-		// build on
-		MapRegion<Area<FCoords>> mr(map, Area<FCoords>(map.get_fcoords(bld->get_position()), 2));
-		do {
-			blocked_fields.add(mr.location(), game().get_gametime() + 15 * 60 * 1000);
-		} while (mr.advance(map));
-		remove_from_dqueue<Widelands::Flag>(eco->flags, &flag);
-		game().send_player_bulldoze(*const_cast<Flag*>(&flag));
-		dead_ends_check_ = true;
-		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;
 }
 
=== modified file 'src/ai/defaultai.h'
--- src/ai/defaultai.h	2018-02-20 21:11:27 +0000
+++ src/ai/defaultai.h	2018-03-25 16:41:13 +0000
@@ -199,7 +199,7 @@
 	bool create_shortcut_road(const Widelands::Flag&,
 	                          uint16_t maxcheckradius,
 	                          int16_t minReduction,
-	                          const int32_t gametime);
+	                          const uint32_t gametime);
 	// trying to identify roads that might be removed
 	bool dispensable_road_test(const Widelands::Road&);
 	bool dismantle_dead_ends();