YAPP - Yet Another PBS Patch (now in trunk!)

[Rubidium]

In the attached savegame there are always trains waiting at for a free spot even though there are (quite often) free spots with free (or so it looks to me) routes to there.

Version 5.1 @ r12486.

[Michi_cc]

I've noticed that it's not possible to remove part of a station if it's reserved, but it is possible to build over it, which destroys the reservation. Is this a "user should know better" issue, or is it accidental?

Both Building a similar tile over an exisiting tile should of course just preserve the reservation. Building a non-similar tile (different axis, blocked) should be forbidden, but I have no clue how to check for that before building. With all the newgrf callback stuff, I'm not even sure that's something possible. If you have some advice how to do that I'll gladly implement overbuilding protection.

-- Michael Lutz

[peter1138]

Station axis is determined by the command parameters, callbacks cannot change it. Problem is the tiles are wiped out quite early in the command, so you'd need some way of remembering the previous state...

[Michi_cc]

In the attached savegame there are always trains waiting at for a free spot even though there are (quite often) free spots with free (or so it looks to me) routes to there.

Working as designed, but probably not as expected. Please note that this problem is really a YAPF problem that is more prominent due to the way that PBS signals only turn green being able to reserve the best path (not any possible path like with pre-signals!).

I have to digress a bit into YAPF to explain that. As you probably know, YAPF implements the A* algorithm. This algorithm uses two important properties to decide on a path, the cost till a specific point, and the estimated cost for reaching the destination. The path cost consists of tile costs, curve costs, slope costs, station cost and so on.

Just calculating the real path costs for a path from one sign to the other yields a lower value than any other occupied platform because of the penalties for reserved tracks. But here comes the crux: YAPF has found one of the nearer platforms as a target and now checks whether any other open path could possibly be shorter. It does this by comparing the cost of the already found route to the sum of the cost of the open path and the estimate to the destination. This estimate is calculated by taking the manhatten distance to the station center tile, which is rather far away in your example and does not correspond to any platforms, leading to a high cost estimate that is higher than the already found path, even though the real path cost would not be higher. This is a general limitation of the A* algorithm.

Increasing the value of the patch setting yapf.rail_pbs_cross_penalty to a sufficiently high value will yield better results in your case. However, I can't recommend a general increase for this value, as trains might then take rather large detours around reserved tiles in more complex extrance/exit areas of stations seriously hindering other trains.

Station axis is determined by the command parameters, callbacks cannot change it. Problem is the tiles are wiped out quite early in the command, so you'd need some way of remembering the previous state...

And how do I find out whether a new station tile is a non-passable tile, even if it has the right axis, before execution phase?

-- Michael Lutz

[Expresso]

Maybe a good idea to make yapp calculate the center of all platforms reachable through a pbs block and make yapf use that for the distance-manhatten, instead of the "center"-tile of the station? However, this opens its own can of worms, so this needs some additional thought. But, if implemented, this will fix the bug in the savegame mentioned above imho.

[Tekky]

As far as I know, in order for A* to find an ideal path, one must set the heuristic to the minimum possible distance. Therefore, one must set the heuristic to the real distance to the closest corner tile of the station(not the Manhattan distance!). If the train is already inside the station rectangle (possible with disjoint stations), the heuristic must be set to 0, effectively degrading the A* pathfinder to a Dijkstra pathfinder.

[Noldo]

Problem with the 'real distance' aka euclidian distance is that it requires square root and therefore is considerably harder to calculate than manhattan. Max(delta x, delta y) to the nearest corned would be as easy as manhattan but always smaller than the real cost.

[Tekky]

Problem with the 'real distance' aka euclidian distance is that it requires square root and therefore is considerably harder to calculate than manhattan.

Yes, since we are not allowed to use floating point numbers due to multiplayer compatibility, taking the square root is a major issue.

Max(delta x, delta y) to the nearest corned would be as easy as manhattan but always smaller than the real cost.

Setting the heuristic too small has significant performance issues, though. The pathfinder will spread more in all directions instead of directing its search toward the destination. Therefore, the best compromise may be to go diagonally until you have the same X or Y coordinate as the destination and then go the rest of the way in a straight line. This requires only the following code:

Code: Select all

/* calculate deltaX and deltaY and make them both positive */
deltaX = abs( destinationX - originX );
deltaY = abs( destinationY - originY );

/* calculate the length of the straight and diagonal part */
straight_part = abs( deltaX-deltaY );
diagonal_part = max( deltaX, deltaY ) - straight_part;
straight_part*= 100;
diagonal_part*= 142;

/* calculate the heuristic */
heuristic = straight_part + diagonal_part;

One could optimize the above code like this:

Code: Select all

/* calculate deltaX and deltaY and make them both positive */
deltaX = abs( destinationX - originX );
deltaY = abs( destinationY - originY );

/* calculate the heuristic */
heuristic = deltaX > deltaY ? deltaX * 100 + deltaY * 42 : deltaY * 100 + deltaX * 42;

The above code seems computationally rather inexpensive to me, at least when you compare it with the additional work of the pathfinder due to not having a good heuristic. However, the optimized version of my code is rather hard to understand.

[Michi_cc]

The above code seems computationally rather inexpensive to me, at least when you compare it with the additional work of the pathfinder due to not having a good heuristic. However, the optimized version of my code is rather hard to understand.

And if you take a look at what YAPF actually does, you'll find it not that significantly different to your solution.

But you're actually missing the point here a bit, the algorithm to calculate the estimate is not the problem. The problem is to determine which tile the distance should be estimated to.
Using the nearest station tile in any form is rather pointless, because finding said tile requires an exhaustive search of all possible paths to really find the nearest station tile in any case, in the worst case meaning a search of the whole map. The only point of A* is to not search the whole map by using an estimate and limiting the search based on that. Calculating this estimate by a complete map search doesn't win you anything. And not doing a complete map search will only produce a different track constellation showing the problem. (Technical note: Under typical conditions, the search will of course finish much earlier, but I don't think a 99%-solution is acceptable here.)

-- Michael Lutz

[Tekky]

Isn't the bounding rectangle of the station stored somewhere? In that case, it should be no problem to find the closest corner of the station's bounding rectangle or to determine whether the origin is already inside the rectangle, in which case the heuristic should be set to 0.

[Expresso]

I've been thinking some more on a logical solution to the problem which occurs in the last save game posted, I might have come up with a decent solution without opening a can of worms.

In order to compute the center tile, you should know which platforms can be reached from the pbs block, directly as well as indirectly, in a reasonable amount of tiles. "Reasonable" might be equal to the maximum station spread. Now, you could follow the track and collect all tiles belonging to the station as you go. If you reach the maximum station spread or encounter another station, the likelihood of the station having platforms beyond that point probably is zero. When you have no more tiles to search, you simply calculate the center of all platform tiles encountered and there's your more accurate center. The resulting value could be cached, as it only needs to be recalculated when the layout of the rails (no, not the signal placement) or the layout of the station platforms change.

[zombie]

Hi.

I appreciate the work done to this patch so far. You did a great job. But I have a really strange problem with trains that reverse after waiting in front of a station for an empty platform. Although I built one-way PBS signals only the train reserves a path beyond the one-way signal although it can never pass this signal. It reserves the path until the next split. After a while the train reverses again to try to enter the station again and if it can enter the station the reservation for the track where the train was wating is cleared. But the rest of the reservation beyond the PBS signal is not cleared.

As this is a main track the reservation blocks the whole system. I have to command the next train that has to travel along the same track to ignore signals to create a new reservation. After this train leaves the the both reservations are gone. Unfortunately I can't provide a savegame and it does not always occur.

Kind regards

Kay Zumbusch

[Progman]

Hi.

I appreciate the work done to this patch so far. You did a great job. But I have a really strange problem with trains that reverse after waiting in front of a station for an empty platform. Although I built one-way PBS signals only the train reserves a path beyond the one-way signal although it can never pass this signal. It reserves the path until the next split. After a while the train reverses again to try to enter the station again and if it can enter the station the reservation for the track where the train was wating is cleared. But the rest of the reservation beyond the PBS signal is not cleared.

As this is a main track the reservation blocks the whole system. I have to command the next train that has to travel along the same track to ignore signals to create a new reservation. After this train leaves the the both reservations are gone. Unfortunately I can't provide a savegame and it does not always occur.

Kind regards

Kay Zumbusch

I can confirm this. Check the attachements.

[vwspeedracer]

I don't have a saved game but I'll throw my hat in and say I've also seen this behavior. I took the easy way out and disabled automatic reverse, but I still see it happen from time to time when I reverse trains manually (when untangling construction-related confusion.)

[zombie]

Hi.

I can confirm this. Check the attachements.

Thanks for those attachments. That's exactly what I was talking about.

Kind regards

Kay Zumbusch

[Mchl]

One of the ways to avoid it, is to put a single signal in the opposite direction on the 'waiting' track. The waiting train will reverse, reach this signal and see there's no path available beyond it, so it'll stop there and wait... until it reverses.

[Two5Kid]

Ermm, sorry to be a bother, anyone compiled this with the working version of OTTD v0.6.0? And where can I get it? Itching to get my hands on YAPP after fumbling around with Gonozal's old version. Thanks in advance.

[Scay]

Look at this thread, contains a precompiled version including a few more patches which you can choose to use if you like:

http://www.tt-forums.net/viewtopic.php? ... &sk=t&sd=a

[Trond]

Make sure to grab the one from Yexo called combi.zip, cause If I remember right, the other build that appeared later in that thread didnt have Yapp...

[Yexo]

Make sure to grab the one from Yexo called combi.zip, cause If I remember right, the other build that appeared later in that thread didnt have Yapp...

Both patches posted there include yapp, but there is some difference:
My patch includes: yapp, paxdest, timetable seperation, and programmable waypoints.
The patch later posted by Roujin includes: yapp, paxdest, old tracks.