Social Media

  • Facebook
  • Google+

Latest Posts

Topic: Congestion Competition

ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 204
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-24, 14:35

More than just fun, this is to help with a planned effort to improve the routing in Widelands, and later to improve AI's behaviour.

I can think of a few variants:

  1. Starting only with HQ, put down a special set of buildings and roads, then wait doing nothing and measure how long it takes for the road system to get fully congested, meaning that no ware moves anymore and player's intervention is absolutely needed to provide a solution.

  2. Like #1, but this time the player is allowed to micromanage the buildings, so as to cause special traffic direction.

  3. Like #1, but this time the player is allowed to use lua console to alter the state of the game.

Winner is the one who achieves full congestion in the shortest amount of time.

Suggestions are welcome.


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 985
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-24, 16:52

I don't understand this idea. Can you be more specific?

If you are interested in a "perfect road system", just ask- there are already mathematical answers face-wink.png


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 204
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-24, 17:07

@einstein13

It may sound strange, but I'm interested in the exact opposite, i.e. a perfectly WRONG road-system, which gets congested as soon as possible. There may be mathematical answers for that too, but I'm interested in whatever answer achieves a small time.


Top Quote
kaputtnik
Avatar
Joined: 2013-02-18, 20:48
Posts: 1470
Ranking
One Elder of Players
Location: Germany
Posted at: 2018-05-24, 19:02

For your first variant there should only be production sites build, which produces endless wares, e.g. farmers. But i guess a fully congested roadsystem will never be reached. Assuming 10 Farms connected to one road which is itself only connected with your headquarters, there will be always a piece of road which isn't congested.

But may i didn't understand exactly your idea...


Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 204
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-24, 20:44

@kaputtnik

Flooding the roads with wares is just one of the requirements to achieve full congestion. The other is to arrange roads and traffic direction in such a way that the transportation system will ultimately halt. Apparently a single long road connecting everything doesn't achieve that, so a more complicated road-network is needed.


Top Quote
kaputtnik
Avatar
Joined: 2013-02-18, 20:48
Posts: 1470
Ranking
One Elder of Players
Location: Germany
Posted at: 2018-05-24, 21:59

Just

  • place some warehouses,
  • add as many wares you want to each warehouse through scripting,
  • connect them with as many roads as you can
  • exchange the wares so that each warehouse removes a ware and one other warehouse prefer that ware

But i guess this also not what you want?


Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 204
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-24, 22:18

@kaputtnik

I simply want full congestion. Like the AI achieves sometimes (and in those cases it ruins both its economy and the game). It's not supposed to be easy for players who every time try the opposite. Outsmarting the AI isn't much of a challenge. Here the challenge is to outdumb it...


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

So if you want to see terrible traffic jam...

I can get several conditions:
1. Place as much buildings producing, not consuming as possible 2. End the road with bottleneck 3. Wait till all flags are fully occupied.

With my last game I even USED this idea. (Why? If you have bottleneck in production place, you won't have bottleneck somewhere else.):
I was producing fish in one place, far away from my main production centre. 18 fisher's huts were at 100% production. All of them connected to one single road. The road had two bottlenecks at once: first was because not every part of the road was with a donkey helping the carrier with moving fish; second, because (at least) one of the distance between flags was 3-units long. So considering that road, all the traffic was concentrated on a single road with limited capacity. The capacity was only 50% less than perfect (or perfect one was 33% far from target one).

So answering to your question, I will make a chain of thesis:

There is no full congestion

In a perfect world (without any bugs!) every ware has its own destination and route. So if we consider no changes on routes, there is no logic way of complete stop of moving the wares. But the world is not perfect. So probably this thesis is not 100% accurate, but 99.99% will be ok.

There are terrible traffic jams

My sub-thesis for this is that: every participant of last tournament had at least one traffic jam. And traffic jam definition here can be: at least 27 wares concentrated on 3 neighbour flags with 3 carriers. Most complex traffic jam I had was with my port building and my short calculations says that it should be about 1500 wares there. It is possible, but unbelievable.

Traffic jams happen just before bottleneck

Bottleneck is: a piece of road with lower capacity than (previous) neighbour(s). So if you have a 2-units road system, the bottleneck will be a piece of road 3-units long. Of course the longest road is, the more visible bottleneck is. Also bottleneck can happen when you have at least 2 roads which are narrowed to 1-road system. Of course those roads should be used.

The bottlenecks aren't the same

As it was told above, the bottleneck can differ. But the mathematical difference is a factor of capacity. If we take 2 equal roads that are narrowed to one, the factor will be 2. So the narrowed road is 2-times less efficient. If we take 2-units length into 3-units one, the factor is 1.5.

Capacity depends on road lengths

Total capacity of a single road can be calculated. Known data is that every unit has velocity equals to 1 unit per 1.8 seconds of gametime. Every minute the carrier walks through 33.3 units. That means... 8.3 full walks between flags in range of 2 units. And 4.16 full walks between flags in range of 4 units. And almost 1 unit per minute in 17-units length road.

The worst traffic system

  1. Build as long roads as possible
  2. Build as less flags as possible
  3. Consider making real bottleneck of bottlenecks of ...

Is this a partly mathematical view on your problem face-smile.png


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 204
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-24, 23:48

@einstein13

Feeding low-capacity roads with high-capacity roads guarantees that on high-enough traffic the high-capacity roads will have to idle for some periods of time, their carriers waiting in front of flags full of wares, while the low-capacity roads serve their load. But none of the involved roads will reach full congestion, as they will still operate, just in a slower pace. In other words, the wares at the flags will keep getting served, slowly but reliably. Given infinite time, such a configuration can serve an infinite amount of wares. This is not what I want.

Under some road-configurations (I'm not totally sure which ones, but it has to do with the state of the involved carriers), some roads may stop operating indefinitely, as one of their flags stops serving them, preferring to serve other roads instead. That can cause problems to the economy, especially if the wares in those roads are valuable. But still the rest of the transportation system is operating. This is not what I want either.

Under some road-configurations (that the AI manages to achieve from time to time), one or more central flags stop serving any ware at all (due to some state of mutual exclusion), and after a while most flags get full of wares and the whole transportation system gets fully congested and nothing moves anymore. This is what I want, in order to consider it a valid participation to the competition. The winner is whoever achieves that in the shortest amount of time.


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 985
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-25, 10:47

Ok...
Let's say:

Carriers in the centre don't move at all. Conditions:

  • 10 farms working on the right
  • 10 wells working on the top
  • 10 woodcutters working down
  • Warehouse for crops is on the left
  • Warehouse for the wood is top
  • Warehouse for the water is on the right
  • first: let building produce some resources
  • then complete roads to the warehouses
  • wait about 2-3 minutes to make congestion

But this happen artificially. AI doesn't do this situation. Probably more often there is a ware rerouting which can cause similar situation.

Avoiding this situation is very simple: make target place for the resource without any bottlenecks. I took care about making this crossroad (or rather triangleroad) a bottleneck for the whole economy. With no circles of roads in your economy you can't have full stop. But this would be inefficient for the economy. So let's say: don't make small circles. Make it big. That will influence that congestion is highly unlike. Also two-ways-circle is also doing this job well. face-smile.png


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote