Merge lp:~widelands-dev/widelands/new-shipping into lp:widelands

[Benedikt Straub]

New planning-ahead ship scheduling algorithm

This algorithm uses a new approach. Each ship has a sorted list of the ports it´s planning to visit next. When new wares are loaded or some port requires a ship, the destinations may be reordered to accommodate for the importance of the several destinations (which depends on distance and number of wares). Ports whose visit is often postponed increase in priority so single wares won´t be sailing around forever if more important orders keep dropping in. Ports that can be visited on-the-fly (only a small detour) between two more important ports are also preferred. Ships may also be called back if a new ware arrives at the port immediately after the ship has left.

I hacked together some savegame compatibility; however, due to the linked bug, trunk savegames may show irrational behaviour.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 5309. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/570269198.
Appveyor build 5082. State: failed. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_new_shipping-5082.

[Klaus Halfmann (klaus-halfmann)]

Thanks for picking this up, as I am just teesting some new Mpa with
a lot of Ports, I can combine two things here. I dont have that much
time the next weeks, though.

[Klaus Halfmann (klaus-halfmann)]

Did a first review, the code is ok, but some more comments
would help me to grasp me the semantics of some stuctures.
and please refactor out some of the bigger loops. (https://de.wikipedia.org/wiki/Refactoring)
Please check my inline comments.

Do you have an idea how big the perfomance impact may be for a Map with a lot of Ports.
e.g. two AI Players on the Nile or my new Map https://www.widelands.org/maps/unreal-waterflow/

You are solving a kind of https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
or https://en.wikipedia.org/wiki/Travelling_salesman_problem

this has potential for exponential (or NP-Hard) complexity. So maybe we should
put in some limits so that we dod not stop the game dunring these calculations.
e.g.

* limit the number of ports on a route to 4/8/16?
* stop some calcualtions after a giiven mount of steps?
* be carefull not to use (local) timings as this depends on the CPU and may rsult in desyncs

Next I will run the regression tests.

Maybe its worth to design a big Map with a lot of Ports (128) to test this?

[Klaus Halfmann (klaus-halfmann)]

We have a lot of regressiontests about seafaring (for a reason :-)
./regression_test.py -b ./widelands

FAILs

test/maps/ship_transportation.wmf/scripting/test_rip_ports_with_worker_in_transit.lua ...
test/maps/ship_transportation.wmf/scripting/test_rip_first_port_with_worker_in_portdock.lua ...
test/maps/ship_transportation.wmf/scripting/test_rip_first_port_with_ware_in_portdock.lua ...
test/maps/ship_transportation.wmf/scripting/test_rip_second_port_with_ware_in_portdock.lua ...
test/maps/ship_transportation.wmf/scripting/test_rip_farm_with_ware_and_worker_in_transit.lua ...
test/maps/ship_transportation.wmf/scripting/test_rip_ports_with_ware_in_transit.lua ...

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

One hard crash from ASAN with:
==14492==ERROR: AddressSanitizer: heap-use-after-free on address 0x6040020e6798 at pc 0x000107e3088e bp 0x7ffeea4f2790 sp 0x7ffeea4f2788
READ of size 8 at 0x6040020e6798 thread T0
    #0 0x107e3088d in std::__1::__tree_end_node<std::__1::__tree_node_base<void*>*>* std::__1::__tree_next_iter<std::__1::__tree_end_node<std::__1::__tree_node_base<void*>*>*, std::__1::__tree_node_base<void*>*>(std::__1::__tree_node_base<void*>*) __tree:176
    #1 0x107e1c53a in std::__1::__tree_const_iterator<Widelands::Ship*, std::__1::__tree_node<Widelands::Ship*, void*>*, long>::operator++() __tree:920
    #2 0x107e1bc2c in Widelands::PortDock::cleanup(Widelands::EditorGameBase&) portdock.cc:200
    #3 0x1074fcef2 in Widelands::MapObject::remove(Widelands::EditorGameBase&) map_object.cc:465
    #4 0x1078b2d7c in Widelands::Warehouse::cleanup(Widelands::EditorGameBase&) warehouse.cc:638
...
previously allocated by thread T0 here:
...
    #4 0x107e3340f in std::__1::unique_ptr<std::__1::__tree_node<Widelands::Ship*, void*>, std::__1::__tree_node_destructor<std::__1::allocator<std::__1::__tree_node<Widelands::Ship*, void*> > > > std::__1::__tree<Widelands::Ship*, std::__1::less<Widelands::Ship*>, std::__1::allocator<Widelands::Ship*> >::__construct_node<Widelands::Ship*>(Widelands::Ship*&&) __tree:2201
    #5 0x107e32bfc in std::__1::pair<std::__1::__tree_iterator<Widelands::Ship*, std::__1::__tree_node<Widelands::Ship*, void*>*, long>, bool> std::__1::__tree<Widelands::Ship*, std::__1::less<Widelands::Ship*>, std::__1::allocator<Widelands::Ship*> >::__emplace_unique_key_args<Widelands::Ship*, Widelands::Ship*>(Widelands::Ship* const&, Widelands::Ship*&&) __tree:2147
    #6 0x107e327ab in std::__1::__tree<Widelands::Ship*, std::__1::less<Widelands::Ship*>, std::__1::allocator<Widelands::Ship*> >::__insert_unique(Widelands::Ship*&&) __tree:1276
    #7 0x107e1eb3f in std::__1::set<Widelands::Ship*, std::__1::less<Widelands::Ship*>, std::__1::allocator<Widelands::Ship*> >::insert(Widelands::Ship*&&) set:635
    #8 0x107e1e3af in Widelands::PortDock::ship_coming(Widelands::Ship&, bool) portdock.cc:330
    #9 0x10772d84b in Widelands::Ship::push_destination(Widelands::Game&, Widelands::PortDock&) ship.cc:763
    #10 0x107df0509 in Widelands::Fleet::push_next_destinations(Widelands::Game&, Widelands::Ship&, Widelands::PortDock const&) fleet.cc:872
    #11 0x107e1fa50 in Widel...

review: Needs Fixing (regression tests)

[Benedikt Straub (nordfriese)]

Thanks for reviewing :)
Implemented or replied to your comments.

I´ve been playing so far on Dust In The Wind where I didn´t notice performance problems (owning ~ half the islands). A big map with many many ports would be great for testing though.

This is sort of like the TSP with additional rules like "dynamic route lengths" (priority weights, esp. numbers of items). But since ships that already have destinations are highly penalized, they will be sifted out quickly and only ships with few destinations will be chosen; so although the recursion call is exponential, the recursion depth should likely always be shallow. (If you have just one ship for a hundred ports, new requests will be ignored for a while rather than assigned in a suboptimal way if your ship already has lots of destinations.)

> * be carefull not to use (local) timings as this depends on the CPU and may rsult in desyncs
I don´t understand, what do you mean by local timings?

[Klaus Halfmann (klaus-halfmann)]

> be carefull not to use (local) timings ...
For some rendering code you might use an approach

long ts = current_time() + kMaxRenderingMillis;
do {
  refine_textures(...)
} while (ts < current_time());

With widelands we must not do such things, got the idea?

[Benedikt Straub (nordfriese)]

Ah ok :) you meant, don´t use realtime as a limit for calculation steps. OK, if playtesting shows that such a limit is necessary (atm I don´t think it is) the limit will be implemented by max number of destinations or perhaps max total route length.

[Klaus Halfmann (klaus-halfmann)]

Loading the Savegame Unreal.wgf from
https://www.magentacloud.de/share/tu4ayusx.k

provokes this ASAN error in
==1418==ERROR: AddressSanitizer: heap-use-after-free on address 0x6040025b5898 at pc 0x00010b77478e ...
#2 0x10b75f8cc in Widelands::PortDock::cleanup(Widelands::EditorGameBase&) portdock.cc:200

please confirm you can reproduce it and can fix the regression tests.

new code looks fine.

[Benedikt Straub (nordfriese)]

Can´t reproduce. I downloaded your savegame, loaded it, let it run for ten minutes gametime and then closed it, all without problems…

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 5314. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/570532677.
Appveyor build 5087. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_new_shipping-5087.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 5317. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/570717296.
Appveyor build 5089. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_new_shipping-5089.

[Klaus Halfmann (klaus-halfmann)]

Mhh, you _did_ compile with LLVM and ASAN?
As this is a use after freee you may live with it for a long time without noticing much of a difference,

What about the regression tests? do they work for you?

[Benedikt Straub (nordfriese)]

Yes, with ASan. It complains about the usual memory leak when closing Widelands, nothing else.
Travis is happy now, regression tests are working there.

[Klaus Halfmann (klaus-halfmann)]

Whatever you did, looks like it fixed the regression tests, too.
I have about no time this weeek. But this deserves some playtesting, mmh.

[Klaus Halfmann (klaus-halfmann)]

Mhh, I have:
Check for working CXX compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/c++ -- works
Apple LLVM version 10.0.1 (clang-1001.0.46.4)
And I get still get this crash at bzr9140[new-shipping]
directy when loading that file.
We had such subtule differences between compilers before.

==1286==ERROR: AddressSanitizer: heap-use-after-free on address 0x604001876498 at pc 0x00010f0ed78e bp 0x7ffee3233ef0 sp 0x7ffee3233ee8
#2 0x10f0d88cc in Widelands::PortDock::cleanup(Widelands::EditorGameBase&) portdock.cc:200

Hmm, trying a Debugger, next.

[Benedikt Straub (nordfriese)]

I have pushed a blind guess what might be causing this, please test whether this fixes it

[Klaus Halfmann (klaus-halfmann)]

Sorry still got it

SaveHandler::save_game() took 2536ms
Reloading the game from replay
=================================================================
==99248==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000c71568 at pc 0x0001102296de bp 0x7ffee2224ef0 sp 0x7ffee2224ee8
    #2 0x110214b23 in Widelands::PortDock::cleanup(Widelands::EditorGameBase&) portdock.cc:200
    #3 0x10f8c9822 in Widelands::MapObject::remove(Widelands::EditorGameBase&) map_object.cc:465
    #4 0x10fc7d67c in Widelands::Warehouse::cleanup(Widelands::EditorGameBase&) warehouse.cc:638
    #5 0x10f8c9822 in Widelands::MapObject::remove(Widelands::EditorGameBase&) map_object.cc:465
    #6 0x10f8c9436 in Widelands::ObjectManager::cleanup(Widelands::EditorGameBase&) map_object.cc:167
    #7 0x10db4f8f4 in Widelands::EditorGameBase::cleanup_objects() editor_game_base.h:170
    #8 0x10e2d1b08 in Widelands::EditorGameBase::cleanup_for_load() editor_game_base.cc:510
    #9 0x10e304d5f in Widelands::Game::cleanup_for_load() game.cc:615
    #10 0x10e3eee66 in Widelands::ReplayWriter::ReplayWriter(Widelands::Game&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::alloca

freed by thread T0 here:
...
    std::__1::__tree_node<Widelands::OPtr<Widelands::Ship>, void*>*, long>) set:647
    #6 0x11021740f in Widelands::PortDock::ship_coming(Widelands::Ship&, bool) portdock.cc:336
    #7 0x10fafac3b in Widelands::Ship::pop_destination(Widelands::Game&, Widelands::PortDock&) ship.cc:777

No idea what this replay writer does, no time for debugging right now

[Benedikt Straub (nordfriese)]

I added some debug output, please try again…

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 5331. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/572672291.
Appveyor build 5103. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_new_shipping-5103.

[Klaus Halfmann (klaus-halfmann)]

I added the complete output to:

https://www.magentacloud.de/share/tu4ayusx.k#$/
Crash.txt

Will try a debugger now ....

[Benedikt Straub (nordfriese)]

Another guess pushed, this one may fix it. (untested, can´t compile atm.) Please test…

[Klaus Halfmann (klaus-halfmann)]

Just started the Debugger and wondered where this this OPtr thing comes from.

But whatever you did looks like you fixed it.

Will go on laying my Map now until I got whatever was possible.

AND thanks!

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 5332. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/572886798.
Appveyor build 5104. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_new_shipping-5104.

[Klaus Halfmann (klaus-halfmann)]

OK, now its getting interesting.
My "Unreal Water" Map got totally slow and stopped with

 1: attacking site at 56x 40, score 5, with 2 soldiers, attacking 2 times, after 102 seconds
Cmd_EnemyFlagAction::execute player(1): flag->owner(3) number=2
Cmd_EnemyFlagAction::execute player(3): flag->owner(2) number=3
TI(55348): destination disappeared or economy mismatch -> fail
Assertion failed: (dest), function load_wares, file ../src/economy/portdock.cc, line 395.
Abort trap: 6

Lets see, if I can get some savegame ...

Check here; https://www.magentacloud.de/share/tu4ayusx.k UnrealAssert.wgf

[Benedikt Straub (nordfriese)]

Ouch. This means that you have an item in your portdock that doesn´t know where it wants to go. Happens all the time in trunk, shouldn´t happen anymore in this branch.
Did you (or some AI) destroy a port shortly before you got the error? Or connected some previously unconnected ports on land? Or saved and reloaded?

[Klaus Halfmann (klaus-halfmann)]

Look like
a) The attached game on partially reproduces the Issue (just slow as hell)
b) A Millitarysite near a Port was under heavy Attack, you ca find two
   barbarian Inhabitat Atlanter Buidlign, ooks I lost them just during the crash.

I set Autosae to Minutes ant will continue ... later.

[Klaus Halfmann (klaus-halfmann)]

OK here comes thee next (me conquering the Imperial Isaland East of mine)

5: (126x 23) expedition spot scoring, colony_scan_area == 21
5: Ullr at 2x 23: PORTSPACE found, we valued it: 0
5: Ullr at 2x 23: explore uphold, visited first time
5: Ullr: continue island circumvention, dir=1
Cmd_EnemyFlagAction::execute player(3): flag->owner(2) number=4
Assertion failed: (old_index < nr_dests), function reorder_destinations, file ../src/logic/map_objects/tribes/ship.cc, line 902.
Abort trap: 6

Loos like this logic needs more Braintwisting :-)

But now I really _will_ stop... good night

review: Needs Fixing

[Klaus Halfmann (klaus-halfmann)]

Debugging can be FUN!, well not for you Benedikt, sorry:

5: Ullr: exploration - breaking for free sea, dir=1
TrainingSite::drop_stalled_soldiers: Kicking somebody out.
Assertion failed: (detour >= base_length), function check_push_destination, file ../src/economy/fleet.cc, line 887.
Abort trap: 6

Application Specific Information:
Assertion failed: (old_index < nr_dests), function reorder_destinations, file ../src/logic/map_objects/tribes/ship.cc, line 902.

I added two more Savegames +/- around the asserts from above

https://www.magentacloud.de/share/tu4ayusx.k

The _may_ be related to shipping soldiers. I "forgot" some Soldiers on the Mainland
and after sending them awy I got theses assertions. Maybe adding some coordinates and
the exact values to the assert may help?

Ill go back to fine tuning my map ...

review: Needs Fixing

[Benedikt Straub (nordfriese)]

I tried out all four UnrealAssert savegames now and *none* of them triggered an assert fail. Do you have replays that end with assert-crashes?

[Klaus Halfmann (klaus-halfmann)]

Mhh, it took about 15-30 minutes to trigger the asserts.
I will be "on call duty" this week, so I have even less time.

I tried one of the new features of trunk : order Soldiers to be sent
to the port immediateley once it was build.

As of some Towers "across the Sea", I was able to plan buldings next to
the Port while it was build. And I connected some Ports being build
to some exiting economy.

I will try some AI-only setups
(Well he AI fails to grasp the evil tricks needed for this Map..)
I will give this some 4 hours (on 10x Speed or such).

Next I will setup a debugger and give you details from "inside the code".

What OS/CPU/Debugger do you use?

Maybe we should recruit some tester from the tournmanent?

[Klaus Halfmann (klaus-halfmann)]

Hello benedikt, I am back and will try
more with a debugger attached, any news from your siede?

[Klaus Halfmann (klaus-halfmann)]

OK, found an obvious Bug:

* Two ships find the same PortSpace
* Tell both of them to build a port.

4: Colonization error: unloading wares to constructionsite of atlanteans_port (owner 4) failed.
 Wares unloaded to the site: 3, max capacity: 3, remaining to unload: 13
 No free capacity to unload another ware
Assertion failed: (wq.get_max_fill() > cur), function ship_update_idle, file ../src/logic/map_objects/tribes/ship.cc, line 653.

The same might happen if you tell a ship to uild a port that is
already (partially) equipped from the Land side

Do you want a save game for tis?

[Benedikt Straub (nordfriese)]

I believe this is a bug in trunk since I didn´t touch that code, but I´ll fix it here. Once the portspace becomes unavailable, other ships shouldn´t be allowed to start colonizing. No savegame needed, should be easy to reproduce. I´ll also add this case to the testsuite.

Still wasn´t able to reproduce any of the UnrealAssert asserts.

[Klaus Halfmann (klaus-halfmann)]

Next one please check: https://www.magentacloud.de/share/tu4ayusx.k ShioCrash2.wgf

Crashes here:
Assertion failed: (old_index < nr_dests), function reorder_destinations,
file ../src/logic/map_objects/tribes/ship.cc, line 902.

With a Debugger I found...

Via the ReplayWriter game.cleanup_for_load(); is called
This in turn calls
void MapObject::remove(EditorGameBase& egbase)
void PortDock::cleanup(EditorGameBase& egbase) // why doing such a fuzz for a cleanup?
void Ship::pop_destination(Game& game, PortDock& pd)
void Ship::reorder_destinations(Game& game)

I assume there is some issue with the == Operator from OPtr<PortDock> optr(pair.first);

if (old_destinations[old_index].first == optr) {
 break; // does not happen
}

This code does not really seem robust, but I still must find out what this OPtr thing is.

Maybe when loading Objects ar kind of cloned by the loading so the code fails?

[Benedikt Straub (nordfriese)]

The OPtr is just a wrapper for a MapObject. I use OPtr<PortDock> rather than PortDock* to avoid segfaults when the portdock is destroyed. The == comparison compares serials, so it´s 100% safe to use.
I found a potential cause for this assert in the way superfluous or invalid destinations are discarded, please check whether you can still reproduce it now…

[Klaus Halfmann (klaus-halfmann)]

OK, I can load the Savegame again, lets continue hunting ...

[Klaus Halfmann (klaus-halfmann)]

Now I was kiled here:

Assertion failed: (detour >= base_length), function check_push_destination, file ../src/economy/fleet.cc, line 887.

5 widelands 0x00000001102aedf9 Widelands::Fleet::check_push_destination(Widelands::Game&, Widelands::Ship&, Widelands::PortDock const&, Widelands::PortDock&, unsigned int) + 1497 (fleet.cc:887)
6 widelands 0x00000001102ad69e Widelands::Fleet::push_next_destinations(Widelands::Game&, Widelands::Ship&, Widelands::PortDock const&) + 3294 (fleet.cc:843)
7 widelands 0x00000001102dd544 Widelands::PortDock::ship_arrived(Widelands::Game&, Widelands::Ship&) + 2260 (portdock.cc:378)
8 widelands 0x000000010fbb1cbe Widelands::Ship::ship_update_transport(Widelands::Game&, Widelands::Bob::State&) + 1166 (ship.cc:316)
9 widelands 0x000000010fbb08d9 Widelands::Ship::ship_update(Widelands::Game&, Widelands::Bob::State&) + 1033 (ship.cc:265)
10 widelands 0x000000010f8ea790 Widelands::Bob::do_act(Widelands::Game&) + 704 (bob.cc:196)
11 widelands 0x000000010f8ea486 Widelands::Bob::act(Widelands::Game&, unsigned int) + 1030 (bob.cc:181)
12 widelands 0x000000010f98d88a Widelands::CmdAct::execute(Widelands::Game&) + 570 (map_object.cc:110)
13 widelands 0x00000001103d42f9 Widelands::CmdQueue::run_queue(int, unsigned int&) + 1497 (cmd_queue.cc:124)
14 widelands 0x000000010e3c9b4d Widelands::Game::think() + 637 (game.cc:602)
15 widelands 0x000000010f3a53c8 InteractiveBase::think() + 488 (interactive_base.cc:516)
16 widelands 0x000000010f4ae6bc InteractivePlayer::think() + 572 (interactive_player.cc:232)
17 widelands 0x000000010ea040e7 UI::Panel::do_think() + 151 (panel.cc:488)
18 widelands 0x000000010ea0230c UI::Panel::do_run() + 2332 (panel.cc:189)
...

Will try to reprodcue this ...

[Benedikt Straub (nordfriese)]

No wonder it was buggy, I used the wrong variable for calculating the length of the detour :)
Please check whether it still happens…

[Klaus Halfmann (klaus-halfmann)]

OK I have a ShipCrash4.wgf at https://www.magentacloud.de/share/tu4ayusx.k

I start this with $ ./widelands --loadgame=~/Downloads/ShipCrash4.wgf

and wait about 10 Minutes for

Assertion failed: (detour >= base_length), function check_push_destination, file ../src/economy/fleet.cc, line 888.
Abort trap: 6

Please consider that I have soldiers that need transport and have special wishes from Laybrinths and Dungeons.

Sorrry for all thee detours :-)

review: Needs Fixing

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 5347. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/577456819.
Appveyor build 5117. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_new_shipping-5117.

[kaputtnik (franku)]

Can you please merge trunk? I am struggling with bug 1839740 ... which is solved in trunk.

I get the same crash:

/widelands-repo/new-shipping/src/economy/fleet.cc:888: void Widelands::Fleet::check_push_destination(Widelands::Game&, Widelands::Ship&, const Widelands::PortDock&, Widelands::PortDock&, uint32_t): Zusicherung »detour >= base_length« nicht erfüllt.

The crash happens after at least one ship arrives a port. I guess its the ship called 'Saturn' in this savgame: https://bugs.launchpad.net/widelands/+bug/1827033/+attachment/5285464/+files/test.wgf

Just press 'E' and click on 'Saturn'

[GunChleoc (gunchleoc)]

I had a look at the check for disallowing double colonization. I think it would be sufficient to check whether there's a building there, we don't care if it's a port or a construction site. It might even be safer, because the enemy might also have been faster with building something there.

[Benedikt Straub (nordfriese)]

The "detour >= base_length" assert should finally be fixed. Also changed the double-colonization check as suggested.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 5356. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/578276856.
Appveyor build 5126. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_new_shipping-5126.

[kaputtnik (franku)]

got another detour assert:

/widelands-repo/new-shipping/src/economy/fleet.cc:890: void Widelands::Fleet::check_push_destination(Widelands::Game&, Widelands::Ship&, const Widelands::PortDock&, Widelands::PortDock&, uint32_t): Zusicherung »detour >= base_length« nicht erfüllt.
Abgebrochen (Speicherabzug geschrieben)

The assert is triggert close after loading this save game: https://bugs.launchpad.net/widelands/+bug/1827033/+attachment/5285703/+files/wl_autosave_00.wgf

Don't know if it is related: Playing a debug build and the game stutters noticeably. The game stops for a short time. Do you want a save game close before this autosave?

[Klaus Halfmann (klaus-halfmann)]

I now got
Assertion failed: (ship.get_nritems() == 0), function ship_arrived,
file ../src/economy/portdock.cc, line 383.
   after
./widelands --loadgame=~/Downloads/ShipCrash5.wgf

Somwhat after 1:56... from https://www.magentacloud.de/share/tu4ayusx.k

Do frisians have very special wares?

[Benedikt Straub (nordfriese)]

The detour-baselength assert will definitely not give any further trouble now – I removed it ;)
Making a detour really can shorten the ship´s path by a few fields in some cases… :P

The ship.get_nritems() assert is also fixed now, though the savegame might remain broken.

[GunChleoc (gunchleoc)]

I have added some comments

=== modified file 'src/economy/fleet.cc'
--- src/economy/fleet.cc	2019-04-24 15:11:23 +0000
+++ src/economy/fleet.cc	2019-09-07 13:04:52 +0000
@@ -336,7 +336,7 @@
 uint32_t Fleet::count_ships_heading_here(EditorGameBase& egbase, PortDock* port) const {
 	uint32_t ships_on_way = 0;
 	for (uint16_t s = 0; s < ships_.size(); s += 1) {
-		if (ships_[s]->get_destination(egbase) == port) {
+		if (ships_[s]->get_current_destination(egbase) == port) {
 			ships_on_way += 1;
 		}
 	}
@@ -400,8 +400,8 @@
 	if (upcast(Game, game, &egbase))
 		ship->set_economy(*game, nullptr);
 
-	if (ship->get_destination(egbase)) {
-		ship->get_destination(egbase)->ship_coming(false);
+	if (ship->get_current_destination(egbase)) {
+		ship->get_current_destination(egbase)->ship_coming(*ship, false);
 		update(egbase);
 	}
 
@@ -633,6 +633,53 @@
 	}
 }
 
+/*
+ * Helper function for assigning ships to ports in need of a ship.
+ * Penalizes the given ship if it is transporting wares.
+ * A small detour to the given portdock is penalized very slightly, a longer detour drastically.
+ * Returns false if the detour would be so long that this ship must not even be considered for serving this port.
+ */
+bool Fleet::penalize_route(Game& game, PortDock& p, const Ship& s, uint32_t* route_length) {
+	const uint32_t real_length = *route_length;
+	uint32_t malus = 1;
+	uint32_t index = 0;
+	PortDock* iterator = nullptr;
+	uint32_t shortest_detour = std::numeric_limits<uint32_t>::max();
+	uint32_t best_index = std::numeric_limits<uint32_t>::max();
+	for (const auto& pair : s.destinations_) {
+		PortDock* pd = pair.first.get(game);
+		Path path;
+		uint32_t detour;
+		if (iterator == &p) {
+			detour = 0;
+		} else if (iterator) {
+			get_path(*iterator, p, path);
+			detour = path.get_nsteps();
+		} else {
+			s.calculate_sea_route(game, p, &path);
+			detour = path.get_nsteps();
+		}
+		if (&p != pd) {
+			get_path(p, *pd, path);
+			detour += path.get_nsteps();
+		}
+		if (detour < shortest_detour) {
+			shortest_detour = detour;
+			best_index = index;
+		}
+		malus += pair.second;
+		iterator = pd;
+		++index;
+	}
+	*route_length += shortest_detour * best_index;
+	if (*route_length + shortest_detour > real_length * malus) {
+		// Unreasonably long detour
+		return false;
+	}
+	*route_length *= malus;
+	return true;
+}
+
 /**
  * Act callback updates ship scheduling of idle ships.
  *
@@ -665,13 +712,14 @@
 		bool waiting = true;
 
 		for (Ship* s : ships_) {
-			if (s->get_destination(game)) {
-				if (s->get_destination(game) == p) {
+			bool fallback = false;
+			if (s->get_current_destination(game)) {
+				if (s->has_destination(game, *p)) {
 					waiting = false;
 					--waiting_ports;
 					break;
 				}
-				continue;  // The ship already has a destination
+				fallback = true;  // The ship already has a destination
 			}
 			if (s->get_ship_state() != Ship::ShipStates::kTransport) {
 				continue;  // Ship is not available, e.g. in expedition
@@ -699,6 +747,11 @@
 			if (route_length == kRouteNotCalculated) {
 				route_length = s->calculate_sea_route(game, *p);
 			}
+			if (fallback) {
+				if (!penalize_route(game, *p, *s, &route_length)) {
+					continue;
+				}
+			}
 
 			if (route_length < shortest_dist) {
 				shortest_dist = route_length;
@@ -708,7 +761,7 @@
 
 		if (waiting && closest_ship) {
 			--waiting_ports;
-			closest_ship->set_destination(p);
+			closest_ship->push_destination(game, *p);
 			closest_ship->send_signal(game, "wakeup");
 		}
 	}
@@ -721,7 +774,7 @@
 
 	// Deal with edge-case of losing destination before reaching it
 	for (Ship* s : ships_) {
-		if (s->get_destination(game)) {
+		if (s->get_current_destination(game)) {
 			continue;  // The ship has a destination
 		}
 		if (s->get_ship_state() != Ship::ShipStates::kTransport) {
@@ -744,107 +797,108 @@
 		}
 
 		if (closest_port) {
-			s->set_destination(closest_port);
+			s->push_destination(game, *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
+ * Tell the given ship where to go next. May push any number of destinations.
  */
-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;
+void Fleet::push_next_destinations(Game& game, Ship& ship, const PortDock& from_port) {
+	std::vector<std::pair<PortDock*, uint32_t>> destinations; // Destinations and the number of items waiting to go there
+	uint32_t total_items = ship.get_nritems(); // All waiting and shipping items
+	uint32_t waiting_items = 0; // Items that have a destination which this ship is not currently planning to visit
+	// Count how many items are waiting to go to each portdock
+	for (auto& it : from_port.waiting_) {
+		if (PortDock* pd = it.destination_dock_.get(game)) {
+			++total_items;
+			if (ship.has_destination(game, *pd)) {
+				continue;
+			}
+			++waiting_items;
+			bool found = false;
+			for (auto& pair : destinations) {
+				if (pair.first == pd) {
+					++pair.second;
+					found = true;
+					break;
+				}
+			}
+			if (!found) {
+				destinations.push_back(std::make_pair(pd, 1));
 			}
 		}
 	}
-	return true;  // default
+	assert(waiting_items <= total_items);
+	if (waiting_items == 0) {
+		// Nothing to do
+		return;
+	}
+	total_items -= waiting_items;
+	// For each destination, decide whether to tell the ship to visit it
+	// or whether it would be better to wait for another ship
+	for (const auto& destpair : destinations) {
+		check_push_destination(game, ship, from_port, *destpair.first, destpair.second * total_items);
+	}
 }
 
-/**
- * For the given ship, go through all ports of this fleet
- * and find the one with the best score.
- * \return that port
+/*
+ * Helper function for push_next_destinations():
+ * Send the given ship to the given portdock (with the given penalty factor)
+ * if the detour this would mean for the ship is not too long
  */
-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::check_push_destination(Game& game, Ship& ship,
+		const PortDock& from_port, PortDock& destination, uint32_t penalty_factor) {
+	assert(!ship.has_destination(game, destination));
+	Path path;
+	get_path(from_port, destination, path);
+	const uint32_t direct_route = path.get_nsteps();
+	assert(direct_route);
+	uint32_t malus = 1;
+	uint32_t shortest_detour = std::numeric_limits<uint32_t>::max();
+	uint32_t best_index = std::numeric_limits<uint32_t>::max();
+	if (ship.destinations_.empty()) {
+		// Idle ships are preferred
+		best_index = 0;
+		malus = 0;
+		shortest_detour = 0;
+	} else {
+		const PortDock* iterator = &from_port;
+		uint32_t index = 0;
+		// This ship is going somewhere else, penalize it's priority for this order by
+		// the detour, the number of items it's shipping and the number of items waiting here
+		for (const auto& pair : ship.destinations_) {
+			const PortDock* pd = pair.first.get(game);
+			uint32_t detour = 0;
+
+			assert(iterator != pd);
+			get_path(*iterator, *pd, path);
+			const uint32_t base_length = path.get_nsteps();
+
+			assert(iterator != &destination);
+			get_path(*iterator, destination, path);
+			detour += path.get_nsteps();
+
+			assert(pd != &destination);
+			get_path(destination, *pd, path);
+			detour += path.get_nsteps();
+
+			detour -= std::min(detour, base_length);
+			if (detour < shortest_detour) {
+				shortest_detour = detour;
+				best_index = index;
+			}
+			malus += pair.second;
+			iterator = pd;
+			++index;
+		}
+	}
+	if (shortest_detour * malus * best_index <= direct_route * penalty_factor) {
+		// Send this ship if the penalty is not too high
+		ship.push_destination(game, destination);
+	}
 }
 
 void Fleet::log_general_info(const EditorGameBase& egbase) const {

=== modified file 'src/economy/fleet.h'
--- src/economy/fleet.h	2019-04-24 06:51:31 +0000
+++ src/economy/fleet.h	2019-09-07 13:04:52 +0000
@@ -121,6 +121,9 @@
 	PortPath& portpath_bidir(uint32_t i, uint32_t j, bool& reverse);
 	const PortPath& portpath_bidir(uint32_t i, uint32_t j, bool& reverse) const;
 
+	bool penalize_route(Game&, PortDock&, const Ship&, uint32_t*);
+	void check_push_destination(Game&, Ship&, const PortDock&, PortDock&, uint32_t);
+
 	std::vector<Ship*> ships_;
 	std::vector<PortDock*> ports_;
 
@@ -155,8 +158,7 @@
 	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);
+	void push_next_destinations(Game&, Ship&, const PortDock& from_port);
 };
 
 }  // namespace Widelands

=== modified file 'src/economy/portdock.cc'
--- src/economy/portdock.cc	2019-07-01 14:58:07 +0000
+++ src/economy/portdock.cc	2019-09-07 13:04:52 +0000
@@ -56,7 +56,6 @@
    : PlayerImmovable(g_portdock_descr),
      fleet_(nullptr),
      warehouse_(wh),
-     ships_coming_(0),
      expedition_ready_(false) {
 }
 
@@ -118,7 +117,7 @@
 }
 
 uint32_t PortDock::get_need_ship() const {
-	return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_ + 1);
+	return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_.size() + 1);
 }
 
 /**
@@ -198,6 +197,13 @@
 		for (ShippingItem& shipping_item : waiting_) {
 			shipping_item.remove(*game);
 		}
+		while (!ships_coming_.empty()) {
+			if (Ship* ship = ships_coming_.begin()->get(*game)) {
+				ship->pop_destination(*game, *this);
+			} else {
+				ships_coming_.erase(ships_coming_.begin());
+			}
+		}
 	}
 
 	if (fleet_)
@@ -288,7 +294,7 @@
 
 	// Destination might have vanished or be in another economy altogether.
 	if (dst && dst->get_economy() == get_economy()) {
-		if (ships_coming_ <= 0) {
+		if (ships_coming_.empty()) {
 			set_need_ship(game, true);
 		}
 	} else {
@@ -320,11 +326,17 @@
 /**
  * A ship changed destination and is now coming to the dock. Increase counter for need_ship.
  */
-void PortDock::ship_coming(bool affirmative) {
+void PortDock::ship_coming(Ship& ship, bool affirmative) {
+	OPtr<Ship> s(&ship);
 	if (affirmative) {
-		++ships_coming_;
+		if (ships_coming_.find(s) == ships_coming_.end()) {
+			ships_coming_.insert(s);
+		}
 	} else {
-		--ships_coming_;
+		auto it = ships_coming_.find(s);
+		if (it != ships_coming_.end()) {
+			ships_coming_.erase(it);
+		}
 	}
 }
 
@@ -332,14 +344,12 @@
  * A ship has arrived at the dock. Set its next destination and load it accordingly.
  */
 void PortDock::ship_arrived(Game& game, Ship& ship) {
-	ship_coming(false);
-
 	if (expedition_ready_) {
 		assert(expedition_bootstrap_ != nullptr);
 
 		// Only use an empty ship.
-		if (ship.get_nritems() < 1) {
-			ship.set_destination(nullptr);
+		if (ship.get_nritems() == 0) {
+			ship.clear_destinations(game);
 			// Load the ship
 			std::vector<Worker*> workers;
 			std::vector<WareInstance*> wares;
@@ -363,11 +373,10 @@
 		}
 	}
 
-	// Decide where the arrived ship will go next
-	PortDock* next_port = fleet_->find_next_dest(game, ship, *this);
-	if (next_port) {
-		// Unload any wares/workers onboard the departing ship which are not favored by next dest
-		ship.unload_unfit_items(game, *this, *next_port);
+	ship.pop_destination(game, *this);
+	fleet_->push_next_destinations(game, ship, *this);
+	if (ship.get_current_destination(game)) {
+		load_wares(game, ship);
 	}
 #ifndef NDEBUG
 	else {
@@ -375,51 +384,64 @@
 	}
 #endif
 
-	// 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
-			// TODO(Nordfriese): This readds the invalid item to the list
-			si_it->set_location(game, warehouse_);
-			si_it->end_shipping(game);
-			si_it = waiting_.erase(si_it);
-		}
-	}
-
-	if (!next_port) {
-		ship.set_destination(nullptr);
-		return;  // no need to load anything
-	}
-
-	// 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) {
-		const PortDock* dest = si_it->get_destination(game);
-		if (dest && fleet_->is_path_favourable(*this, *next_port, *dest)) {
-			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::load_wares(Game& game, Ship& ship) {
+	uint32_t free_capacity = ship.descr().get_capacity() - ship.get_nritems();
+	std::unordered_map<const PortDock*, bool> destination_check;
+	for (auto it = waiting_.begin(); it != waiting_.end() && free_capacity;) {
+		PortDock* dest = it->destination_dock_.get(game);
+		assert(dest);
+		assert(dest != this);
+		// Decide whether to load this item
+		bool load_item;
+		auto dc = destination_check.find(dest);
+		if (dc != destination_check.end()) {
+			load_item = dc->second;
+		} else {
+			uint32_t time = ship.estimated_arrival_time(game, *dest);
+			Path direct_route;
+			fleet_->get_path(*this, *dest, direct_route);
+			if (time == kInvalidDestination) {
+				time = direct_route.get_nsteps();
+			}
+			for (const OPtr<Ship>& ship_ptr : ships_coming_) {
+				Ship* s = ship_ptr.get(game);
+				assert(s);
+				uint32_t t = s->estimated_arrival_time(game, *dest, this);
+				if (t == kInvalidDestination) {
+					// The ship is not planning to go there yet, perhaps we can ask for a detour?
+					t = s->estimated_arrival_time(game, *this);
+					assert(s->count_destinations() >= 1);
+					if (time > t + static_cast<int32_t>(direct_route.get_nsteps() * s->count_destinations())) {
+						time = kInvalidDestination;
+						break;
+					}
+				} else if (t < time) {
+					// A ship is coming that is planning to visit the ware's destination sooner than this one
+					time = kInvalidDestination;
+					break;
+				}
+			}
+			load_item = time < kInvalidDestination;
+			destination_check.emplace(dest, load_item);
+		}
+		if (load_item) {
+			if (!ship.has_destination(game, *dest)) {
+				ship.push_destination(game, *dest);
+			}
+			ship.add_item(game, *it);
+			it = waiting_.erase(it);
+			--free_capacity;
+		} else {
+			++it;
+		}
+	}
+}
+
 void PortDock::set_need_ship(Game& game, bool need) {
 	if (need && fleet_) {
-		molog("trigger fleet update\n");
 		fleet_->update(game);
 	}
 }
@@ -449,8 +471,18 @@
 
 /**
  * Return the number of wares or workers waiting at the dock.
+ * If a destination dock is specified, count only items heading for this destination.
  */
-uint32_t PortDock::count_waiting() const {
+uint32_t PortDock::count_waiting(const PortDock* dest) const {
+	if (dest) {
+		uint32_t w = 0;
+		for (const ShippingItem& si : waiting_) {
+			if (si.destination_dock_.serial() == dest->serial()) {
+				++w;
+			}
+		}
+		return w;
+	}
 	return waiting_.size();
 }
 
@@ -504,7 +536,7 @@
 	}
 }
 
-constexpr uint8_t kCurrentPacketVersion = 4;
+constexpr uint8_t kCurrentPacketVersion = 5;
 
 PortDock::Loader::Loader() : warehouse_(0) {
 }
@@ -523,15 +555,18 @@
 		pd.set_position(egbase(), pd.dockpoints_[i]);
 	}
 
-	pd.ships_coming_ = fr.unsigned_8();
-
-	// TODO(GunChleoc): Savegame compatibility Build 20
-	if (packet_version < 4) {
-		pd.ships_coming_ = 0;
+	if (packet_version >= 5) {
+		const uint32_t ships = fr.unsigned_32();
+		for (uint32_t i = 0; i < ships; ++i) {
+			ships_coming_.insert(fr.unsigned_32());
+		}
+	} else {
+		// TODO(GunChleoc): Savegame compatibility Build 20
+		fr.unsigned_8();
 		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_;
+			if (ship->has_destination(egbase(), pd)) {
+				ships_coming_.insert(ship_serial);
 			}
 		}
 	}
@@ -554,6 +589,9 @@
 	PortDock& pd = get<PortDock>();
 	pd.warehouse_ = &mol().get<Warehouse>(warehouse_);
 
+	for (Serial s : ships_coming_) {
+		pd.ships_coming_.insert(OPtr<Ship>(&mol().get<Ship>(s)));
+	}
 	for (uint32_t i = 0; i < waiting_.size(); ++i) {
 		pd.waiting_.push_back(waiting_[i].get(mol()));
 	}
@@ -609,7 +647,10 @@
 		write_coords_32(&fw, coords);
 	}
 
-	fw.unsigned_8(ships_coming_);
+	fw.unsigned_32(ships_coming_.size());
+	for (const OPtr<Ship>& s : ships_coming_) {
+		fw.unsigned_32(mos.get_object_file_index(*s.get(egbase)));
+	}
 
 	fw.unsigned_32(waiting_.size());
 	for (ShippingItem& shipping_item : waiting_) {

=== modified file 'src/economy/portdock.h'
--- src/economy/portdock.h	2019-07-05 11:16:24 +0000
+++ src/economy/portdock.h	2019-09-07 13:04:52 +0000
@@ -109,13 +109,13 @@
 
 	void shipping_item_arrived(Game&, ShippingItem&);
 	void shipping_item_returned(Game&, ShippingItem&);
-	void ship_coming(bool affirmative);
+	void ship_coming(Ship&, bool affirmative);
 	void ship_arrived(Game&, Ship&);
 
 	void log_general_info(const EditorGameBase&) const override;
 
 	uint32_t count_waiting(WareWorker waretype, DescriptionIndex wareindex) const;
-	uint32_t count_waiting() const;
+	uint32_t count_waiting(const PortDock* = nullptr) const;
 
 	// Returns true if a expedition is started or ready to be send out.
 	bool expedition_started() const;
@@ -143,11 +143,13 @@
 	void update_shippingitem(Game&, std::list<ShippingItem>::iterator);
 	void set_need_ship(Game&, bool need);
 
+	void load_wares(Game&, Ship&);
+
 	Fleet* fleet_;
 	Warehouse* warehouse_;
 	PositionList dockpoints_;
 	std::list<ShippingItem> waiting_;
-	uint8_t ships_coming_;
+	std::set<OPtr<Ship>> ships_coming_;
 	bool expedition_ready_;
 
 	std::unique_ptr<ExpeditionBootstrap> expedition_bootstrap_;
@@ -165,6 +167,7 @@
 	private:
 		uint32_t warehouse_;
 		std::vector<ShippingItem::Loader> waiting_;
+		std::set<Serial> ships_coming_;
 	};
 
 public:

=== modified file 'src/economy/shippingitem.cc'
--- src/economy/shippingitem.cc	2019-04-24 06:51:31 +0000
+++ src/economy/shippingitem.cc	2019-09-07 13:04:52 +0000
@@ -139,13 +139,20 @@
 	}
 }
 
-constexpr uint16_t kCurrentPacketVersion = 1;
+constexpr uint16_t kCurrentPacketVersion = 2;
 
 void ShippingItem::Loader::load(FileRead& fr) {
 	try {
 		uint8_t packet_version = fr.unsigned_8();
-		if (packet_version == kCurrentPacketVersion) {
+		if (packet_version <= kCurrentPacketVersion) {
 			serial_ = fr.unsigned_32();
+			if (packet_version >= 2) {
+				destination_serial_ = fr.unsigned_32();
+			} else {
+				// TODO(Nordfriese): Remove when we break savegame compatibility
+				log("WARNING: Loading shippingitem with possible nullptr destination, which may result in bugs later\n");
+				destination_serial_ = 0;
+			}
 		} else {
 			throw UnhandledVersionError("ShippingItem", packet_version, kCurrentPacketVersion);
 		}
@@ -156,14 +163,17 @@
 
 ShippingItem ShippingItem::Loader::get(MapObjectLoader& mol) {
 	ShippingItem it;
-	if (serial_ != 0)
+	if (serial_ != 0) {
 		it.object_ = &mol.get<MapObject>(serial_);
+		it.destination_dock_ = destination_serial_ ? &mol.get<PortDock>(destination_serial_) : nullptr;
+	}
 	return it;
 }
 
 void ShippingItem::save(EditorGameBase& egbase, MapObjectSaver& mos, FileWrite& fw) {
 	fw.unsigned_8(kCurrentPacketVersion);
 	fw.unsigned_32(mos.get_object_file_index_or_zero(object_.get(egbase)));
+	fw.unsigned_32(mos.get_object_file_index_or_zero(destination_dock_.get(egbase)));
 }
 
 }  // namespace Widelands

=== modified file 'src/economy/shippingitem.h'
--- src/economy/shippingitem.h	2019-04-24 06:51:31 +0000
+++ src/economy/shippingitem.h	2019-09-07 13:04:52 +0000
@@ -63,11 +63,13 @@
 
 	private:
 		uint32_t serial_ = 0U;
+		uint32_t destination_serial_ = 0U;
 	};
 
 	void save(EditorGameBase& egbase, MapObjectSaver& mos, FileWrite& fw);
 
 private:
+	friend struct Fleet;
 	friend class PortDock;
 	friend struct Ship;
 

=== modified file 'src/economy/ware_instance.cc'
--- src/economy/ware_instance.cc	2019-05-25 10:47:18 +0000
+++ src/economy/ware_instance.cc	2019-09-07 13:04:52 +0000
@@ -107,7 +107,7 @@
 		return worker->get_location(game);
 
 	if (upcast(Ship, ship, loc)) {
-		if (PortDock* pd = ship->get_destination(game))
+		if (PortDock* pd = ship->get_current_destination(game))
 			return pd;
 
 		return ship->get_fleet()->get_arbitrary_dock();

=== modified file 'src/logic/map_objects/tribes/ship.cc'
--- src/logic/map_objects/tribes/ship.cc	2019-08-21 17:57:37 +0000
+++ src/logic/map_objects/tribes/ship.cc	2019-09-07 13:04:52 +0000
@@ -134,8 +134,8 @@
 Ship::~Ship() {
 }
 
-PortDock* Ship::get_destination(EditorGameBase& egbase) const {
-	return destination_.get(egbase);
+PortDock* Ship::get_current_destination(EditorGameBase& egbase) const {
+	return destinations_.empty() ? nullptr : destinations_.front().first.get(egbase);
 }
 
 PortDock* Ship::get_lastdock(EditorGameBase& egbase) const {
@@ -294,7 +294,7 @@
 bool Ship::ship_update_transport(Game& game, Bob::State& state) {
 	const Map& map = game.map();
 
-	PortDock* dst = get_destination(game);
+	PortDock* dst = get_current_destination(game);
 	if (!dst) {
 		// The ship has no destination, so let it sleep
 		ship_update_idle(game, state);
@@ -313,7 +313,7 @@
 		}
 
 		dst->ship_arrived(game, *this);  // This will also set the destination
-		dst = get_destination(game);
+		dst = get_current_destination(game);
 		if (dst) {
 			start_task_movetodock(game, *dst);
 		} else {
@@ -736,22 +736,208 @@
 	}
 }
 
+bool Ship::has_destination(EditorGameBase& egbase, const PortDock& pd) const {
+	for (const auto& pair : destinations_) {
+		if (pair.first.get(egbase) == &pd) {
+			return true;
+		}
+	}
+	return false;
+}
+
 /**
  * Enter a new destination port for the ship.
  * Call this after (un)loading the ship, for proper logging.
  */
-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");
+void Ship::push_destination(Game& game, PortDock& pd) {
+	for (const auto& pair : destinations_) {
+		if (pair.first.get(game) == &pd) {
+			// We're already going there
+			return;
+		}
 	}
+	destinations_.push_back(std::make_pair(OPtr<PortDock>(&pd), 1));
+	reorder_destinations(game);
+	molog("push_destination(%u): rerouted to portdock %u (carrying %" PRIuS " items)\n",
+			pd.serial(), get_current_destination(game)->serial(), items_.size());
+	pd.ship_coming(*this, true);
 	Notifications::publish(NoteShip(this, NoteShip::Action::kDestinationChanged));
 }
 
+void Ship::clear_destinations(Game& game) {
+	while (!destinations_.empty()) {
+		pop_destination(game, *destinations_.front().first.get(game));
+	}
+}
+
+/**
+ * Remove this destination from the queue
+ */
+void Ship::pop_destination(Game& game, PortDock& pd) {
+	pd.ship_coming(*this, false);
+	for (auto it = destinations_.begin(); it != destinations_.end(); ++it) {
+		if (it->first.get(game) == &pd) {
+			destinations_.erase(it);
+			reorder_destinations(game);
+			if (destinations_.empty()) {
+				molog("pop_destination(%u): no destinations and %" PRIuS " items left\n",
+						pd.serial(), items_.size());
+			} else {
+				molog("pop_destination(%u): rerouted to portdock %u (carrying %" PRIuS " items)\n",
+						pd.serial(), get_current_destination(game)->serial(), items_.size());
+			}
+			return;
+		}
+	}
+}
+
+// Recursively find the best ordering for our destinations
+static inline float prioritised_distance(Path& path, uint32_t priority, uint32_t items) {
+	return static_cast<float>(path.get_nsteps() * items) / (priority * priority);
+}
+using DestinationsQueue = std::vector<std::pair<PortDock*, uint32_t>>;
+static std::pair<DestinationsQueue, float> shortest_order(Game* game,
+                                                          Fleet* fleet,
+                                                          bool is_on_dock,
+                                                          void* start,
+                                                          const DestinationsQueue& remaining_to_visit,
+                                                          const std::map<PortDock*, uint32_t> shipping_items) {
+	const size_t nr_dests = remaining_to_visit.size();
+	assert(nr_dests > 0);
+	auto get_first_path = [game, start, remaining_to_visit, fleet, is_on_dock](Path& path, PortDock& dest) {
+		if (is_on_dock) {
+			PortDock* p = static_cast<PortDock*>(start);
+			if (p != remaining_to_visit[0].first) {
+				fleet->get_path(*p, dest, path);
+			}
+		} else {
+			static_cast<Ship*>(start)->calculate_sea_route(*game, dest, &path);
+		}
+	};
+	if (nr_dests == 1) {
+		// Recursion break: Only one portdock left
+		Path path;
+		get_first_path(path, *remaining_to_visit[0].first);
+		return std::pair<DestinationsQueue, float>(remaining_to_visit, prioritised_distance(
+				path, remaining_to_visit[0].second, shipping_items.at(remaining_to_visit[0].first)));
+	}
+
+	std::pair<DestinationsQueue, float> best_result;
+	best_result.second = std::numeric_limits<float>::max();
+	for (const auto& pair : remaining_to_visit) {
+		DestinationsQueue remaining;
+		for (const auto& p : remaining_to_visit) {
+			if (p.first != pair.first) {
+				remaining.push_back(p);
+			}
+		}
+		auto result = shortest_order(game, fleet, true, pair.first, remaining, shipping_items);
+		result.first.emplace(result.first.begin(), pair);
+		Path path;
+		get_first_path(path, *pair.first);
+		const float length = result.second + prioritised_distance(path, pair.second, shipping_items.at(pair.first));
+		if (length < best_result.second) {
+			best_result.first = result.first;
+			best_result.second = length;
+		}
+	}
+	assert(best_result.second < std::numeric_limits<float>::max());
+	assert(best_result.first.size() == nr_dests);
+	return best_result;
+}
+
+void Ship::reorder_destinations(Game& game) {
+	upcast(PortDock, pd, get_position().field->get_immovable());
+	size_t nr_dests = 0;
+	DestinationsQueue old_dq;
+	PortDock* fallback_dest = nullptr;
+	std::map<PortDock*, uint32_t> shipping_items;
+	for (const auto& pair : destinations_) {
+		PortDock* p = pair.first.get(game);
+		assert(p);
+		uint32_t nr_items = 0;
+		for (const auto& si : items_) {
+			if (si.get_destination(game) == p) {
+				++nr_items;
+			}
+		}
+		if (nr_items == 0 && p->count_waiting() == 0 && !p->expedition_started() && (!pd || pd->count_waiting(p) == 0)) {
+			fallback_dest = p;
+			// We don't need to go there anymore
+			p->ship_coming(*this, false);
+			continue;
+		}
+		old_dq.push_back(std::make_pair(p, pair.second));
+		++nr_dests;
+		shipping_items[p] = nr_items;
+	}
+	if (nr_dests <= 1) {
+		destinations_.clear();
+		if (nr_dests > 0) {
+			destinations_.push_back(old_dq[0]);
+		} else if (fallback_dest) {
+			destinations_.push_back(std::make_pair(OPtr<PortDock>(fallback_dest), 1));
+			fallback_dest->ship_coming(*this, true);
+		}
+		return;
+	}
+
+	const OPtr<PortDock> old_dest = destinations_.front().first;
+	DestinationsQueue dq = shortest_order(&game, fleet_, pd,
+			pd ? static_cast<void*>(pd) : static_cast<void*>(this), old_dq, shipping_items).first;
+	assert(dq.size() == nr_dests);
+
+	std::vector<std::pair<OPtr<PortDock>, uint32_t>> old_destinations = destinations_;
+	const size_t nr_all_old_dests = old_destinations.size();
+	destinations_.clear();
+	size_t index = 0;
+	for (const auto& pair : dq) {
+		OPtr<PortDock> optr(pair.first);
+		uint32_t priority = pair.second;
+		size_t old_index = 0;
+		for (; old_destinations[old_index].first != optr; ++old_index) {
+			assert(old_index < nr_all_old_dests);
+		}
+		if (old_index < index) {
+			priority += index - old_index;
+		}
+		destinations_.push_back(std::make_pair(optr, priority));
+		++index;
+	}
+	if (old_dest != destinations_.front().first) {
+		send_signal(game, "wakeup");
+	}
+}
+
+/**
+ * Returns an estimation for the time in arbitrary units from now until the moment when
+ * this ship will probably arrive at the given PortDock. This may change later when
+ * destinations are added or removed.
+ * Returns kInvalidDestination if we are not planning to visit this PortDock or if we are not planning
+ * to visit the given intermediate portdock earlier than the destination.
+ */
+uint32_t Ship::estimated_arrival_time(Game& game, const PortDock& dest, const PortDock* intermediate) const {
+	uint32_t time = 0;
+	const PortDock* iterator = nullptr;
+	for (const auto& pair : destinations_) {
+		Path path;
+		if (iterator) {
+			fleet_->get_path(*iterator, *pair.first.get(game), path);
+		} else {
+			calculate_sea_route(game, *pair.first.get(game), &path);
+		}
+		iterator = pair.first.get(game);
+		if (iterator == intermediate) {
+			intermediate = nullptr;
+		}
+		time += path.get_nsteps();
+		if (iterator == &dest) {
+			return intermediate ? kInvalidDestination : time;
+		}
+	}
+	return kInvalidDestination;
+}
+
 void Ship::add_item(Game& game, const ShippingItem& item) {
 	assert(items_.size() < descr().get_capacity());
 
@@ -782,23 +968,6 @@
 }
 
 /**
- * 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_) {
-		const PortDock* dest = si.get_destination(game);
-		if (dest && fleet_->is_path_favourable(here, nextdest, *dest)) {
-			items_[dst++] = si;
-		} else {
-			here.shipping_item_returned(game, si);
-		}
-	}
-	items_.resize(dst);
-}
-
-/**
  * Find a path to the dock @p pd, returns its length, and the path optionally.
  */
 uint32_t Ship::calculate_sea_route(Game& game, PortDock& pd, Path* finalpath) const {
@@ -918,6 +1087,11 @@
 /// @note only called via player command
 void Ship::exp_construct_port(Game& game, const Coords& c) {
 	assert(expedition_);
+	if (is_a(Building, game.map().get_fcoords(c).field->get_immovable())) {
+		// Another expedition ship (or an enemy player) was a second faster
+		set_ship_state_and_notify(ShipStates::kExpeditionWaiting, NoteShip::Action::kDestinationChanged);
+		return;
+	}
 	get_owner()->force_csite(c, get_owner()->tribe().port());
 
 	// Make sure that we have space to squeeze in a lumberjack
@@ -1032,7 +1206,7 @@
 	if ((draw_text & TextToDraw::kStatistics) != TextToDraw::kNone) {
 		switch (ship_state_) {
 		case (ShipStates::kTransport):
-			if (destination_.is_set()) {
+			if (!destinations_.empty()) {
 				/** TRANSLATORS: This is a ship state. The ship is currently transporting wares. */
 				statistics_string = pgettext("ship_state", "Shipping");
 			} else {
@@ -1073,25 +1247,25 @@
 void Ship::log_general_info(const EditorGameBase& egbase) const {
 	Bob::log_general_info(egbase);
 
-	molog("Ship belongs to fleet: %u\n destination: %s\n lastdock: %s\n",
+	molog("Ship belongs to fleet %u\nlastdock: %s\n",
 	      fleet_ ? fleet_->serial() : 0,
-	      (destination_.is_set()) ? (boost::format("%u (%d x %d)") % destination_.serial() %
-	                                 destination_.get(egbase)->get_positions(egbase)[0].x %
-	                                 destination_.get(egbase)->get_positions(egbase)[0].y)
-	                                   .str()
-	                                   .c_str() :
-	                                "-",
 	      (lastdock_.is_set()) ? (boost::format("%u (%d x %d)") % lastdock_.serial() %
 	                              lastdock_.get(egbase)->get_positions(egbase)[0].x %
 	                              lastdock_.get(egbase)->get_positions(egbase)[0].y)
 	                                .str()
 	                                .c_str() :
 	                             "-");
+	molog("Has %" PRIuS " destination(s):\n", destinations_.size());
+	for (const auto& pair : destinations_) {
+		molog("    · %u (%3dx%3d) (priority %u)\n",
+				pair.first.serial(), pair.first.get(egbase)->get_positions(egbase)[0].x,
+				pair.first.get(egbase)->get_positions(egbase)[0].y, pair.second);
+	}
 
 	molog("In state: %u (%s)\n", static_cast<unsigned int>(ship_state_),
 	      (expedition_) ? "expedition" : "transportation");
 
-	if (destination_.is_set() && get_position().field->get_immovable() == destination_.get(egbase)) {
+	if (!destinations_.empty() && get_position().field->get_immovable() == destinations_.front().first.get(egbase)) {
 		molog("Currently in destination portdock\n");
 	}
 
@@ -1149,7 +1323,7 @@
 ==============================
 */
 
-constexpr uint8_t kCurrentPacketVersion = 8;
+constexpr uint8_t kCurrentPacketVersion = 9;
 
 const Bob::Task* Ship::Loader::get_task(const std::string& name) {
 	if (name == "shipidle" || name == "ship")
@@ -1157,7 +1331,7 @@
 	return Bob::Loader::get_task(name);
 }
 
-void Ship::Loader::load(FileRead& fr) {
+void Ship::Loader::load(FileRead& fr, uint8_t packet_version) {
 	Bob::Loader::load(fr);
 
 	// Economy
@@ -1194,7 +1368,18 @@
 
 	shipname_ = fr.c_string();
 	lastdock_ = fr.unsigned_32();
-	destination_ = fr.unsigned_32();
+
+	if (packet_version >= 9) {
+		const uint32_t nr_dest = fr.unsigned_32();
+		for (uint32_t i = 0; i < nr_dest; ++i) {
+			const uint32_t s = fr.unsigned_32();
+			const uint32_t p = fr.unsigned_32();
+			destinations_.push_back(std::make_pair(s, p));
+		}
+	} else {
+		// TODO(Nordfriese): Remove when we break savegame compatibility
+		destinations_.push_back(std::make_pair(fr.unsigned_32(), 1));
+	}
 
 	items_.resize(fr.unsigned_32());
 	for (ShippingItem::Loader& item_loader : items_) {
@@ -1207,10 +1392,12 @@
 
 	Ship& ship = get<Ship>();
 
-	if (lastdock_)
+	if (lastdock_) {
 		ship.lastdock_ = &mol().get<PortDock>(lastdock_);
-	if (destination_)
-		ship.destination_ = &mol().get<PortDock>(destination_);
+	}
+	for (const auto& pair : destinations_) {
+		ship.destinations_.push_back(std::make_pair(&mol().get<PortDock>(pair.first), pair.second));
+	}
 
 	ship.items_.resize(items_.size());
 	for (uint32_t i = 0; i < items_.size(); ++i) {
@@ -1259,7 +1446,7 @@
 	try {
 		// The header has been peeled away by the caller
 		uint8_t const packet_version = fr.unsigned_8();
-		if (packet_version == kCurrentPacketVersion) {
+		if (packet_version >= 8 && packet_version <= kCurrentPacketVersion) {
 			try {
 				const ShipDescr* descr = nullptr;
 				// Removing this will break the test suite
@@ -1267,7 +1454,7 @@
 				const DescriptionIndex& ship_index = egbase.tribes().safe_ship_index(name);
 				descr = egbase.tribes().get_ship_descr(ship_index);
 				loader->init(egbase, mol, descr->create_object());
-				loader->load(fr);
+				loader->load(fr, packet_version);
 			} catch (const WException& e) {
 				throw GameDataError("Failed to load ship: %s", e.what());
 			}
@@ -1316,7 +1503,11 @@
 
 	fw.string(shipname_);
 	fw.unsigned_32(mos.get_object_file_index_or_zero(lastdock_.get(egbase)));
-	fw.unsigned_32(mos.get_object_file_index_or_zero(destination_.get(egbase)));
+	fw.unsigned_32(destinations_.size());
+	for (const auto& pair : destinations_) {
+		fw.unsigned_32(mos.get_object_file_index_or_zero(pair.first.get(egbase)));
+		fw.unsigned_32(pair.second);
+	}
 
 	fw.unsigned_32(items_.size());
 	for (ShippingItem& shipping_item : items_) {

=== modified file 'src/logic/map_objects/tribes/ship.h'
--- src/logic/map_objects/tribes/ship.h	2019-04-24 06:51:31 +0000
+++ src/logic/map_objects/tribes/ship.h	2019-09-07 13:04:52 +0000
@@ -80,6 +80,8 @@
 
 constexpr int32_t kShipInterval = 1500;
 
+constexpr uint32_t kInvalidDestination = std::numeric_limits<uint32_t>::max();
+
 /**
  * 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
@@ -96,7 +98,8 @@
 
 	// Returns the current destination or nullptr if there is no current
 	// destination.
-	PortDock* get_destination(EditorGameBase& egbase) const;
+	PortDock* get_current_destination(EditorGameBase& egbase) const;
+	bool has_destination(EditorGameBase&, const PortDock&) const;
 
 	// Returns the last visited portdock of this ship or nullptr if there is none or
 	// the last visited was removed.
@@ -106,7 +109,13 @@
 		return economy_;
 	}
 	void set_economy(Game&, Economy* e);
-	void set_destination(PortDock*);
+	void push_destination(Game&, PortDock&);
+	void pop_destination(Game&, PortDock&);
+	void clear_destinations(Game&);
+	uint32_t estimated_arrival_time(Game&, const PortDock& dest, const PortDock* intermediate = nullptr) const;
+	size_t count_destinations() const {
+		return destinations_.size();
+	}
 
 	void init_auto_task(Game&) override;
 
@@ -130,7 +139,6 @@
 
 	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
@@ -270,11 +278,17 @@
 	Fleet* fleet_;
 	Economy* economy_;
 	OPtr<PortDock> lastdock_;
-	OPtr<PortDock> destination_;
 	std::vector<ShippingItem> items_;
 	ShipStates ship_state_;
 	std::string shipname_;
 
+	// Our destinations in the order on which we are planning to visit them.
+	// When destinations are added or removed, the whole list will be reordered under
+	// the aspect of efficiency. Every time an entry is postponed, its priority will
+	// be increased to make it less likely that it will never be visited.
+	std::vector<std::pair<OPtr<PortDock>, uint32_t>> destinations_;
+	void reorder_destinations(Game&);
+
 	struct Expedition {
 		~Expedition();
 
@@ -294,14 +308,14 @@
 
 		const Task* get_task(const std::string& name) override;
 
-		void load(FileRead& fr);
+		void load(FileRead& fr, uint8_t);
 		void load_pointers() override;
 		void load_finish() override;
 
 	private:
 		// Initialize everything to make cppcheck happy.
 		uint32_t lastdock_ = 0U;
-		uint32_t destination_ = 0U;
+		std::vector<std::pair<uint32_t, uint32_t>> destinations_;
 		Serial economy_serial_;
 		ShipStates ship_state_ = ShipStates::kTransport;
 		std::string shipname_;

=== modified file 'src/scripting/lua_map.cc'
--- src/scripting/lua_map.cc	2019-08-21 17:57:37 +0000
+++ src/scripting/lua_map.cc	2019-09-07 13:04:52 +0000
@@ -5696,7 +5696,7 @@
 // UNTESTED
 int LuaShip::get_destination(lua_State* L) {
 	EditorGameBase& egbase = get_egbase(L);
-	return upcasted_map_object_to_lua(L, get(L, egbase)->get_destination(egbase));
+	return upcasted_map_object_to_lua(L, get(L, egbase)->get_current_destination(egbase));
 }
 
 /* RST

=== modified file 'src/wui/seafaring_statistics_menu.cc'
--- src/wui/seafaring_statistics_menu.cc	2019-07-31 16:43:58 +0000
+++ src/wui/seafaring_statistics_menu.cc	2019-09-07 13:04:52 +0000
@@ -260,7 +260,7 @@
 	ShipFilterStatus status = ShipFilterStatus::kAll;
 	switch (state) {
 	case Widelands::Ship::ShipStates::kTransport:
-		if (ship.get_destination(iplayer().game()) != nullptr) {
+		if (ship.get_current_destination(iplayer().game())) {
 			status = ShipFilterStatus::kShipping;
 		} else {
 			status = ShipFilterStatus::kIdle;

=== modified file 'src/wui/shipwindow.cc'
--- src/wui/shipwindow.cc	2019-02-23 11:00:49 +0000
+++ src/wui/shipwindow.cc	2019-09-07 13:04:52 +0000
@@ -233,7 +233,7 @@
 	}
 	bool can_act = igbase_.can_act(ship->owner().player_number());
 
-	btn_destination_->set_enabled(ship->get_destination(igbase_.egbase()));
+	btn_destination_->set_enabled(ship->get_current_destination(igbase_.egbase()));
 	btn_sink_->set_enabled(can_act);
 
 	display_->clear();
@@ -311,7 +311,7 @@
 	if (ship == nullptr) {
 		return;
 	}
-	if (PortDock* destination = ship->get_destination(igbase_.egbase())) {
+	if (PortDock* destination = ship->get_current_destination(igbase_.egbase())) {
 		igbase_.map_view()->scroll_to_field(
 		   destination->get_warehouse()->get_position(), MapView::Transition::Smooth);
 	}

=== added file 'test/maps/expedition.wmf/scripting/test_no_double_colonizing.lua'
--- test/maps/expedition.wmf/scripting/test_no_double_colonizing.lua	1970-01-01 00:00:00 +0000
+++ test/maps/expedition.wmf/scripting/test_no_double_colonizing.lua	2019-09-07 13:04:52 +0000
@@ -0,0 +1,36 @@
+run(function()
+   port:set_wares {
+      blackwood = 100,
+      log = 100,
+      gold = 20,
+      granite = 20,
+      grout = 20,
+      iron = 20,
+      reed = 20,
+   }
+   port:set_workers("barbarians_builder", 5)
+
+   create_two_ships()
+   port:start_expedition()
+   wait_for_message("Expedition")
+   port:start_expedition()
+   wait_for_message("Expedition")
+
+   first_ship.island_explore_direction="ccw"
+   sleep(2000)
+   assert_equal("ccw", first_ship.island_explore_direction)
+   wait_for_message("Port Space")
+   second_ship.island_explore_direction="ccw"
+   sleep(2000)
+   assert_equal("ccw", second_ship.island_explore_direction)
+   wait_for_message("Port Space")
+
+   second_ship:build_colonization_port()
+   sleep(5000)
+   first_ship:build_colonization_port()
+   -- This test is to check that there won't be any crash now
+   wait_for_message("Port")
+
+   print("# All Tests passed.")
+   wl.ui.MapView():close()
+end)