technical difference between NPF and YAPF
Moderator: OpenTTD Developers
technical difference between NPF and YAPF
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.
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.
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)
OpenTTD: manual #openttdcoop: blog | wiki | public server | NewGRF pack | DevZone
OpenTTD: manual #openttdcoop: blog | wiki | public server | NewGRF pack | DevZone
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).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.
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.
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).
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).
-
- Tycoon
- Posts: 1395
- Joined: 12 Jun 2004 00:37
- Location: United Kingdom of Great Britain and Northern Ireland
- Contact:
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?
.
Is it because of ships? Though do any of the algorithms handle ships well?
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.
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.
As far as I know, OPF is still used for the signals.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?
We Am De Best
Host of ThroughTheTube site
Host of ThroughTheTube site
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.
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.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.
We Am De Best
Host of ThroughTheTube site
Host of ThroughTheTube site
- athanasios
- Tycoon
- Posts: 3138
- Joined: 23 Jun 2005 00:09
- Contact:
You may be right when you compare it with other PFs.KUDr wrote:Yes, OPF is the best PF yet for ships.
It is so good: Ships can't travel diagonally.
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.
"If no one is a fool I am also a fool." -The TTD maniac.
I prefer to be contacted through PMs. Thanks.
Thanks for your information. I'm afraid I also have little time, but I will try my best to implement my new signalling system.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.
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.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.
Who is online
Users browsing this forum: No registered users and 15 guests