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

[ypopezios]

Improved ware/worker routing algorithm for ships and portdocks.

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

[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.

[ypopezios (ypopezios)]

AppVeyor seems broken. Otherwise, this branch is now mature and big enough. Not going to add anything more into it, so as to keep it easier for reviewers. If people test it, it can make it into build 20.

[hessenfarmer (stephan-lutz)]

Reason for appveyor not working anymore currently is that the glbinding package has been upgraded in the repo of MSYS from 2.1.4 to 3.0.2.1 which seems to have issues with our code now.

[GunChleoc (gunchleoc)]

I have pushed a commit with a code review and some small tweaks. Please have a look at the NOCOM comments.

Not tested yet.

[ypopezios (ypopezios)]

Added inline comments concerning the NOCOM comments.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 3961. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/428035209.
Appveyor build 3759. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ship_scheduling_2-3759.

[GunChleoc (gunchleoc)]

I had actually programmed a really nice endless loop with those iterators... all fixed now. I have also improved the savegame compatibility, so it's only calculated once during game loading.

Thanks for this great feature! :)

@bunnybot merge

review: Approve

[GunChleoc (gunchleoc)]

One of the tests in our test suite has an endless loop in it:

test/maps/ship_transportation.wmf/scripting/test_rip_ports_with_worker_in_transit.lua

This already happened with older versions of this branch, so I don't think that it's anything I did.

review: Needs Fixing

[bunnybot (widelandsofficial)]

Refusing to merge, since Travis is not green. Use @bunnybot merge force for merging anyways.

Travis build 3977. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/428723984.

[GunChleoc (gunchleoc)]

There are still failures in the test suite.

Instructions on how to run it manually:

https://wl.widelands.org/wiki/RegressionTests/#test-scenarios

[ypopezios (ypopezios)]

From what I understand, the test suite forces the removal of ports and ships without running clean-up code. That invalidates the state of transports and breaks the advanced logic. I'm not sure if it is worthy to change the logic, instead of changing the tests.

[GunChleoc (gunchleoc)]

This removal of ports and ships simulated actions that can be taken by a user, so yes, the new code needs to be able to deal with that. Users can sink ships and destroy ports. Ports can also be destroyed if the enemy conquers the territory.

[ypopezios (ypopezios)]

Are you sure that there is proper simulation of user-actions here? Cause I suspect that there is just a magical removal, without calling e.g. sinking function. Of course the code should cover cases of destruction, but how to do that if it is not properly called? The old code was checking every time every combination of everything, wasting resources. Do we really want to do things that way?

[GunChleoc (gunchleoc)]

Yes, the simulation should be correct. Calling the sink_ship function is calling the sink_ship function, and it doesn't matter if the caller is a Lua script or a UI button. Both will send off the same player command. If they don't, it's a bug.

And yes, we do want Widelands not to get into an undefined state when a user performs an action, even if it's sinking a ship or destroying a port. We allow those user actions, so they need to be supported.

I have been thinking about this some more, changes in the test suite should be OK in the following 2 cases:

1. The new algorithm needs a bit more time to get back into a well-defined state than the old algorithm. In this case, add a sleep statement to the test suite.

2. The new algorithm gets back into a well-defined state which is different from the well-defined state that the old algorithm used to have. Change the asserts to reflect the new well-defined state.

In all other cases, the new algorithm needs fixing.

[ypopezios (ypopezios)]

This is not perfect, but should be enough for this branch.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4079. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/435223747.
Appveyor build 3875. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ship_scheduling_2-3875.

[ypopezios (ypopezios)]

Concerning the specific TODO, the code for invalid destinations pre-existed my involvement and is suspicious enough. I just moved it earlier in the function, in order to catch more cases. I don't know which are those cases (they don't happen in any part of the code that I touched), only that some of them appear when loading a savegame. I'm not familiar with that part of the codebase, so maybe this TODO is not for me.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4094. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/437518591.
Appveyor build 3890. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_ship_scheduling_2-3890.

[GunChleoc (gunchleoc)]

The TODOs get tagged with the person who created them, so we can get back to them later in case we don't understand the TODO. It doesn't mean that you have to fix it personally ;)

Test suite is green now, and I have also done a saveloading test with a savegame from trunk.

Running 8 AIs on The Nile on auto_speed slowed down to a crawl before 4 hours gametime, but we are having a problem in trunk (https://bugs.launchpad.net/widelands/+bug/1795976), so it might not be related to this branch.

This will make a great feature for Build 21, thank you! :)

review: Approve

[ypopezios (ypopezios)]

Thanks for clarifying the TODO tags. I would expect the creator to be written on the left and the assignee on the right of it.

The only way for this branch to slow down the game is if the ports and the ships become hundreds. Even in that case, it should be lighter than the previous code, so I don't think that there is a problem with it.

Did you mean Build 20? I don't see why it has to wait for Build 21. If there is indeed a problem with the code, it would be easier for me to address it now, before the code gets off my brain's cache.

[GunChleoc (gunchleoc)]

No, I did mean Build 21. We are in feature freeze, and feature freeze means it's feature freeze for everybody. Otherwise, we'll never get a release out, because there will always be that one cool feature we'll want to squeeze in. It's very tempting.

Having an assignee in TODO comment would only make sense if development was paid in this project, which it isn't. Changing the format now will mean changing a bazillion TODO comments in the code base + changing the codecheck rule. I already cleaned them up once and I'm not eager to do it again ;)

[ypopezios (ypopezios)]

You keep calling that a feature, while it is mostly a fix for the long-standing poor scheduling, so technically it still applies despite the feature freeze. Furthermore, the freeze was announced on 2018-09-17, while this branch has been approved on 2018-09-14. The late problems with the test suite were just that, problems with the test suite, not with the branch. If you insist to be strict with that, you are free to be, but this will inevitably freeze my motivation as well.

[GunChleoc (gunchleoc)]

Well, I have fully mature branches that have been sitting around for a year that won't make it in because they are still waiting for a code review slot... I could just call them "UI bugs" and insist on having them in Build 20, delaying the release until who knows when, maybe another year?

Every changed line of code has the potential for bugs, and as we have seen from the failing test suite, there are edge cases that don't immediately come up during gameplay testing. You are providing some complex control flow in your branches, so the potential for undiscovered new bugs is high. I have just fixed an endless loop that was introduced in February and only reported last week. So, I don't think that we should risk it with the release coming shortly. Widelands is too mature for the player base to find bugs like that acceptable in a release.

Also, the release procedure that we are using has been developed by my predecessor over the course of > 15 years, so I'm expecting there to be reasons for it to be like it is.

Patience is part of the game, I'm afraid. If you are too demotivated to carry on by having to wait for a few weeks until a feature gets in, here is nothing that we can do about it. I'd be sad to see you leave :'(

[ypopezios (ypopezios)]

"Widelands is too mature for the player base to find bugs like that acceptable in a release."

Unless you have asked the player-base about the matter, the above statement is arbitrary. If you dare, you can conduct a poll on the issue. Projects much bigger and much more serious than Widelands have no problem releasing code that is not tested in every possible way, exactly to involve the user-base in the testing process (even more so when it comes to complex control flow). The endless loop you fixed after many months, would have been both reported and fixed much earlier if there was a release to expose it to users. Most importantly, the vast majority of modern user-bases has no more problem dealing with minor bugs, as long as they have an easy way to report them and the programmers are eager to fix them in soon-to-follow bug-fixing releases. Users can be as patient as the programmers, especially non-paying users.

Of course all that may leave your "German mentality" untouched, and this is not the place for a theoretical discussion. Still motivation is no less important than patience, and Widelands needs developers at least as much as it needs users. Or so I was told, among other non-truths, like that there are more testers than developers. On the bright side, it is good to know the practical value of my contributions, before undertaking something as big as fixing the routing or the AI.

[GunChleoc (gunchleoc)]

Please stop insulting everybody whenever you don't get your way. Yes, the release cycles are too long. No, we won't solve the problem of managing testing exposure by merging your feature right now this very instant.

Changing the release process in the middle of a release is not going to happen, because that's far too stressful for me. I'm only human and this is supposed to be a fun hobby. End of discussion.

[GunChleoc (gunchleoc)]

@bunnybot merge

[ypopezios (ypopezios)]

You can end a discussion, but you cannot help your case. Quite expectedly, the "few weeks" of the "release coming shortly" turned out to be more than half a year (and still counting). Congratulations for the upcoming release, and I wish it to really happen and not to be "too little too late". I also hope that all those months you had your "fun" and maybe you got a lesson on realism. "Widelands is too mature for the player base", but the players base (and even the developers base), although being a beast of patience, it is not mature enough for a project like Widelands. That used to be an educated analysis, but today is a proven reality. Hopefully the persons who got insulted by the analysis, will not get also insulted by reality itself.

[GunChleoc (gunchleoc)]

Considering all the desyncs and unexpected bugs we were struggling with, do you really think adding a complex new algorithm to the code would have made things any more predictable, or speeded up the release in any way whatsoever? It would have potentially slowed things even further. I'm sorry that's not fast enough for you, but when you work together with other people on a project of this size in our spare time, things don't happen right this instant.

Merging the anti-congestion algorithm before the release was a mistake and cost us more time, because we had some transport bugs coming up and needed to find out where it came from. Adding it back in will cost us even more time.

[ypopezios (ypopezios)]

It is funny how you still mention "this instance" when the scale of things here is whole months. Of course introducing new bugs doesn't speed-up things, but I don't remember you ever bothering with project's speed to begin with. Still introducing developers can definitely speed-up things. Especially those that are familiar with the introduced bugs, and those able for real development instead of merely hacking existing hacks. Which mistake was more serious in the longterm shouldn't be hard to see. The anti-congestion algorithm hardly introduced any bugs, it basically brought on the surface pre-existing ones. In any case, nobody cared for my time here, so I don't care if my contributions will be used or not. I have long moved on. Happy coding.

[GunChleoc (gunchleoc)]

Yes, introducing new developers - especially ones that are as capable as you are - definitely does speed up things. Repeatedly spending a lot of time, energy and frustration on discussions like this one however does not.

And yes, development can always take longer that one has projected, which is the nature of things. Also, going into feature freeze is a common practice that you will need to learn how to deal with if you're still interested in working collaboratively on software projects this size, even if they are just for fun.

I'm sorry that we didn't manage to communicate better and that you have not been happy here. I wish you all the best and that you will find a community that will suit you better.

[ypopezios (ypopezios)]

What has been common practice when Widelands started development, is not the favorite approach anymore and doesn't have to remain the same practice forever. Big fails in prediction is not in the nature of programming, but in the nature of old-fashioned development. Collaborative development is not an exception. The industry has moved forward (although not all parts of it) and a project like Widelands would only benefit from reconsidering its paleolithic approach (and this is something that the rest of Widelands developers seemed to realize).

No, I don't need to deal with that stuff in our era. It's not my business anymore, but the ideal point in time to reconsider a project's approach is right after a major release, so don't lose that rare-in-Widelands opportunity. There are good chances that you will be wondering why you didn't do it earlier.

I have not been in search for a community, I didn't come here begging to belong somewhere. I offered to help, but I got "embraced" with immediate doubts and trash. I tried my best to consider it as a problem of communication or culture. So I gave it a chance and proved that I can contribute (which I did in various fields, including the most demanding one). In the end it was not a problem of communication, but one of realism. Even abandoning the project could be considered as a form of helping it wake up.

And I don't believe that I'm a special case. Not many developers would tolerate that environment. Widelands community is suffering from isolationism. Open doors cannot help when minds are closed. This is a well-known pattern in open-source projects.

=== modified file 'src/economy/fleet.cc'
--- src/economy/fleet.cc	2019-02-23 11:00:49 +0000
+++ src/economy/fleet.cc	2019-04-24 08:27:58 +0000
@@ -305,7 +305,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();
 
@@ -401,6 +401,7 @@
 		ship->set_economy(*game, nullptr);
 
 	if (ship->get_destination(egbase)) {
+		ship->get_destination(egbase)->ship_coming(false);
 		update(egbase);
 	}
 
@@ -633,8 +634,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
  */
@@ -642,230 +642,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	2019-02-23 11:00:49 +0000
+++ src/economy/fleet.h	2019-04-24 08:27:58 +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	2019-04-24 06:01:37 +0000
+++ src/economy/portdock.cc	2019-04-24 08:27:58 +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.
  *
@@ -248,7 +253,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()) {
@@ -272,7 +277,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()) {
@@ -282,44 +287,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;
@@ -338,46 +365,59 @@
 			// 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;
+		}
+	}
+
+	// Check for items with invalid destination. TODO(ypopezios): Prevent invalid destinations
+	for (auto si_it = waiting_.begin(); si_it != waiting_.end(); ++si_it) {
+		if (!si_it->get_destination(game)) {
+			// 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);
+		}
+	}
+
+	// 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 wares/workers which go to chosen destination
+	for (auto si_it = waiting_.begin(); si_it != waiting_.end() && remaining_capacity > 0; ++si_it) {
+		if (si_it->get_destination(game) == next_port) {
+			ship.add_item(game, *si_it);
+			si_it = waiting_.erase(si_it);
+			--remaining_capacity;
+		}
+	}
+
+	// Then load any wares/workers favored by the chosen destination
+	for (auto si_it = waiting_.begin(); si_it != waiting_.end() && remaining_capacity > 0; ++si_it) {
+		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);
 	}
 }
@@ -446,13 +486,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_) {
@@ -461,12 +501,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>();
@@ -480,7 +520,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_) {
@@ -500,10 +551,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() {
@@ -528,10 +579,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);
 		}
@@ -554,7 +606,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	2019-04-24 06:01:37 +0000
+++ src/economy/portdock.h	2019-04-24 08:27:58 +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;
 
@@ -114,6 +113,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;
@@ -140,14 +142,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_;
@@ -158,7 +160,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	2019-02-23 11:00:49 +0000
+++ src/economy/shippingitem.cc	2019-04-24 08:27:58 +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	2019-02-23 11:00:49 +0000
+++ src/economy/shippingitem.h	2019-04-24 08:27:58 +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	2019-04-24 06:01:37 +0000
+++ src/logic/map_objects/tribes/ship.cc	2019-04-24 08:27:58 +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;
 	}
 	case ShipStates::kSinkRequest:
@@ -728,14 +738,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));
 }
 
@@ -746,14 +759,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);
@@ -812,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);
 	}
 }
 
@@ -836,10 +874,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);
@@ -970,8 +1008,9 @@
 /// @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;
+	}
 	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	2019-04-24 06:01:37 +0000
+++ src/logic/map_objects/tribes/ship.h	2019-04-24 08:27:58 +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

=== modified file 'test/maps/expedition.wmf/scripting/init.lua'
--- test/maps/expedition.wmf/scripting/init.lua	2017-11-08 15:53:57 +0000
+++ test/maps/expedition.wmf/scripting/init.lua	2019-04-24 08:27:58 +0000
@@ -207,7 +207,7 @@
 
    -- Now cancel the expedition before it even got send out.
    cancel_expedition_in_shipwindow()
-   sleep(100)
+   sleep(40000)
    assert_equal(1, p1:get_workers("barbarians_builder"))
    sleep(8000)  -- ship needs a while to get wares back.
    check_wares_in_port_are_all_there()
@@ -248,7 +248,7 @@
    assert_equal(1, p1:get_workers("barbarians_builder"))
 
    cancel_expedition_in_shipwindow(expedition_ship)
-   sleep(20000)
+   sleep(50000)
    assert_equal(1, p1:get_workers("barbarians_builder"))
    check_wares_in_port_are_all_there()
 
@@ -288,7 +288,7 @@
    assert_equal(1, p1:get_workers("barbarians_builder"))
 
    cancel_expedition_in_shipwindow(first_ship)
-   sleep(20000)
+   sleep(50000)
    assert_equal(1, p1:get_workers("barbarians_builder"))
    check_wares_in_port_are_all_there()
 

=== modified file 'test/maps/expedition.wmf/scripting/test_cancel_when_port_space_was_reached_two_ships.lua'
--- test/maps/expedition.wmf/scripting/test_cancel_when_port_space_was_reached_two_ships.lua	2017-11-08 15:53:57 +0000
+++ test/maps/expedition.wmf/scripting/test_cancel_when_port_space_was_reached_two_ships.lua	2019-04-24 08:27:58 +0000
@@ -31,7 +31,7 @@
    assert_equal(1, p1:get_workers("barbarians_builder"))
 
    cancel_expedition_in_shipwindow(expedition_ship)
-   sleep(20000)
+   sleep(50000)
    assert_equal(1, p1:get_workers("barbarians_builder"))
    check_wares_in_port_are_all_there()