Currently Online

Latest Posts

Topic: Congestion Competition

king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1668
Ranking
One Elder of Players
Posted at: 2018-05-25, 14:41

nice job researching the causes of road jams.

Unfortunately, sometimes small circles are not avoidable


Top Quote
ypopezios
Avatar
Topic Opener
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-25, 17:52

Based on what has been suggested so far, one road-configuration is this:

Widelands Logo

All six carriers are idle (actually moving their legs on place, which isn't a nice spectacle) and there is no hope of recovering without player's intervention, no matter how much time will pass. I consider that to be a design problem and not a feature of the game.

So, as a first step I plan to prevent that case at the flag-level, having flags communicate with each-other before approving a transfer. I will provide details on a separate thread. Meanwhile, feel free to find other cases of full congestion.


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-26, 01:19

king_of_nowhere wrote:

Unfortunately, sometimes small circles are not avoidable

In my last tournament game there are many circles. But I tried to make them not to cause roundabout flow. Rather one way flow.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1668
Ranking
One Elder of Players
Posted at: 2018-05-26, 16:03

ypopezios wrote:

Based on what has been suggested so far, one road-configuration is this:

Widelands Logo

All six carriers are idle (actually moving their legs on place, which isn't a nice spectacle) and there is no hope of recovering without player's intervention, no matter how much time will pass. I consider that to be a design problem and not a feature of the game.

So, as a first step I plan to prevent that case at the flag-level, having flags communicate with each-other before approving a transfer. I will provide details on a separate thread. Meanwhile, feel free to find other cases of full congestion.

great job. I think you nailed down the basics of how the worst kkind of congestions generate. That's great information to find a fix.

einstein13 wrote:

king_of_nowhere wrote:

Unfortunately, sometimes small circles are not avoidable

In my last tournament game there are many circles. But I tried to make them not to cause roundabout flow. Rather one way flow.

To increase the traffic flow, I made two parallel roads. In order to allow wares to move from the external road to a specific production site, I had to make a connection that would intersect the inner road. Whenever I have 2 of those connection, there is a small circle. And it worked fine as long as they could manage traffic, but when they started getting congested, rerouting of wares along the various circles was worsening the problem.


Top Quote
Tibor

Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2018-05-26, 20:40

And something similar with only two warehouses and single road would not be possible? Or perhaps single road between two warehouses without any flag on it (only two belonging to two warehouses)


Top Quote
ypopezios
Avatar
Topic Opener
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-26, 22:00

@Tibor

So far we haven't managed what you describe. The main reason is that, on their arrival to a flag, carriers are smart enough (this is specifically mentioned in current code) to replace their delivered ware with one which goes to the opposite flag, so they can operate two full flags without a problem. But feel free to experiment and come with any other possibility.


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-27, 20:39

I can be wrong, but my mathematical feelings say "no" to other possibilities.

The 2-dimensional plane with triangle borders (Widelands world) makes less possibilities of choosing any shapes. In fact I can imagine only two of them:

  • line
  • circle

Here: line can be any representation of configuration with flag-road-flag-road-flag...flag-road-flag with two endings and no intersections; circle - similar representation, but there is no endings because first and last flag is the same object. In such a world all road cases can be explained by only those two objects connected by a flags that we can call a union flag.

So in last picture you can see exactly 4 shapes: 3 lines and 1 circle with 3 union flags, all belongs to one line each.

And what @ypopezios said (here I agree with him face-smile.png ), there is no possibility to make clear congestion on line object. There can be a bug that will cause this issue, but it is out of our scope. Also I can't explain how this bug should work, since (as it was told) if a carrier can see any ware that can be switched, he will instantly make a switch.

About circle - we already have a solution about that, so there is nothing to explain more.

Also I have to say sorry, that at first I tried to prove that there is no standard possibility of congestion and I was wrong. So here I have to say that my knowledge say "no" to other possibilities, but I may be wrong again. Maybe someone with mathematical symmetry theory will know more and can prove that I am wrong or not?


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
ypopezios
Avatar
Topic Opener
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-28, 20:16

We could think of congestion as a non-advancing queue. Warehouses have infinite capacity of wares (this is unrealistic, but it has been a conscious design-choice so far), thus they don't have queues. Consumption-buildings never order more wares than their capacity, thus they don't have queues either. Production-buildings use the flag in front of them for their output queue, thus acting as roads with their worker being the carrier. Therefore, buildings in Widelands are never the cause of congestion.

Carriers pass through other carriers and depart from a place as soon as they have 1 ware (that may change for animals in the future), thus they can be ignored from a queue analysis. Roads have the shape of a queue, but in Widelands their behaviour is reduced to the behaviour of their carriers, thus they can get ignored too. Ships also leave a port as soon as there is any type of load for them, thus they don't have queues. Finally, flags have limited capacity (currently 8 wares) and no limit to the number of wares choosing them as an intermediate destination, thus they do have queues.

When a system has queues, any of them may stop getting served and cause local congestion. Denial of service happens when all carriers responsible for serving a road are waiting for something else to happen before resuming operation. That waiting is prolonged if another denial of service is present further down that direction. Since final destinations (buildings) never deny service, full congestion happens only when the series of denials somehow returns to a previous point in it (thus a form of circle), causing a state of mutual denial. In practice, that mutual denial can be caused either by inability of ware swapping or some form of circular traffic.

It is characteristic in configurations like the above triangle that, if the loop gets replaced by a multi-way crossroad, full congestion doesn't occur. This is counter-intuitive, since a multitude of flags have multiple times higher capacity than a single central flag. But as long as capacity is not infinite, being lower only slows-down overall service, while being higher only delays potential problems (circular configurations get congested only when they are fed with more wares per time than they can serve). It is also counter-intuitive, because in real-life a carrier would simply bypass the flag and go deliver the ware directly to its destination. A similar approach would be for carriers meeting at a flag to exchange either their wares or their roads, ignoring the flag. But since Widelands' transportation system is designed around flags, we can forget such solutions and rather focus on flags. Stay tuned.


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-28, 22:27

@ypopezios
Have you ever played Settlers II or Settlers I ? Widelands is based on that design. Those games have design of road-flag transportation system. This is a heart of early Settlers games. Changing this you will change almost everything. Here you have a wall of 22 years history. face-wink.png

About switching circle into crossroad: it is possible, but sometimes it can slow down even more and make the game impossible to go forward. Imagine that you have system of flags A-B-C-D. Between B and C you have long distance (it is a bottleneck). Also imagine that you are producing something that will go from A to D and something else from D to A. So you will have a long queue there with 100% capacity on B-C connection. If you place a road E-B-F it can never move any resource, because the flag B will contain 8 wares that will be switched to 7+1 and then again to 8. That is not a direct congestion you would like to have, but it is possible to stop whole economy for a long time (with infinite resources even forever).

I will try to make an example for that.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-28, 22:57

image

It is not a direct congestion, but it is enough to stop the economy for a long time


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote