widelands-dev team mailing list archive

[ypopezios <ypopezios@xxxxxxxx>]

ypopezios has proposed merging lp:~widelands-dev/widelands/ship_scheduling_2 into lp:widelands.

Commit message:
Improved ware/worker routing algorithm for ships and portdocks.

Requested reviews:
  GunChleoc (gunchleoc)

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

See description of the branch:
https://code.launchpad.net/~widelands-dev/widelands/ship_scheduling_2
-- 
Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/ship_scheduling_2.

=== modified file 'src/economy/fleet.cc'
--- src/economy/fleet.cc	2018-09-05 06:42:21 +0000
+++ src/economy/fleet.cc	2018-09-21 19:46:09 +0000
@@ -300,7 +300,7 @@
  *
  * @return true if successful, or false if the docks are not actually part of the fleet.
  */
-bool Fleet::get_path(PortDock& start, PortDock& end, Path& path) {
+bool Fleet::get_path(const PortDock& start, const PortDock& end, Path& path) {
 	uint32_t startidx = std::find(ports_.begin(), ports_.end(), &start) - ports_.begin();
 	uint32_t endidx = std::find(ports_.begin(), ports_.end(), &end) - ports_.begin();
 
@@ -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,207 @@
 	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) {
-
-		// 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
+	// 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;
+		uint32_t shortest_dist = kRouteNotCalculated;
+		bool waiting = true;
+
+		for (Ship* s : ships_) {
+			if (s->get_destination(game)) {
+				if (s->get_destination(game) == p) {
+					waiting = false;
+					--waiting_ports;
+					break;
+				}
+				continue; // The ship already has a destination
+			}
+			if (s->get_ship_state() != Ship::ShipStates::kTransport) {
+				continue; // Ship is not available, e.g. in expedition
+			}
+
+			// Here we get distance ship->port
+			uint32_t route_length = kRouteNotCalculated;
+
+			// Get precalculated distance for ships available at ports
+			{
+				PortDock* cur_port = get_dock(game, s->get_position());
+				if (cur_port) { // Ship is at a port
+					if (cur_port == p) { // Same port
+						route_length = 0;
+					} else { // Different port
+						Path precalculated_path;
+						if (get_path(*cur_port, *p, precalculated_path)) {
+							route_length = precalculated_path.get_nsteps();
+						}
+					}
+				}
+			}
+
+			// Get distance for ships available but not at a port (should not happen frequently)
+			if (route_length == kRouteNotCalculated) {
+				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;
 	}
+
+	// Deal with edge-case of losing destination before reaching it
+	for (Ship* s : ships_) {
+		if (s->get_destination(game)) {
+			continue; // The ship has a destination
+		}
+		if (s->get_ship_state() != Ship::ShipStates::kTransport) {
+			continue; // Ship is not available, e.g. in expedition
+		}
+		if (s->items_.empty()) {
+			continue; // No pending wares/workers
+		}
+
+		// Send ship to the closest port
+		PortDock* closest_port = nullptr;
+		uint32_t shortest_dist = kRouteNotCalculated;
+
+		for (PortDock* p : ports_) {
+			uint32_t route_length = s->calculate_sea_route(game, *p);
+			if (route_length < shortest_dist) {
+				shortest_dist = route_length;
+				closest_port = p;
+			}
+		}
+
+		if (closest_port) {
+			s->set_destination(closest_port);
+			s->send_signal(game, "wakeup");
+		}
+	}
+}
+
+/**
+ * For the given three consecutive ports, decide if their path is favourable or not.
+ * \return true if the path from start to finish >= the path from middle to finish
+ */
+bool Fleet::is_path_favourable(const PortDock& start, const PortDock& middle, const PortDock& finish) {
+	if (&middle != &finish) {
+		Path path_start_to_finish;
+		Path path_middle_to_finish;
+#ifndef NDEBUG
+		assert(get_path(start, finish, path_start_to_finish));
+#else
+		get_path(start, finish, path_start_to_finish);
+#endif
+		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
+ */
+PortDock* Fleet::find_next_dest(Game& game, const Ship& ship, const PortDock& from_port) {
+	PortDock* best_port = nullptr;
+	float best_score = 0.0f;
+
+	for (PortDock* p : ports_) {
+		if (p == &from_port) {
+			continue; // same port
+		}
+
+		float score = 0.0f;
+		WareInstance* ware;
+		Worker* worker;
+
+		// Score for wares/workers onboard that ship for that port
+		for (const ShippingItem& si : ship.items_) {
+			if (si.get_destination(game) == p) {
+				si.get(game, &ware, &worker);
+				if (ware) {
+					score += 1; // TODO(ypopezios): increase by ware's importance
+				} else { // worker
+					score += 4;
+				}
+			}
+		}
+
+		// Score for wares/workers waiting at that port
+		for (const ShippingItem& si : from_port.waiting_) {
+			if (si.get_destination(game) == p) {
+				si.get(game, &ware, &worker);
+				if (ware) {
+					score += 1; // TODO(ypopezios): increase by ware's importance
+				} else { // worker
+					score += 4;
+				}
+			}
+		}
+
+		if (score == 0.0f && p->get_need_ship() == 0) {
+			continue; // empty ship to empty port
+		}
+
+		// Here we get distance ship->port
+		uint32_t route_length = kRouteNotCalculated;
+
+		// Get precalculated distance if the ship is at a port
+		{
+			Path precalculated_path;
+			if (get_path(from_port, *p, precalculated_path)) { // try to use precalculated path
+				route_length = precalculated_path.get_nsteps();
+			}
+		}
+
+		// Get distance for when the ship is not at a port (should not happen frequently)
+		if (route_length == kRouteNotCalculated) {
+			route_length = ship.calculate_sea_route(game, *p);
+		}
+
+		score = (score + 1.0f) * (score + p->get_need_ship());
+		score = score * (1.0f - 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) const {

=== modified file 'src/economy/fleet.h'
--- src/economy/fleet.h	2018-09-04 15:48:47 +0000
+++ src/economy/fleet.h	2018-09-21 19:46:09 +0000
@@ -46,6 +46,9 @@
 	DISALLOW_COPY_AND_ASSIGN(FleetDescr);
 };
 
+constexpr int32_t kFleetInterval = 5000;
+constexpr uint32_t kRouteNotCalculated = std::numeric_limits<uint32_t>::max();
+
 /**
  * Manage all ships and ports of a player that are connected
  * by ocean.
@@ -96,7 +99,7 @@
 
 	void log_general_info(const EditorGameBase&) const override;
 
-	bool get_path(PortDock& start, PortDock& end, Path& path);
+	bool get_path(const PortDock& start, const PortDock& end, Path& path);
 	void add_neighbours(PortDock& pd, std::vector<RoutingNodeNeighbour>& neighbours);
 
 	uint32_t count_ships() const;
@@ -152,6 +155,8 @@
 	void save(EditorGameBase&, MapObjectSaver&, FileWrite&) override;
 
 	static MapObject::Loader* load(EditorGameBase&, MapObjectLoader&, FileRead&);
+	bool is_path_favourable(const PortDock& start, const PortDock& middle, const PortDock& finish);
+	PortDock* find_next_dest(Game&, const Ship&, const PortDock& from_port);
 };
 
 }  // namespace Widelands

=== modified file 'src/economy/portdock.cc'
--- src/economy/portdock.cc	2018-09-04 15:48:47 +0000
+++ src/economy/portdock.cc	2018-09-21 19:46:09 +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.
  *
@@ -247,7 +252,7 @@
  * its route.
  */
 void PortDock::update_shippingitem(Game& game, WareInstance& ware) {
-	for (std::vector<ShippingItem>::iterator item_iter = waiting_.begin();
+	for (auto item_iter = waiting_.begin();
 	     item_iter != waiting_.end(); ++item_iter) {
 
 		if (item_iter->object_.serial() == ware.serial()) {
@@ -271,7 +276,7 @@
  * updated its route.
  */
 void PortDock::update_shippingitem(Game& game, Worker& worker) {
-	for (std::vector<ShippingItem>::iterator item_iter = waiting_.begin();
+	for (auto item_iter = waiting_.begin();
 	     item_iter != waiting_.end(); ++item_iter) {
 
 		if (item_iter->object_.serial() == worker.serial()) {
@@ -281,44 +286,66 @@
 	}
 }
 
-void PortDock::update_shippingitem(Game& game, std::vector<ShippingItem>::iterator it) {
+void PortDock::update_shippingitem(Game& game, std::list<ShippingItem>::iterator it) {
 	it->update_destination(game, *this);
 
-	PortDock* dst = it->get_destination(game);
+	const PortDock* dst = it->get_destination(game);
 	assert(dst != this);
 
 	// 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 to the dock. Increase counter for need_ship.
+ */
+void PortDock::ship_coming(bool affirmative) {
+	if (affirmative) {
+		++ships_coming_;
+	} else {
+		--ships_coming_;
+	}
+}
+
+/**
+ * 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,61 @@
 			// 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 remaining_capacity = ship.descr().get_capacity() - ship.get_nritems();
+
+	// Firstly load the items which go to chosen destination, while also checking for items with invalid destination
+	for (auto si_it = waiting_.begin(); si_it != waiting_.end(); ++si_it) {
+		const PortDock* itemdest = si_it->get_destination(game);
+		if (itemdest) {
+			// Valid destination. Only load the item if it matches the ship's destination and the ship still has room for it
+			if (remaining_capacity > 0 && itemdest == next_port) {
+				ship.add_item(game, *si_it); // load it
+				si_it = waiting_.erase(si_it);
+				--remaining_capacity;
+			}
+		} else {
+			// Invalid destination. Carry the item back into the warehouse
+			si_it->set_location(game, warehouse_);
+			si_it->end_shipping(game);
+			si_it = waiting_.erase(si_it);
+		}
+	}
+
+	if (remaining_capacity > 0) {
+		// There is still come capacity left. Load any items favored by the chosen destination on the ship.
+		for (auto si_it = waiting_.begin(); si_it != waiting_.end() && remaining_capacity > 0; ++si_it) {
+			assert(si_it->get_destination(game) != nullptr);
+			if (fleet_->is_path_favourable(*this, *next_port, *si_it->get_destination(game))) {
+				ship.add_item(game, *si_it);
+				si_it = waiting_.erase(si_it);
+				--remaining_capacity;
+			}
+		}
+	}
+
+	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 +487,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 (const ShippingItem& shipping_item : waiting_) {
@@ -460,12 +502,12 @@
 	}
 }
 
-constexpr uint8_t kCurrentPacketVersion = 3;
+constexpr uint8_t kCurrentPacketVersion = 4;
 
 PortDock::Loader::Loader() : warehouse_(0) {
 }
 
-void PortDock::Loader::load(FileRead& fr) {
+void PortDock::Loader::load(FileRead& fr, uint8_t packet_version) {
 	PlayerImmovable::Loader::load(fr);
 
 	PortDock& pd = get<PortDock>();
@@ -479,7 +521,18 @@
 		pd.set_position(egbase(), pd.dockpoints_[i]);
 	}
 
-	pd.need_ship_ = fr.unsigned_8();
+	pd.ships_coming_ = fr.unsigned_8();
+
+	// TODO(GunChleoc): Savegame compatibility Build 20
+	if (packet_version < 4) {
+		pd.ships_coming_ = 0;
+		for (const Serial ship_serial : pd.owner().ships()) {
+			Ship* ship = dynamic_cast<Ship*>(egbase().objects().get_object(ship_serial));
+			if (ship->get_destination(egbase())->serial() == pd.serial()) {
+				++pd.ships_coming_;
+			}
+		}
+	}
 
 	waiting_.resize(fr.unsigned_32());
 	for (ShippingItem::Loader& shipping_loader : waiting_) {
@@ -499,10 +552,10 @@
 	PortDock& pd = get<PortDock>();
 	pd.warehouse_ = &mol().get<Warehouse>(warehouse_);
 
-	pd.waiting_.resize(waiting_.size());
 	for (uint32_t i = 0; i < waiting_.size(); ++i) {
-		pd.waiting_[i] = waiting_[i].get(mol());
+		pd.waiting_.push_back(waiting_[i].get(mol()));
 	}
+	assert(pd.waiting_.size() == waiting_.size());
 }
 
 void PortDock::Loader::load_finish() {
@@ -527,10 +580,11 @@
 	try {
 		// The header has been peeled away by the caller
 
+		// TODO(GunChleoc): Savegame compatibility Build 20
 		uint8_t const packet_version = fr.unsigned_8();
-		if (packet_version == kCurrentPacketVersion) {
+		if (packet_version >= 3 && packet_version <= kCurrentPacketVersion) {
 			loader->init(egbase, mol, *new PortDock(nullptr));
-			loader->load(fr);
+			loader->load(fr, packet_version);
 		} else {
 			throw UnhandledVersionError("PortDock", packet_version, kCurrentPacketVersion);
 		}
@@ -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-09-04 15:48:47 +0000
+++ src/economy/portdock.h	2018-09-21 19:46:09 +0000
@@ -20,6 +20,7 @@
 #ifndef WL_ECONOMY_PORTDOCK_H
 #define WL_ECONOMY_PORTDOCK_H
 
+#include <list>
 #include <memory>
 
 #include "base/macros.h"
@@ -85,9 +86,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 +112,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&) const override;
@@ -139,14 +141,14 @@
 
 	void init_fleet(EditorGameBase& egbase);
 	void set_fleet(Fleet* fleet);
-	void update_shippingitem(Game&, std::vector<ShippingItem>::iterator);
+	void update_shippingitem(Game&, std::list<ShippingItem>::iterator);
 	void set_need_ship(Game&, bool need);
 
 	Fleet* fleet_;
 	Warehouse* warehouse_;
 	PositionList dockpoints_;
-	std::vector<ShippingItem> waiting_;
-	bool need_ship_;
+	std::list<ShippingItem> waiting_;
+	uint8_t ships_coming_;
 	bool expedition_ready_;
 
 	std::unique_ptr<ExpeditionBootstrap> expedition_bootstrap_;
@@ -157,7 +159,7 @@
 	public:
 		Loader();
 
-		void load(FileRead&);
+		void load(FileRead&, uint8_t packet_version);
 		void load_pointers() override;
 		void load_finish() override;
 

=== modified file 'src/economy/shippingitem.cc'
--- src/economy/shippingitem.cc	2018-04-07 16:59:00 +0000
+++ src/economy/shippingitem.cc	2018-09-21 19:46:09 +0000
@@ -105,7 +105,7 @@
 		worker->end_shipping(game);
 }
 
-PortDock* ShippingItem::get_destination(Game& game) {
+const PortDock* ShippingItem::get_destination(Game& game) const {
 	return destination_dock_.get(game);
 }
 

=== modified file 'src/economy/shippingitem.h'
--- src/economy/shippingitem.h	2018-04-07 16:59:00 +0000
+++ src/economy/shippingitem.h	2018-09-21 19:46:09 +0000
@@ -53,7 +53,7 @@
 	void get(const EditorGameBase& game, WareInstance** ware, Worker** worker) const;
 
 	void set_economy(Game&, Economy* e);
-	PortDock* get_destination(Game&);
+	const PortDock* get_destination(Game&) const;
 
 	void remove(EditorGameBase&);
 

=== modified file 'src/logic/map_objects/tribes/ship.cc'
--- src/logic/map_objects/tribes/ship.cc	2018-09-11 16:58:16 +0000
+++ src/logic/map_objects/tribes/ship.cc	2018-09-21 19:46:09 +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_item(game, *dst)) {
+			schedule_act(game, kShipInterval);
+			return true;
+		}
+
+		dst->ship_arrived(game, *this); // This will also set the 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,14 +702,14 @@
 			}
 
 			expedition_.reset(nullptr);
-			return start_task_idle(game, descr().main_animation(), 1500);
+			return start_task_idle(game, descr().main_animation(), kShipInterval);
 		}
 	}
 		FALLS_THROUGH;
 	case ShipStates::kExpeditionWaiting:
 	case ShipStates::kExpeditionPortspaceFound: {
 		// wait for input
-		start_task_idle(game, descr().main_animation(), 1500);
+		start_task_idle(game, descr().main_animation(), kShipInterval);
 		return;
 	}
 		FALLS_THROUGH;
@@ -729,14 +739,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));
 }
 
@@ -747,14 +760,39 @@
 	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_item(Game& game, PortDock& pd) {
+	bool unloaded = false;
+	size_t dst = 0;
+	for (ShippingItem& si : items_) {
+		if (!unloaded) {
+			const 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, const PortDock& nextdest) {
+	size_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);
@@ -813,7 +851,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);
 	}
 }
 
@@ -837,10 +875,10 @@
 
 	set_economy(game, expedition_->economy);
 
-	for (int i = items_.size() - 1; i >= 0; --i) {
+	for (const ShippingItem& si : items_) {
 		WareInstance* ware;
 		Worker* worker;
-		items_.at(i).get(game, &ware, &worker);
+		si.get(game, &ware, &worker);
 		if (worker) {
 			worker->reset_tasks(game);
 			worker->start_task_idle(game, 0, -1);
@@ -971,8 +1009,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-09-05 06:42:21 +0000
+++ src/logic/map_objects/tribes/ship.h	2018-09-21 19:46:09 +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_item(Game&, PortDock&);
+	void unload_unfit_items(Game&, PortDock& here, const 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