widelands-dev team mailing list archive

[toptopple <7010622@xxxxxx>]

toptopple has proposed merging lp:~7010622-q/widelands/topple-seafaring-2 into lp:widelands.

Commit message:
further improvements of sea exploration AI (seafaring)
max. expedition time made adapting to map size (60-210 min)

Requested reviews:
  Widelands Developers (widelands-dev)

For more details, see:
https://code.launchpad.net/~7010622-q/widelands/topple-seafaring-2/+merge/312111

changed "visited spots" list to player-global list
made expedition-max-time dependent on the map size (60 to 210 min)
stabilised island circle movement (against random direction choice)
improved spot scoring "other-region" evaluation to radius 10
reaction to "no open sea" is again ship-explore-island"
removed blocking of map region
-- 
Your team Widelands Developers is requested to review the proposed merge of lp:~7010622-q/widelands/topple-seafaring-2 into lp:widelands.

=== modified file 'src/ai/ai_help_structs.h'
--- src/ai/ai_help_structs.h	2016-08-04 15:49:05 +0000
+++ src/ai/ai_help_structs.h	2016-11-30 04:53:43 +0000
@@ -431,15 +431,13 @@
 
 struct ShipObserver {
 	Widelands::Ship* ship;
-	Widelands::Coords expedition_start_point;
-	std::unordered_set<uint32_t> visited_spots;
+	bool waiting_for_command_ = false;
+	uint32_t last_command_time = 0;
 
-	// a ship circumvents all islands in the same direction, the value
-	// is assigned only once
+	// direction by which the ship circumvents an island
+	// this is the last circle-island command's direction
 	Widelands::IslandExploreDirection island_circ_direction =
 	   Widelands::IslandExploreDirection::kClockwise;
-	bool waiting_for_command_ = false;
-	uint32_t last_command_time = 0;
 };
 
 struct WareObserver {

=== modified file 'src/ai/defaultai.cc'
--- src/ai/defaultai.cc	2016-11-24 19:45:32 +0000
+++ src/ai/defaultai.cc	2016-11-30 04:53:43 +0000
@@ -870,8 +870,21 @@
 		throw wexception("Corrupted AI data");
 	}
 
+	// initialise max duration of single ship's expedition
+	uint32_t ar1 = uint32_t(map.get_height()) * map.get_width();
+	uint32_t rt1 = round(sqrt(ar1));
+	printf("--- EXPEDITION MAP AREA ROOT == %u\n", rt1);
+	int scope = 320 - 64;
+	int off = rt1 - 64;
+	if (off < 0) off = 0;
+	if (off > scope) off = scope;
+	expedition_max_duration = kExpeditionMinDuration +
+			double(off) * (kExpeditionMaxDuration - kExpeditionMinDuration) / scope;
+	printf("--- EXPEDITION MAX DURATION == %u\n", expedition_max_duration/1000);
+	assert(expedition_max_duration >= kExpeditionMinDuration && expedition_max_duration > 0);
+
 	// Sometimes there can be a ship in expedition, but expedition start time is not given
-	// f.e. human player played this player before
+	// e.g. human player played this player before
 	if (expedition_ship_ != kNoShip && persistent_data->expedition_start_time == kNoExpedition) {
 		// Current gametime is better then 'kNoExpedition'
 		persistent_data->expedition_start_time = gametime;
@@ -4131,7 +4144,7 @@
 		}
 }
 
-// walk and search for territory controlled by other player
+// walk and search for territory controlled by some player type
 // usually scanning radius is enough but sometimes we must walk to
 // verify that an enemy territory is really accessible by land
 bool DefaultAI::other_player_accessible(const uint32_t max_distance,
@@ -4179,7 +4192,7 @@
 				return true;
 			}
 
-			// if anybody but not me
+			// if somebody but not me
 			if (type == WalkSearch::kOtherPlayers && f->get_owned_by() != pn) {
 				*tested_fields = done.size();
 				return true;

=== modified file 'src/ai/defaultai.h'
--- src/ai/defaultai.h	2016-11-24 19:53:52 +0000
+++ src/ai/defaultai.h	2016-11-30 04:53:43 +0000
@@ -162,7 +162,7 @@
 	void update_mineable_field(Widelands::MineableField&);
 	void update_productionsite_stats();
 
-	// for productionsites
+	// for production sites
 	Widelands::BuildingNecessity
 	check_building_necessity(Widelands::BuildingObserver& bo, PerfEvaluation purpose, uint32_t);
 
@@ -227,6 +227,7 @@
 	template <typename T> void check_range(const T, const T, const char*);
 
 	// Functions used for seafaring / defaultai_seafaring.cc
+	Widelands::IslandExploreDirection randomExploreDirection();
 	void gain_ship(Widelands::Ship&, NewShip);
 	void check_ship_in_expedition(Widelands::ShipObserver&, uint32_t);
 	void expedition_management(Widelands::ShipObserver&);
@@ -337,12 +338,15 @@
 	enum { kReprioritize, kStopShipyard, kStapShipyard };
 	bool seafaring_economy;  // false by default, until first port space is found
 	uint32_t expedition_ship_;
+	uint32_t expedition_max_duration;
 	std::vector<int16_t> marine_task_queue;
+	std::unordered_set<uint32_t> expedition_visited_spots;
 
 	// common for defaultai.cc and defaultai_seafaring.cc
 	static constexpr int kColonyScanStartArea = 35;
 	static constexpr int kColonyScanMinArea = 10;
-	static constexpr int kExpeditionMaxDuration = 120 * 60 * 1000;
+	static constexpr int kExpeditionMinDuration = 60 * 60 * 1000;
+	static constexpr int kExpeditionMaxDuration = 210 * 60 * 1000;
 	static constexpr uint32_t kNoShip = std::numeric_limits<uint32_t>::max();
 	static constexpr uint32_t kNever = std::numeric_limits<uint32_t>::max();
 	static constexpr uint32_t kNoExpedition = 0;

=== modified file 'src/ai/defaultai_seafaring.cc'
--- src/ai/defaultai_seafaring.cc	2016-11-23 21:37:22 +0000
+++ src/ai/defaultai_seafaring.cc	2016-11-30 04:53:43 +0000
@@ -29,10 +29,9 @@
 	uint16_t mineable_fields_count = 0;
 	uint32_t tested_fields = 0;
 
-	// abort if any player - including self - is too near to the spot (radius 8)
-	// TODO(toptopple): extract function for player distance only
+	// abort if any player - including self - is too near to the spot (radius 10)
 	if (other_player_accessible(
-	       8, &tested_fields, &mineable_fields_count, candidate_spot, WalkSearch::kAnyPlayer)) {
+	       10, &tested_fields, &mineable_fields_count, candidate_spot, WalkSearch::kAnyPlayer)) {
 		return 0;
 	}
 
@@ -226,9 +225,9 @@
 
 	if (!allships.empty()) {
 		// iterating over ships and doing what is needed
-		for (std::list<ShipObserver>::iterator i = allships.begin(); i != allships.end(); ++i) {
+		for (std::list<ShipObserver>::iterator so = allships.begin(); so != allships.end(); ++so) {
 
-			const Widelands::Ship::ShipStates ship_state = i->ship->get_ship_state();
+			const Widelands::Ship::ShipStates ship_state = so->ship->get_ship_state();
 
 			// Here we manage duration of expedition and related variables
 			if (ship_state == Widelands::Ship::ShipStates::kExpeditionWaiting ||
@@ -240,42 +239,41 @@
 				// - expedition_start_time
 				// - expected_colony_scan
 				// - no_more_expeditions_
-				check_ship_in_expedition(*i, gametime);
+				check_ship_in_expedition(*so, gametime);
 
 				// We are not in expedition mode (or perhaps building a colonisation port)
 				// so resetting start time
-			} else if (expedition_ship_ == i->ship->serial()) {
+			} else if (expedition_ship_ == so->ship->serial()) {
 				// Obviously expedition just ended
 				persistent_data->expedition_start_time = kNoExpedition;
 				expedition_ship_ = kNoShip;
 			}
 
 			// only two states need an attention
-			if ((i->ship->get_ship_state() == Widelands::Ship::ShipStates::kExpeditionWaiting ||
-			     i->ship->get_ship_state() ==
-			        Widelands::Ship::ShipStates::kExpeditionPortspaceFound) &&
-			    !i->waiting_for_command_) {
-				if (gametime - i->last_command_time > 180 * 1000) {
-					i->waiting_for_command_ = true;
+			if ((so->ship->get_ship_state() == Widelands::Ship::ShipStates::kExpeditionWaiting ||
+			     so->ship->get_ship_state() == Widelands::Ship::ShipStates::kExpeditionPortspaceFound) &&
+			    !so->waiting_for_command_) {
+				if (gametime - so->last_command_time > 180 * 1000) {
+					so->waiting_for_command_ = true;
 					log("  %1d: last command for ship at %3dx%3d was %3d seconds ago, something wrong "
 					    "here?...\n",
-					    player_number(), i->ship->get_position().x, i->ship->get_position().y,
-					    (gametime - i->last_command_time) / 1000);
+					    player_number(), so->ship->get_position().x, so->ship->get_position().y,
+					    (gametime - so->last_command_time) / 1000);
 				}
 			}
 			// if ships is waiting for command
-			if (i->waiting_for_command_) {
-				expedition_management(*i);
+			if (so->waiting_for_command_) {
+				expedition_management(*so);
 				action_taken = true;
 			}
 
 			// Checking utilization
-			if (i->ship->get_ship_state() == Widelands::Ship::ShipStates::kTransport) {
+			if (so->ship->get_ship_state() == Widelands::Ship::ShipStates::kTransport) {
 				// Good utilization is 10 pieces of ware onboard, to track utilization we use range
 				// 0-10000
 				// to avoid float or rounding errors if integers in range 0-100
 				const int16_t tmp_util =
-				   (i->ship->get_nritems() > 10) ? 10000 : i->ship->get_nritems() * 1000;
+				   (so->ship->get_nritems() > 10) ? 10000 : so->ship->get_nritems() * 1000;
 				// This number is kind of average
 				persistent_data->ships_utilization =
 				   persistent_data->ships_utilization * 19 / 20 + tmp_util / 20;
@@ -323,49 +321,47 @@
 }
 
 /**
- * This is part of check_ships() function separated due to readibility purpuses
+ * This is part of check_ships() function separated for readability
  */
-void DefaultAI::check_ship_in_expedition(ShipObserver& so, uint32_t const gametime) {
+ void DefaultAI::check_ship_in_expedition(ShipObserver& so, uint32_t const gametime) {
 	// consistency check
 	assert(expedition_ship_ == so.ship->serial() || expedition_ship_ == kNoShip);
+	uint32_t expedition_time = gametime - persistent_data->expedition_start_time;
 
-	// This is obviously new expedition
+	// obviously a new expedition
 	if (expedition_ship_ == kNoShip) {
 		assert(persistent_data->expedition_start_time == kNoExpedition);
 		persistent_data->expedition_start_time = gametime;
 		expedition_ship_ = so.ship->serial();
 
-		// Already known expedition, all we do now, is decreasing persistent_data->colony_scan_area
-		// based on lapsed time
-	} else if (gametime - persistent_data->expedition_start_time < kExpeditionMaxDuration) {
+	// expedition is overdue, setting no_more_expeditions = true
+	// also we attempt to cancel expedition (the code for cancellation may not work properly)
+	// TODO(unknown): - test expedition cancellation deeply (may need to be fixed)
+	} else if (expedition_time >= expedition_max_duration) {
+		assert(persistent_data->expedition_start_time > 0);
+		persistent_data->colony_scan_area = kColonyScanMinArea;
+		persistent_data->no_more_expeditions = kTrue;
+		game().send_player_cancel_expedition_ship(*so.ship);
+
+	// for known and running expedition
+	} else {
+		// decrease persistent_data->colony_scan_area based on lapsed time
 		assert(persistent_data->expedition_start_time > kNoExpedition);
-		// remaining_time is a percent so in range 0-100
+		assert(expedition_time < expedition_max_duration);
+
+		// calculate percentage of remaining expedition time (range 0-100)
 		const uint32_t remaining_time = 100 - ((gametime - persistent_data->expedition_start_time) /
-		                                       (kExpeditionMaxDuration / 100));
+		                                       (expedition_max_duration / 100));
 		assert(remaining_time <= 100);
 
-		// We calculate expected value and actual value (persistent_data->colony_scan_area
-		// is changed only when needed)
+		// calculate a new persistent_data->colony_scan_area (value is unchanged or decreased)
 		const uint32_t expected_colony_scan =
 		   kColonyScanMinArea + (kColonyScanStartArea - kColonyScanMinArea) * remaining_time / 100;
 		assert(expected_colony_scan >= kColonyScanMinArea &&
 		       expected_colony_scan <= kColonyScanStartArea);
-
-		// So changing it if needed
 		if (expected_colony_scan < persistent_data->colony_scan_area) {
 			persistent_data->colony_scan_area = expected_colony_scan;
 		}
-
-		// Expedition overdue. Setting no_more_expeditions = true
-		// But we do not cancel it, the code for cancellation does not work properly now
-		// TODO(unknown): - expedition code for cancellation needs to be fixed and afterwareds
-		// AI can be changed to cancel overdue expedition
-	} else if (gametime - persistent_data->expedition_start_time >= kExpeditionMaxDuration) {
-		assert(persistent_data->expedition_start_time > 0);
-		persistent_data->colony_scan_area = kColonyScanMinArea;
-		persistent_data->no_more_expeditions = kTrue;
-
-		game().send_player_cancel_expedition_ship(*so.ship);
 	}
 }
 
@@ -374,11 +370,7 @@
 
 	allships.push_back(ShipObserver());
 	allships.back().ship = &ship;
-	if (game().logic_rand() % 20 < 10) {
-		allships.back().island_circ_direction = IslandExploreDirection::kClockwise;
-	} else {
-		allships.back().island_circ_direction = IslandExploreDirection::kCounterClockwise;
-	}
+	allships.back().island_circ_direction = randomExploreDirection();
 
 	if (type == NewShip::kBuilt) {
 		marine_task_queue.push_back(kStopShipyard);
@@ -397,8 +389,14 @@
 	}
 }
 
+Widelands::IslandExploreDirection DefaultAI::randomExploreDirection () {
+	return game().logic_rand() % 20 < 10 ?
+	     Widelands::IslandExploreDirection::kClockwise :
+	     Widelands::IslandExploreDirection::kCounterClockwise;
+}
+
 // this is called whenever ship received a notification that requires
-// navigation decisions (these notifiation are processes not in 'real time')
+// navigation decisions (these notification are processes not in 'real time')
 void DefaultAI::expedition_management(ShipObserver& so) {
 
 	Map& map = game().map();
@@ -406,53 +404,55 @@
 	// probability for island exploration repetition
 	const int repeat_island_prob = 20;
 
-	// second we put current spot into visited_spots
-	bool first_time_here = so.visited_spots.count(so.ship->get_position().hash()) == 0;
+	// second we put current spot into expedition visited_spots
+	bool first_time_here = expedition_visited_spots.count(so.ship->get_position().hash()) == 0;
 	if (first_time_here) {
-		so.visited_spots.insert(so.ship->get_position().hash());
+		expedition_visited_spots.insert(so.ship->get_position().hash());
 	}
 
-	// if we have portspace following options are avaiable:
-	// 1. Build a port there
-	if (!so.ship->exp_port_spaces().empty()) {  // making sure we have possible portspaces
+	// if we have a port-space we can build a Port or continue exploring
+	// 1. examine to build a port (colony founding)
+	if (!so.ship->exp_port_spaces().empty()) {
 
 		// we score the place (value max == 8)
 		const uint8_t spot_score = spot_scoring(so.ship->exp_port_spaces().front()) * 2;
 
-		if (game().logic_rand() % 8 < spot_score) {  // we build a port here
+		// we make a decision based on the score value and random
+		if (game().logic_rand() % 8 < spot_score) {
+			// we build a port here
 			game().send_player_ship_construct_port(*so.ship, so.ship->exp_port_spaces().front());
 			so.last_command_time = gametime;
 			so.waiting_for_command_ = false;
-			// blocking the area for some time to save AI from idle attempts to built there
-			// buildings
-			// TODO(TiborB): how long it takes to build a port?
-			// I used 5 minutes
-			MapRegion<Area<FCoords>> mr(
-			   map, Area<FCoords>(map.get_fcoords(so.ship->exp_port_spaces().front()), 8));
-			do {
-				blocked_fields.add(mr.location(), game().get_gametime() + 5 * 60 * 1000);
-			} while (mr.advance(map));
 
 			return;
 		}
 	}
 
 	// 2. Go on with expedition
-
-	// we were not here before
-	if (first_time_here) {
+    // we were not here before
+	// OR we might randomly repeat island exploration
+	if (first_time_here || game().logic_rand() % 100 < repeat_island_prob) {
+		if (first_time_here) {
+			printf("EXPLORE- first time here\n");
+		} else {
+			printf("EXPLORE- here before\n");
+		}
+
+		// determine direction of island circle movement
+		// Note: if the ship doesn't own an island-explore-direction it is in inter-island exploration
+		// in this case we create a new direction at random, otherwise continue circle movement
+		if (!so.ship->is_island_circling()) {
+			so.island_circ_direction = randomExploreDirection();
+			printf("EXPLORE- set new SAIL direction: %u\n", so.island_circ_direction);
+		} else {
+			printf("EXPLORE- continue ISLAND CIRCLE, dir=%u\n", so.island_circ_direction);
+		}
+
+		// send the ship to circle island
 		game().send_player_ship_explore_island(*so.ship, so.island_circ_direction);
 
-		// we were here before but we might randomly repeat island exploration
-	} else if (game().logic_rand() % 100 < repeat_island_prob) {
-		// let's add randomness to the Brown's molecule movement of ship
-		// TODO(toptopple): make the following decision dependent on ship state != circle-island
-		Widelands::IslandExploreDirection dir =
-		   game().logic_rand() % 10 < 5 ? Widelands::IslandExploreDirection::kClockwise :
-		                                  Widelands::IslandExploreDirection::kCounterClockwise;
-		game().send_player_ship_explore_island(*so.ship, dir);
 
-		// we head for open sea again
+    // we head for open sea again
 	} else {
 		// determine swimmable directions
 		std::vector<Direction> possible_directions;
@@ -475,19 +475,17 @@
 		// we test if there is open sea
 		if (possible_directions.empty()) {
 			// 2.A No there is no open sea
-			// ## test-out of cancel-expedition method
-			// ## circle island has danger of endless repetition
-			// TODO(unknown): we should implement a 'rescue' procedure like 'sail for x fields and
-			// rethink'
-			game().send_player_cancel_expedition_ship(*so.ship);
-			// game().send_player_ship_explore_island(*so.ship, so.island_circ_direction);
+			// TODO(unknown): we should implement a 'rescue' procedure like 'sail for x fields and wait-state'
+			game().send_player_ship_explore_island(*so.ship, so.island_circ_direction);
+			printf("EXPLORE- jamming spot, cont CIRCLE, dir=%u\n", so.island_circ_direction);
 
 		} else {
 			// 2.B Yes, pick one of available directions
-			const Direction final_direction =
-			   possible_directions.at(game().logic_rand() % possible_directions.size());
-			game().send_player_ship_scouting_direction(
-			   *so.ship, static_cast<WalkingDir>(final_direction));
+			const Direction direction =
+			      possible_directions.at(game().logic_rand() % possible_directions.size());
+			game().send_player_ship_scouting_direction(*so.ship, static_cast<WalkingDir>(direction));
+
+			printf("EXPLORE- break free FOR SEA, dir=%u\n", direction);
 		}
 	}
 
@@ -495,3 +493,4 @@
 	so.waiting_for_command_ = false;
 	return;
 }
+

=== modified file 'src/logic/map_objects/tribes/ship.h'
--- src/logic/map_objects/tribes/ship.h	2016-11-03 07:20:57 +0000
+++ src/logic/map_objects/tribes/ship.h	2016-11-30 04:53:43 +0000
@@ -207,6 +207,11 @@
 		return expedition_->swimmable[dir - 1];
 	}
 
+	// whether the ship's expedition is in state "island-exploration" (circular movement)
+	bool is_island_circling () {
+		return expedition_->island_exploration;
+	}
+
 	/// \returns whether the expedition ship is close to the coast
 	bool exp_close_to_coast() const {
 		if (!expedition_)