Waypoints effect on pathfinder CPU load

OpenTTD is a fully open-sourced reimplementation of TTD, written in C++, boasting improved gameplay and many new features.

Moderator: OpenTTD Developers

Post Reply
User avatar
TimeLapse1357
Traffic Manager
Traffic Manager
Posts: 132
Joined: 10 Mar 2015 07:13
Location: Southern California

Waypoints effect on pathfinder CPU load

Post by TimeLapse1357 » 06 Oct 2016 07:03

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?

User avatar
SilverSurferZzZ
Route Supervisor
Route Supervisor
Posts: 469
Joined: 29 Oct 2013 23:31

Re: Waypoints effect on pathfinder CPU load

Post by SilverSurferZzZ » 06 Oct 2016 09:40

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.
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!

Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4741
Joined: 09 Sep 2007 05:03
Location: home

Re: Waypoints effect on pathfinder CPU load

Post by Alberth » 06 Oct 2016 11:57

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.
Being a OpenTTD developer does not mean I know what I am doing.
Also, other OpenTTD developers may have different opinions.

Eddi
Tycoon
Tycoon
Posts: 7418
Joined: 17 Jan 2007 00:14

Re: Waypoints effect on pathfinder CPU load

Post by Eddi » 08 Oct 2016 06:55

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.
You might not exactly be interested in Ferion, but if you are, have fun :)

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Waypoints effect on pathfinder CPU load

Post by ic111 » 09 Oct 2016 13:46

Alberth wrote: The killer here is the large number of alternative routes. More routes to compute means (exponentially) more work.
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.

User avatar
FLHerne
Tycoon
Tycoon
Posts: 1537
Joined: 12 Jul 2011 12:09
Location: St Ives, Cambs, UK

Re: Waypoints effect on pathfinder CPU load

Post by FLHerne » 09 Oct 2016 14:17

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.
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.

Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4741
Joined: 09 Sep 2007 05:03
Location: home

Re: Waypoints effect on pathfinder CPU load

Post by Alberth » 09 Oct 2016 14:31

ic111 wrote:
Alberth wrote: The killer here is the large number of alternative routes. More routes to compute means (exponentially) more work.
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.
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.

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 OpenTTD developer does not mean I know what I am doing.
Also, other OpenTTD developers may have different opinions.

Eddi
Tycoon
Tycoon
Posts: 7418
Joined: 17 Jan 2007 00:14

Re: Waypoints effect on pathfinder CPU load

Post by Eddi » 10 Oct 2016 14:47

ic111 wrote:
Alberth wrote: The killer here is the large number of alternative routes. More routes to compute means (exponentially) more work.
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.
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.

an algorithm can be "linear" in input size, but if the input is an unary number, it's still basically exponential...
You might not exactly be interested in Ferion, but if you are, have fun :)

Post Reply

Return to “General OpenTTD”

Who is online

Users browsing this forum: No registered users and 3 guests