Waypoints effect on pathfinder CPU load
Moderator: OpenTTD Developers
- TimeLapse1357
- Traffic Manager
- Posts: 132
- Joined: 10 Mar 2015 07:13
- Location: Southern California
Waypoints effect on pathfinder CPU load
I play on 2Kx2K maps and often have long train lines between cities, 200-300 tiles. when I get to about 1500 combined vehicles the game starts to slow down to the point where fast-forward speed is the same as normal.
I tried the trick of putting buoys every 10-20 tiles on ship routes and it had a noticeable effect.
Would putting waypoints every 50-100 tiles on very long sections of track decrease the pathfinder CPU load, since it is only having to look fifty tiles ahead instead of 300+ ? I have tried it on a couple of maps, and it seems to work but I don't have a good way of timing it to be sure.
also would I be correct in assuming that a single train takes less PCU Load than two road vehicles?
I tried the trick of putting buoys every 10-20 tiles on ship routes and it had a noticeable effect.
Would putting waypoints every 50-100 tiles on very long sections of track decrease the pathfinder CPU load, since it is only having to look fifty tiles ahead instead of 300+ ? I have tried it on a couple of maps, and it seems to work but I don't have a good way of timing it to be sure.
also would I be correct in assuming that a single train takes less PCU Load than two road vehicles?
- SilverSurferZzZ
- Route Supervisor
- Posts: 468
- Joined: 29 Oct 2013 23:31
Re: Waypoints effect on pathfinder CPU load
Map size, number of vehicles (ships in special by his pathfinder)... all count to the CPU. And more things, more load.
My advice is too simple, at this moment knows the limits of your computer, down (a little) the map size and play.
In the new game will not have CPU overload, and you can play without problems.
The CPU load of one train VS two cars... I don't know. I've never checked.
My advice is too simple, at this moment knows the limits of your computer, down (a little) the map size and play.
In the new game will not have CPU overload, and you can play without problems.
The CPU load of one train VS two cars... I don't know. I've never checked.
NewGRFs__
City names/Landscape: Naruto | Planets | Lovers | Halloween | Kaijus
Vehicles: Famous Cars | Super Cars | Racing Cars | Cars Cars | Improved M Cars
SilverSurferZzZ has left the building!
City names/Landscape: Naruto | Planets | Lovers | Halloween | Kaijus
Vehicles: Famous Cars | Super Cars | Racing Cars | Cars Cars | Improved M Cars
SilverSurferZzZ has left the building!
Re: Waypoints effect on pathfinder CPU load
Pathfinders have huge problems with many alternative routes of (mostly) the same length. With ships, the number of routes literally explodes. A ship can take turn left, turn right, or go straight at every tile. Each variation in turning is a new path that is examined. Eg straight and then left is different from left and then straight, even though you'll end up at the same tile. Buoys reduce the load, because the number of steps to consider to the next goal becomes smaller, exponentially reducing the number of paths to explore.
Road vehicles typically drive around in an urban area, where there are short roads and lots of junctions, each junction is searched in every direction, so more junctions means more routes to explore. It's normally much less bad than ships however, since normally not every tile is a junction. The Manhattan style of roads does make that we have many equally long routes though.
Trains typically drive on loooooong stretches of tracks without junction, and the number of junctions is very small. That means the number of routes to search is also very small. Of course, if you put track in all directions on every tile, you get the same problem like with ships.
Trains also have signals, which also influences path finders, but I am not sure how exactly.
The killer here is the large number of alternative routes. More routes to compute means (exponentially) more work. Waypoints help in the sense that they stop the search earlier, much like buoys do. However, since the number of routes to consider for RVs and trains is often much much smaller than for ships, the effect is much much smaller.
As for RVs vs train, I don't know. It really depends on the layout of roads and tracks, at least with respect to the path finder.
Road vehicles typically drive around in an urban area, where there are short roads and lots of junctions, each junction is searched in every direction, so more junctions means more routes to explore. It's normally much less bad than ships however, since normally not every tile is a junction. The Manhattan style of roads does make that we have many equally long routes though.
Trains typically drive on loooooong stretches of tracks without junction, and the number of junctions is very small. That means the number of routes to search is also very small. Of course, if you put track in all directions on every tile, you get the same problem like with ships.
Trains also have signals, which also influences path finders, but I am not sure how exactly.
The killer here is the large number of alternative routes. More routes to compute means (exponentially) more work. Waypoints help in the sense that they stop the search earlier, much like buoys do. However, since the number of routes to consider for RVs and trains is often much much smaller than for ships, the effect is much much smaller.
As for RVs vs train, I don't know. It really depends on the layout of roads and tracks, at least with respect to the path finder.
Being a retired OpenTTD developer does not mean I know what I am doing.
Re: Waypoints effect on pathfinder CPU load
judging 2 road vehicles vs. 1 train is tricky, because while the pathfinder will be called more often with the road vehicles, the pathfinder is not the only thing that uses CPU time.
things like actually moving the vehicles (has to be done individually for each wagon) or processing the cargo (aging, etc.), which the train will have more of, do also use some processing power.
things like actually moving the vehicles (has to be done individually for each wagon) or processing the cargo (aging, etc.), which the train will have more of, do also use some processing power.
Re: Waypoints effect on pathfinder CPU load
What algorithm does OpenTTD use for the problem of pathfinding? I am a bit surprised about the term "exponential" in this context, since algorithms like Dijkstra are certainly not exponential.Alberth wrote: The killer here is the large number of alternative routes. More routes to compute means (exponentially) more work.
Re: Waypoints effect on pathfinder CPU load
NPF and YAPF are both A* - NPF has every track segment as a node, YAPF calculates the segments between junctions/signals and uses those.
Ships actually use 'tracks' as if water tiles had rails in every possible orientation. That's six track segments on every water tile, and every tile edge is a six-way junction.
Each ship appears to recalculate its entire route at every tile edge - I can't find any caching despite the paths being hugely expensive to calculate, identical between ships with the same pair of orders and almost never changing.
I think 'exponential' was in a generic more-than-linear sense rather than mathematical, but it's not as far off as it ought to be.
Ships actually use 'tracks' as if water tiles had rails in every possible orientation. That's six track segments on every water tile, and every tile edge is a six-way junction.
Each ship appears to recalculate its entire route at every tile edge - I can't find any caching despite the paths being hugely expensive to calculate, identical between ships with the same pair of orders and almost never changing.
I think 'exponential' was in a generic more-than-linear sense rather than mathematical, but it's not as far off as it ought to be.
Temporary Permanent signature filling text. Content coming soon delayed indefinitely! Oh, and I have had a screenshot thread.
Linux user (XMonad DWM/KDE, Arch), IRC obsessive and rail enthusiast. No longer building robots; now I ring church bells.
Author of an incredibly boring stickied post about NewGRFs.
Linux user (XMonad DWM/KDE, Arch), IRC obsessive and rail enthusiast. No longer building robots; now I ring church bells.
Author of an incredibly boring stickied post about NewGRFs.
Re: Waypoints effect on pathfinder CPU load
I don't know what the precise complexity of A* is, but indeed it may be less than truly exponential. On the other hand, Dijkstra or A* routing is designed to work with paths of varying costs and not too many junctions.ic111 wrote:What algorithm does OpenTTD use for the problem of pathfinding? I am a bit surprised about the term "exponential" in this context, since algorithms like Dijkstra are certainly not exponential.Alberth wrote: The killer here is the large number of alternative routes. More routes to compute means (exponentially) more work.
As FLHerne says, a piece of sea is basically one giant junction, completely filled with "track" that ships follow, and all paths are equally expensive. This is worst case for A* & friends. As a result pathfinding really explores all paths in a bread-width fashion towards the goal.
Being a retired OpenTTD developer does not mean I know what I am doing.
Re: Waypoints effect on pathfinder CPU load
People are using the term "exponential" a bit loosely around here, basically for everything non-linear. also, it's not really about the complexity of the algorithm, for a given size input, but that the input size (number of nodes) is magnitudes higher for ships.ic111 wrote:What algorithm does OpenTTD use for the problem of pathfinding? I am a bit surprised about the term "exponential" in this context, since algorithms like Dijkstra are certainly not exponential.Alberth wrote: The killer here is the large number of alternative routes. More routes to compute means (exponentially) more work.
an algorithm can be "linear" in input size, but if the input is an unary number, it's still basically exponential...
Who is online
Users browsing this forum: No registered users and 3 guests