Trouble with path signals

[kaomoneus]

Hi folks!
Could somebody explain, why those two trains are stuck?

If I got right the signals manual, then train at left should reserve top path, whilst train at right should wait until former will take top path and then go.

[Eddi]

the problem is this: there is a pathfinder penalty for occupied tracks, which should prevent this situation and let the train pick the detour over the other track.

however, this is counted per occupied tile, so a 1-tile train is too short to counterbalance the extra turns and distances of the longer track.

so the solution is to either use longer trains, or increase the pathfinder penalty for path reservations

[ebla71]

the problem is this: there is a pathfinder penalty for occupied tracks, which should prevent this situation and let the train pick the detour over the other track.

however, this is counted per occupied tile, so a 1-tile train is too short to counterbalance the extra turns and distances of the longer track.

so the solution is to either use longer trains, or increase the pathfinder penalty for path reservations

Would it help to place the "exit signal" on the detour track in the bottom right corner further towards the middle of the "siding"? Or, to put the question another way: How far is the pathfinder "looking forward" - only until the next signal in the direction of travel or beyond that?

Another idea: instead of having one "through-track" and a "siding" with the two extra turns - what about using a "Y"-shaped separation (and re-joining) of the two tracks? Then both sections of track should be equally long.

Something else I noticed is that that "exit signal" on the "siding" seems to be not on the straight part of track, one tile to the top right but rather on the "turn", as it is facing a bit differently. So maybe just need to place the two signals on tile (x,y) and (x,y+1) instead of the case here on tile (x,y) and (x+1,y+1) (sorry, no time to draw a picture to illustrate that)

[Eddi]

the pathfinder is looking the full distance until the destination station, but signal states and path reservations are considered only for the first 10 signals (default setting, can be changed)

note that changing pathfinder settings can mess up your network in undesired ways, and should be done carefully.

[jfs]

You should not have a signal where the white train is stopped. It's an unsafe stopping position, because it can cause a deadlock when trains are stopped there.
Your passing loops should also be strictly directional, so trains going east will always use one track and trains going west will always use the other track, to make sure traffic can flow regardless of occupation.

(Note that if you make the passing loops directional, then the white signal becomes a safe stopping position, and you can keep it.)

[Taschi]

(Note that if you make the passing loops directional, then the white signal becomes a safe stopping position, and you can keep it.)

It would still be theoretically possible to get a deadlock with one train in each track of the loop and one train waiting at each entrance, i. e. 4 trains in total. Or am I overlooking something here?

[odisseus]

Yes, you are right. The white signal is not a safe location to wait, unless one of these conditions is met:

1. The track behind the signal (occupied by the grey train) is a dead end and can hold only one train (e.g. it may be a terminus platform);
2. The section of the tracks in front of the signal contains at least as many passing loops as there are trains that travel over these tracks, or an overflow depot.

In general, placing a signal there is a bad idea, unless it is a platform entrance.

By the way, the passing loops should always have one-way signals. Here's why.

[LaChupacabra]

You should not have a signal where the white train is stopped. It's an unsafe stopping position, because it can cause a deadlock when trains are stopped there.

I agree with that, but in this case it doesn't fix the problem. Even if you remove these signals, the trains will be stuck, which seems to have no any sensible reason.
It seems that it is like Eddi writes, i.e. pathfinder doesn't see the occupation of a single section of the track when determining the route.

Below is a screenshot and save that reproduces the problem.

pathfinder bug.png

(451.01 KiB) Not downloaded yet

I don't know what is the reason why the occupancy of a single section is not taken into account. Maybe it can be fixed?

[Eddi]

it IS taken into account.

the pathfinder tries to look at all possible paths to the destination. the general idea is to look for the shortest path, however, there are certain penalties added to allow for slight detours. e.g. when there are two paths, but one has more curves, each curve gets a penalty, so that the one with fewer curves is chosen, even if it is slightly longer.

now for your situation, you have the slightly longer branching track, and a few curves on the branching track. and these penalties combined are larger than the penalty for a single reserved track. so the detour will not be taken.

[jfs]

Below is a screenshot and save that reproduces the problem.

The problem is that you're making passing loops with two-way tracks. Make the passing loops strictly directional, don't allow trains to run in two directions on a length of track inside the loop.

[kaomoneus]

Thanks everybody. Making loops directional works to me.

...And yet. I still don't get stuff with penalties. It seems that penalties make sense when you have *several* alternatives. But should you calculate penalties when all routes but one are occupied?

[Taschi]

...And yet. I still don't get stuff with penalties. It seems that penalties make sense when you have *several* alternatives. But should you calculate penalties when all routes but one are occupied?

The underlying assumption behind the pathfinder penalties is that a blocked path will eventually stop being blocked. Thus, if there is one route that is blocked, and one route that is free but is significantly longer, the train will wait for the blocked path to become free, rather than going from London to Glasgow via Moscow and Cape Town because that route just happens to be free.

In your case, there is a deadlock, so the assumption that the blocked path will eventually stop being blocked is wrong and the matchmaker ends up making a wrong call. Of course, in your case, the difference between the two path lengths is fairly low, but so is the number of blocked tiles in the shorter path, so the heuristic just makes a wrong call here.

On the other hand, the pathfinder can't just outright discard any route that is "blocked", because on any high-throughput 2-lane route, there will DEFINITELY be other trains in the way, but following that route will still most likely be faster by far than taking a detour.

In general, OpenTTD's pathfinder is one of the smartest I've ever seen in any game so as long as you follow some core design principles (like "make your stuff deadlock-proof") it'll work like a charm.

[ebla71]

...And yet. I still don't get stuff with penalties. It seems that penalties make sense when you have *several* alternatives. But should you calculate penalties when all routes but one are occupied?

The underlying assumption behind the pathfinder penalties is that a blocked path will eventually stop being blocked. Thus, if there is one route that is blocked, and one route that is free but is significantly longer, the train will wait for the blocked path to become free, rather than going from London to Glasgow via Moscow and Cape Town because that route just happens to be free.

In your case, there is a deadlock, so the assumption that the blocked path will eventually stop being blocked is wrong and the matchmaker ends up making a wrong call.

Would it be possible for a modified pathfinder to consider every couple of "game cycles" (maybe best in slightly randomized intervals) to send a train on a somewhat longer route?

Or does a train simply not know (and cannot find out due to general code design) how long it has already been waiting at a signal?

[Wahazar]

There is option for this: automatic reversing on signals

[Taschi]

There is option for this: automatic reversing on signals

That is neither an answer to the question asked by ebla71 in the post directly above yours, nor is it the most sensible option for their original problem.

Would it be possible for a modified pathfinder to consider every couple of "game cycles" (maybe best in slightly randomized intervals) to send a train on a somewhat longer route?

Or does a train simply not know (and cannot find out due to general code design) how long it has already been waiting at a signal?

Something like that would probably be possible, but outside of very specific problems like yours it really wouldn't be helpful. Once you've gotten the hang of designing intersections, stations and loops (which you will fairly quickly if you just keep playing), deadlocks are a very rare occurance anyway. The pathfinder works really well the way it is.

(And, like stated above, if you just increased the penalty for occupied tracks in the options, even your edge case would work like a charm.)

[kaomoneus]

... wait for the blocked path to become free, rather than going from London to Glasgow via Moscow and Cape Town because that route just happens to be free.

Thanks for good explanation!

As a possible enhancement I would propose another sort of heuristics: wait for shortest route with some timeout. Timeout value if somewhat like

k*<Shortest free route length>/<Shortest route length>, where
"k" might be either constant factor or might be proportional to probability that shortest route is free.

[Eddi]

that could be achieved by multiplying the penalty for reserved tracks by the time spent waiting for a free path.

k*<Shortest free route length>/<Shortest route length>

calculating those two values separately would be too CPU intensive.

[kaomoneus]

that could be achieved by multiplying the penalty for reserved tracks by the time spent waiting for a free path.

Btw, is it a C++ or Squirrel part?

[Eddi]

that's C++