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

Proposed by Benedikt Straub on 2019-08-10
Status: Work in progress
Proposed branch: lp:~widelands-dev/widelands/new-shipping
Merge into: lp:widelands
Diff against target: 1331 lines (+580/-227)
13 files modified
src/economy/fleet.cc (+150/-96)
src/economy/fleet.h (+4/-2)
src/economy/portdock.cc (+106/-65)
src/economy/portdock.h (+6/-3)
src/economy/shippingitem.cc (+13/-3)
src/economy/shippingitem.h (+2/-0)
src/economy/ware_instance.cc (+1/-1)
src/logic/map_objects/tribes/ship.cc (+238/-47)
src/logic/map_objects/tribes/ship.h (+20/-6)
src/scripting/lua_map.cc (+1/-1)
src/wui/seafaring_statistics_menu.cc (+1/-1)
src/wui/shipwindow.cc (+2/-2)
test/maps/expedition.wmf/scripting/test_no_double_colonizing.lua (+36/-0)
To merge this branch: bzr merge lp:~widelands-dev/widelands/new-shipping
Reviewer Review Type Date Requested Status
Klaus Halfmann 2019-08-10 Needs Fixing on 2019-08-27
Review via email: mp+371155@code.launchpad.net

Commit message

New planning-ahead ship scheduling algorithm

Description of the change

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.

To post a comment you must log in.
9136. By Nordfriese on 2019-08-10

Fix cornercase found by travis

9137. By Nordfriese on 2019-08-10

Another edge case

bunnybot (widelandsofficial) wrote :

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) wrote :

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) wrote :

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) wrote :
Download full text (3.6 KiB)

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

Read more...

review: Needs Fixing (regression tests)
9138. By Nordfriese on 2019-08-11

Addressed review

Benedikt Straub (nordfriese) wrote :

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) wrote :

> 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) wrote :

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.

9139. By Nordfriese on 2019-08-11

Fix compiler warning

Klaus Halfmann (klaus-halfmann) wrote :

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) wrote :

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) wrote :

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.

9140. By Nordfriese on 2019-08-12

Fix compiler warning

bunnybot (widelandsofficial) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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

9141. By Nordfriese on 2019-08-15

Replace some raw pointers with OPtr

9142. By Nordfriese on 2019-08-15

compile error

Klaus Halfmann (klaus-halfmann) wrote :

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

9143. By Nordfriese on 2019-08-16

debug log output

Benedikt Straub (nordfriese) wrote :

I added some debug output, please try again…

bunnybot (widelandsofficial) wrote :

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) wrote :

I added the complete output to:

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

Will try a debugger now ....

9144. By Nordfriese on 2019-08-16

Don´t modify list while iterating over it

Benedikt Straub (nordfriese) wrote :

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

Klaus Halfmann (klaus-halfmann) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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

Klaus Halfmann (klaus-halfmann) wrote :

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) wrote :

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) wrote :

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?

9145. By Nordfriese on 2019-08-27

Try to fix an assert

Benedikt Straub (nordfriese) wrote :

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) wrote :

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

9146. By Nordfriese on 2019-08-27

Fixed a bug where two ships could build two ports at the same spot

Klaus Halfmann (klaus-halfmann) wrote :

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

9147. By Nordfriese on 2019-08-27

Detour calculation fix in Fleet::check_push_destination

Benedikt Straub (nordfriese) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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.

9148. By Nordfriese on 2019-08-29

Fixed detour calculation and improved double-colonizing check

Benedikt Straub (nordfriese) wrote :

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

bunnybot (widelandsofficial) wrote :

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) wrote :

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) wrote :

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?

9149. By Nordfriese on 2019-09-03

Never add shipping items without pushing their destination

9150. By Nordfriese on 2019-09-03

Removed invalid assert

Benedikt Straub (nordfriese) wrote :

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) wrote :

I have added some comments

9151. By Nordfriese on 2019-09-07

Addressed code review

9152. By Nordfriese on 2019-09-07

Merged trunk

Unmerged revisions

9152. By Nordfriese on 2019-09-07

Merged trunk

9151. By Nordfriese on 2019-09-07

Addressed code review

9150. By Nordfriese on 2019-09-03

Removed invalid assert

9149. By Nordfriese on 2019-09-03

Never add shipping items without pushing their destination

9148. By Nordfriese on 2019-08-29

Fixed detour calculation and improved double-colonizing check

9147. By Nordfriese on 2019-08-27

Detour calculation fix in Fleet::check_push_destination

9146. By Nordfriese on 2019-08-27

Fixed a bug where two ships could build two ports at the same spot

9145. By Nordfriese on 2019-08-27

Try to fix an assert

9144. By Nordfriese on 2019-08-16

Don´t modify list while iterating over it

9143. By Nordfriese on 2019-08-16

debug log output

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'src/economy/fleet.cc'
2--- src/economy/fleet.cc 2019-04-24 15:11:23 +0000
3+++ src/economy/fleet.cc 2019-09-07 13:04:52 +0000
4@@ -336,7 +336,7 @@
5 uint32_t Fleet::count_ships_heading_here(EditorGameBase& egbase, PortDock* port) const {
6 uint32_t ships_on_way = 0;
7 for (uint16_t s = 0; s < ships_.size(); s += 1) {
8- if (ships_[s]->get_destination(egbase) == port) {
9+ if (ships_[s]->get_current_destination(egbase) == port) {
10 ships_on_way += 1;
11 }
12 }
13@@ -400,8 +400,8 @@
14 if (upcast(Game, game, &egbase))
15 ship->set_economy(*game, nullptr);
16
17- if (ship->get_destination(egbase)) {
18- ship->get_destination(egbase)->ship_coming(false);
19+ if (ship->get_current_destination(egbase)) {
20+ ship->get_current_destination(egbase)->ship_coming(*ship, false);
21 update(egbase);
22 }
23
24@@ -633,6 +633,53 @@
25 }
26 }
27
28+/*
29+ * Helper function for assigning ships to ports in need of a ship.
30+ * Penalizes the given ship if it is transporting wares.
31+ * A small detour to the given portdock is penalized very slightly, a longer detour drastically.
32+ * Returns false if the detour would be so long that this ship must not even be considered for serving this port.
33+ */
34+bool Fleet::penalize_route(Game& game, PortDock& p, const Ship& s, uint32_t* route_length) {
35+ const uint32_t real_length = *route_length;
36+ uint32_t malus = 1;
37+ uint32_t index = 0;
38+ PortDock* iterator = nullptr;
39+ uint32_t shortest_detour = std::numeric_limits<uint32_t>::max();
40+ uint32_t best_index = std::numeric_limits<uint32_t>::max();
41+ for (const auto& pair : s.destinations_) {
42+ PortDock* pd = pair.first.get(game);
43+ Path path;
44+ uint32_t detour;
45+ if (iterator == &p) {
46+ detour = 0;
47+ } else if (iterator) {
48+ get_path(*iterator, p, path);
49+ detour = path.get_nsteps();
50+ } else {
51+ s.calculate_sea_route(game, p, &path);
52+ detour = path.get_nsteps();
53+ }
54+ if (&p != pd) {
55+ get_path(p, *pd, path);
56+ detour += path.get_nsteps();
57+ }
58+ if (detour < shortest_detour) {
59+ shortest_detour = detour;
60+ best_index = index;
61+ }
62+ malus += pair.second;
63+ iterator = pd;
64+ ++index;
65+ }
66+ *route_length += shortest_detour * best_index;
67+ if (*route_length + shortest_detour > real_length * malus) {
68+ // Unreasonably long detour
69+ return false;
70+ }
71+ *route_length *= malus;
72+ return true;
73+}
74+
75 /**
76 * Act callback updates ship scheduling of idle ships.
77 *
78@@ -665,13 +712,14 @@
79 bool waiting = true;
80
81 for (Ship* s : ships_) {
82- if (s->get_destination(game)) {
83- if (s->get_destination(game) == p) {
84+ bool fallback = false;
85+ if (s->get_current_destination(game)) {
86+ if (s->has_destination(game, *p)) {
87 waiting = false;
88 --waiting_ports;
89 break;
90 }
91- continue; // The ship already has a destination
92+ fallback = true; // The ship already has a destination
93 }
94 if (s->get_ship_state() != Ship::ShipStates::kTransport) {
95 continue; // Ship is not available, e.g. in expedition
96@@ -699,6 +747,11 @@
97 if (route_length == kRouteNotCalculated) {
98 route_length = s->calculate_sea_route(game, *p);
99 }
100+ if (fallback) {
101+ if (!penalize_route(game, *p, *s, &route_length)) {
102+ continue;
103+ }
104+ }
105
106 if (route_length < shortest_dist) {
107 shortest_dist = route_length;
108@@ -708,7 +761,7 @@
109
110 if (waiting && closest_ship) {
111 --waiting_ports;
112- closest_ship->set_destination(p);
113+ closest_ship->push_destination(game, *p);
114 closest_ship->send_signal(game, "wakeup");
115 }
116 }
117@@ -721,7 +774,7 @@
118
119 // Deal with edge-case of losing destination before reaching it
120 for (Ship* s : ships_) {
121- if (s->get_destination(game)) {
122+ if (s->get_current_destination(game)) {
123 continue; // The ship has a destination
124 }
125 if (s->get_ship_state() != Ship::ShipStates::kTransport) {
126@@ -744,107 +797,108 @@
127 }
128
129 if (closest_port) {
130- s->set_destination(closest_port);
131+ s->push_destination(game, *closest_port);
132 s->send_signal(game, "wakeup");
133 }
134 }
135 }
136
137 /**
138- * For the given three consecutive ports, decide if their path is favourable or not.
139- * \return true if the path from start to finish >= the path from middle to finish
140+ * Tell the given ship where to go next. May push any number of destinations.
141 */
142-bool Fleet::is_path_favourable(const PortDock& start,
143- const PortDock& middle,
144- const PortDock& finish) {
145- if (&middle != &finish) {
146- Path path_start_to_finish;
147- Path path_middle_to_finish;
148-#ifndef NDEBUG
149- assert(get_path(start, finish, path_start_to_finish));
150-#else
151- get_path(start, finish, path_start_to_finish);
152-#endif
153- if (get_path(middle, finish, path_middle_to_finish)) {
154- if (path_middle_to_finish.get_nsteps() > path_start_to_finish.get_nsteps()) {
155- return false;
156+void Fleet::push_next_destinations(Game& game, Ship& ship, const PortDock& from_port) {
157+ std::vector<std::pair<PortDock*, uint32_t>> destinations; // Destinations and the number of items waiting to go there
158+ uint32_t total_items = ship.get_nritems(); // All waiting and shipping items
159+ uint32_t waiting_items = 0; // Items that have a destination which this ship is not currently planning to visit
160+ // Count how many items are waiting to go to each portdock
161+ for (auto& it : from_port.waiting_) {
162+ if (PortDock* pd = it.destination_dock_.get(game)) {
163+ ++total_items;
164+ if (ship.has_destination(game, *pd)) {
165+ continue;
166+ }
167+ ++waiting_items;
168+ bool found = false;
169+ for (auto& pair : destinations) {
170+ if (pair.first == pd) {
171+ ++pair.second;
172+ found = true;
173+ break;
174+ }
175+ }
176+ if (!found) {
177+ destinations.push_back(std::make_pair(pd, 1));
178 }
179 }
180 }
181- return true; // default
182+ assert(waiting_items <= total_items);
183+ if (waiting_items == 0) {
184+ // Nothing to do
185+ return;
186+ }
187+ total_items -= waiting_items;
188+ // For each destination, decide whether to tell the ship to visit it
189+ // or whether it would be better to wait for another ship
190+ for (const auto& destpair : destinations) {
191+ check_push_destination(game, ship, from_port, *destpair.first, destpair.second * total_items);
192+ }
193 }
194
195-/**
196- * For the given ship, go through all ports of this fleet
197- * and find the one with the best score.
198- * \return that port
199+/*
200+ * Helper function for push_next_destinations():
201+ * Send the given ship to the given portdock (with the given penalty factor)
202+ * if the detour this would mean for the ship is not too long
203 */
204-PortDock* Fleet::find_next_dest(Game& game, const Ship& ship, const PortDock& from_port) {
205- PortDock* best_port = nullptr;
206- float best_score = 0.0f;
207-
208- for (PortDock* p : ports_) {
209- if (p == &from_port) {
210- continue; // same port
211- }
212-
213- float score = 0.0f;
214- WareInstance* ware;
215- Worker* worker;
216-
217- // Score for wares/workers onboard that ship for that port
218- for (const ShippingItem& si : ship.items_) {
219- if (si.get_destination(game) == p) {
220- si.get(game, &ware, &worker);
221- if (ware) {
222- score += 1; // TODO(ypopezios): increase by ware's importance
223- } else { // worker
224- score += 4;
225- }
226- }
227- }
228-
229- // Score for wares/workers waiting at that port
230- for (const ShippingItem& si : from_port.waiting_) {
231- if (si.get_destination(game) == p) {
232- si.get(game, &ware, &worker);
233- if (ware) {
234- score += 1; // TODO(ypopezios): increase by ware's importance
235- } else { // worker
236- score += 4;
237- }
238- }
239- }
240-
241- if (score == 0.0f && p->get_need_ship() == 0) {
242- continue; // empty ship to empty port
243- }
244-
245- // Here we get distance ship->port
246- uint32_t route_length = kRouteNotCalculated;
247-
248- // Get precalculated distance if the ship is at a port
249- {
250- Path precalculated_path;
251- if (get_path(from_port, *p, precalculated_path)) { // try to use precalculated path
252- route_length = precalculated_path.get_nsteps();
253- }
254- }
255-
256- // Get distance for when the ship is not at a port (should not happen frequently)
257- if (route_length == kRouteNotCalculated) {
258- route_length = ship.calculate_sea_route(game, *p);
259- }
260-
261- score = (score + 1.0f) * (score + p->get_need_ship());
262- score = score * (1.0f - route_length / (score + route_length));
263- if (score > best_score) {
264- best_score = score;
265- best_port = p;
266- }
267- }
268-
269- return best_port;
270+void Fleet::check_push_destination(Game& game, Ship& ship,
271+ const PortDock& from_port, PortDock& destination, uint32_t penalty_factor) {
272+ assert(!ship.has_destination(game, destination));
273+ Path path;
274+ get_path(from_port, destination, path);
275+ const uint32_t direct_route = path.get_nsteps();
276+ assert(direct_route);
277+ uint32_t malus = 1;
278+ uint32_t shortest_detour = std::numeric_limits<uint32_t>::max();
279+ uint32_t best_index = std::numeric_limits<uint32_t>::max();
280+ if (ship.destinations_.empty()) {
281+ // Idle ships are preferred
282+ best_index = 0;
283+ malus = 0;
284+ shortest_detour = 0;
285+ } else {
286+ const PortDock* iterator = &from_port;
287+ uint32_t index = 0;
288+ // This ship is going somewhere else, penalize it's priority for this order by
289+ // the detour, the number of items it's shipping and the number of items waiting here
290+ for (const auto& pair : ship.destinations_) {
291+ const PortDock* pd = pair.first.get(game);
292+ uint32_t detour = 0;
293+
294+ assert(iterator != pd);
295+ get_path(*iterator, *pd, path);
296+ const uint32_t base_length = path.get_nsteps();
297+
298+ assert(iterator != &destination);
299+ get_path(*iterator, destination, path);
300+ detour += path.get_nsteps();
301+
302+ assert(pd != &destination);
303+ get_path(destination, *pd, path);
304+ detour += path.get_nsteps();
305+
306+ detour -= std::min(detour, base_length);
307+ if (detour < shortest_detour) {
308+ shortest_detour = detour;
309+ best_index = index;
310+ }
311+ malus += pair.second;
312+ iterator = pd;
313+ ++index;
314+ }
315+ }
316+ if (shortest_detour * malus * best_index <= direct_route * penalty_factor) {
317+ // Send this ship if the penalty is not too high
318+ ship.push_destination(game, destination);
319+ }
320 }
321
322 void Fleet::log_general_info(const EditorGameBase& egbase) const {
323
324=== modified file 'src/economy/fleet.h'
325--- src/economy/fleet.h 2019-04-24 06:51:31 +0000
326+++ src/economy/fleet.h 2019-09-07 13:04:52 +0000
327@@ -121,6 +121,9 @@
328 PortPath& portpath_bidir(uint32_t i, uint32_t j, bool& reverse);
329 const PortPath& portpath_bidir(uint32_t i, uint32_t j, bool& reverse) const;
330
331+ bool penalize_route(Game&, PortDock&, const Ship&, uint32_t*);
332+ void check_push_destination(Game&, Ship&, const PortDock&, PortDock&, uint32_t);
333+
334 std::vector<Ship*> ships_;
335 std::vector<PortDock*> ports_;
336
337@@ -155,8 +158,7 @@
338 void save(EditorGameBase&, MapObjectSaver&, FileWrite&) override;
339
340 static MapObject::Loader* load(EditorGameBase&, MapObjectLoader&, FileRead&);
341- bool is_path_favourable(const PortDock& start, const PortDock& middle, const PortDock& finish);
342- PortDock* find_next_dest(Game&, const Ship&, const PortDock& from_port);
343+ void push_next_destinations(Game&, Ship&, const PortDock& from_port);
344 };
345
346 } // namespace Widelands
347
348=== modified file 'src/economy/portdock.cc'
349--- src/economy/portdock.cc 2019-07-01 14:58:07 +0000
350+++ src/economy/portdock.cc 2019-09-07 13:04:52 +0000
351@@ -56,7 +56,6 @@
352 : PlayerImmovable(g_portdock_descr),
353 fleet_(nullptr),
354 warehouse_(wh),
355- ships_coming_(0),
356 expedition_ready_(false) {
357 }
358
359@@ -118,7 +117,7 @@
360 }
361
362 uint32_t PortDock::get_need_ship() const {
363- return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_ + 1);
364+ return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_.size() + 1);
365 }
366
367 /**
368@@ -198,6 +197,13 @@
369 for (ShippingItem& shipping_item : waiting_) {
370 shipping_item.remove(*game);
371 }
372+ while (!ships_coming_.empty()) {
373+ if (Ship* ship = ships_coming_.begin()->get(*game)) {
374+ ship->pop_destination(*game, *this);
375+ } else {
376+ ships_coming_.erase(ships_coming_.begin());
377+ }
378+ }
379 }
380
381 if (fleet_)
382@@ -288,7 +294,7 @@
383
384 // Destination might have vanished or be in another economy altogether.
385 if (dst && dst->get_economy() == get_economy()) {
386- if (ships_coming_ <= 0) {
387+ if (ships_coming_.empty()) {
388 set_need_ship(game, true);
389 }
390 } else {
391@@ -320,11 +326,17 @@
392 /**
393 * A ship changed destination and is now coming to the dock. Increase counter for need_ship.
394 */
395-void PortDock::ship_coming(bool affirmative) {
396+void PortDock::ship_coming(Ship& ship, bool affirmative) {
397+ OPtr<Ship> s(&ship);
398 if (affirmative) {
399- ++ships_coming_;
400+ if (ships_coming_.find(s) == ships_coming_.end()) {
401+ ships_coming_.insert(s);
402+ }
403 } else {
404- --ships_coming_;
405+ auto it = ships_coming_.find(s);
406+ if (it != ships_coming_.end()) {
407+ ships_coming_.erase(it);
408+ }
409 }
410 }
411
412@@ -332,14 +344,12 @@
413 * A ship has arrived at the dock. Set its next destination and load it accordingly.
414 */
415 void PortDock::ship_arrived(Game& game, Ship& ship) {
416- ship_coming(false);
417-
418 if (expedition_ready_) {
419 assert(expedition_bootstrap_ != nullptr);
420
421 // Only use an empty ship.
422- if (ship.get_nritems() < 1) {
423- ship.set_destination(nullptr);
424+ if (ship.get_nritems() == 0) {
425+ ship.clear_destinations(game);
426 // Load the ship
427 std::vector<Worker*> workers;
428 std::vector<WareInstance*> wares;
429@@ -363,11 +373,10 @@
430 }
431 }
432
433- // Decide where the arrived ship will go next
434- PortDock* next_port = fleet_->find_next_dest(game, ship, *this);
435- if (next_port) {
436- // Unload any wares/workers onboard the departing ship which are not favored by next dest
437- ship.unload_unfit_items(game, *this, *next_port);
438+ ship.pop_destination(game, *this);
439+ fleet_->push_next_destinations(game, ship, *this);
440+ if (ship.get_current_destination(game)) {
441+ load_wares(game, ship);
442 }
443 #ifndef NDEBUG
444 else {
445@@ -375,51 +384,64 @@
446 }
447 #endif
448
449- // Check for items with invalid destination. TODO(ypopezios): Prevent invalid destinations
450- for (auto si_it = waiting_.begin(); si_it != waiting_.end(); ++si_it) {
451- if (!si_it->get_destination(game)) {
452- // Invalid destination. Carry the item back into the warehouse
453- // TODO(Nordfriese): This readds the invalid item to the list
454- si_it->set_location(game, warehouse_);
455- si_it->end_shipping(game);
456- si_it = waiting_.erase(si_it);
457- }
458- }
459-
460- if (!next_port) {
461- ship.set_destination(nullptr);
462- return; // no need to load anything
463- }
464-
465- // Then load the remaining capacity of the departing ship with relevant items
466- uint32_t remaining_capacity = ship.descr().get_capacity() - ship.get_nritems();
467-
468- // Firstly load the wares/workers which go to chosen destination
469- for (auto si_it = waiting_.begin(); si_it != waiting_.end() && remaining_capacity > 0; ++si_it) {
470- if (si_it->get_destination(game) == next_port) {
471- ship.add_item(game, *si_it);
472- si_it = waiting_.erase(si_it);
473- --remaining_capacity;
474- }
475- }
476-
477- // Then load any wares/workers favored by the chosen destination
478- for (auto si_it = waiting_.begin(); si_it != waiting_.end() && remaining_capacity > 0; ++si_it) {
479- const PortDock* dest = si_it->get_destination(game);
480- if (dest && fleet_->is_path_favourable(*this, *next_port, *dest)) {
481- ship.add_item(game, *si_it);
482- si_it = waiting_.erase(si_it);
483- --remaining_capacity;
484- }
485- }
486-
487- ship.set_destination(next_port);
488 set_need_ship(game, !waiting_.empty());
489 }
490
491+void PortDock::load_wares(Game& game, Ship& ship) {
492+ uint32_t free_capacity = ship.descr().get_capacity() - ship.get_nritems();
493+ std::unordered_map<const PortDock*, bool> destination_check;
494+ for (auto it = waiting_.begin(); it != waiting_.end() && free_capacity;) {
495+ PortDock* dest = it->destination_dock_.get(game);
496+ assert(dest);
497+ assert(dest != this);
498+ // Decide whether to load this item
499+ bool load_item;
500+ auto dc = destination_check.find(dest);
501+ if (dc != destination_check.end()) {
502+ load_item = dc->second;
503+ } else {
504+ uint32_t time = ship.estimated_arrival_time(game, *dest);
505+ Path direct_route;
506+ fleet_->get_path(*this, *dest, direct_route);
507+ if (time == kInvalidDestination) {
508+ time = direct_route.get_nsteps();
509+ }
510+ for (const OPtr<Ship>& ship_ptr : ships_coming_) {
511+ Ship* s = ship_ptr.get(game);
512+ assert(s);
513+ uint32_t t = s->estimated_arrival_time(game, *dest, this);
514+ if (t == kInvalidDestination) {
515+ // The ship is not planning to go there yet, perhaps we can ask for a detour?
516+ t = s->estimated_arrival_time(game, *this);
517+ assert(s->count_destinations() >= 1);
518+ if (time > t + static_cast<int32_t>(direct_route.get_nsteps() * s->count_destinations())) {
519+ time = kInvalidDestination;
520+ break;
521+ }
522+ } else if (t < time) {
523+ // A ship is coming that is planning to visit the ware's destination sooner than this one
524+ time = kInvalidDestination;
525+ break;
526+ }
527+ }
528+ load_item = time < kInvalidDestination;
529+ destination_check.emplace(dest, load_item);
530+ }
531+ if (load_item) {
532+ if (!ship.has_destination(game, *dest)) {
533+ ship.push_destination(game, *dest);
534+ }
535+ ship.add_item(game, *it);
536+ it = waiting_.erase(it);
537+ --free_capacity;
538+ } else {
539+ ++it;
540+ }
541+ }
542+}
543+
544 void PortDock::set_need_ship(Game& game, bool need) {
545 if (need && fleet_) {
546- molog("trigger fleet update\n");
547 fleet_->update(game);
548 }
549 }
550@@ -449,8 +471,18 @@
551
552 /**
553 * Return the number of wares or workers waiting at the dock.
554+ * If a destination dock is specified, count only items heading for this destination.
555 */
556-uint32_t PortDock::count_waiting() const {
557+uint32_t PortDock::count_waiting(const PortDock* dest) const {
558+ if (dest) {
559+ uint32_t w = 0;
560+ for (const ShippingItem& si : waiting_) {
561+ if (si.destination_dock_.serial() == dest->serial()) {
562+ ++w;
563+ }
564+ }
565+ return w;
566+ }
567 return waiting_.size();
568 }
569
570@@ -504,7 +536,7 @@
571 }
572 }
573
574-constexpr uint8_t kCurrentPacketVersion = 4;
575+constexpr uint8_t kCurrentPacketVersion = 5;
576
577 PortDock::Loader::Loader() : warehouse_(0) {
578 }
579@@ -523,15 +555,18 @@
580 pd.set_position(egbase(), pd.dockpoints_[i]);
581 }
582
583- pd.ships_coming_ = fr.unsigned_8();
584-
585- // TODO(GunChleoc): Savegame compatibility Build 20
586- if (packet_version < 4) {
587- pd.ships_coming_ = 0;
588+ if (packet_version >= 5) {
589+ const uint32_t ships = fr.unsigned_32();
590+ for (uint32_t i = 0; i < ships; ++i) {
591+ ships_coming_.insert(fr.unsigned_32());
592+ }
593+ } else {
594+ // TODO(GunChleoc): Savegame compatibility Build 20
595+ fr.unsigned_8();
596 for (const Serial ship_serial : pd.owner().ships()) {
597 Ship* ship = dynamic_cast<Ship*>(egbase().objects().get_object(ship_serial));
598- if (ship->get_destination(egbase())->serial() == pd.serial()) {
599- ++pd.ships_coming_;
600+ if (ship->has_destination(egbase(), pd)) {
601+ ships_coming_.insert(ship_serial);
602 }
603 }
604 }
605@@ -554,6 +589,9 @@
606 PortDock& pd = get<PortDock>();
607 pd.warehouse_ = &mol().get<Warehouse>(warehouse_);
608
609+ for (Serial s : ships_coming_) {
610+ pd.ships_coming_.insert(OPtr<Ship>(&mol().get<Ship>(s)));
611+ }
612 for (uint32_t i = 0; i < waiting_.size(); ++i) {
613 pd.waiting_.push_back(waiting_[i].get(mol()));
614 }
615@@ -609,7 +647,10 @@
616 write_coords_32(&fw, coords);
617 }
618
619- fw.unsigned_8(ships_coming_);
620+ fw.unsigned_32(ships_coming_.size());
621+ for (const OPtr<Ship>& s : ships_coming_) {
622+ fw.unsigned_32(mos.get_object_file_index(*s.get(egbase)));
623+ }
624
625 fw.unsigned_32(waiting_.size());
626 for (ShippingItem& shipping_item : waiting_) {
627
628=== modified file 'src/economy/portdock.h'
629--- src/economy/portdock.h 2019-07-05 11:16:24 +0000
630+++ src/economy/portdock.h 2019-09-07 13:04:52 +0000
631@@ -109,13 +109,13 @@
632
633 void shipping_item_arrived(Game&, ShippingItem&);
634 void shipping_item_returned(Game&, ShippingItem&);
635- void ship_coming(bool affirmative);
636+ void ship_coming(Ship&, bool affirmative);
637 void ship_arrived(Game&, Ship&);
638
639 void log_general_info(const EditorGameBase&) const override;
640
641 uint32_t count_waiting(WareWorker waretype, DescriptionIndex wareindex) const;
642- uint32_t count_waiting() const;
643+ uint32_t count_waiting(const PortDock* = nullptr) const;
644
645 // Returns true if a expedition is started or ready to be send out.
646 bool expedition_started() const;
647@@ -143,11 +143,13 @@
648 void update_shippingitem(Game&, std::list<ShippingItem>::iterator);
649 void set_need_ship(Game&, bool need);
650
651+ void load_wares(Game&, Ship&);
652+
653 Fleet* fleet_;
654 Warehouse* warehouse_;
655 PositionList dockpoints_;
656 std::list<ShippingItem> waiting_;
657- uint8_t ships_coming_;
658+ std::set<OPtr<Ship>> ships_coming_;
659 bool expedition_ready_;
660
661 std::unique_ptr<ExpeditionBootstrap> expedition_bootstrap_;
662@@ -165,6 +167,7 @@
663 private:
664 uint32_t warehouse_;
665 std::vector<ShippingItem::Loader> waiting_;
666+ std::set<Serial> ships_coming_;
667 };
668
669 public:
670
671=== modified file 'src/economy/shippingitem.cc'
672--- src/economy/shippingitem.cc 2019-04-24 06:51:31 +0000
673+++ src/economy/shippingitem.cc 2019-09-07 13:04:52 +0000
674@@ -139,13 +139,20 @@
675 }
676 }
677
678-constexpr uint16_t kCurrentPacketVersion = 1;
679+constexpr uint16_t kCurrentPacketVersion = 2;
680
681 void ShippingItem::Loader::load(FileRead& fr) {
682 try {
683 uint8_t packet_version = fr.unsigned_8();
684- if (packet_version == kCurrentPacketVersion) {
685+ if (packet_version <= kCurrentPacketVersion) {
686 serial_ = fr.unsigned_32();
687+ if (packet_version >= 2) {
688+ destination_serial_ = fr.unsigned_32();
689+ } else {
690+ // TODO(Nordfriese): Remove when we break savegame compatibility
691+ log("WARNING: Loading shippingitem with possible nullptr destination, which may result in bugs later\n");
692+ destination_serial_ = 0;
693+ }
694 } else {
695 throw UnhandledVersionError("ShippingItem", packet_version, kCurrentPacketVersion);
696 }
697@@ -156,14 +163,17 @@
698
699 ShippingItem ShippingItem::Loader::get(MapObjectLoader& mol) {
700 ShippingItem it;
701- if (serial_ != 0)
702+ if (serial_ != 0) {
703 it.object_ = &mol.get<MapObject>(serial_);
704+ it.destination_dock_ = destination_serial_ ? &mol.get<PortDock>(destination_serial_) : nullptr;
705+ }
706 return it;
707 }
708
709 void ShippingItem::save(EditorGameBase& egbase, MapObjectSaver& mos, FileWrite& fw) {
710 fw.unsigned_8(kCurrentPacketVersion);
711 fw.unsigned_32(mos.get_object_file_index_or_zero(object_.get(egbase)));
712+ fw.unsigned_32(mos.get_object_file_index_or_zero(destination_dock_.get(egbase)));
713 }
714
715 } // namespace Widelands
716
717=== modified file 'src/economy/shippingitem.h'
718--- src/economy/shippingitem.h 2019-04-24 06:51:31 +0000
719+++ src/economy/shippingitem.h 2019-09-07 13:04:52 +0000
720@@ -63,11 +63,13 @@
721
722 private:
723 uint32_t serial_ = 0U;
724+ uint32_t destination_serial_ = 0U;
725 };
726
727 void save(EditorGameBase& egbase, MapObjectSaver& mos, FileWrite& fw);
728
729 private:
730+ friend struct Fleet;
731 friend class PortDock;
732 friend struct Ship;
733
734
735=== modified file 'src/economy/ware_instance.cc'
736--- src/economy/ware_instance.cc 2019-05-25 10:47:18 +0000
737+++ src/economy/ware_instance.cc 2019-09-07 13:04:52 +0000
738@@ -107,7 +107,7 @@
739 return worker->get_location(game);
740
741 if (upcast(Ship, ship, loc)) {
742- if (PortDock* pd = ship->get_destination(game))
743+ if (PortDock* pd = ship->get_current_destination(game))
744 return pd;
745
746 return ship->get_fleet()->get_arbitrary_dock();
747
748=== modified file 'src/logic/map_objects/tribes/ship.cc'
749--- src/logic/map_objects/tribes/ship.cc 2019-08-21 17:57:37 +0000
750+++ src/logic/map_objects/tribes/ship.cc 2019-09-07 13:04:52 +0000
751@@ -134,8 +134,8 @@
752 Ship::~Ship() {
753 }
754
755-PortDock* Ship::get_destination(EditorGameBase& egbase) const {
756- return destination_.get(egbase);
757+PortDock* Ship::get_current_destination(EditorGameBase& egbase) const {
758+ return destinations_.empty() ? nullptr : destinations_.front().first.get(egbase);
759 }
760
761 PortDock* Ship::get_lastdock(EditorGameBase& egbase) const {
762@@ -294,7 +294,7 @@
763 bool Ship::ship_update_transport(Game& game, Bob::State& state) {
764 const Map& map = game.map();
765
766- PortDock* dst = get_destination(game);
767+ PortDock* dst = get_current_destination(game);
768 if (!dst) {
769 // The ship has no destination, so let it sleep
770 ship_update_idle(game, state);
771@@ -313,7 +313,7 @@
772 }
773
774 dst->ship_arrived(game, *this); // This will also set the destination
775- dst = get_destination(game);
776+ dst = get_current_destination(game);
777 if (dst) {
778 start_task_movetodock(game, *dst);
779 } else {
780@@ -736,22 +736,208 @@
781 }
782 }
783
784+bool Ship::has_destination(EditorGameBase& egbase, const PortDock& pd) const {
785+ for (const auto& pair : destinations_) {
786+ if (pair.first.get(egbase) == &pd) {
787+ return true;
788+ }
789+ }
790+ return false;
791+}
792+
793 /**
794 * Enter a new destination port for the ship.
795 * Call this after (un)loading the ship, for proper logging.
796 */
797-void Ship::set_destination(PortDock* pd) {
798- destination_ = pd;
799- if (pd) {
800- molog("set_destination / sending to portdock %u (carrying %" PRIuS " items)\n", pd->serial(),
801- items_.size());
802- pd->ship_coming(true);
803- } else {
804- molog("set_destination / none\n");
805+void Ship::push_destination(Game& game, PortDock& pd) {
806+ for (const auto& pair : destinations_) {
807+ if (pair.first.get(game) == &pd) {
808+ // We're already going there
809+ return;
810+ }
811 }
812+ destinations_.push_back(std::make_pair(OPtr<PortDock>(&pd), 1));
813+ reorder_destinations(game);
814+ molog("push_destination(%u): rerouted to portdock %u (carrying %" PRIuS " items)\n",
815+ pd.serial(), get_current_destination(game)->serial(), items_.size());
816+ pd.ship_coming(*this, true);
817 Notifications::publish(NoteShip(this, NoteShip::Action::kDestinationChanged));
818 }
819
820+void Ship::clear_destinations(Game& game) {
821+ while (!destinations_.empty()) {
822+ pop_destination(game, *destinations_.front().first.get(game));
823+ }
824+}
825+
826+/**
827+ * Remove this destination from the queue
828+ */
829+void Ship::pop_destination(Game& game, PortDock& pd) {
830+ pd.ship_coming(*this, false);
831+ for (auto it = destinations_.begin(); it != destinations_.end(); ++it) {
832+ if (it->first.get(game) == &pd) {
833+ destinations_.erase(it);
834+ reorder_destinations(game);
835+ if (destinations_.empty()) {
836+ molog("pop_destination(%u): no destinations and %" PRIuS " items left\n",
837+ pd.serial(), items_.size());
838+ } else {
839+ molog("pop_destination(%u): rerouted to portdock %u (carrying %" PRIuS " items)\n",
840+ pd.serial(), get_current_destination(game)->serial(), items_.size());
841+ }
842+ return;
843+ }
844+ }
845+}
846+
847+// Recursively find the best ordering for our destinations
848+static inline float prioritised_distance(Path& path, uint32_t priority, uint32_t items) {
849+ return static_cast<float>(path.get_nsteps() * items) / (priority * priority);
850+}
851+using DestinationsQueue = std::vector<std::pair<PortDock*, uint32_t>>;
852+static std::pair<DestinationsQueue, float> shortest_order(Game* game,
853+ Fleet* fleet,
854+ bool is_on_dock,
855+ void* start,
856+ const DestinationsQueue& remaining_to_visit,
857+ const std::map<PortDock*, uint32_t> shipping_items) {
858+ const size_t nr_dests = remaining_to_visit.size();
859+ assert(nr_dests > 0);
860+ auto get_first_path = [game, start, remaining_to_visit, fleet, is_on_dock](Path& path, PortDock& dest) {
861+ if (is_on_dock) {
862+ PortDock* p = static_cast<PortDock*>(start);
863+ if (p != remaining_to_visit[0].first) {
864+ fleet->get_path(*p, dest, path);
865+ }
866+ } else {
867+ static_cast<Ship*>(start)->calculate_sea_route(*game, dest, &path);
868+ }
869+ };
870+ if (nr_dests == 1) {
871+ // Recursion break: Only one portdock left
872+ Path path;
873+ get_first_path(path, *remaining_to_visit[0].first);
874+ return std::pair<DestinationsQueue, float>(remaining_to_visit, prioritised_distance(
875+ path, remaining_to_visit[0].second, shipping_items.at(remaining_to_visit[0].first)));
876+ }
877+
878+ std::pair<DestinationsQueue, float> best_result;
879+ best_result.second = std::numeric_limits<float>::max();
880+ for (const auto& pair : remaining_to_visit) {
881+ DestinationsQueue remaining;
882+ for (const auto& p : remaining_to_visit) {
883+ if (p.first != pair.first) {
884+ remaining.push_back(p);
885+ }
886+ }
887+ auto result = shortest_order(game, fleet, true, pair.first, remaining, shipping_items);
888+ result.first.emplace(result.first.begin(), pair);
889+ Path path;
890+ get_first_path(path, *pair.first);
891+ const float length = result.second + prioritised_distance(path, pair.second, shipping_items.at(pair.first));
892+ if (length < best_result.second) {
893+ best_result.first = result.first;
894+ best_result.second = length;
895+ }
896+ }
897+ assert(best_result.second < std::numeric_limits<float>::max());
898+ assert(best_result.first.size() == nr_dests);
899+ return best_result;
900+}
901+
902+void Ship::reorder_destinations(Game& game) {
903+ upcast(PortDock, pd, get_position().field->get_immovable());
904+ size_t nr_dests = 0;
905+ DestinationsQueue old_dq;
906+ PortDock* fallback_dest = nullptr;
907+ std::map<PortDock*, uint32_t> shipping_items;
908+ for (const auto& pair : destinations_) {
909+ PortDock* p = pair.first.get(game);
910+ assert(p);
911+ uint32_t nr_items = 0;
912+ for (const auto& si : items_) {
913+ if (si.get_destination(game) == p) {
914+ ++nr_items;
915+ }
916+ }
917+ if (nr_items == 0 && p->count_waiting() == 0 && !p->expedition_started() && (!pd || pd->count_waiting(p) == 0)) {
918+ fallback_dest = p;
919+ // We don't need to go there anymore
920+ p->ship_coming(*this, false);
921+ continue;
922+ }
923+ old_dq.push_back(std::make_pair(p, pair.second));
924+ ++nr_dests;
925+ shipping_items[p] = nr_items;
926+ }
927+ if (nr_dests <= 1) {
928+ destinations_.clear();
929+ if (nr_dests > 0) {
930+ destinations_.push_back(old_dq[0]);
931+ } else if (fallback_dest) {
932+ destinations_.push_back(std::make_pair(OPtr<PortDock>(fallback_dest), 1));
933+ fallback_dest->ship_coming(*this, true);
934+ }
935+ return;
936+ }
937+
938+ const OPtr<PortDock> old_dest = destinations_.front().first;
939+ DestinationsQueue dq = shortest_order(&game, fleet_, pd,
940+ pd ? static_cast<void*>(pd) : static_cast<void*>(this), old_dq, shipping_items).first;
941+ assert(dq.size() == nr_dests);
942+
943+ std::vector<std::pair<OPtr<PortDock>, uint32_t>> old_destinations = destinations_;
944+ const size_t nr_all_old_dests = old_destinations.size();
945+ destinations_.clear();
946+ size_t index = 0;
947+ for (const auto& pair : dq) {
948+ OPtr<PortDock> optr(pair.first);
949+ uint32_t priority = pair.second;
950+ size_t old_index = 0;
951+ for (; old_destinations[old_index].first != optr; ++old_index) {
952+ assert(old_index < nr_all_old_dests);
953+ }
954+ if (old_index < index) {
955+ priority += index - old_index;
956+ }
957+ destinations_.push_back(std::make_pair(optr, priority));
958+ ++index;
959+ }
960+ if (old_dest != destinations_.front().first) {
961+ send_signal(game, "wakeup");
962+ }
963+}
964+
965+/**
966+ * Returns an estimation for the time in arbitrary units from now until the moment when
967+ * this ship will probably arrive at the given PortDock. This may change later when
968+ * destinations are added or removed.
969+ * Returns kInvalidDestination if we are not planning to visit this PortDock or if we are not planning
970+ * to visit the given intermediate portdock earlier than the destination.
971+ */
972+uint32_t Ship::estimated_arrival_time(Game& game, const PortDock& dest, const PortDock* intermediate) const {
973+ uint32_t time = 0;
974+ const PortDock* iterator = nullptr;
975+ for (const auto& pair : destinations_) {
976+ Path path;
977+ if (iterator) {
978+ fleet_->get_path(*iterator, *pair.first.get(game), path);
979+ } else {
980+ calculate_sea_route(game, *pair.first.get(game), &path);
981+ }
982+ iterator = pair.first.get(game);
983+ if (iterator == intermediate) {
984+ intermediate = nullptr;
985+ }
986+ time += path.get_nsteps();
987+ if (iterator == &dest) {
988+ return intermediate ? kInvalidDestination : time;
989+ }
990+ }
991+ return kInvalidDestination;
992+}
993+
994 void Ship::add_item(Game& game, const ShippingItem& item) {
995 assert(items_.size() < descr().get_capacity());
996
997@@ -782,23 +968,6 @@
998 }
999
1000 /**
1001- * Unload all items not favored by given next dest.
1002- * Assert all items for current portdock have already been unloaded.
1003- */
1004-void Ship::unload_unfit_items(Game& game, PortDock& here, const PortDock& nextdest) {
1005- size_t dst = 0;
1006- for (ShippingItem& si : items_) {
1007- const PortDock* dest = si.get_destination(game);
1008- if (dest && fleet_->is_path_favourable(here, nextdest, *dest)) {
1009- items_[dst++] = si;
1010- } else {
1011- here.shipping_item_returned(game, si);
1012- }
1013- }
1014- items_.resize(dst);
1015-}
1016-
1017-/**
1018 * Find a path to the dock @p pd, returns its length, and the path optionally.
1019 */
1020 uint32_t Ship::calculate_sea_route(Game& game, PortDock& pd, Path* finalpath) const {
1021@@ -918,6 +1087,11 @@
1022 /// @note only called via player command
1023 void Ship::exp_construct_port(Game& game, const Coords& c) {
1024 assert(expedition_);
1025+ if (is_a(Building, game.map().get_fcoords(c).field->get_immovable())) {
1026+ // Another expedition ship (or an enemy player) was a second faster
1027+ set_ship_state_and_notify(ShipStates::kExpeditionWaiting, NoteShip::Action::kDestinationChanged);
1028+ return;
1029+ }
1030 get_owner()->force_csite(c, get_owner()->tribe().port());
1031
1032 // Make sure that we have space to squeeze in a lumberjack
1033@@ -1032,7 +1206,7 @@
1034 if ((draw_text & TextToDraw::kStatistics) != TextToDraw::kNone) {
1035 switch (ship_state_) {
1036 case (ShipStates::kTransport):
1037- if (destination_.is_set()) {
1038+ if (!destinations_.empty()) {
1039 /** TRANSLATORS: This is a ship state. The ship is currently transporting wares. */
1040 statistics_string = pgettext("ship_state", "Shipping");
1041 } else {
1042@@ -1073,25 +1247,25 @@
1043 void Ship::log_general_info(const EditorGameBase& egbase) const {
1044 Bob::log_general_info(egbase);
1045
1046- molog("Ship belongs to fleet: %u\n destination: %s\n lastdock: %s\n",
1047+ molog("Ship belongs to fleet %u\nlastdock: %s\n",
1048 fleet_ ? fleet_->serial() : 0,
1049- (destination_.is_set()) ? (boost::format("%u (%d x %d)") % destination_.serial() %
1050- destination_.get(egbase)->get_positions(egbase)[0].x %
1051- destination_.get(egbase)->get_positions(egbase)[0].y)
1052- .str()
1053- .c_str() :
1054- "-",
1055 (lastdock_.is_set()) ? (boost::format("%u (%d x %d)") % lastdock_.serial() %
1056 lastdock_.get(egbase)->get_positions(egbase)[0].x %
1057 lastdock_.get(egbase)->get_positions(egbase)[0].y)
1058 .str()
1059 .c_str() :
1060 "-");
1061+ molog("Has %" PRIuS " destination(s):\n", destinations_.size());
1062+ for (const auto& pair : destinations_) {
1063+ molog(" · %u (%3dx%3d) (priority %u)\n",
1064+ pair.first.serial(), pair.first.get(egbase)->get_positions(egbase)[0].x,
1065+ pair.first.get(egbase)->get_positions(egbase)[0].y, pair.second);
1066+ }
1067
1068 molog("In state: %u (%s)\n", static_cast<unsigned int>(ship_state_),
1069 (expedition_) ? "expedition" : "transportation");
1070
1071- if (destination_.is_set() && get_position().field->get_immovable() == destination_.get(egbase)) {
1072+ if (!destinations_.empty() && get_position().field->get_immovable() == destinations_.front().first.get(egbase)) {
1073 molog("Currently in destination portdock\n");
1074 }
1075
1076@@ -1149,7 +1323,7 @@
1077 ==============================
1078 */
1079
1080-constexpr uint8_t kCurrentPacketVersion = 8;
1081+constexpr uint8_t kCurrentPacketVersion = 9;
1082
1083 const Bob::Task* Ship::Loader::get_task(const std::string& name) {
1084 if (name == "shipidle" || name == "ship")
1085@@ -1157,7 +1331,7 @@
1086 return Bob::Loader::get_task(name);
1087 }
1088
1089-void Ship::Loader::load(FileRead& fr) {
1090+void Ship::Loader::load(FileRead& fr, uint8_t packet_version) {
1091 Bob::Loader::load(fr);
1092
1093 // Economy
1094@@ -1194,7 +1368,18 @@
1095
1096 shipname_ = fr.c_string();
1097 lastdock_ = fr.unsigned_32();
1098- destination_ = fr.unsigned_32();
1099+
1100+ if (packet_version >= 9) {
1101+ const uint32_t nr_dest = fr.unsigned_32();
1102+ for (uint32_t i = 0; i < nr_dest; ++i) {
1103+ const uint32_t s = fr.unsigned_32();
1104+ const uint32_t p = fr.unsigned_32();
1105+ destinations_.push_back(std::make_pair(s, p));
1106+ }
1107+ } else {
1108+ // TODO(Nordfriese): Remove when we break savegame compatibility
1109+ destinations_.push_back(std::make_pair(fr.unsigned_32(), 1));
1110+ }
1111
1112 items_.resize(fr.unsigned_32());
1113 for (ShippingItem::Loader& item_loader : items_) {
1114@@ -1207,10 +1392,12 @@
1115
1116 Ship& ship = get<Ship>();
1117
1118- if (lastdock_)
1119+ if (lastdock_) {
1120 ship.lastdock_ = &mol().get<PortDock>(lastdock_);
1121- if (destination_)
1122- ship.destination_ = &mol().get<PortDock>(destination_);
1123+ }
1124+ for (const auto& pair : destinations_) {
1125+ ship.destinations_.push_back(std::make_pair(&mol().get<PortDock>(pair.first), pair.second));
1126+ }
1127
1128 ship.items_.resize(items_.size());
1129 for (uint32_t i = 0; i < items_.size(); ++i) {
1130@@ -1259,7 +1446,7 @@
1131 try {
1132 // The header has been peeled away by the caller
1133 uint8_t const packet_version = fr.unsigned_8();
1134- if (packet_version == kCurrentPacketVersion) {
1135+ if (packet_version >= 8 && packet_version <= kCurrentPacketVersion) {
1136 try {
1137 const ShipDescr* descr = nullptr;
1138 // Removing this will break the test suite
1139@@ -1267,7 +1454,7 @@
1140 const DescriptionIndex& ship_index = egbase.tribes().safe_ship_index(name);
1141 descr = egbase.tribes().get_ship_descr(ship_index);
1142 loader->init(egbase, mol, descr->create_object());
1143- loader->load(fr);
1144+ loader->load(fr, packet_version);
1145 } catch (const WException& e) {
1146 throw GameDataError("Failed to load ship: %s", e.what());
1147 }
1148@@ -1316,7 +1503,11 @@
1149
1150 fw.string(shipname_);
1151 fw.unsigned_32(mos.get_object_file_index_or_zero(lastdock_.get(egbase)));
1152- fw.unsigned_32(mos.get_object_file_index_or_zero(destination_.get(egbase)));
1153+ fw.unsigned_32(destinations_.size());
1154+ for (const auto& pair : destinations_) {
1155+ fw.unsigned_32(mos.get_object_file_index_or_zero(pair.first.get(egbase)));
1156+ fw.unsigned_32(pair.second);
1157+ }
1158
1159 fw.unsigned_32(items_.size());
1160 for (ShippingItem& shipping_item : items_) {
1161
1162=== modified file 'src/logic/map_objects/tribes/ship.h'
1163--- src/logic/map_objects/tribes/ship.h 2019-04-24 06:51:31 +0000
1164+++ src/logic/map_objects/tribes/ship.h 2019-09-07 13:04:52 +0000
1165@@ -80,6 +80,8 @@
1166
1167 constexpr int32_t kShipInterval = 1500;
1168
1169+constexpr uint32_t kInvalidDestination = std::numeric_limits<uint32_t>::max();
1170+
1171 /**
1172 * Ships belong to a player and to an economy. The usually are in a (unique)
1173 * fleet for a player, but only if they are on standard duty. Exploration ships
1174@@ -96,7 +98,8 @@
1175
1176 // Returns the current destination or nullptr if there is no current
1177 // destination.
1178- PortDock* get_destination(EditorGameBase& egbase) const;
1179+ PortDock* get_current_destination(EditorGameBase& egbase) const;
1180+ bool has_destination(EditorGameBase&, const PortDock&) const;
1181
1182 // Returns the last visited portdock of this ship or nullptr if there is none or
1183 // the last visited was removed.
1184@@ -106,7 +109,13 @@
1185 return economy_;
1186 }
1187 void set_economy(Game&, Economy* e);
1188- void set_destination(PortDock*);
1189+ void push_destination(Game&, PortDock&);
1190+ void pop_destination(Game&, PortDock&);
1191+ void clear_destinations(Game&);
1192+ uint32_t estimated_arrival_time(Game&, const PortDock& dest, const PortDock* intermediate = nullptr) const;
1193+ size_t count_destinations() const {
1194+ return destinations_.size();
1195+ }
1196
1197 void init_auto_task(Game&) override;
1198
1199@@ -130,7 +139,6 @@
1200
1201 void add_item(Game&, const ShippingItem&);
1202 bool withdraw_item(Game&, PortDock&);
1203- void unload_unfit_items(Game&, PortDock& here, const PortDock& nextdest);
1204
1205 // A ship with task expedition can be in four states: kExpeditionWaiting, kExpeditionScouting,
1206 // kExpeditionPortspaceFound or kExpeditionColonizing in the first states, the owning player of
1207@@ -270,11 +278,17 @@
1208 Fleet* fleet_;
1209 Economy* economy_;
1210 OPtr<PortDock> lastdock_;
1211- OPtr<PortDock> destination_;
1212 std::vector<ShippingItem> items_;
1213 ShipStates ship_state_;
1214 std::string shipname_;
1215
1216+ // Our destinations in the order on which we are planning to visit them.
1217+ // When destinations are added or removed, the whole list will be reordered under
1218+ // the aspect of efficiency. Every time an entry is postponed, its priority will
1219+ // be increased to make it less likely that it will never be visited.
1220+ std::vector<std::pair<OPtr<PortDock>, uint32_t>> destinations_;
1221+ void reorder_destinations(Game&);
1222+
1223 struct Expedition {
1224 ~Expedition();
1225
1226@@ -294,14 +308,14 @@
1227
1228 const Task* get_task(const std::string& name) override;
1229
1230- void load(FileRead& fr);
1231+ void load(FileRead& fr, uint8_t);
1232 void load_pointers() override;
1233 void load_finish() override;
1234
1235 private:
1236 // Initialize everything to make cppcheck happy.
1237 uint32_t lastdock_ = 0U;
1238- uint32_t destination_ = 0U;
1239+ std::vector<std::pair<uint32_t, uint32_t>> destinations_;
1240 Serial economy_serial_;
1241 ShipStates ship_state_ = ShipStates::kTransport;
1242 std::string shipname_;
1243
1244=== modified file 'src/scripting/lua_map.cc'
1245--- src/scripting/lua_map.cc 2019-08-21 17:57:37 +0000
1246+++ src/scripting/lua_map.cc 2019-09-07 13:04:52 +0000
1247@@ -5696,7 +5696,7 @@
1248 // UNTESTED
1249 int LuaShip::get_destination(lua_State* L) {
1250 EditorGameBase& egbase = get_egbase(L);
1251- return upcasted_map_object_to_lua(L, get(L, egbase)->get_destination(egbase));
1252+ return upcasted_map_object_to_lua(L, get(L, egbase)->get_current_destination(egbase));
1253 }
1254
1255 /* RST
1256
1257=== modified file 'src/wui/seafaring_statistics_menu.cc'
1258--- src/wui/seafaring_statistics_menu.cc 2019-07-31 16:43:58 +0000
1259+++ src/wui/seafaring_statistics_menu.cc 2019-09-07 13:04:52 +0000
1260@@ -260,7 +260,7 @@
1261 ShipFilterStatus status = ShipFilterStatus::kAll;
1262 switch (state) {
1263 case Widelands::Ship::ShipStates::kTransport:
1264- if (ship.get_destination(iplayer().game()) != nullptr) {
1265+ if (ship.get_current_destination(iplayer().game())) {
1266 status = ShipFilterStatus::kShipping;
1267 } else {
1268 status = ShipFilterStatus::kIdle;
1269
1270=== modified file 'src/wui/shipwindow.cc'
1271--- src/wui/shipwindow.cc 2019-02-23 11:00:49 +0000
1272+++ src/wui/shipwindow.cc 2019-09-07 13:04:52 +0000
1273@@ -233,7 +233,7 @@
1274 }
1275 bool can_act = igbase_.can_act(ship->owner().player_number());
1276
1277- btn_destination_->set_enabled(ship->get_destination(igbase_.egbase()));
1278+ btn_destination_->set_enabled(ship->get_current_destination(igbase_.egbase()));
1279 btn_sink_->set_enabled(can_act);
1280
1281 display_->clear();
1282@@ -311,7 +311,7 @@
1283 if (ship == nullptr) {
1284 return;
1285 }
1286- if (PortDock* destination = ship->get_destination(igbase_.egbase())) {
1287+ if (PortDock* destination = ship->get_current_destination(igbase_.egbase())) {
1288 igbase_.map_view()->scroll_to_field(
1289 destination->get_warehouse()->get_position(), MapView::Transition::Smooth);
1290 }
1291
1292=== added file 'test/maps/expedition.wmf/scripting/test_no_double_colonizing.lua'
1293--- test/maps/expedition.wmf/scripting/test_no_double_colonizing.lua 1970-01-01 00:00:00 +0000
1294+++ test/maps/expedition.wmf/scripting/test_no_double_colonizing.lua 2019-09-07 13:04:52 +0000
1295@@ -0,0 +1,36 @@
1296+run(function()
1297+ port:set_wares {
1298+ blackwood = 100,
1299+ log = 100,
1300+ gold = 20,
1301+ granite = 20,
1302+ grout = 20,
1303+ iron = 20,
1304+ reed = 20,
1305+ }
1306+ port:set_workers("barbarians_builder", 5)
1307+
1308+ create_two_ships()
1309+ port:start_expedition()
1310+ wait_for_message("Expedition")
1311+ port:start_expedition()
1312+ wait_for_message("Expedition")
1313+
1314+ first_ship.island_explore_direction="ccw"
1315+ sleep(2000)
1316+ assert_equal("ccw", first_ship.island_explore_direction)
1317+ wait_for_message("Port Space")
1318+ second_ship.island_explore_direction="ccw"
1319+ sleep(2000)
1320+ assert_equal("ccw", second_ship.island_explore_direction)
1321+ wait_for_message("Port Space")
1322+
1323+ second_ship:build_colonization_port()
1324+ sleep(5000)
1325+ first_ship:build_colonization_port()
1326+ -- This test is to check that there won't be any crash now
1327+ wait_for_message("Port")
1328+
1329+ print("# All Tests passed.")
1330+ wl.ui.MapView():close()
1331+end)