Transport Tycoon Forums

Guys, I would like to ask all of you to help me to test new pathfinder prototype (svn://svn.openttd.com/branch/yapf). Once it will be debugged, I can move forward to the next dev phase with it - I would like to add the segment cost caching to improve the YAPF performance. Now YAPF for trains spends like 90% of time in the segment cost calculation so the caching its results could help a bit.

YAPF setup
GUI/Configure Patches/Vehicles/ there are 3 YAPF related settings (ships, road vehs, trains):

• 0: original PF or NPF (YAPF disabled)
• 1: reference YAPF (don't need to be tested alone)
• 2: preferred YAPF allowing 90-deg turns
• 3: preferred YAPF with 90-deg turns disabled

So please test type 2 or 3 primarily.

Bug reports here or on IRC. Thanks.
KUDr

History:

1. Zipped YAPF r4511 Windows Executable (update: added missing english.lng file - thanks Darkvater)
2. Updated Windows Executable (r4523)
   - fix: assert in GetTileOwner (thanks yanek)
   - fix: trains can't find route via some bridges (thanks Celestar)
3. Updated Windows Executable (r4533)
   - fix: lost road vehs (thanks MeusH)
4. Updated Windows Executable (r4535)
   - fix: if path not found, go as close to the destination as possible (trains and roadvehs)
   - fix: another distance calculation problem (thanks yanek)
5. Updated Windows Executable (r4543)
   - fix: decreased look-ahead red signal penalty - should fix crazy train looping (thanks yanek)
   - add: FindNearestDepot and CheckReverse support for trains (thanks Celestar)
   - add: red signal penalties depending on signal type (thanks yanek)
   - fix: wrong 'best node' manipulation caused target info overwrite
   - remove: YAPF type 4 for ships and trains
   - add: penalty for trains passing stations
6. Updated Windows Executable (r4545)
   - fix: decreased speed limit penalty (thanks webfreakz)
7. Updated Windows Executable (r4587)
   - add: FindNearestDepot support for roadvehs
   - add: segment cost cache for trains
8. Updated Windows Executable (r4615)
   - fix: Cost cache now invalidates when track layout changes (thanks TSC for reporting the problem)
9. Updated Windows Executable (r4622)
   - fix: trains can't find route to the waypoint (thanks webfreakz)
10. Updated Windows Executable (r4634)
    - experiment: depot exit now acts as presignal entry
    - fix: FindNearestDepot gave up when train head or tail was in tunnel. Now it will give up only if both ends are in tunnel. (thanks misnomer)
11. Updated Windows Executable (r4647)
    - fix: missing YapfNotifyTrackLayoutChange() when track is deleted by disaster (thanks XeryusTC)
12. Updated Windows Executable (r4694)
    - fix: YAPF cache was not notified about some minor track layout changes such as "load game" (many thanks to ledow)
13. Updated Windows Executable (r4700)
    - fix: if first red signal is two-way it is now treated as dead-end (thanks Hackykid)
14. Updated Windows Executable (r4712)
    -fix: some diesel engines can't find path when rail combined with elrail (thanks Eddi|zuHause)
    -fix: when train is deciding whether to reverse or not while leaving station, the rule 'treat first red two-way signal as dead end' doesn't apply (should make Eddi|zuHause more happy with the YAPF / two-way stations)
    -fix: random crashes when opening some GUI (i.e. cheats window) on Win32 debug build. (not YAPF related)
15. Updated Windows Executable (r4833)
    -fix: first red COMBO signal now gives the same penalty as EXIT (thanks DW)
    -debug: added path cost / distance to the log

Should I switch on the NPF?
Because with NPF off and trains mode = 3, they still can make 90 deg. turns.

EDIT: there is also a strange behaviour at the station exit, because there is no route to the next station. If i connect the line(or switch the YAPF off), the train exit the station through the green signal.

gkirilov: if you want to disable 90-deg turns (and use YAPF type 3) then you should have NPF on. Otherwise it doesn't matter. If you have set the YAPF type to non-zero, it takes control over the transport type for which it is set.

For example if you select non-zero YAPF type for trains only, then roadvehs and ships will use other pathfinder depending on NPF state (on/off).

1. So there is no NPF, only the original PF and YAPF?

2. check prev. post i edited it with an image:
- the line between the 2 stations is broken, YAPF for trains = 3, NPF option is ON - the train goes to the back of the one way signal in stead of going to the green signal.(dont mind the options on the screenshot)

3. YAPF for trains = 3, NPF = ON, IF the option for the 90 deg. is OFF then trains still can make 90 deg. turns (which should be defined by = 3, according to you).

gkirilov:

1) if you switch off the YAPF for any transport type (i.e. trains) by setting YAPF type = 0, then all is the same for trains as before the YAPF came. It means, that if you have switched NPF on then NPF will be used. Otherwise NTP is used. Simply NPF can override NTP and YAPF can override both NPF and NTP.

2) Yes. This is known feature now. Because the path was not found, the train is out of control. I must think more about that case if it will be a big issue. I don't know if it is better to stop the train in such case and post message to the user or simply go 'somewhere'.

3) No. One thing is the pathfinder and another thing is the train controller. Now the YAPF settings have no influence to the train controller. In such case you should have also "Disable 90-deg turns" option ON. Otherwise the pathfinder will prefer non-90-deg turns, but if there is no such way, train can still do 90-deg turns. Note that it is prototype and I want to experiment with all combinations. Once the YAPF will be finished it will probably become default pathfinder for all transport types and the "Disable 90-deg turns" option will work normally as with NPF.

Forgot to note: I am also experimenting with look-ahead yapf feature. It should help in the case of traffic jam. So if you notice unusal undesired behavior that can be related to it, please report it too:

KUDr, is it something like yellow signal patch? I really like that patch and I think your lookahead feature is almost the same

MeusH: it is something much simpler now: YAPF counts signals while going ahead and applies penalty for each nearby red signal depending on how many signals it passed alredy. The applied penalty decreases with each signal it passes. Really simple thing.

Which is almost the same as how the yellow signals are penalized. They use distance from train instead of signals though.

KUDr wrote:2) Yes. This is known feature now. Because the path was not found, the train is out of control. I must think more about that case if it will be a big issue. I don't know if it is better to stop the train in such case and post message to the user or simply go 'somewhere'.

The pathfinder always behaved randomly if no path could be found to its destination. A solution could be to send the train to the nearest depot and inform the user of it, but that will be unliked by some players. Eg you start your train on an unfinished track while you are still building it then it going to a depot would pretty much suck.

I'd vote for keeping it the same. Just let the train run taking random turns, messing up your network and inform the user after a while that its train is lost.

and inform the user after a while that its train is lost.

Excellent idea. But the current "train is lost" warning should be changed to proper "train did not make any income for $time"

ok, roadvehs and trains now try to get as close to the target as possible
thanks
KUDr

Just tried to load a game with >700 trains (no rvs or ships). 2048x512 map with huge cities. On AMD Athlon @ 2100MHz average load 60% (some spikes to 100%, some drops to 20/30%). Mode 3 for trains (no 90 deg. turns on the map though)
So I guess it is better than the NPF. (could It be optimized more ? Because if you add some RVs and ships the picture will probably become not very nice (ugly) ).

gkirilov: Today I added segment cost cache to improve the YAPF performance a bit. On my machine (AMD 64 X2 4400+) the YAPF now takes 90ms of total CPU time per game day (map with 1000+ trains).
It is less than 10% since the game day length is more than one second.
The other stuff in the game (train control loop) takes more (approx 50%) CPU time. It doesn't seem that YAPF optimization can help in this case.

Yes, ship pathfinding is a different story. There can be milions of nodes visited by ship PF in each turn. It will need something radically new, not just optimized A* implementation.

KUDr: Ships probably need to use lanes. This, I think, could be totally transparent to the user. The ship pathfinder could make and cache shipping lanes all around the map (wherever ships have orders), using the usual pathfinding routine. These would be checked, instead of being found from scratch, when a ship came to need a destination (a simple iteration of tiles along a shipping lane to make sure it's all still wet). If the shipping lane is found not to be navigable, then the real pathfinder is woken up to find a new one.

Basically, it's just really aggressive path caching.

If a ship was sent via a buoy, this would have the interesting side-effect that other ships would tend to pass that same buoy even if not ordered to do so, because the cached lanes would be based on that first trip.

What about a mix of Brianetta's idea and the way it worked in Old TTD:
The pathfinding algorithm handles a network of buoys. Everytime the player places a buoy this network is updated. Now if you build a ship
and send it to some docks, the game checks if all those docks are close
enough to the buoy network, and if all the docks are reachable via the
network.
This would still require that you build buoys every X tiles, but you won't
have to add them to the ship's order list.
At least I would like that, as buoys wont get useless. And building ships
isn't too easy then (like planes).

Problem with that is that players won't build buoys.

So, is that really a reason to remove them?
I guess there are some people who don't understand how signals work.
Now you could also remove them and make an algorithm that trains will
find their way without them, and without crashing. And buses and trucks
could drive on the grass, so you dont need roads either.
The game shouldn't be too easy. Thats why many players hate planes.
Without buoys ships are the same like planes.
Just my 2ct.

But this gets a little OT I think.

I don't remember anybody suggesting that they be removed. There are many reasons why players might want buoys - it's just not fair, or realistic, to expect players to scatter buoys across the high seas.

I'm with brian on this one