Topic: ware routing tweak

Tibor Joined: 2009-03-23, 23:24 Posts: 1316 One Elder of Players Location: Slovakia	Posted at: 2020-02-01, 19:17 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 Top Quote

JanO Joined: 2015-08-02, 11:56 Posts: 91 Likes to be here	Posted at: 2020-02-02, 22:39 You mean "a" instead of "e"? Don't bother 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 Top Quote

Tibor Joined: 2009-03-23, 23:24 Posts: 1316 One Elder of Players Location: Slovakia	Posted at: 2020-02-03, 08:20 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 Joined: 2014-12-11, 23:16 Posts: 1112 One Elder of Players Location: Bavaria	Posted at: 2020-02-03, 09:00 JanO wrote: You mean "a" instead of "e"? Don't bother 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 Joined: 2009-03-23, 23:24 Posts: 1316 One Elder of Players Location: Slovakia	Posted at: 2020-02-03, 09:21 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 Joined: 2014-12-11, 23:16 Posts: 1112 One Elder of Players Location: Bavaria	Posted at: 2020-02-03, 10:15 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 Joined: 2009-03-23, 23:24 Posts: 1316 One Elder of Players Location: Slovakia	Posted at: 2020-02-03, 13:07 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 Joined: 2015-08-02, 11:56 Posts: 91 Likes to be here	Posted at: 2020-02-03, 18:37 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 Joined: 2014-12-11, 23:16 Posts: 1112 One Elder of Players Location: Bavaria	Posted at: 2020-02-03, 19:02 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