Transfer priority patch

[Nizamov Shawkat]

Hi!

I have prepared another patch for transfer priority system, as discussed in http://wl.widelands.org/forum/topic/610/
Now patch does not change anything in inner workings of widelands, excluding, of course the transportation.
It makes only several small additions to already defined classes and its wighting algorithm is very clear.

It works in following way:

1) By default all wares, which were dropped at the flag for delivery, have minimal priority 0.
2) Priority set in destination building is determined. It is given as 2/4/8 integer depending on low/normal/high priority. Priorities respected as well for production sites as for construction sites.
3) If destination is a construction site, it is modified +2 (obviously, higher priority)
4) If destination is a warehouse, it is modified -2 (ware being delivered to warehouse have small importance for player in short term, in fact, it is useless now if going to be stored at warehouse)
5) if this is a last transportation step, then modify +2 (preference given for items almost at their destination point)
6) if item needs just two steps to destination, then +1.

So, depending on the actual conditions, ware may have priorities from 0 till 12 (last step to construction site), but usually are expected to be about 4-6.

After that, when carrier tries to pick up some item at the flag, it looks for the highest priority item (and takes the first in the queue, if there are several with the same priority). All items, that now missed the chance for delivery, increase their priorities +1. The maximal priority that may be achieved this way is clamped to 16. Even for the worst possible case - if the flag is very busy with constant flow of highest priority items, the lowest initial priority item will wait no more than 15 attempts, because, by that time it will be picked up as a highest priority in FIFO fashion.

The patch was checked in the game. Obviously, I am biased, but I should note that the game became more pleasant and smooth, especially, there is virtually no extra wait time for constructions if resources are available.

If the item has no request attached (are there any actually such cases? are these items really important if they were not requested?) - then it is treated as priority 0.

I hope it would be successfully reviewed.

[Nizamov Shawkat (nizamov-shawkat)]

PS: unfortunately, Transfer class is not very useful here. Economical priority determination code went to the Request

[Nicolai Hähnle (nha)]

I like the approach of your patch.

Two things I would change in the logic:
1) In the first hunk, change if (trans_steps == 2) to if (trans_steps <= 2) in the interest of robustness.
2) In the same hunk, clamp priority to be >= 0 (or change get_transfer_priority() so that it returns an uint32_t and clamps appropriately). The reason is that your assumption that m_target_building->get_priority() returns something >= 2 might be changed in the future.

Also, to keep the style consistent, please don't use lines like
if (...) do_something();
Instead, put the code in the if() on its own line:
if (...)
    do_something();

Please move variable declarations into the innermost scope where they are used, and as far down as possible. I'm looking at the first hunk: it makes no sense to declare trans_steps and req outside the if-block. Also, you should generally initialize variables within the statement that declares them, unless that is impossible for some reason.

As for your remark about Requests, items that are simply moving into a warehouse because they are not needed should not have an associated Request.

Also for the record, you can push your changes as a bzr branch to Launchpad and then submit a Merge Request. I believe that that would be more in line with the intended workflow.

[Nicolai Hähnle (nha)]

And in case it wasn't clear, I like your patch, and I think we should add it (given the changes I've outlined above). Thank you for looking into this.

[Andreas Breitschopp (ab-tools)]

Hello Nizamov,

first thanks again for your great work on that:
I've tested your patch with BZR revision 5752 now a little bit and it works very good - I just came across one problem with a multiplayer game.

When I save a multiplayer game (tested with two players in a LAN (Windows compilation); guess with an internet game it'll be the same) and reload the saved game again, Widelands crashes with this stack trace:
  kernel32.dll!7c812afb()
  [Unten angegebene Rahmen sind möglicherweise nicht korrekt und/oder fehlen, keine Symbole geladen für kernel32.dll]
  kernel32.dll!7c812afb()
  widelands.exe!_CxxThrowException(void * pExceptionObject=0x017296d8, const _s__ThrowInfo * pThrowInfo=0x00c8241c) Zeile 161 C++
> widelands.exe!Widelands::Carrier::find_pending_item(Widelands::Game & game={...}) Zeile 482 C++
  widelands.exe!Widelands::Carrier::road_update(Widelands::Game & game={...}, Widelands::Bob::State & state={...}) Zeile 92 C++
  widelands.exe!Widelands::Bob::do_act(Widelands::Game & game={...}) Zeile 226 C++
  widelands.exe!Widelands::Bob::act(Widelands::Game & game={...}, const unsigned int data=104) Zeile 209 C++
  widelands.exe!Widelands::Cmd_Act::execute(Widelands::Game & game={...}) Zeile 109 C++
  widelands.exe!Widelands::Cmd_Queue::run_queue(const int interval=67, int & game_time_var=53300) Zeile 121 C++
  widelands.exe!Widelands::Game::think() Zeile 581 C++
  widelands.exe!Interactive_Base::think() Zeile 337 C++
  widelands.exe!Interactive_Player::think() Zeile 332 C++
  widelands.exe!UI::Panel::do_think() Zeile 544 C++
  widelands.exe!UI::Panel::run() Zeile 176 C++
  widelands.exe!Widelands::Game::run(UI::ProgressWindow & loader_ui={...}, Widelands::Game::Start_Game_Type start_game_type=Loaded) Zeile 551 C++
  widelands.exe!NetClient::run() Zeile 208 C++
  widelands.exe!WLApplication::mainmenu_multiplayer() Zeile 1716 C++
  widelands.exe!WLApplication::mainmenu() Zeile 1486 C++
  widelands.exe!WLApplication::run() Zeile 421 C++
  widelands.exe!SDL_main(int argc=1, char * * argv=0x0172fea0) Zeile 50 C++
  widelands.exe!_main() + 0x130 Bytes C
  widelands.exe!_WinMain@16() + 0x100 Bytes C
  widelands.exe!__tmainCRTStartup() Zeile 263 + 0x2c Bytes C
  widelands.exe!WinMainCRTStartup() Zeile 182 C
  kernel32.dll!7c817077()

I've tested it also with BZR revision 5752 without your patch and then this problem did not occur. So it has to be related with your patch.

Could you please verify this problem? It is very easy to reproduce on my side:
- Start a new multiplayer game.
- I just started to build one building for both players.
- Save the game within the wares are transported to the construction sites.
- Reload the multiplayer game.
=> Widelands crashed after few seconds.

[Nicolai Hähnle (nha)]

Indeed, the patch lacks save game support. I totally missed that. You'll have to make sure the priorities are properly saved and loaded.

[Andreas Breitschopp (ab-tools)]

Hello Nizamov again,

just want to add that the game crashes when loading a single player gamein BZR revision 5752 with your patch, too. So it is not related to multiplayer.

[Andreas Breitschopp (ab-tools)]

OK, I've created an additional patch to add savegame support for Nizamovs patch.

I've tested it and now saving and loading games works just fine.

One question here:
is it really necessary that the priority is defined as Signed32 or wouldn't be an Unsigned32 enough?

[Nicolai Hähnle (nha)]

I agree about using an uint32_t instead of int32_t; that kind of ties in with the concerns I've voiced previously about making sure you don't get negative priority numbers.

Andreas, at a quick glance your patch to add savegame support looks good to me.

[Nizamov Shawkat (nizamov-shawkat)]

Hi!

Unfortunately, making priority uint32_t breaks things somehow. There is a part of logic where comparison is made against -1. Compiler gives the warning about comparing signed and unsigned variables, but that is not a problem. Somehow this part leads to a crash, if priority is unsigned. However, the actual functions in transfer.cc and request.cc, that this priority variable depends on, are made uint32_t. So, its actual value is always non-negative. But can not be unsigned, I am not competent enough in C to understand this case.

I also corrected the style of the patch and added also Andreas patch. Attached is the resulting patch, I have tested it a little bit, things work as expected. And you are right, wares for warehouse go without request, so they default to priority 0. It maybe a little bit too small, but this makes sense only in marginal cases.

I'll try to push it to launchpad and request the merge, when figure out how it should be performed.

[Nicolai Hähnle (nha)]

Thanks for the updated patch. I'll take care of it this weekend at the latest (perhaps tonight, depending on my time).

As for the uint32_t: the warning about comparing signed and unsigned must not be ignored. I don't remember the implicit conversion rules of C++ by heart, but if the variables are implicitly compared as unsigned, then clearly the logic becomes incorrect and this can lead to further cascading problems.

I think having priority == 0 for wares going to warehouses is exactly as it should be, because those wares aren't actually requested for anything. So with your patches, wares that are requested for something (whether construction site or production) will be favoured significantly over wares that are simply idle and not required anywhere. It's logical and what people would expect.

[David Fendt (david-hundertachtzehn)]

I think the patch is a big improvement, but which priority is which number and how much it increase of decrease in which case should be discussed. For now I think it is more important to get this working. Changeing the numbers can be done in future.

By the way: Should that be discussed here or at the forum?

[Nicolai Hähnle (nha)]

I've committed your patch with only minor changes, I removed the number of steps field from Transfer, because it was really only an alias for Route::get_nrsteps() which is a simple size() operations, and I reordered the comment and #define before ack_pending_item() properly.

Thank you for your work!

[Andreas Breitschopp (ab-tools)]

Thanks for pushing this patch to trunk, Nicolai.

I guess we can close my issue #669918 now, because if this is working good, we indeed won't need a manual transport priority system.

[Andreas Breitschopp (ab-tools)]

Hello Nicolai,

thanks for closing my other issue.

Now only #680164 in this context is left, but Nizamov started to work also on this issue already. So maybe we get some improvements for the ware allocation soon, too.

Best regards
Andreas

[SirVer (sirver)]

Released in build16-rc1