technical difference between NPF and YAPF

Tekky · Post by **Tekky** » 27 Jun 2007 19:29

I am currently trying to understand the difference between NPF and YAPF in order to determine whether I can use one of these pathfinders for my project or whether I must make my own pathfinder.

As far as I can tell, whenever a train reaches a switch, the pathfinder is called to determine which path to take. NPF uses the A* pathfinding algorithm and it considers every tile to be a node for the A* algorithm.

Is the main difference between YAPF and NPF that YAPF caches its results? Are they any other major technical differences between NPF and YAPF?

Unfortunately, the wiki article for NPF and the wiki article for YAPF do not specify these details.

XeryusTC · Post by **XeryusTC** » 27 Jun 2007 19:42

The big difference between YAPF and NPF are that YAPF uses way less CPU than NPF because it doesn't get called everytime a train enters a new tile. YAPF only gets called when a train reaches a split, or when there is a change in the network IIRC.

Tekky · Post by **Tekky** » 27 Jun 2007 19:54

Thanks for your reply. But I'm sure there must be more major differences between YAPF and NPF besides that YAPF is only called when there is a track split/switch. Or is this really the biggest difference, apart from YAPF being written in C++ and NPF in C?

Post by **peter1138** » 27 Jun 2007 20:04

Go with YAPF. NPF may well be removed at some point...

Tekky · Post by **Tekky** » 29 Jun 2007 15:47

Thanks, I will study the source code of YAPF, then

prissi · Post by **prissi** » 29 Jun 2007 17:37

If you just want to see some A* more C-style like pathfinder, you could also have a look at the simutrans source code ...

KUDr · Post by **KUDr** » 30 Jun 2007 13:17

XeryusTC wrote:The big difference between YAPF and NPF are that YAPF uses way less CPU than NPF because it doesn't get called everytime a train enters a new tile. YAPF only gets called when a train reaches a split, or when there is a change in the network IIRC.

This is not true. NPF and YAPF are called the same way and at the same moment - when train needs PF support (choice reached, leaving station - need to know which direction will be the best - whether to reverse or not, and for servicing - to find the nearest depot and then to navigate there).

Also both use the same algorithm.

There are 3 major implementation differences:
- NPF creates node for each tile while YAPF extends node by following the tile/trackdir until something important (station, waypoint, choice, etc.) is seen. This node extension is called segment.
- YAPF caches its segments - begin/end tile/trackdir, cost, last signal tile/trackdir, etc.
- YAPF has much more complex structure - it is template based to allow compiler to optimize calls between YAPF modules by inlining.

All 3 differences are there for CPU load optimization. Unfortunately it makes YAPF code hard to read/understand.

If you want to learn about PFs or if you don't care about performance, I would recommend you to start with NPF. It is a flexible, well designed, pure A* pathfinder. A good source for learning and experiments.

Otherwise take YAPF, wish you good luck. Or start with NPF and I can assist you with YAPF later.

Tekky · Post by **Tekky** » 01 Jul 2007 12:45

Thanks for your advice, KUDr. I think I will follow your advice and use NPF for experimenting and upgrade to YAPF later, when everything else works.

By the way, KUDr, what are your future plans for PBS? Are you planning to implement the same PBS signalling system for YAPF as the old one which used NPF? The reason I am asking is that I am planning to make a completely different PBS system, which is based on realistic signalling. I have described my project in this wiki article. It would be stupid of me if I started work on such a new signalling system if you already are working on a similar system (or even a better one).

Moriarty · Post by **Moriarty** » 01 Jul 2007 19:53

Slightly off-topic, but why hasn't the code-base settled on one pathfinder yet and removed the others? YAPF is well tested. As I understand it there are several patches that are pathfinder dependent, and culling pathfinders would also clear that up and allow development to concentrate on only one.
.
Is it because of ships? Though do any of the algorithms handle ships well?

Tekky · Post by **Tekky** » 01 Jul 2007 21:24

My experience with ships is that both NPF and YAPF cause the performance to drop significantly even with only 10 ships on the map.

The only way I was able to get ships to work in an acceptable way is to use the old pathfinder (not NPF and not YAPF) and to place many buoys so that ships do not get lost.

Sacro · Post by **Sacro** » 01 Jul 2007 21:41

Moriarty wrote:Slightly off-topic, but why hasn't the code-base settled on one pathfinder yet and removed the others? YAPF is well tested. As I understand it there are several patches that are pathfinder dependent, and culling pathfinders would also clear that up and allow development to concentrate on only one.
.
Is it because of ships? Though do any of the algorithms handle ships well?

As far as I know, OPF is still used for the signals.

KUDr · Post by **KUDr** » 02 Jul 2007 01:08

Yes, OPF is the best PF yet for ships. And is used also by AIs (road/rail building) and for signaling.
NPF is the only advanced PF suitable for such patches. NTP is suitable only for trains but it is very fast and simple.
I can't imagine regular user with some programing skills trying to deal with YAPF because all other PFs were removed. This would be logical consequence and it could prevent users from making such patches.

It can also happen that implementing some new feature on top of YAPF will be impossible or at least very difficult due to several limitations caused by YAPF optimizations. Also some redesign of YAPF may be needed.

Tekky: I had a plan to come with new signaling (where all signals are red by default and all of them behave as PBS). It started a lot of discussions how new signaling should work and to be honest I began to feel lost in that all.

Therefore I started to play with new GUI which is still not finished. Currently i have not enough time to continue on it.
So feel free to try to do something reasonable in this direction. If your new signals will be generally accepted (code quality, performance, playability) I will support you in your effort rather than to start 'my own' newsignals project. There are many areas in OTTD where I can do something.

Sacro · Post by **Sacro** » 02 Jul 2007 01:13

KUDr wrote:Yes, OPF is the best PF yet for ships. And is used also by AIs (road/rail building) and for signaling.
NPF is the only advanced PF suitable for such patches. NTP is suitable only for trains but it is very fast and simple.
I can't imagine regular user with some programing skills trying to deal with YAPF because all other PFs were removed. This would be logical consequence and it could prevent users from making such patches.

It can also happen that implementing some new feature on top of YAPF will be impossible or at least very difficult due to several limitations caused by YAPF optimizations. Also some redesign of YAPF may be needed.

Tekky: I had a plan to come with new signaling (where all signals are red by default and all of them behave as PBS). It started a lot of discussions how new signaling should work and to be honest I began to feel lost in that all.

Therefore I started to play with new GUI which is still not finished. Currently i have not enough time to continue on it.
So feel free to try to do something reasonable in this direction. If your new signals will be generally accepted (code quality, performance, playability) I will support you in your effort rather than to start 'my own' newsignals project. There are many areas in OTTD where I can do something.

I would like to discuss this with you, I'm around on IRC most of the time.

athanasios · Post by **athanasios** » 02 Jul 2007 21:27

KUDr wrote:Yes, OPF is the best PF yet for ships.

You may be right when you compare it with other PFs.

It is so good: Ships can't travel diagonally.

Tekky · Post by **Tekky** » 08 Jul 2007 11:51

KUDr wrote: Tekky: I had a plan to come with new signaling (where all signals are red by default and all of them behave as PBS). It started a lot of discussions how new signaling should work and to be honest I began to feel lost in that all.

Therefore I started to play with new GUI which is still not finished. Currently i have not enough time to continue on it.
So feel free to try to do something reasonable in this direction. If your new signals will be generally accepted (code quality, performance, playability) I will support you in your effort rather than to start 'my own' newsignals project. There are many areas in OTTD where I can do something.

Thanks for your information. I'm afraid I also have little time, but I will try my best to implement my new signalling system.

Tekky · Post by **Tekky** » 12 Jul 2007 18:24

KUDr wrote:There are 3 major implementation differences:
- NPF creates node for each tile while YAPF extends node by following the tile/trackdir until something important (station, waypoint, choice, etc.) is seen. This node extension is called segment.
- YAPF caches its segments - begin/end tile/trackdir, cost, last signal tile/trackdir, etc.
- YAPF has much more complex structure - it is template based to allow compiler to optimize calls between YAPF modules by inlining.

I have updated the wiki article for YAPF with this information you just gave me, since this information will also be very important for other developers.

Transport Tycoon Forums

technical difference between NPF and YAPF

technical difference between NPF and YAPF

Who is online