Donation

Help us to pay our server!
(: Consider a donation :)



Social Media

  • Facebook
  • Google+

Currently Online

Latest Posts

Topic: Improve road-system concerning jams

ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 186
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-31, 19:54

Note: This thread adopts a useful practice to improve its readability: The first/opening post will get regularly updated from later posts with every important information, so as to keep everything important in one place.

This thread is a parallel to: Congestion Competition and a solution to: ai roads getting jammed a lot

The requirements are these:

  • Avoid full congestion of a road-system and most cases of half-full congestion.
  • Prevent a road-system from getting messed-up by overproduction of a single type of ware.
  • Improve the situation where a rare ware needs to move quickly through a busy road-system.
  • Be relatively easy to explain to players.
  • Don't alter the existing system too much.
  • Achieve the above points without stressing the computer.

This is not a perfect final solution, it is merely a considerable improvement, an early step to the right direction, of a bigger effort to improve Widelands' road-system and overall performance of big maps.

After much analysis and calculations, number 6 has been found to be the critical one, and it all comes down to the following algorithm, which checks the number, type and destination of wares stored on a flag, waiting to be carried by someone:

  • If a ware of the same type is heading to the opposite direction, then remotely swap the two wares, avoiding their transfer on that road. Otherwise:
  • If the number of wares is 0-5, consider that as a low risk of congestion and allow the transfer of any ware to the flag. Of course 5 wares are more risky than 0, but not by much. This should be the most common case and is identical to the old approach.
  • If the number of wares is 6 or 7, consider that as a middle risk of congestion and deny the transfer of any type of ware that is already stored on that flag. Allow transfer of non-stored types.
  • If the number of wares is 8 (maximum), consider that as a high risk of congestion and deny the transfer of any type of ware that is already stored on the flag. Also deny the transfer of any other ware, except if one of the stored wares is heading to the opposite direction and thus it can get locally swapped by the carrier.

UPDATE: An implementation of that got merged in the official installation for build 20.

Edited: 2018-08-09, 11:58
Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 186
Ranking
Widelands-Forum-Junkie
Posted at: 2018-06-26, 18:14

The first implementation of a hopefully congestion-free version of Widelands is available on the opening post. All players interested in demanding maps (big and/or narrow) are encouraged to try it and, other than testing whether congestion will occur, to also pay close attention to the behaviour of the carriers, whether it is fully expectable. The changes happen to also affect the promotion of roads, but this is something addressed in a different fix.


Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 2479
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2018-07-06, 22:48

I just did a round of code reviews on both of your branches - are you happy with the state of the road promotion one for merging?


Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 186
Ranking
Widelands-Forum-Junkie
Posted at: 2018-07-07, 04:02

@GunChleoc

Those two branches have some target functions in common, so I'd be happy to see one of them merged, for the other to work with cleaner code.


Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 2479
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2018-07-07, 10:50

OK, I have triggered a merge for road_promotions, since it has been tested. Thanks for your work on this! face-smile.png

Edited: 2018-07-07, 10:51
Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 186
Ranking
Widelands-Forum-Junkie
Posted at: 2018-07-07, 11:31

Just to note that the said merge doesn't close the present topic. Actually, this thread is still in its first days. I will have to review the code of its branch, as it cannot incorporate directly the changes of road_promotions. I will report back here of course.


Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 186
Ranking
Widelands-Forum-Junkie
Posted at: 2018-07-29, 23:37

This is again working and ready for testing, this time including the road-promotion fix. Use the links at the end of the opening post to get windows versions.


Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 186
Ranking
Widelands-Forum-Junkie
Posted at: 2018-08-09, 11:50

The proposed (imperfect) solution got merged, so further testing can take place with trunk versions.


Top Quote