Latest Posts

Topic: Decongestion algorithm

LienRag
Avatar
Topic Opener
Joined: 2024-05-04, 16:59
Posts: 28
OS: Linux
Ranking
Pry about Widelands
Posted at: 2024-07-25, 19:02

Hi Widelands;.

I understand that avoiding Congestion is a skill and requires careful planning, but the way congestion works now is way too punishing imho, especially for non-hardcore players.

Especially, Congestion where all the carriers go in the same direction is harsh but manageable, it just delays the transportation of wares by the bottleneck it produces, but the wares get where they need to be, it just takes way more time.
So it's the right way of punishing the player : reduced efficiency of the economy, but proportional to the bottleneck created, and doesn't spiral out of control.

But Congestion where carriers try to transport wares in both direction sometimes lead to a complete breakdown of the economy, with no easy way to solve : the carrier who's supposed to take away the ware is prevented from depositing his own ware, so the flag doesn't allow for ANY transportation at all.

It also brings paradoxical behaviors : I had bakeries with water in front of them, but not producing anything because water was missing, and as such not serving as the sink for water and flour that they were supposed to be.
I guess that the water that was supposed to be delivered to them was blocked a few flags away by the general congestion, but that's a very counter-intuitive behavior and leads to an infuriating cascade of problems that takes a real lot of micro-management to solve.

I also had buildings not completing (and so not functioning as a sink for building materials and input wares) even though the building material was in front of them.

So, my suggestion is to have a very simple decongestion algorithm, which should be easy to implement : when a flag is full, the building which are in front of it check if they need an item that is on the flag, and if they do then they take it whatever destination the ware was initially supposed to go.
Yes, it will bring some other problems, but imho that's getting back to the right type of punishment for bad road planning, and shouldn't cascade like the current behavior.

A similar algorithm could be proposed as an option for Warehouses, aside the existing ones "normal, don't accept wares, remove wares, fetch wares" : decongestion ware.
A warehouse whose flag is full should drop its current action, check if on the flag there is a ware that has the option "decongestion" active, and if so, send the worker take the ware and put in the warehouse (if there are many with "decongestion" active, it should take the most abundant one).
Then when the flag isn't full, the warehouse worker should take the wares with "decongestion" active which are in the warehouse and drop them on the flag.

It makes careful planning a little less mandatory, but not that much (you still need to plan for the right warehouses on the right spots) so imho it is quite balanced.
And it should allow to solve relatively quickly even the hardest congestion conundrums, provided the player starts with method.


Top Quote
kaputtnik
Avatar
Joined: 2013-02-18, 20:48
Posts: 2542
OS: Archlinux
Version: current master
Ranking
One Elder of Players
Location: Germany
Posted at: 2024-07-25, 20:02

Take a look at my-roads-are-congested-with-too-many-wares

While i understand that new players might get congestion on the roads, i think it is a thing one has to learn.

Formerly, especially on some specific maps, i had this problem also. But in the meantime i never get into such situations. Ok, never say never face-grin.png ... sometimes it happens to me also now but with some additional roads and time it get solved and wares get transported normally again.

widelands is a game where you have to mange your economy, and roads are a fundamental thing in the economy of widelands. If we change this widelands will not be widelands anymore, imho.


Top Quote
LienRag
Avatar
Topic Opener
Joined: 2024-05-04, 16:59
Posts: 28
OS: Linux
Ranking
Pry about Widelands
Posted at: 2024-07-25, 22:04

Yes, this is precisely what I said in my first phrase (well, technically the second, the first being "hello widelands").

I'm not sure that my proposal would entirely remove the necessity to manage one's economy, though - it will just make it less punishing and easier to correct.

"Managing your economy" != "having everything break down in a spiral of doom if you make one mistake" and is imho more fun in the "if you make mistakes your economy gets slower", which my proposal keeps.


Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16
Posts: 2730
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2024-07-26, 08:42

well,
We are open for suggestions all the time, however please avoid the phrase "that should be easy to implement" unless you are suggesting the exact necessary code changes (although that would be better done in a Pull request.
From my perspective (although I am not the expert for the econmy code) the suggested change would not work well with our current economy code.
Backkground is that our economy works on a request basis. So if there is a request generated, the code looks whether we have a suitable ware in our economy, to fulfill that request if yes a ware gets assigned with this request (you can see this by the darker colour of the ware in the input queue of the building where the request got created. now the ware knows its target and the routing code is executed for the ware (this takes the load factor of flags into account, to prefer less congested alternative routes), this routing code is quite expensive in terms of processing time. Afterwards the economy has not much to do with the ware anymore, as it is just finding its way by working the path assigned to it. Only we do check whether the path is still valid. if this mechanism would be implemented we would need to change the code of the complete economy as we would need to implment the checks suggested, the cancellation mechanism of requests, the reopening of requests and a lot of other things.
However I believe I remember, that our chieftain already invented or even implemented in the dev version the concept of economic regions which should prefer nearby supplies over supplies far away and this should help to deal with this issue as well.


Top Quote
kaputtnik
Avatar
Joined: 2013-02-18, 20:48
Posts: 2542
OS: Archlinux
Version: current master
Ranking
One Elder of Players
Location: Germany
Posted at: 2024-07-26, 15:39

LienRag wrote:

"Managing your economy" != "having everything break down in a spiral of doom if you make one mistake" and is imho more fun in the "if you make mistakes your economy gets slower", which my proposal keeps.

As i said one can solve congested roads: Build more roads as alternative routes. Beside building new roads a warehouse should have roads which bypasses the warehouses flag. So wares which doesn't go to the warehouse will not clogging the warehouses flag. As a last resort one can also remove flags with lots of wares and build a new road, or better roads. But keep in mind that destroying a flag that holds a lot of wares, the wares will be lost.

If possible you could also use double-roads, like in the screenshot.


Attachment:
shot0002.png

Top Quote
LienRag
Avatar
Topic Opener
Joined: 2024-05-04, 16:59
Posts: 28
OS: Linux
Ranking
Pry about Widelands
Posted at: 2024-07-26, 16:01

hessenfarmer wrote:

well,
We are open for suggestions all the time, however please avoid the phrase "that should be easy to implement" unless you are suggesting the exact necessary code changes (although that would be better done in a Pull request.
From my perspective (although I am not the expert for the econmy code) the suggested change would not work well with our current economy code.
Backkground is that our economy works on a request basis. So if there is a request generated, the code looks whether we have a suitable ware in our economy, to fulfill that request if yes a ware gets assigned with this request (you can see this by the darker colour of the ware in the input queue of the building where the request got created. now the ware knows its target and the routing code is executed for the ware (this takes the load factor of flags into account, to prefer less congested alternative routes), this routing code is quite expensive in terms of processing time. Afterwards the economy has not much to do with the ware anymore, as it is just finding its way by working the path assigned to it. Only we do check whether the path is still valid. if this mechanism would be implemented we would need to change the code of the complete economy as we would need to implment the checks suggested, the cancellation mechanism of requests, the reopening of requests and a lot of other things.
However I believe I remember, that our chieftain already invented or even implemented in the dev version the concept of economic regions which should prefer nearby supplies over supplies far away and this should help to deal with this issue as well.

Thanks for the explanations.

What I mean is that it could be a simple override, like what happens (I guess) when a flag is destroyed.

And wares put back on the flag (for decongestion of Warehouses) could be treated as new wares, I also guess.

It's true that I don't know your codebase, but from what I understand the changes should be limited (by reusing existing mechanisms, as mentioned above).

Of course cancellation of requests would be more frequent with a decongestion algorithm than with flag destruction (as I guess that most players don't usually destroy flags with wares), so the impact on the processing resources needed may be a problem.


Top Quote
mxb2001
Avatar
Joined: 2019-05-20, 18:49
Posts: 282
OS: Linux
Version: 1.2
Ranking
Tribe Member
Location: The land of the thirsty spider
Posted at: 2024-07-27, 01:30

kaputtnik wrote: But keep in mind that destroying a flag that holds a lot of wares, the wares will be lost.

Just don't destroy the flag in front of your buildings (such as was the case Lien had) as that would be rather more costly. : )

Depends on the building though. Some are pretty damn cheap. Bakeries could be torched and rebuilt I guess...


--
To Boldly Go Where No Man Has Gone Before

Top Quote
teppo

Joined: 2012-01-30, 09:42
Posts: 424
Ranking
Tribe Member
Posted at: 2024-07-27, 13:22

LienRag wrote:

It also brings paradoxical behaviors : I had bakeries with water in front of them, but not producing anything because water was missing, and as such not serving as the sink for water and flour that they were supposed to be.
I guess that the water that was supposed to be delivered to them was blocked a few flags away by the general congestion, but that's a very counter-intuitive behavior and leads to an infuriating cascade of problems that takes a real lot of micro-management to solve.

Presently, wares are carried to buildings by the same person who brings it to flag. If a ware needed by building is sitting on the flag, then the ware was probably not intended to that building at all. Or at least it was so previously. With source code available, it might be possible to change the behavior so that the worker picks his stuff from flag, instead of deliver to door.

Some things that could happen when the flag is stuck:

  • The carrier could attempt to re-route the ware (assuming circular topilogy (=other routes exist)).
  • The carried could attempt to see if another identical ware is on the other side of the choke point heading towards here. If found, replace the targers (assuming non-circular topology). This way, neither of these two items would need to pass though the stuck flag.

Making these in a cpu-efficient way might be a challenge.


Top Quote