technical difference between NPF and YAPF

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

Post Reply
Tekky
Route Supervisor
Route Supervisor
Posts: 420
Joined: 19 Dec 2006 04:24

technical difference between NPF and YAPF

Post by Tekky »

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.

User avatar
XeryusTC
Tycoon
Tycoon
Posts: 15415
Joined: 02 May 2005 11:05
Skype: XeryusTC
Location: localhost

Post by XeryusTC »

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.
Don't panic - My YouTube channel - Follow me on twitter (@XeryusTC) - Play Tribes: Ascend - Tired of Dropbox? Try SpiderOak (use this link and we both get 1GB extra space)
Image
OpenTTD: manual #openttdcoop: blog | wiki | public server | NewGRF pack | DevZone
Image Image Image Image Image Image Image

Tekky
Route Supervisor
Route Supervisor
Posts: 420
Joined: 19 Dec 2006 04:24

Post by Tekky »

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?

peter1138
OpenTTD Developer
OpenTTD Developer
Posts: 1646
Joined: 30 Mar 2005 09:43

Post by peter1138 »

Go with YAPF. NPF may well be removed at some point...
He's like, some kind of OpenTTD developer.

Tekky
Route Supervisor
Route Supervisor
Posts: 420
Joined: 19 Dec 2006 04:24

Post by Tekky »

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

User avatar
prissi
Chief Executive
Chief Executive
Posts: 647
Joined: 15 Nov 2004 19:46
Location: Berlin, Germany
Contact:

Post by prissi »

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
OpenTTD Developer
OpenTTD Developer
Posts: 219
Joined: 11 Jan 2006 21:36
Location: Czech Republic

Post by KUDr »

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
Route Supervisor
Route Supervisor
Posts: 420
Joined: 19 Dec 2006 04:24

Post by Tekky »

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
Tycoon
Tycoon
Posts: 1395
Joined: 12 Jun 2004 00:37
Location: United Kingdom of Great Britain and Northern Ireland
Contact:

Post by Moriarty »

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
Route Supervisor
Route Supervisor
Posts: 420
Joined: 19 Dec 2006 04:24

Post by Tekky »

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
Tycoon
Tycoon
Posts: 1142
Joined: 18 Jun 2005 21:08
Location: Here
Contact:

Post by Sacro »

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.
We Am De Best

Host of ThroughTheTube site

KUDr
OpenTTD Developer
OpenTTD Developer
Posts: 219
Joined: 11 Jan 2006 21:36
Location: Czech Republic

Post by KUDr »

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
Tycoon
Tycoon
Posts: 1142
Joined: 18 Jun 2005 21:08
Location: Here
Contact:

Post by Sacro »

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.
We Am De Best

Host of ThroughTheTube site

User avatar
athanasios
Tycoon
Tycoon
Posts: 3138
Joined: 23 Jun 2005 00:09
Contact:

Post by athanasios »

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. :roll:
http://members.fortunecity.com/gamesart
"If no one is a fool I am also a fool." -The TTD maniac.


I prefer to be contacted through PMs. Thanks.

Tekky
Route Supervisor
Route Supervisor
Posts: 420
Joined: 19 Dec 2006 04:24

Post by Tekky »

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
Route Supervisor
Route Supervisor
Posts: 420
Joined: 19 Dec 2006 04:24

Post by Tekky »

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.

Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 8 guests