Round robin scheduling for trains / Train Limits can Soft-Deadlock when Incoming and Outgoing are Both Full

[asheiduk]

If you where to have train schedule with A B C for example, and more trains, then some trains could be considered "pending" for C being stationnary at station B preventing some trains leaving A. The Soft deadlock could still occur if those trains waiting at A prevent train at C from completing the 3step loop.

I'm not sure about the last sentence: If the trains in "B" are also "ready to go" (i.e. the wait condition is completed) then they would also unregister at "B" and a train from "A" could register and start moving. If nothing else this would unlock a "C" train.

But in this case, it could be that train at B are waiting for materials. trains at A are thus logically waiting for room in the next train stop. and preventing trains at C from piling up behind them despite train condition for train stop A being fulfilled. This is the acual behavior. Here the proposed change would allows all trains at C to complete the loop and you'd have more trains behind each A station than you set the limit to. ( potentially causing train waiting outside stackers or crash if you don't use signals ).

If signals are missing then both the current and the new behaviour can deadlock (hard, not soft). Consider that a train in "A" inches forward a little bit to the next signal. The station is free now (in old and in new behaviour) and a nearby train repathes and shows up immediately at the station. If the incoming train blocks the outgoing train due to missing signals then this is a hard deadlock. Since reapthes are possible this a matter of "when" not a matter of "if".

In other word, the proposed change wouldn't function in all soft-deadlock situations but would cause some existing system to break. ( at least from my understanding maybe i've missed someting).

I don't think this proposal is intended to solve all deadlocks -- soft or hard. But it is an imprevement. Regarding the "breaking things": I though the same at first. But I couldn't come up with a Short, Self Contained, Correct, Example to demonstrate that. The examples I've come up with would break also with the current behaviour.

On a side note the same thing can happen if you only have 2 block in your train network, and 2 trains. Then each train is on its own block and there is a soft deadlock. Or let say 5 block and 5 trains. The same logic apply if you have 20 trains and the sum of the limit allowed in your station is also exactly 20.

I don't think mixing signals (and therefore blocks) and train stops adds something to the topic here -- see above.

[mmmPI]

This is a good potential point and one reason I posted this in Ideas and Suggestions instead of bugs. There could be unforeseen side-effects.

[/quote]

Thank you x), Nilaus is funny to hear when he says it's a not a "bug in a technical sense", it's an un-in-tend-practical feature

And if I recall the whole Train Limits feature was added to help reduce the “18 trains race to a single station that just opened” issue.

Yes the so called herd effect. When all station are closed and only 1 opens, if the limit is 1 only 1 train moves there with the limit. Without, ALL pending trains with that station would have started their way and would have either get stuck of need a force repath if you close the 1 station after 1 train.

However, in the video those stations are closed. When they were open the trains were running smoothly since there was a free station available. However, adding another train in the empty branch and enabling all the stations would likely trigger this same condition. And if all five of those trains were empty there could be a rush of trains.

Here i think you means the empty station in the bottom part of the example at 4:26. Those empty station are closed. But this is different than what i was trying to explain at first. This is related to the sidenote at the end of my previous post in my mind. Basically by closing the empty stations in the bottom part, you reduce the amount of total station availble for trains to the exact number of trains, causing a soft deadlock.

It's a bit different than the other thing which would be "when does a train leaves a station for the game".

In this case there is not 1 precise moment, which cause the confusion. There is 1 moment where the train leaves the station and stop outputting a signal T. And there is another moment when the train actually moves toward the next destination and visually leaves the station.

In between those 2 moment, there is no signal T, but the train limit and train present as read by the station is still 1.

The fact that it's still 1 is what causes the deadlock because no other train can join including trains stuck in the same state.

But in my opinion it is necessary that it is still 1 otherwise in between the 2 moment i mentionned, [when a train is stuck with "destination full" at departure], then the station would be considered "available" or "open" with the limit 0/1. And a train would be free to go there. ( no deadlock).

Trains should not be allowed to move in a train stop when the previous train hasn't left, that's good. ( except in situation where it creates deadlock ).

I think the occuring of those deadlock are consequences of the limit implementation, but also necessary. It's how it is supposed to work for the general cases. Which in the edge case where you have eactly the same number of trains and stations-limit-slots well the limit prevent train from moving. The limit SHOULD prevent train from moving .

Perhaps a better solution might be for the limits system to check if a train pair are both “waiting to leave” and therefore have valid paths to each other (or basically is there a receiving station for this train that wants to leave which *also* has a train wanting to leave) then, in very certain circumstances schedule an overflow limit (or whatever has to happen behind the scenes).

That would be a theoric solution, in this case the pairing would function it would prevent the deadlock caused by the mechanism in question.

But one terrible case would be something like having stations called A B C D E F G H I J and so on, so say 26 stations, and then you also have 26 trains with the alphabet as schedule. There is a soft dead-lock, since the train at Z can't go to A, the train at A can't go to B and so on, the "pairing" would require that the game detect there is a possibility for the trains to move if all 26 of them move at the same time.

And this is still a "simple" case, because it's just 1 loop, but there could be trains with part of the alphabet, and other trains with another parts overlapping, so maybe only 2 or 4 or 12 of those 26 could move at the same time. The system would have to check so many possibilities in the worst cases.

[asheiduk]

However, in the video those stations are closed. When they were open the trains were running smoothly since there was a free station available. However, adding another train in the empty branch and enabling all the stations would likely trigger this same condition. And if all five of those trains were empty there could be a rush of trains.

AFAICT the current rule of thumb is: For N Stations you can have at most have N-1 trains. The new rule of thumb would just increment "N-1" to "N". But going above N just calls for deadlocks.

Perhaps a better solution might be for the limits system to check if a train pair are both “waiting to leave” and therefore have valid paths to each other (or basically is there a receiving station for this train that wants to leave which *also* has a train wanting to leave) then, in very certain circumstances schedule an overflow limit (or whatever has to happen behind the scenes).

Sounds complicated both to implement and to understand by the player. And it would not solve the C vs T signal issue.

[mmmPI]

I'm not sure about the last sentence: If the trains in "B" are also "ready to go" (i.e. the wait condition is completed) then they would also unregister at "B" and a train from "A" could register and start moving. If nothing else this would unlock a "C" train.

I was attempting to describe the same deadlock that occur with 2 station but instead with 3 stations. Trains do no "unregister" until they have a free destination.

If have 1 train at A pending for B, 1 train at B pending for C and 1 train at C pending for A, then you have a deadlock.

If the train at B is not pending for C but instead receiveing material. then the train waiting in A is logically stopped preventing the train waiting at C to come in A. Because the train in A is not "unregistered from A yet" since the train at B is still loading. The train A is then stuck with "destination full message". And here you don't want the train at C to come to A.

Later when the train in B is filled with material, it cannot go to C since there is a train waiting for room in A where there is a train waiting for room in B where there is a train waiting for room in C and so on.

Hence why a "pairing" would be required to unlock the mess.

But the earlier proposed solution would have allowed the train stuck in C to go to A no matter the state of B, wether it is being filled with material, or if it was just a softdeadlock.

If signals are missing then both the current and the new behaviour can deadlock (hard, not soft). Consider that a train in "A" inches forward a little bit to the next signal. The station is free now (in old and in new behaviour) and a nearby train repathes and shows up immediately at the station. If the incoming train blocks the outgoing train due to missing signals then this is a hard deadlock. Since reapthes are possible this a matter of "when" not a matter of "if".

This is something different i'm not talking about missing signal, just in the case where you don't use signal. in this case train don't crash when you use the train limit system. because only 1 train can be at a train stop with a limit of 1, never 2.

There would be 2 trains at the same train stop if you allow a train to "unregister" with "destination full", the stuck train and a potential arriving train that would crash into the first one. ( or wait outside the stacker if you use signals).

I don't think this proposal is intended to solve all deadlocks -- soft or hard. But it is an imprevement. Regarding the "breaking things": I though the same at first. But I couldn't come up with a Short, Self Contained, Correct, Example to demonstrate that. The examples I've come up with would break also with the current behaviour.

I don't think mixing signals (and therefore blocks) and train stops adds something to the topic here -- see above.

Well if you don't use signals, there are system that function atm and they would ALL break wuth the proposal.

A simple case is a loop with station A B C D without any signal, and 3 trains on it. ( 4 trains would create the soft deadlock).

Let say your 3 train are supposed to go to A untill full then B untill empty then C untill full then D untill empty.

All limit are always 1.

let say you set the limit of station C to 0

the train in station B is waiting to be unloaded, and then will wait with "destination full".

With the original proposal, the train at A when full will go to station B since the proposal means the train at B is unregistered. And then the train that was in A will crash into the train waiting at B.

this system function without signals at the moment.




The other thing i wanted to explain with signals is that the hard deadlock occur when you don't have enough blocks , the soft deadlock occur when you don't have enough "station-limit-slot". It's the same logic.

Edit : this basically =

AFAICT the current rule of thumb is: For N Stations you can have at most have N-1 trains. The new rule of thumb would just increment "N-1" to "N". But going above N just calls for deadlocks.

[Tricorius]

If have 1 train at A pending for B, 1 train at B pending for C and 1 train at C pending for A, then you have a deadlock.

If the train at B is not pending for C but instead receiveing material. then the train waiting in A is logically stopped preventing the train waiting at C to come in A. Because the train in A is not "unregistered from A yet" since the train at B is still loading. The train A is then stuck with "destination full message". And here you don't want the train at C to come to A. (This is a valid lock due to activity on a train that hasn’t completed its “wait condition” and should block trains “behind” it.)

Later when the train in B is filled with material, it cannot go to C since there is a train waiting for room in A where there is a train waiting for room in B where there is a train waiting for room in C and so on.

…

But the earlier proposed solution would have allowed the train stuck in C to go to A no matter the state of B, wether it is being filled with material, or if it was just a softdeadlock.

The proposal would not unregister B since it is still loading. So it has 1/1, preventing A from moving. It *can’t* get a valid path, so it doesn’t unregister (perhaps I implied that restraint instead of stating it). Therefore it is also still at 1/1 because it hasn’t unregistered it’s lock (no valid option). Since it is still 1/1, then C can’t unregister as it has no valid path.

When B fills, it completed its wait condition, and is now T = 0 && C > 0. It unregisters.

B is now 0/1 and A can path to it. So A unregisters and becomes 0/1. Now C can path to it and becomes 0/1. For a tick or so. Then since they all now have trains pathing they are 1/1 again and with stay so until the new trains arrive and the whole thing happens again.

Therefore:

To clarify the "bug":
1. train wants to leave
2. there is no free station available. All destinations report x/x as trainlimit/train reservation.
3.The train has left the station (no "T" signal) yet the station counts the departed train toward the reserved trains in x/x

I'd like to extand 3) with: ("C" signal is still greater than zero)

The tooltip for the "C" signal is: "Number of trains going to this train stop. Includes the stopped train" So even the tooltip suggests that "Read stopped train" and "Read train count" should correlate -- but don't actually.

The clarification needs a

4) The train will only release its reservation if it would otherwise be allowed to continue to its next stop (the next stop isn’t stuck at max limit. (This prevents a premature pathing if the destination is blocked by a train still taking action.)

[mmmPI]

When B fills, it completed its wait condition, and is now T = 0 && C > 0. It unregisters.

B is now 0/1 and A can path to it. So A unregisters and becomes 0/1. Now C can path to it and becomes 0/1. For a tick or so. Then since they all now have trains pathing they are 1/1 again and with stay so until the new trains arrive and the whole thing happens again.

balden part is problematic to me. If it unregisters it means it has found a valid path to C, which is not possible since there is a train in C waiting for room in A where there is a train waiting for room in B.

The train in B cannot see a valid path to C unless the game also does a pairing to make all 3 train rotate at the same time.

The clarification needs a

4) The train will only release its reservation if it would otherwise be allowed to continue to its next stop (the next stop isn’t stuck at max limit. (This prevents a premature pathing if the destination is blocked by a train still taking action.)

This doesn't seem to solve the problem for me, in the case when you have N trains and also N station available, the trains would not otherwise be allowed to continue to their destination. If you add this condition i think you are re-introducing the soft deadlock. ( which again imo is not something you can avoid if you have N train and N station-limit-slot) the solution would be like Nilaus says in the video to always have more station opens than trains. at least 1.


Edit: I participated in the discussion about the train limit, I was sceptical about it, that it could be implemented, and that players would find ways to use it at first but i was wrong

[Tricorius]

When B fills, it completed its wait condition, and is now T = 0 && C > 0. It unregisters.

B is now 0/1 and A can path to it. So A unregisters and becomes 0/1. Now C can path to it and becomes 0/1. For a tick or so. Then since they all now have trains pathing they are 1/1 again and with stay so until the new trains arrive and the whole thing happens again.

balden part is problematic to me. If it unregisters it means it has found a valid path to C, which is not possible since there is a train in C waiting for room in A where there is a train waiting for room in B.

The train in B cannot see a valid path to C unless the game also does a pairing to make all 3 train rotate at the same time.

The train system is already “looking ahead” to the next station. Right now, it doesn’t consider a train that has completed its wait condition a valid path. This proposal would have to check that condition. So:

4) The train will only release its reservation if it would otherwise be allowed to continue to its next stop (the next stop isn’t stuck at max limit—has an active train that has not completed its wait condition—T <> 0). (This prevents a premature pathing if the destination is blocked by a train still taking action.)

So, B, while loading, is T=1 (I think) which is a hard-block. When it completes, it’s T=0 && C > 0, thus it qualifies for a soft-block.

I guess the algorithm may not unlock any trains in that iteration so none would be released. However, the next iteration should unregister at least one of the trains, which would set the others in motion. (Might take a few iterations depending on how the algorithm works; but all trains would unlock cleanly soon(ish).

This doesn't seem to solve the problem for me, in the case when you have N trains and also N station available, the trains would not otherwise be allowed to continue to their destination. If you add this condition i think you are re-introducing the soft deadlock. ( which again imo is not something you can avoid if you have N train and N station-limit-slot) the solution would be like Nilaus says in the video to always have more station opens than trains. at least 1.

Edit: I participated in the discussion about the train limit, I was sceptical about it, that it could be implemented, and that players would find ways to use it at first but i was wrong

As mentioned above, the system would have to take into consideration a “hard-lock” (train’s wait condition is unfulfilled) and “soft-lock” (train’s wait condition is fulfilled). A hard lock means no valid path; sorry you get to wait until the next iteration and check again. A soft lock means you *might* be good to go. (Depending on how the algorithm iterates the pathing lists.)

Admittedly, this does, as mentioned earlier, only solve up to N stations and N trains (which I think is a reasonable assumption to have). If you have one too many trains, it’s going to hard-deadlock and you’ll see a train stuck somewhere.

In the case of N = N, you just see a bunch of trains, sitting in all their stations saying “destination full” and you’re thinking “well…they shouldn’t be”…

The ultimate solution, of course, in Factorio is supply > demand. But that doesn’t solve the logic paradox of having a chain of trains that are sitting on their thumbs, effectively saying to each other “no…I insist! You go first.” (It took Nilaus a while to debug this and come to the conclusion that these other options aren’t viable—due partially to this “bug”—and to end up understanding that it is even a supply / demand issue in the first place. Seeing all your trains with “destination full” makes me think I goofed up signals or a circuit condition.)

[mmmPI]

4) The train will only release its reservation if it would otherwise be allowed to continue to its next stop (the next stop isn’t stuck at max limit—has an active train that has not completed its wait condition—T <> 0). (This prevents a premature pathing if the destination is blocked by a train still taking action.)

I think this is a more formal description of a simplified "pairing system."

In other word following the conditions of 4) would work, but with your description only if the schedule is 2 station.

If you have more than 2 station you need to add other conditions to possibly realease the reservation. Which may be or not possible to do in practice i cannot picture that if it's possible

Precisely, in the situation of the alphabet with each letter being a station and having 26 trains. The game would need to look at the next stop state, which itself depend on the next stop state, which itself depend on the next stop state, and this is circular. While your 4) consider the anwser for a train departure only depends on its own condition and the next stop. but the next stop state depend on stop even further, which itself depend on the stop even further and so on.

Maybe i'm wrong this is just projections so it's easy to make mistakes but i think your proposal 4) with the specifications quoted wouldn't break existing system ( such as those not using signals) but wouldn't solve soft deadlocks with more than 2 stations.

( but i'm having trouble vizualising with more than 1 trains or more complex schedule, i need more time to think about it )

[Tricorius]

4) The train will only release its reservation if it would otherwise be allowed to continue to its next stop (the next stop isn’t stuck at max limit—has an active train that has not completed its wait condition—T <> 0). (This prevents a premature pathing if the destination is blocked by a train still taking action.)

I think this is a more formal description of a simplified "pairing system."

In other word following the conditions of 4) would work, but with your description only if the schedule is 2 station.

If you have more than 2 station you need to add other conditions to possibly realease the reservation. Which may be or not possible to do in practice i cannot picture that if it's possible

Precisely, in the situation of the alphabet with each letter being a station and having 26 trains. The game would need to look at the next stop state, which itself depend on the next stop state, which itself depend on the next stop state, and this is circular. While your 4) consider the anwser for a train departure only depends on its own condition and the next stop. but the next stop state depend on stop even further, which itself depend on the stop even further and so on.

Maybe i'm wrong this is just projections so it's easy to make mistakes but i think your proposal 4) with the specifications quoted wouldn't break existing system ( such as those not using signals) but wouldn't solve soft deadlocks with more than 2 stations.

( but i'm having trouble vizualising with more than 1 trains or more complex schedule, i need more time to think about it )

Should be fine. Each train checks the station in front of it (already does this, it’s just more restrictive in the permission to go to the next station). This should allow any size of chained stations. It should basically be able to use whatever algorithm they currently use (since limits already work). This proposal loosens that restriction in a very specific way.

As mentioned, the algorithm would be strict (perhaps it won’t release the limit reservation if either station in the check was “cleared” during the current iteration—or whatever). But eventually, over a series of iterations the trains would be clear to leave to the next station, releasing a chain reaction of cleared stations.

[mmmPI]

The ultimate solution, of course, in Factorio is supply > demand. But that doesn’t solve the logic paradox of having a chain of trains that are sitting on their thumbs, effectively saying to each other “no…I insist! You go first.”

haha that's exactly what i imagine train thinking and a good simplication of the problem.

sorry i've been editing a lot my post which makes it difficult to adress points precisely.


It could be nice indeed if there was such solution in the game so that the paradox doesn't occur. But maybe it would also be less of a problem if there was an easier way to understand/visualize when this problem is occuring.

As mentioned, the algorithm would be strict (perhaps it won’t release the limit reservation if either station in the check was “cleared” during the current iteration—or whatever). But eventually, over a series of iterations the trains would be clear to leave to the next station, releasing a chain reaction of cleared stations.

The idea that an algorithm could take up to 26 ticks to solve the problem where you have the alphabet as individual station and 26 trains causing a soft-deadlock is appealing and makes more sense than trying to solve the problem every tick. But at this point it requires more knowledge on the internal code than what i have as a player .

The problem is see for an algorithm that would take up to 26 ticks to solve the problem with 26 station in a deadlock loop, is that it could only function if states are the same at least 26 ticks. If the "early" part of the loop is reset frequently it's harder. Also the memory required to store the early part of the loop over the next tick to continue looking for potential pairing. But i know nothing in algorithm and what capable devs can do

[disentius]

Nice discussion:)
The biggest point is consistency imo. A train station should either be occupied ( T > 0, and C > 0) or not (T = 0, and the departing train is not counted towards C)

[DrFenouil]

Hello,

Imagine you have 3 train stops (S1, S2, S3) with a train limit set to 2 and with the same name. You have 6 trains leaving from the same place. The first train stop (S1) is the closest and the third (S3) is the farthest.

Now let the trains run. The first train will go to S1, the second to S1, the third to S2, the fourth to S2, the fifth to S3 and the sixth to S3. So I will write S1-S1-S2-S2-S3-S3. Trains always go to the nearest train stop, regardless of their position on that train stop.

I think an improvement would be for trains to go to the nearest train stop where they can be in the first position, if not to the nearest train stop where they can be in the second position etc... I our example we would have: S1-S2-S3-S1-S2-S3.

What do you think ?
Sorry if this topic has already been covered.

[DrFenouil]

I realize I didn't give a reason for my suggestion. Here is the continuation of the previous post.

Now imagine that theses 3 train stops are extraction sites (iron or copper), and they're so for from your production center that you need to have 2 trains to keep the flow of your production. Your 6 trains have just been unloaded in your production center.

With the current train behavio, the first train goes to S1 and is loaded, the second goes to S1 and waits, the third goes to S2 and is loaded, the fourth goes to S2 and waits, etc. It's not optimal.

With my suggestion, the first train goes to S1 and is loaded, the second goes to S2 and is loaded, the third goes to S3 and is loaded, the fourth goes to S1 and wait etc. It's better because the first train can have time to empty before the fourth arrives.

If there are only 2 trains ready to go to extraction sites, with the current behaviors the first is loaded and the second waits while with my suggestion both trains are loaded.

[Nidan]

Trains generally use the closet station first, I don't think that's going to change. But you can force the suggested routing by using the circuit network: Connect all 3 stations, read their incoming trains signal and set the limit to 1 + (incoming trains / stations).

The same suggestion was also made in this thread: viewtopic.php?f=6&t=100570

[Koub]

The same suggestion was also made in this thread: viewtopic.php?f=6&t=100570

[Koub] It seems to be the case. Merging both threads. Shout in here if I understood both suggestions wrong.

[ssilk]

also merged another thread into this. thanks for pointing.

And I want to point out here again
1. If you have N stations with a train limit of 1 you can add only N trains to the game. Otherwise it can lead to deadlocks.
2. Use buffer stations.
3. Or circuits to control the limits yourself.


And I just had the new idea, that the game might be able to warn you, if you have a combination of train schedules with limits, that might lead to deadlocks.

[ssilk]

A nice trick

[Tricorius]

A nice trick

Meh. Hacky. And I’d probably rather have the soft locks that add that junk into the train schedule.

I realize most people probably don’t care. But I would *technically* consider the fact that the waiting list isn’t consistent on what it considers a slot in the waitlist for the station a bug.

But it’s a tiny one. And this may be the case where the “solution” might cause more issues than keeping it as is.

[ssilk]

As said (and I repeat my suggestion from above): the game could count all waiting slots on all stations and compare it with the schedules for that stations and if the number of trains > number of slots it could warn the player. Not thought deeper into it (definitely much more complex than this), but it feels like a good compromise.

A nice trick

Meh. Hacky. And I’d probably rather have the soft locks that add that junk into the train schedule.

I just wanted to show this. I won’t use this trick either. Experience shows, that these kind of tricks will lead sooner or later to (other) problems. I like to build rock-solid mechanisms. As the devs do. And that means (in my opinion), that the system as it is is rock-solid.

I realize most people probably don’t care. But I would *technically* consider the fact that the waiting list isn’t consistent on what it considers a slot in the waitlist for the station a bug.

Considering that a train that is ready to leave can be seen as a free station is exactly this kind of problem, that will lead to other problems. You consider it as bug, I think it’s completely logical and cannot be changed without bringing in real bugs.

But it’s a tiny one. And this may be the case where the “solution” might cause more issues than keeping it as is.

Well, I think the problem is, that the normal player sees it as obvious bug: “why isn’t the train moving? It’s ready it could start now!”
This is a frustrating moment.

But where should it go to? So the safest way is to wait, and when it’s clear where to go, then it can free the stop.

[Tertius]

But it’s a tiny one. And this may be the case where the “solution” might cause more issues than keeping it as is.

Well, I think the problem is, that the normal player sees it as obvious bug: “why isn’t the train moving? It’s ready it could start now!”
This is a frustrating moment.

But where should it go to? So the safest way is to wait, and when it’s clear where to go, then it can free the stop.

Database management systems (the program that hosts for example a SQL database) have deadlock resolving/deadlock avoiding algorithms. This here is a very good and concise explanation how DBMS can handle these:
https://www.geeksforgeeks.org/deadlock-in-dbms/
Some of this might be applied to Factorio as well, although it's probably a bit different since there are no waiting queues for resource allocation. Either you get the station reservation, or you don't get the reservation, and the next tick you retry again, since there is no waiting queue.