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

[ypopezios]

See description of the branch:
https://code.launchpad.net/~widelands-dev/widelands/ship_scheduling_2

Get windows builds and ask for testing - do not review yet

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 3754. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/412020649.
Appveyor build 3554. State: failed. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ship_scheduling_2-3554.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 3758. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/412187264.
Appveyor build 3558. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ship_scheduling_2-3558.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 3855. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/422224908.
Appveyor build 3653. State: failed. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ship_scheduling_2-3653.

=== modified file 'src/economy/fleet.cc'
--- src/economy/fleet.cc	2018-04-07 16:59:00 +0000
+++ src/economy/fleet.cc	2018-08-29 19:19:29 +0000
@@ -628,8 +628,7 @@
 }
 
 /**
- * Act callback updates ship scheduling. All decisions about where transport ships
- * are supposed to go are made via this function.
+ * Act callback updates ship scheduling of idle ships.
  *
  * @note Do not call this directly; instead, trigger it via @ref update
  */
@@ -637,230 +636,178 @@
 	act_pending_ = false;
 
 	if (!active()) {
-		// If we are here, most likely act() was called by a port with waiting wares or an expedition
-		// ready
-		// although there are still no ships. We can't handle it now, so we reschedule the act()
-		schedule_act(game, 5000);  // retry in the next time
+		// If we are here, most likely act() was called by a port with waiting wares or
+		// with an expedition ready, although there are still no ships.
+		// We can't handle it now, so we reschedule the act()
+		schedule_act(game, kFleetInterval);  // retry in the next time
 		act_pending_ = true;
 		return;
 	}
 
 	molog("Fleet::act\n");
 
-	// we need to calculate what ship is to be send to which port
-	// for this we will have temporary data structure with format
-	// <<ship,port>,score>
-	// where ship and port are not objects but positions in ports_ and ships_
-	// this is to allow native hashing
-	std::map<std::pair<uint16_t, uint16_t>, uint16_t> scores;
-
-	// so we will identify all pairs: idle ship : ports, and score all such
-	// pairs. We consider
-	// - count of wares onboard, first ware (oldest) is counted as 8 (prioritization)
-	//   (counting wares for particular port only)
-	// - count wares waiting at the port/3
-	// - distance between ship and a port (0-10 points, the closer the more points)
-	// - is another ship heading there right now?
-
-	// at the end we must know if requrests of all ports asking for ship were addressed
-	// if any unsatisfied, we must schedule new run of this function
-	// when we send a ship there, the port is removed from list
-	std::list<uint16_t> waiting_ports;
-
-	// this is just helper - first member of scores map
-	std::pair<uint16_t, uint16_t> mapping;  // ship number, port number
-
-	// first we go over ships - idle ones (=without destination)
-	// then over wares on these ships and create first ship-port
-	// pairs with score
-	for (uint16_t s = 0; s < ships_.size(); s += 1) {
-		if (ships_[s]->get_destination(game)) {
-			continue;
-		}
-		if (ships_[s]->get_ship_state() != Ship::ShipStates::kTransport) {
-			continue;  // in expedition obviously
-		}
-
-		for (uint16_t i = 0; i < ships_[s]->get_nritems(); i += 1) {
-			PortDock* dst = ships_[s]->items_[i].get_destination(game);
-			if (!dst) {
-				// if wares without destination on ship without destination
-				// such ship can be send to any port, and should be sent
-				// to some port, so we add 1 point to score for each port
-				for (uint16_t p = 0; p < ports_.size(); p += 1) {
-					mapping.first = s;
-					mapping.second = p;
-					scores[mapping] += 1;
-				}
-				continue;
-			}
-
-			bool destination_found = false;  // Just a functional check
-			for (uint16_t p = 0; p < ports_.size(); p += 1) {
-				if (ports_[p] == ships_[s]->items_[i].get_destination(game)) {
-					mapping.first = s;
-					mapping.second = p;
-					scores[mapping] += (i == 0) ? 8 : 1;
-					destination_found = true;
-				}
-			}
-			if (!destination_found) {
-				// Perhaps the throw here is too strong
-				// we can still remove it before stable release if it proves too much
-				// during my testing this situation never happened
-				throw wexception("A ware with destination that does not match any of player's"
-				                 " ports, ship %u, ware's destination: %u",
-				                 ships_[s]->serial(),
-				                 ships_[s]->items_[i].get_destination(game)->serial());
-			}
-		}
-	}
-
-	// now opposite aproach - we go over ports to find out those that have wares
-	// waiting for ship then find candidate ships to satisfy the requests
-	for (uint16_t p = 0; p < ports_.size(); p += 1) {
-		PortDock& pd = *ports_[p];
-		if (!pd.get_need_ship()) {
-			continue;
-		}
-
-		// general stategy is "one ship for port is enough", but sometimes
-		// amount of ware waiting for ship is too high
-		if (count_ships_heading_here(game, &pd) * 25 > pd.count_waiting()) {
-			continue;
-		}
-
-		waiting_ports.push_back(p);
-
-		// scoring and entering the pair into scores (or increasing existing
-		// score if the pair is already there)
-		for (uint16_t s = 0; s < ships_.size(); s += 1) {
-
-			if (ships_[s]->get_destination(game)) {
-				continue;  // already has destination
-			}
-
-			if (ships_[s]->get_ship_state() != Ship::ShipStates::kTransport) {
-				continue;  // in expedition obviously
-			}
-
-			mapping.first = s;
-			mapping.second = p;
-			// following aproximately considers free capacity of a ship
-			scores[mapping] += ((ships_[s]->get_nritems() > 15) ? 1 : 3) +
-			                   std::min(ships_[s]->descr().get_capacity() - ships_[s]->get_nritems(),
-			                            ports_[p]->count_waiting()) /
-			                      3;
-		}
-	}
-
-	// Now adding score for distance
-	for (auto ship_port_relation : scores) {
+	// For each waiting port, try to find idle ships and send to it the closest one.
+	uint16_t waiting_ports = ports_.size();
+	for (PortDock* p : ports_) {
+		if (p->get_need_ship() == 0) {
+			--waiting_ports;
+			continue;
+		}
+
+		Ship* closest_ship = nullptr;
+		float shortest_dist = 10000;
+		bool waiting = true;
+
+		for (Ship* s : ships_) {
+			if (s->get_destination(game)) {
+				if (s->get_destination(game) == p) {
+					waiting = false;
+					--waiting_ports;
+					break;
+				}
+				continue; // has already destination
+			}
+			if (s->get_ship_state() != Ship::ShipStates::kTransport) {
+				continue; // in expedition obviously
+			}
+
+			// here we get distance ship->port
+			int16_t route_length = 10000;
+
+			PortDock* cur_port = get_dock(game, s->get_position());
+			if (cur_port) { // we are in a port
+				if (cur_port == p) { // same port
+					route_length = 0;
+				} else { // different port
+					Path tmp_path;
+					if (get_path(*cur_port, *p, tmp_path)) { // try to use precalculated path
+						route_length = tmp_path.get_nsteps();
+					}
+				}
+			}
+
+			if (route_length == 10000) { // above failed, so we calculate path "manually"
+				// most probably the ship is not in a port (should not happen frequently)
+				route_length = s->calculate_sea_route(game, *p);
+			}
+
+			if (route_length < shortest_dist) {
+				shortest_dist = route_length;
+				closest_ship = s;
+			}
+		}
+
+		if (waiting && closest_ship) {
+			--waiting_ports;
+			closest_ship->set_destination(p);
+			closest_ship->send_signal(game, "wakeup");
+		}
+	}
+
+	if (waiting_ports > 0) {
+		molog("... there are %u ports requesting ship(s) we cannot satisfy yet\n", waiting_ports);
+		schedule_act(game, kFleetInterval);  // retry next time
+		act_pending_ = true;
+	}
+}
+
+/**
+ * For the given three consecutive ports, decide if their path is favourable or not.
+ * \return true/false for yes/no
+ */
+bool Fleet::is_path_favourable(PortDock& start, PortDock& middle, PortDock& finish) {
+	if (&middle != &finish) {
+		Path path_start_to_finish;
+		Path path_middle_to_finish;
+
+		assert(get_path(start, finish, path_start_to_finish));
+		if (get_path(middle, finish, path_middle_to_finish)) {
+			if (path_middle_to_finish.get_nsteps() > path_start_to_finish.get_nsteps()) {
+				return false;
+			}
+		}
+	}
+	return true; // default
+}
+
+/**
+ * For the given ship, go through all ports of this fleet
+ * and find the one with the best score.
+ * \return that port
+ *
+ * @note cur_port is never nullptr (we are always in a port),
+ * but that is kept in case the design changes in the future
+ */
+PortDock* Fleet::find_next_dest(Game& game, Ship& ship, PortDock* const cur_port) {
+	// uint32_t const max_capacity = ship.descr().get_capacity();
+	PortDock* best_port = nullptr;
+	float best_score = 0;
+
+	for (PortDock* p : ports_) {
+		if (p == cur_port) {
+			continue; // same port
+		}
+
+		float score = 0;
+		WareInstance* ware;
+		Worker* worker;
+
+		// score for wares/workers onboard that ship for that port
+		for (uint16_t i = 0; i < ship.get_nritems(); ++i) {
+			ShippingItem& si = ship.items_[i];
+			if (si.get_destination(game) == p) {
+				si.get(game, &ware, &worker);
+				if (ware) {
+					score += 1; // TODO: increase by ware's importance
+				} else { // worker
+					score += 4;
+				}
+			}
+		}
+
+		if (cur_port) { // we are in a port
+			// score for wares/workers waiting at that port
+			for (uint16_t i = 0; i < cur_port->count_waiting(); ++i) {
+				ShippingItem& si = cur_port->waiting_[i];
+				if (si.get_destination(game) == p) {
+					si.get(game, &ware, &worker);
+					if (ware) {
+						score += 1; // TODO: increase by ware's importance
+					} else { // worker
+						score += 4;
+					}
+				}
+			}
+		}
+
+		if (score == 0 && p->get_need_ship() == 0) {
+			continue; // empty ship to empty port
+		}
 
 		// here we get distance ship->port
-		// possibilities are:
-		// - we are in port and it is the same as target port
-		// - we are in other port, then we use get_dock() function to fetch precalculated path
-		// - if above fails, we calculate path "manually"
 		int16_t route_length = -1;
 
-		PortDock* current_portdock =
-		   get_dock(game, ships_[ship_port_relation.first.first]->get_position());
-
-		if (current_portdock) {  // we try to use precalculated paths of game
-
-			// we are in the same portdock
-			if (current_portdock == ports_[ship_port_relation.first.second]) {
-				route_length = 0;
-			} else {  // it is different portdock then
-				Path tmp_path;
-				if (get_path(*current_portdock, *ports_[ship_port_relation.first.second], tmp_path)) {
-					route_length = tmp_path.get_nsteps();
-				}
-			}
-		}
-
-		// most probably the ship is not in a portdock (should not happen frequently)
-		if (route_length == -1) {
-			route_length = ships_[ship_port_relation.first.first]->calculate_sea_route(
-			   game, *ports_[ship_port_relation.first.second]);
-		}
-
-		// now we have length of route, so we need to calculate score
-		int16_t score_for_distance = 0;
-		if (route_length < 3) {
-			score_for_distance = 10;
-		} else {
-			score_for_distance = 8 - route_length / 50;
-		}
-		// must not be negative
-		score_for_distance = (score_for_distance < 0) ? 0 : score_for_distance;
-
-		scores[ship_port_relation.first] += score_for_distance;
-	}
-
-	// looking for best scores and sending ships accordingly
-	uint16_t best_ship = 0;
-	uint16_t best_port = 0;
-
-	// after sending a ship we will remove one or more items from scores
-	while (!scores.empty()) {
-		uint16_t best_score = 0;
-
-		// searching for combination with highest score
-		for (const auto& combination : scores) {
-			if (combination.second > best_score) {
-				best_score = combination.second;
-				best_ship = combination.first.first;
-				best_port = combination.first.second;
-			}
-		}
-		if (best_score == 0) {
-			// this is check of correctnes of this algorithm, this should not happen
-			throw wexception("Fleet::act(): No port-destination pair selected or its score is zero");
-		}
-
-		// making sure the winner has no destination set
-		assert(!ships_[best_ship]->get_destination(game));
-
-		// now actual setting destination for "best ship"
-		ships_[best_ship]->set_destination(game, *ports_[best_port]);
-		molog("... ship %u sent to port %u, wares onboard: %2d, the port is asking for a ship: %s\n",
-		      ships_[best_ship]->serial(), ports_[best_port]->serial(),
-		      ships_[best_ship]->get_nritems(), (ports_[best_port]->get_need_ship()) ? "yes" : "no");
-
-		// pruning the scores table
-		// the ship that was just sent somewhere cannot be send elsewhere :)
-		for (auto it = scores.cbegin(); it != scores.cend();) {
-
-			// decreasing score for target port as there was a ship just sent there
-			if (it->first.second == best_port) {
-				mapping.first = it->first.first;
-				mapping.second = it->first.second;
-				scores[mapping] /= 2;
-				// just make sure it is nonzero
-				scores[mapping] = (scores[mapping] == 0) ? 1 : scores[mapping];
-			}
-
-			// but removing all pairs where best ship is participating as it is not available anymore
-			// (because it was sent to "best port")
-			if (it->first.first == best_ship) {
-				scores.erase(it++);
-			} else {
-				++it;
-			}
-		}
-
-		// also removing the port from waiting_ports
-		waiting_ports.remove(best_port);
-	}
-
-	if (!waiting_ports.empty()) {
-		molog("... there are %" PRIuS " ports requesting ship(s) we cannot satisfy yet\n",
-		      waiting_ports.size());
-		schedule_act(game, 5000);  // retry next time
-		act_pending_ = true;
-	}
+		if (cur_port) { // we are in a port
+			Path tmp_path;
+			if (get_path(*cur_port, *p, tmp_path)) { // try to use precalculated path
+				route_length = tmp_path.get_nsteps();
+			}
+		}
+
+		if (route_length == -1) { // above failed, so we calculate path "manually"
+			// most probably the ship is not in a port (should not happen frequently)
+			route_length = ship.calculate_sea_route(game, *p);
+		}
+
+		score = (score + 1) * (score + p->get_need_ship());
+		score = score * (1 - route_length / (score + route_length));
+		if (score > best_score) {
+			best_score = score;
+			best_port = p;
+		}
+	}
+
+	return best_port;
 }
 
 void Fleet::log_general_info(const EditorGameBase& egbase) {

=== modified file 'src/economy/fleet.h'
--- src/economy/fleet.h	2018-04-16 07:03:12 +0000
+++ src/economy/fleet.h	2018-08-29 19:19:29 +0000
@@ -46,6 +46,8 @@
 	DISALLOW_COPY_AND_ASSIGN(FleetDescr);
 };
 
+constexpr int32_t kFleetInterval = 5000;
+
 /**
  * Manage all ships and ports of a player that are connected
  * by ocean.
@@ -152,6 +154,8 @@
 	void save(EditorGameBase&, MapObjectSaver&, FileWrite&) override;
 
 	static MapObject::Loader* load(EditorGameBase&, MapObjectLoader&, FileRead&);
+	bool is_path_favourable(PortDock& start, PortDock& middle, PortDock& finish);
+	PortDock* find_next_dest(Game&, Ship&, PortDock* const cur_port);
 };
 
 }  // namespace Widelands

=== modified file 'src/economy/portdock.cc'
--- src/economy/portdock.cc	2018-04-16 07:03:12 +0000
+++ src/economy/portdock.cc	2018-08-29 19:19:29 +0000
@@ -34,6 +34,7 @@
 #include "logic/game_data_error.h"
 #include "logic/map_objects/tribes/ship.h"
 #include "logic/map_objects/tribes/warehouse.h"
+#include "logic/path.h"
 #include "logic/player.h"
 #include "logic/widelands_geometry_io.h"
 #include "map_io/map_object_loader.h"
@@ -55,7 +56,7 @@
    : PlayerImmovable(g_portdock_descr),
      fleet_(nullptr),
      warehouse_(wh),
-     need_ship_(false),
+     ships_coming_(0),
      expedition_ready_(false) {
 }
 
@@ -116,6 +117,10 @@
 	return nullptr;
 }
 
+uint32_t PortDock::get_need_ship() const {
+	return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_ + 1);
+}
+
 /**
  * Signal to the dock that it now belongs to the given economy.
  *
@@ -289,36 +294,58 @@
 
 	// Destination might have vanished or be in another economy altogether.
 	if (dst && dst->get_economy() == get_economy()) {
-		set_need_ship(game, true);
+		if (ships_coming_ <= 0) {
+			set_need_ship(game, true);
+		}
 	} else {
 		it->set_location(game, warehouse_);
 		it->end_shipping(game);
 		*it = waiting_.back();
 		waiting_.pop_back();
-
-		if (waiting_.empty())
-			set_need_ship(game, false);
-	}
-}
-
-/**
- * A ship has arrived at the dock. Clear all items designated for this dock,
- * and load the ship.
+	}
+}
+
+/**
+ * Receive shipping item from unloading ship.
+ * Called by ship code.
+ */
+void PortDock::shipping_item_arrived(Game& game, ShippingItem& si) {
+	si.set_location(game, warehouse_);
+	si.end_shipping(game);
+}
+
+/**
+ * Receive shipping item from departing ship.
+ * Called by ship code.
+ */
+void PortDock::shipping_item_returned(Game& game, ShippingItem& si) {
+	si.set_location(game, this);
+	waiting_.push_back(si);
+}
+
+/**
+ * A ship changed destination and is now coming at the dock. Increase counter for need_ship.
+ */
+void PortDock::ship_coming(bool affirmative) {
+	if (affirmative) {
+		++ships_coming_;
+	} else {
+		ships_coming_ = std::max(0, ships_coming_ - 1); // max used for compatibility with old savegames
+	}
+}
+
+/**
+ * A ship has arrived at the dock. Set its next destination and load it accordingly.
  */
 void PortDock::ship_arrived(Game& game, Ship& ship) {
-	std::vector<ShippingItem> items_brought_by_ship;
-	ship.withdraw_items(game, *this, items_brought_by_ship);
-
-	for (ShippingItem& shipping_item : items_brought_by_ship) {
-		shipping_item.set_location(game, warehouse_);
-		shipping_item.end_shipping(game);
-	}
+	ship_coming(false);
 
 	if (expedition_ready_) {
 		assert(expedition_bootstrap_ != nullptr);
 
 		// Only use an empty ship.
 		if (ship.get_nritems() < 1) {
+			ship.set_destination(nullptr);
 			// Load the ship
 			std::vector<Worker*> workers;
 			std::vector<WareInstance*> wares;
@@ -337,46 +364,73 @@
 			// The expedition goods are now on the ship, so from now on it is independent from the port
 			// and thus we switch the port to normal, so we could even start a new expedition,
 			cancel_expedition(game);
-			return fleet_->update(game);
-		}
-	}
-
-	if (ship.get_nritems() < ship.descr().get_capacity() && !waiting_.empty()) {
-		uint32_t nrload =
-		   std::min<uint32_t>(waiting_.size(), ship.descr().get_capacity() - ship.get_nritems());
-
-		while (nrload--) {
-			// Check if the item has still a valid destination
-			if (waiting_.back().get_destination(game)) {
-				// Destination is valid, so we load the item onto the ship
-				ship.add_item(game, waiting_.back());
-			} else {
-				// The item has no valid destination anymore, so we just carry it
-				// back in the warehouse
-				waiting_.back().set_location(game, warehouse_);
-				waiting_.back().end_shipping(game);
-			}
-			waiting_.pop_back();
-		}
-
-		if (waiting_.empty()) {
-			set_need_ship(game, false);
-		}
-	}
-
-	fleet_->update(game);
+			fleet_->update(game);
+			return;
+		}
+	}
+
+	// decide where the arrived ship will go next
+	PortDock* next_port = fleet_->find_next_dest(game, ship, this);
+	if (!next_port) {
+		ship.set_destination(next_port);
+		return; // no need to load anything
+	}
+
+	// unload any wares/workers onboard the departing ship which are not favored by next dest
+	ship.unload_unfit_items(game, *this, *next_port);
+
+	// then load the remaining capacity of the departing ship with relevant items
+	uint32_t rest_capacity = ship.descr().get_capacity() - ship.get_nritems();
+
+	// firstly load the items which go to chosen dest, while also checking for items with invalid dest
+	uint32_t dst = 0;
+	for (ShippingItem& si : waiting_) {
+		PortDock* itemdest = si.get_destination(game);
+		if (itemdest) { // valid dest
+			if (rest_capacity == 0) {
+				waiting_[dst++] = si; // keep the item here
+			} else {
+				if (itemdest == next_port) { // the item goes to chosen dest
+					ship.add_item(game, si); // load it
+					--rest_capacity;
+				} else { // different dest
+					waiting_[dst++] = si; // keep it here for now
+				}
+			}
+		} else { // invalid dest
+			// carry the item back in the warehouse
+			si.set_location(game, warehouse_);
+			si.end_shipping(game);
+		}
+	}
+	waiting_.resize(dst);
+
+	if (rest_capacity > 0) { // there is still capacity
+		// load any items favored by the chosen dest
+		dst = 0;
+		for (ShippingItem& si : waiting_) {
+			if (rest_capacity == 0) {
+				waiting_[dst++] = si; // keep the item here
+			} else {
+				if (fleet_->is_path_favourable(*this, *next_port, *si.get_destination(game))) {
+					ship.add_item(game, si);
+					--rest_capacity;
+				} else { // item is not favored by the chosen dest
+					// spare it from getting trapped inside the wrong ship
+					waiting_[dst++] = si;
+				}
+			}
+		}
+		waiting_.resize(dst);
+	}
+	ship.set_destination(next_port);
+
+	set_need_ship(game, !waiting_.empty());
 }
 
 void PortDock::set_need_ship(Game& game, bool need) {
-	molog("set_need_ship(%s)\n", need ? "true" : "false");
-
-	if (need == need_ship_)
-		return;
-
-	need_ship_ = need;
-
-	if (fleet_) {
-		molog("... trigger fleet update\n");
+	if (need && fleet_) {
+		molog("trigger fleet update\n");
 		fleet_->update(game);
 	}
 }
@@ -445,13 +499,13 @@
 
 	if (warehouse_) {
 		Coords pos(warehouse_->get_position());
-		molog("PortDock for warehouse %u (at %i,%i) in fleet %u, need_ship: %s, waiting: %" PRIuS
+		molog("PortDock for warehouse %u (at %i,%i) in fleet %u, expedition_ready: %s, waiting: %" PRIuS
 		      "\n",
 		      warehouse_->serial(), pos.x, pos.y, fleet_ ? fleet_->serial() : 0,
-		      need_ship_ ? "true" : "false", waiting_.size());
+		      expedition_ready_ ? "true" : "false", waiting_.size());
 	} else {
-		molog("PortDock without a warehouse in fleet %u, need_ship: %s, waiting: %" PRIuS "\n",
-		      fleet_ ? fleet_->serial() : 0, need_ship_ ? "true" : "false", waiting_.size());
+		molog("PortDock without a warehouse in fleet %u, expedition_ready: %s, waiting: %" PRIuS "\n",
+		      fleet_ ? fleet_->serial() : 0, expedition_ready_ ? "true" : "false", waiting_.size());
 	}
 
 	for (ShippingItem& shipping_item : waiting_) {
@@ -479,7 +533,7 @@
 		pd.set_position(egbase(), pd.dockpoints_[i]);
 	}
 
-	pd.need_ship_ = fr.unsigned_8();
+	pd.ships_coming_ = fr.unsigned_8();
 
 	waiting_.resize(fr.unsigned_32());
 	for (ShippingItem::Loader& shipping_loader : waiting_) {
@@ -553,7 +607,7 @@
 		write_coords_32(&fw, coords);
 	}
 
-	fw.unsigned_8(need_ship_);
+	fw.unsigned_8(ships_coming_);
 
 	fw.unsigned_32(waiting_.size());
 	for (ShippingItem& shipping_item : waiting_) {

=== modified file 'src/economy/portdock.h'
--- src/economy/portdock.h	2018-04-07 16:59:00 +0000
+++ src/economy/portdock.h	2018-08-29 19:19:29 +0000
@@ -85,9 +85,7 @@
 		return fleet_;
 	}
 	PortDock* get_dock(Flag& flag) const;
-	bool get_need_ship() const {
-		return need_ship_ || expedition_ready_;
-	}
+	uint32_t get_need_ship() const;
 
 	void set_economy(Economy*) override;
 
@@ -113,6 +111,9 @@
 	void add_shippingitem(Game&, Worker&);
 	void update_shippingitem(Game&, Worker&);
 
+	void shipping_item_arrived(Game&, ShippingItem&);
+	void shipping_item_returned(Game&, ShippingItem&);
+	void ship_coming(bool affirmative);
 	void ship_arrived(Game&, Ship&);
 
 	void log_general_info(const EditorGameBase&) override;
@@ -146,7 +147,7 @@
 	Warehouse* warehouse_;
 	PositionList dockpoints_;
 	std::vector<ShippingItem> waiting_;
-	bool need_ship_;
+	uint8_t ships_coming_;
 	bool expedition_ready_;
 
 	std::unique_ptr<ExpeditionBootstrap> expedition_bootstrap_;

=== modified file 'src/logic/map_objects/tribes/ship.cc'
--- src/logic/map_objects/tribes/ship.cc	2018-07-08 15:16:16 +0000
+++ src/logic/map_objects/tribes/ship.cc	2018-08-29 19:19:29 +0000
@@ -303,12 +303,22 @@
 
 	FCoords position = map.get_fcoords(get_position());
 	if (position.field->get_immovable() == dst) {
-		molog("ship_update: Arrived at dock %u\n", dst->serial());
-		lastdock_ = dst;
-		destination_ = nullptr;
-		dst->ship_arrived(game, *this);
-		start_task_idle(game, descr().main_animation(), 250);
-		Notifications::publish(NoteShip(this, NoteShip::Action::kDestinationChanged));
+		if (lastdock_ != dst) {
+			molog("ship_update: Arrived at dock %u\n", dst->serial());
+			lastdock_ = dst;
+		}
+		if (withdraw_items(game, *dst)) {
+			schedule_act(game, kShipInterval);
+			return true;
+		}
+
+		dst->ship_arrived(game, *this); // this should call set_destination
+		dst = get_destination(game);
+		if (dst) {
+			start_task_movetodock(game, *dst);
+		} else {
+			start_task_idle(game, descr().main_animation(), 250);
+		}
 		return true;
 	}
 
@@ -484,7 +494,7 @@
 			}
 
 			if (totalprob == 0) {
-				start_task_idle(game, descr().main_animation(), 1500);
+				start_task_idle(game, descr().main_animation(), kShipInterval);
 				return;
 			}
 
@@ -496,13 +506,13 @@
 			}
 
 			if (dir == 0 || dir > LAST_DIRECTION) {
-				start_task_idle(game, descr().main_animation(), 1500);
+				start_task_idle(game, descr().main_animation(), kShipInterval);
 				return;
 			}
 
 			FCoords neighbour = map.get_neighbour(position, dir);
 			if (!(neighbour.field->nodecaps() & MOVECAPS_SWIM)) {
-				start_task_idle(game, descr().main_animation(), 1500);
+				start_task_idle(game, descr().main_animation(), kShipInterval);
 				return;
 			}
 
@@ -542,7 +552,7 @@
 						             pgettext("ship", "Waiting"), _("Island Circumnavigated"),
 						             _("An expedition ship sailed around its island without any events."),
 						             "images/wui/ship/ship_explore_island_cw.png");
-						return start_task_idle(game, descr().main_animation(), 1500);
+						return start_task_idle(game, descr().main_animation(), kShipInterval);
 					}
 				}
 				// The ship is supposed to follow the coast as close as possible, therefore the check
@@ -585,7 +595,7 @@
 				    shipname_.c_str());
 				set_ship_state_and_notify(
 				   ShipStates::kExpeditionWaiting, NoteShip::Action::kWaitingForCommand);
-				start_task_idle(game, descr().main_animation(), 1500);
+				start_task_idle(game, descr().main_animation(), kShipInterval);
 				return;
 			}
 		} else {  // scouting towards a specific direction
@@ -598,7 +608,7 @@
 			// coast reached
 			set_ship_state_and_notify(
 			   ShipStates::kExpeditionWaiting, NoteShip::Action::kWaitingForCommand);
-			start_task_idle(game, descr().main_animation(), 1500);
+			start_task_idle(game, descr().main_animation(), kShipInterval);
 			// Send a message to the player, that a new coast was reached
 			send_message(game,
 			             /** TRANSLATORS: A ship has discovered land */
@@ -692,7 +702,7 @@
 			}
 
 			expedition_.reset(nullptr);
-			return start_task_idle(game, descr().main_animation(), 1500);
+			return start_task_idle(game, descr().main_animation(), kShipInterval);
 		}
 	}
 		FALLS_THROUGH;
@@ -701,7 +711,7 @@
 	case ShipStates::kSinkRequest:
 	case ShipStates::kSinkAnimation: {
 		// wait for input
-		start_task_idle(game, descr().main_animation(), 1500);
+		start_task_idle(game, descr().main_animation(), kShipInterval);
 		return;
 	}
 	}
@@ -727,14 +737,17 @@
 
 /**
  * Enter a new destination port for the ship.
- *
- * @note This is supposed to be called only from the scheduling code of @ref Fleet.
+ * Call this after un/loading the ship, for proper logging.
  */
-void Ship::set_destination(Game& game, PortDock& pd) {
-	molog("set_destination / sending to portdock %u (carrying %" PRIuS " items)\n", pd.serial(),
-	      items_.size());
-	destination_ = &pd;
-	send_signal(game, "wakeup");
+void Ship::set_destination(PortDock* pd) {
+	destination_ = pd;
+	if (pd) {
+		molog("set_destination / sending to portdock %u (carrying %" PRIuS " items)\n", pd->serial(),
+			  items_.size());
+		pd->ship_coming(true);
+	} else {
+		molog("set_destination / none\n");
+	}
 	Notifications::publish(NoteShip(this, NoteShip::Action::kDestinationChanged));
 }
 
@@ -745,14 +758,40 @@
 	items_.back().set_location(game, this);
 }
 
-void Ship::withdraw_items(Game& game, PortDock& pd, std::vector<ShippingItem>& items) {
-	uint32_t dst = 0;
-	for (uint32_t src = 0; src < items_.size(); ++src) {
-		PortDock* destination = items_[src].get_destination(game);
-		if (!destination || destination == &pd) {
-			items.push_back(items_[src]);
+/**
+ * Unload one item designated for given dock or for no dock.
+ * \return true if item unloaded.
+ */
+bool Ship::withdraw_items(Game& game, PortDock& pd) {
+	bool unloaded = false;
+	uint32_t dst = 0;
+	for (ShippingItem& si : items_) {
+		if (!unloaded) {
+			PortDock* itemdest = si.get_destination(game);
+			if (!itemdest || itemdest == &pd) {
+				pd.shipping_item_arrived(game, si);
+				unloaded = true;
+				continue;
+			}
+		}
+
+		items_[dst++] = si;
+	}
+	items_.resize(dst);
+	return unloaded;
+}
+
+/**
+ * Unload all items not favored by given next dest.
+ * Assert all items for current portdock have already been unloaded.
+ */
+void Ship::unload_unfit_items(Game& game, PortDock& here, PortDock& nextdest) {
+	uint32_t dst = 0;
+	for (ShippingItem& si : items_) {
+		if (fleet_->is_path_favourable(here, nextdest, *si.get_destination(game))) {
+			items_[dst++] = si;
 		} else {
-			items_[dst++] = items_[src];
+			here.shipping_item_returned(game, si);
 		}
 	}
 	items_.resize(dst);
@@ -811,7 +850,7 @@
 		// I (tiborb) failed to invoke this situation when testing so
 		// I am not sure if following line behaves allright
 		get_fleet()->update(game);
-		start_task_idle(game, descr().main_animation(), 5000);
+		start_task_idle(game, descr().main_animation(), kFleetInterval);
 	}
 }
 
@@ -969,8 +1008,12 @@
 /// @note only called via player command
 void Ship::sink_ship(Game& game) {
 	// Running colonization has the highest priority + a sink request is only valid once
-	if (!state_is_sinkable())
+	if (!state_is_sinkable()) {
 		return;
+	}
+	if (destination_.is_set()) {
+		destination_.get(game)->ship_coming(false);
+	}
 	ship_state_ = ShipStates::kSinkRequest;
 	// Make sure the ship is active and close possible open windows
 	ship_wakeup(game);

=== modified file 'src/logic/map_objects/tribes/ship.h'
--- src/logic/map_objects/tribes/ship.h	2018-07-12 05:44:15 +0000
+++ src/logic/map_objects/tribes/ship.h	2018-08-29 19:19:29 +0000
@@ -78,6 +78,8 @@
 	DISALLOW_COPY_AND_ASSIGN(ShipDescr);
 };
 
+constexpr int32_t kShipInterval = 1500;
+
 /**
  * Ships belong to a player and to an economy. The usually are in a (unique)
  * fleet for a player, but only if they are on standard duty. Exploration ships
@@ -104,7 +106,7 @@
 		return economy_;
 	}
 	void set_economy(Game&, Economy* e);
-	void set_destination(Game&, PortDock&);
+	void set_destination(PortDock*);
 
 	void init_auto_task(Game&) override;
 
@@ -126,8 +128,9 @@
 		return items_[idx];
 	}
 
-	void withdraw_items(Game& game, PortDock& pd, std::vector<ShippingItem>& items);
-	void add_item(Game&, const ShippingItem& item);
+	void add_item(Game&, const ShippingItem&);
+	bool withdraw_items(Game&, PortDock&);
+	void unload_unfit_items(Game&, PortDock& here, PortDock& nextdest);
 
 	// A ship with task expedition can be in four states: kExpeditionWaiting, kExpeditionScouting,
 	// kExpeditionPortspaceFound or kExpeditionColonizing in the first states, the owning player of