Topic: ware routing tweak

Forums » Player Forums » Game Suggestions » ware routing tweak
Tibor

Topic Opener
Joined: 2009-03-23, 23:24 UTC+1.0
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2020-02-01, 19:17 UTC+1.0

Hi, based on the current discussion in other forum I looked into code and came up with one trivial tweak:

https://github.com/widelands/widelands/compare/ware_routing_tweak

Basically it changes the formula how transporation cost THIS_FLAG -> NEIGHBOUR_FLAG is calculated. Now it just sums count of wares on both flags. My tweak considers:

  • number of wares waiting to be transported THIS_FLAG -> NEIGHBOUR_FLAG
  • number of wares on NEIGHBOUR_FLAG

I did some test with AI but nothing interesting to see. So I offer this for testing and feedback

Just two notes:

  • it needs alternative less used paths (logically)
  • next route is calculated when ware arrives on the flag, so once it waits there it does no recalculation, so once the roads are completely stuck it will not help (but this behavior is the same as before)

And one developer note - old formula was 'bi-directional', this one is not, I have no idea if it matters somewhere in the code...

EDIT:

It is not possible to update the title, is it?

Edited: 2020-02-01, 20:46 UTC+1.0
Top Quote
JanO
Avatar
Joined: 2015-08-02, 11:56 UTC+2.0
Posts: 179
Ranking
At home in WL-forums
 Posted at: 2020-02-02, 22:39 UTC+1.0

You mean "a" instead of "e"? Don't bother face-smile.png This work is a very good start.
Maybe counting all wares on both flags for the penalty is a bit too hard. Imagine a busy road with two carriers between all flags (maybe 5 of them). If for whatever reason on the last flag there is a short stop in transportation (warehouse close by and you start building a big military building), this can send new wares on the 5-flags-road on incredibly long alternative routes (5 flags * 8 wares * 2 because each flag is counted twice =80 flags for pathfinding algorithm). So I would suggest to start counting only when the number of waiting wares exceeds the number of carriers and furthermore divide the number by something (start with halves)

Edited: 2020-02-02, 22:39 UTC+1.0
Top Quote
Tibor

Topic Opener
Joined: 2009-03-23, 23:24 UTC+1.0
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2020-02-03, 08:20 UTC+1.0

The number of carriers is good comment, I will look into code if it is possible to get this number easily.

The score is now calculated as:

max( num_of_wares_at_NEIGHBOUR_FLAG-5 , 0 ) + wares_in_queue_for_NEIGHBOUR_FLAG
Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16 UTC+1.0
Posts: 2845
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2020-02-03, 09:00 UTC+1.0

JanO wrote:

You mean "a" instead of "e"? Don't bother face-smile.png This work is a very good start.
Maybe counting all wares on both flags for the penalty is a bit too hard. Imagine a busy road with two carriers between all flags (maybe 5 of them). If for whatever reason on the last flag there is a short stop in transportation (warehouse close by and you start building a big military building), this can send new wares on the 5-flags-road on incredibly long alternative routes (5 flags * 8 wares * 2 because each flag is counted twice =80 flags for pathfinding algorithm). So I would suggest to start counting only when the number of waiting wares exceeds the number of carriers and furthermore divide the number by something (start with halves)

old formula was (wares_on_this_flag + wares_on_next_flag) / 2

so the new formula just starts to increase the penalty if there are more then 5 wares on the next flag and traffic is monodirectional. It decreases penalty if traffic is bidirectional.
Taking carriers into consideration might be a good idea nevertheless. I will try to test this tonight.

Top Quote
Tibor

Topic Opener
Joined: 2009-03-23, 23:24 UTC+1.0
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2020-02-03, 09:21 UTC+1.0

hessenfarmer wrote:

JanO wrote: monodirectional. It decreases penalty if traffic is bidirectional.

We dont care about the traffic in opposite direction at all.... it does not affect the time for transfer in "our" direction

Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16 UTC+1.0
Posts: 2845
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2020-02-03, 10:15 UTC+1.0

Tibor wrote:

hessenfarmer wrote:

JanO wrote: monodirectional. It decreases penalty if traffic is bidirectional.

We dont care about the traffic in opposite direction at all.... it does not affect the time for transfer in "our" direction

And that is why your new formula is better then the old one I believe, as it takes direction into account.

Top Quote
Tibor

Topic Opener
Joined: 2009-03-23, 23:24 UTC+1.0
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2020-02-03, 13:07 UTC+1.0

hessenfarmer wrote:

And that is why your new formula is better then the old one I believe, as it takes direction into account.

There are two considerations:

  • higher CPU use (but should not be that much)
  • should not happen, but theoretically an individual ware can ping between two adjacent flags as the other way is always shorter. This is a consequence of the fact that transport costs between two flags are not the same in both directions. But I am not sure if this can happen
Top Quote
JanO
Avatar
Joined: 2015-08-02, 11:56 UTC+2.0
Posts: 179
Ranking
At home in WL-forums
 Posted at: 2020-02-03, 18:37 UTC+1.0

I think the pingpong would be possible, but how bad would that be? For the ware it would not matter, maybe it's bad for CPU. But what is worse, a ware in pingpong mode, unnecessarily triggering the pathfinding algorithm or an additional check in the concestion-rerouting-code...

Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16 UTC+1.0
Posts: 2845
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2020-02-03, 19:02 UTC+1.0

JanO wrote:

I think the pingpong would be possible, but how bad would that be? For the ware it would not matter, maybe it's bad for CPU. But what is worse, a ware in pingpong mode, unnecessarily triggering the pathfinding algorithm or an additional check in the concestion-rerouting-code...

theoretically possible in a triangle situation with exactly the same cost on each path. but as costs are changing constantly I believe this would clear after max. 2 toggles. So I would not bother at all until shown otherwise.

Top Quote