The International Simutrans Forum

 

Author Topic: Overcrowding. Deadlocks. Max loading...  (Read 8439 times)

0 Members and 1 Guest are viewing this topic.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Overcrowding. Deadlocks. Max loading...
« on: March 07, 2009, 05:47:14 AM »
Just at the same time the overcrowding problem with passengers and deadlocking was being discussed, I was having and trying to solve the same in my game (one with pak.german).  The problem, simplified, is this:

We have one product, wood, and factories and consumers linked like this:

FactoryA  |                            | ConsumerA
ConsumerB | STATION1 -------  STATION2 | FactoryB


FactoryA makes STATION1 full of wood for ConsumerA.
FactoryB makes STATION2 full of wood for ConsumerB.
A train in STATION1 cannot move wood to STATION2 because it is full.
A train in STATION2 cannot move wood to STATION1 because it is full.

In the real example, there is a pair of hub stations in between to pass a plateau.  It is important because with the simplified example there would be no problem: the full patch will consider only transfers and not destinations because the store is supposed to be inside the factory.

To solve that, I tried to make two separate stations on each side: one pair to move wood from east to west and the other to move wood from west to east:

FactoryA  | STATION1(W->E) -->-->---  STATION2(W->E) | ConsumerA
ConsumerB | STATION1(E->W) --<--<---  STATION2(E->W) | FactoryB


But, what happens?  Trains will not refuse to transport wood in the wrong direction and the deadlock survives.

The solution I've devised was already proposed a lot of times here: max loading.  So, with one train, I can do this and get a very good profit because it will be loaded in both directions.  Its schedule:
  • STATION1(W->E), load min 100%, max 100%
  • STATION2(W->E), load min 0%, max 0%
  • STATION2(E->W), load min 100%, max 100%
  • STATION1(E->W), load min 0%, max 0%

A patch is attached.  Please, consider this:
  • With the max patch, it comes the overcrowding and QoS patch since I'm playing with that
  • No aesthetics is intended (only to test functionality)
  • Trunk games cannot be loaded and saved games will not be loaded by trunk

EDIT 1: The game I'm playing, for seeing the problem/solution. The involved stations are located at the north part of the map and their names are LYON transfer and ZURICH transfer.
http://simutrans-germany.com/files/upload/c53.sve

EDIT 2: And a cross-compiled Windows binary for lazy people  ;)
http://simutrans-germany.com/~patches/download.php?file=sim-wingdi-max-r2260.zip
« Last Edit: March 07, 2009, 06:25:54 AM by isidoro »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9585
  • Languages: De,EN,JP
Re: Overcrowding. Deadlocks. Max loading...
« Reply #1 on: March 07, 2009, 09:29:32 PM »
You could get you max loading also using shorter stations, as written also in said thread.

This will also not work for passengers: Imagine the line between a harbour and a transfers station and both are overcrowded. If you cannot simply add another harbour (because of space constraits) then thing will get very difficult.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Overcrowding. Deadlocks. Max loading...
« Reply #2 on: March 08, 2009, 12:03:48 AM »
The patch is more complicated than what is seen at first sight.  The shorter station is not equivalent.  With the patch, if a vehicle is 100% loaded and reaches a point in which 60% load is marked, that is enforced.  40% of pax/goods will unload.

Changes had to be done to routing too.  Imagine a line:
A-B-C(0%)-D-E(0%)-F

Vehicle will be completely unloaded in C and E.  Thus, B is no connected with D if only this route exists.  That also make circular routes profitable, even with payment relative to transfer.

In my implementation of avoiding full stations, passengers work different than goods due to one of your suggestions.  If a pax cannot travel any longer, it becomes unhappy and discarded.  But for goods, it cannot be done, as you said, because then an unlimited source of money can be built.  With passengers, I've had no problems hitherto.

Offline whoami

  • Devotees (Inactive)
  • *
  • Posts: 693
Re: Overcrowding. Deadlocks. Max loading...
« Reply #3 on: March 10, 2009, 05:38:02 PM »
FactoryA  | STATION1(W->E) -->-->---  STATION2(W->E) | ConsumerA
ConsumerB | STATION1(E->W) --<--<---  STATION2(E->W) | FactoryB
I would call this example artificial, because it happens only in rare circumstances, and even then the player has the choice to solve this by connecting a single stop only to one factory (by coverage area).

40% of pax/goods will unload. (...) Vehicle will be completely unloaded in C and E.  Thus, B is no connected with D if only this route exists. (...)
A-B-C(0%)-D-E(0%)-F
Forced unloading, especially complete unloading, changes routing, exactly. Consider the case where there is no additional route (of matching goods category) from C (or E) to the actual destination - unloading then makes no sense, the goods shouldn't be loaded at A/B/D at all. If unloading can happen at several stations, complete routes have to be found for all of them.

What about convoys with different goods categories - which ones should be unloaded, to which amount? There needs to be a GUI that allows the player to define that.

Quote
That also make circular routes profitable, even with payment relative to transfer.
That is a non-problem, because the behaviour was changed on purpose, and is now configurable.

Quote
In my implementation of avoiding full stations, passengers work different than goods due to one of your suggestions.
In general, I would appreciate any solution and further development that tries hard to avoid different cases and exceptions that the player needs to know to build a working network.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Overcrowding. Deadlocks. Max loading...
« Reply #4 on: March 11, 2009, 02:00:14 AM »
whoami, you have missed some points here, imho.  My fault, I guess.  I'll try to further explain it:

I would call this example artificial, because it happens only in rare circumstances, and even then the player has the choice to solve this by connecting a single stop only to one factory (by coverage area).

The example is not artificial, but a simplification.  Deadlocks can only happen at transfer stations.  In those places, you can't play with coverage areas to solve it.  I further explain that in http://forum.simutrans.com/index.php?topic=1040.msg17288#msg17288

Forced unloading, especially complete unloading, changes routing, exactly. Consider the case where there is no additional route (of matching goods category) from C (or E) to the actual destination - unloading then makes no sense, the goods shouldn't be loaded at A/B/D at all. If unloading can happen at several stations, complete routes have to be found for all of them.

Sure.  And that is already done in the patch.  If something has been previously loaded, the patch makes sure that it is because there is a complete route.  It was the most difficult part of the patch.

What about convoys with different goods categories - which ones should be unloaded, to which amount? There needs to be a GUI that allows the player to define that.

Well, that behaves exactly the same as the minimum loading level.  When you put that the convoy has to be 100% loaded before continuing in present ST code, what about convoys with different categories?  It is a property of the route, not of the convoy.

That is a non-problem, because the behaviour was changed on purpose, and is now configurable.

I agree.  It's a non-problem for people wanting to only play with the original revenue system (which can be easily exploited, btw)

In general, I would appreciate any solution and further development that tries hard to avoid different cases and exceptions that the player needs to know to build a working network.

Well, passengers and goods do behave very differently in ST now.  It is not really an exception since now they already behave differently.  Goods cannot become unhappy, for instance.  Passengers and goods are generated differently, etc.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9585
  • Languages: De,EN,JP
Re: Overcrowding. Deadlocks. Max loading...
« Reply #5 on: March 11, 2009, 09:35:58 AM »
Passengers and goods behave the same, with one execption: goods are merged only if their desitnation coordinates are identical while passengers are merged when their destination station are identical. Other than that they are treated exactly the same way.

And a forced unloading would break the simutrans routing in many way, since it would lead to connected routes which are actually not conntected at all.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Overcrowding. Deadlocks. Max loading...
« Reply #6 on: March 11, 2009, 01:13:40 PM »
Passengers and goods behave the same, once they are generated.  But they behave very differently when they are generated (that's the main reason for they to be differently treated in this case, btw).  So, I can't see an exception here.  It's not like saying coal and wood will have different behaviors.  That would be an exception.

Can you give an example of the second?  I've been playing for some time and have seen none.

Offline whoami

  • Devotees (Inactive)
  • *
  • Posts: 693
Re: Overcrowding. Deadlocks. Max loading...
« Reply #7 on: March 11, 2009, 11:27:07 PM »
The example is not artificial, but a simplification.  Deadlocks can only happen at transfer stations.  In those places, you can't play with coverage areas to solve it.
I could try to keep up my point by extending it to transfer stations, but it would be a bad design choice to require the player to set up completely separated networks for every kind of goods connection, or choose the alternative of risking deadlocks. Unwanted/unintended routing already happens anyway. Who knows if the players would appreciate a function that allows them to specify a static route (which makes sense mostly for high-volume goods connections).

Quote
Sure. And that is already done in the patch.
Sorry, I wasn't able to understand the patch, it involved changes to several core modules, and wasn't limited to dealing with overflowing stops or deadlocks.

Quote
Well, that behaves exactly the same as the minimum loading level.  When you put that the convoy has to be 100% loaded before continuing in present ST code, what about convoys with different categories? 
Example: train has one capacity (X% of the total) for freight category A, and Y% for category B. To leave when enough of category A is loaded, set loading level to a value <= X. This assumes that nothing of category B will be eligible there.

Forced unloading is different - the program has to decide which freight may leave the convoy at the stop.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Overcrowding. Deadlocks. Max loading...
« Reply #8 on: March 13, 2009, 12:16:02 AM »
...but it would be a bad design choice to require the player to set up completely separated networks for every kind of goods connection,...

As I explain above.  It is not required to build a separate network for every kind of goods.  Kind of goods has nothing to do with it.  Goods are treated as a whole.  The objective is to build a single network without goods dependence loops.

Sorry, I wasn't able to understand the patch,...

Forcing a capacity limit in stations may produce deadlocks.  This patch gives the player a tool to be able to design networks free from the deadlock danger.  Surprisingly enough, allowing the player to set the max. loading value for a convoy allows the design of those kinds of networks.  In essence, it allows one-way connections.

For example, if you have two stations A and B and a steel train connecting them, in traditional Simutrans, that train will carry any steel from A to B and any steel from B to A.  It is always a bidirectional connection.

With this patch, you can set a route:
  • Wait 100% load at A
  • Max. Load 0% at B

With such a route, steel will be carried from A to B, but never from B to A.  Using such routes, you can build a network free from deadlocks.  I hope I made it clear.

Example: train has one capacity (X% of the total) for freight category A, and Y% for category B. To leave when enough of category A is loaded, set loading level to a value <= X. This assumes that nothing of category B will be eligible there.

The patch doesn't work like that: suppose it is 40% steel, 60% wood.  You set max loading at 50%.  20% of steel and 30% of wood will be loaded if you have plenty of both at the station.

Offline ij

  • *
  • Posts: 41
Re: Overcrowding. Deadlocks. Max loading...
« Reply #9 on: March 13, 2009, 09:20:46 AM »
IMHO this max. load idea is horrible, it avoids deadlock yes, but it's cost...

It forces player to design highly unrealistic one-way connection. It's well, unrealistic and arguably very uneconomical as well.

If there's a bidirectional train between two stations that are overcrowded the train will basically load as much as it carries over so no balance at the either of the stations is going to change anywhere (assuming that it is a "joint-congestion", ie., it's feed from outside and then basically large quantity of goods are waiting to get moved to other end, the latter is not always true but lets ignore that for now), IMHO loading should be allowed in this kind of case regardless of the overcrowded check. The real solution would be to force the feeders of such a "joint-congestion" point to slow down which will happen in this situation because they cannot push more to overcrowded stations until the situation clears up. There's no need to stop vehicles that don't add anything to the congestion.

How about allowing loading in case both stations if both stations have eligible goods back to the other regardless of overcrowded state (needs more complex check since it would actually be possible in a circle line as well but most of the cases are just between two stations, the circle line just needs to be handled on the slow path), it should be cheap enough to calculate. If there are two consecutive "joint-congestion" points the feeder/consumer-consumer/feeder vehicles would keep moving while feeders-only need to slow down since they cannot load at will if the destination is overcrowded.

Offline isidoro

  • Devotee
  • *
  • Posts: 1129
Re: Overcrowding. Deadlocks. Max loading...
« Reply #10 on: March 13, 2009, 01:19:09 PM »
I think you had an excellent idea, ij!  Allow sending goods to the station if we're sure that there's a full load at destination back.  It will certainly not alleviate all cases (cycles of higher orders), but I guess that most in real situations.

I can't agree with your dislike about max. loading.  In past time, I didn't find it useful too, though long time demanded.  But, in combination with your mechanism, it can solve 100% cases.  Besides, players can use it to regulate flux of goods and make circular lines profitable, even with the new payment system.

Offline ij

  • *
  • Posts: 41
Re: Overcrowding. Deadlocks. Max loading...
« Reply #11 on: March 14, 2009, 08:11:38 AM »
I can't agree with your dislike about max. loading.  In past time, I didn't find it useful too, though long time demanded.  But, in combination with your mechanism, it can solve 100% cases.  Besides, players can use it to regulate flux of goods and make circular lines profitable, even with the new payment system.

I can imagine you find so... I suppose its because we lack schedules, ie., the other key element of reality which would effectively deal such regulation. Our trains just follow greedy behavior to begin with :-D. On the second thought, besides schedules the cars are real and switchable and some would be moved as empty if necessary in real railroads too so it's probably not as unrealistics I claimed it to be.