Experimental RoutePlanner Patch

[prissi]

@kudr
I do not see a problem with A* (since I am using it in simutrans too to determine building routes, and there it is considerably faster than the old breath search). My point was, if a search for a way takes very long (longer than a flood fill of the entire map array!) then there is something wrong with the usage, heuristics, or implementation of the A* pathfinder.

[KUDr]

prissi: Why? simple FF is not full PF. Full A* PF spends most of its time manipulating with nodes, calculating estimates, etc., while FF simply fills the array. For straight routes the A* PF is much faster, but if the route is complicated and A* PF needs to visit most of water tiles then A* must be significantly slower considering that for simple FF you don't need to manipulate with nodes (storing, searching for them in the hash map, etc.) you will find simple FF significantly faster than full A* PF (for complicated routes.

But still you can be right at one point. Node in YAPF contains also direction. Maybe this is the problem you are talking about. But then it would be design issue, not implementation problem.

Maybe rewriting it so that node == tile would give faster results but when i tried it, the paths taken were suboptimal (more curves than necessary). Also it was not easy to avoid 90-deg turns. Maybe i need to think harder next time.

But still all this discussion is pointless. Searching through ~1M nodes will always take seconds while using regions (~2k nodes) it can take milliseconds. Let JazzyJaffa to complete his two level PF. This itself can help a lot to improve ship pathfinding. Later we can consider caching routes (invoking PF only at start, not on every tile edge) and storing the path in a savegame.

[Bilbo]

Bilbo: it is not so simple as you imply. Look into code and you will understand.

1. You cannot let both threads working on the same map array. One thread writing into array while another thread is reading from it is very risky. Tiles being updated are in the inconsistent state for a while. It would surely lead at least to assert violations inside map accessors. In the worst case you will experience also crashes due to buffer overruns when some map bits are converted into values using translation tables. Simply PF must read a valid / consistent values from the map.

Yes, that may be a problem ...

2. Snapshot is also not a solution. PFs are supposed to use existing map accessors for low level map read operations. All those accessors use global map array pointer so they simply work over one map at one time. Would you rewrite all accessors to use some given map pointer? It would slowdown map access and make things even more complex than now.

Snapshots are slow, unless you use some clever structure with sort of copy-on-write that allow you to hold more versions concurrently, but that will complicate things a lot. And may slow down everything considerably.

There are much better ways how use threads in this game. You can run parallel threads over the same map array when:
- either all threads are only reading from the map (probably hard to find such operations)

Run pathfinding for all vehicles that need it in appropriate number of threads (based on number of CPU's/cores) at once. For very large and busy networks (like 500 trains) chance of 2 or more vehicles reaching juction and needing pathfinding in same frame is quite high.

- or if they will not access same tiles - i.e. one thread handling vehicle movement while another one can handle vehicle loading/unloading. You only need to remember vehicle state transitions and apply them at the end (synced) to keep the resulting state deterministic. Same for many other cases.

Loading or unloading write anything to map array?

But please don't waste our time by such crazy theories like '... if the second thread will only read from it then it is safe ...'. Read some smart books about multi threading programing.

Of course this does not work for example with simple linked lists or basically most simple structures, as if someone writes concurrently, even "only reading" can get you to an entry that was just freed and you got SIGSEGV right away, but for ordinary array which is not freed or resized it could work IF the PF can handle inconsistent tile that may happen from time to time. If not, the thread could be run only when tile array is not changing (like in the vehicle movement phase) - but that would require some locking and right, it may be difficult.

[prissi]

@kudr, I think we do not really disagree. I have no idea why there is a hash needed for a pathfinder, which way on tiles in an array, but if you say so ... But a flood fill can store its nodes (and if you look at the common recursive implementation, they are implicitely on the stack.) and it would have no impact in its time dependence. In any case A* should do better, there is no doubt about this.

Back to topic: for finding routes on land I have just limited the number of nodes tested (in simutrans). If a certain route of 100 tiles takes more than 100000 tiles to find (i.e. is more than twice as long), then the derivation is certainly something the user does not want to built anyway. Therefore, for route building limiting the pathfinder node count might be a reasonable comprimize on large maps.

With ships, the hierachical idea is probably the best. (Simutrans just calculates routes after finishing loading, and will only recalculate the route if the way of any vehicle is blocked, which might be appropriate for ships too.) One may combine this, by calculating the route once and then just "leave" a trail of virtual waypoints for the way back or to iterate the hierachies.

[Bilbo]

Back to topic: for finding routes on land I have just limited the number of nodes tested (in simutrans). If a certain route of 100 tiles takes more than 100000 tiles to find (i.e. is more than twice as long), then the derivation is certainly something the user does not want to built anyway. Therefore, for route building limiting the pathfinder node count might be a reasonable comprimize on large maps.

Yes, for long distance it will, but for short distance path where you have to crawl alongside that refinery and find some way through semi-urbanized area where the land is partially blocked by 2 other stations, even good and optimal path may be 3x as long as strainght one. But you can still reasonable limit it to something like "2x air distance + 100 tiles"

[Rubidium]

Run pathfinding for all vehicles that need it in appropriate number of threads (based on number of CPU's/cores) at once. For very large and busy networks (like 500 trains) chance of 2 or more vehicles reaching juction and needing pathfinding in same frame is quite high.

You know that the pathfinders decision also based on the red signal state (even quite far ahead)?
When you run it in multiple threads other trains have a chance to set a signal to red in one computer whereas it isn't red in the other. Another thing that happens is that the vehicles choose (sometimes) randomly the "best" direction when multiple directions are equally good (or when the vehicle has no orders), which makes vehicles go to other locations if the random calls are made in a different order. This causes desyncs and IS actually the reason why OpenTTD is still single threaded as almost every game state related action cannot be run in another order. Even performing the pathfinding and unloading of vehicles at the same time gives you this issue.
And do not come with: "you can just add some mutexes around all the code that actually changes stuff" because that happens in so many places that the overhead of the synchronisation between cores takes more time than the benefit you would have.

[JazzyJaffa]

The region pf is working. This is for a ship going all the way across a high sea-level rough map:

dbg: [yapf] [YAPF^]- 0- 2907 us - 1784 rounds - 49 open - 1783 closed - CHR 0.0% - c1899(sc0, ts0, o0) --
Regions passed through: 105
dbg: [yapf] [YAPFw]- 2- 979 us - 2365 rounds - 710 open - 2364 closed - CHR 0.0% - c536(sc0, ts0, o0) --

the first line is the high-level pf (2ms) and the second the ships actual tile level pf (.9ms)

The code is very rough atm, I'll clean it up for a patch.

[Bilbo]

Run pathfinding for all vehicles that need it in appropriate number of threads (based on number of CPU's/cores) at once. For very large and busy networks (like 500 trains) chance of 2 or more vehicles reaching juction and needing pathfinding in same frame is quite high.

You know that the pathfinders decision also based on the red signal state (even quite far ahead)?

I know ... 10 signals ahead by default, right? Still, finding path alone did not toggle any signals .... the movement of train later according to path found will

When you run it in multiple threads other trains have a chance to set a signal to red in one computer whereas it isn't red in the other. Another thing that happens is that the vehicles choose (sometimes) randomly the "best" direction when multiple directions are equally good (or when the vehicle has no orders), which makes vehicles go to other locations if the random calls are made in a different order. This causes desyncs and IS actually the reason why OpenTTD is still single threaded as almost every game state related action cannot be run in another order. Even performing the pathfinding and unloading of vehicles at the same time gives you this issue.
And do not come with: "you can just add some mutexes around all the code that actually changes stuff" because that happens in so many places that the overhead of the synchronisation between cores takes more time than the benefit you would have.

Games in general are difficult to be programmed multithreaded ... and yes, I forgot about the Random() in pathfinders - this would break network synchronization. I found about this when I tried some patch that included finding a nearest depot on client side as part of its function (which was not done on server side). Once that function was triggered, game almost immediately desynced due to Random() being called few more times in the depot finding code.

So pathfinding can't be run in parallel with current implementation ... and loading/unloading can't be run in parallel anyway (2 trains can try to load/unload at 1 station, which mean you'll need to handle this collisions if there is not enough cargo at station ...)

Well, adding some multithreading could be possible but it would be very difficult and I think it would mean completely rewriting most of the core functionality. Which is probably something that nobody will want to :)

Ok, forget the idea. Lets keep the thing single-threaded :) Though usage of second core to compress the save games on background is good :)

[Bilbo]

The region pf is working. This is for a ship going all the way across a high sea-level rough map:

dbg: [yapf] [YAPF^]- 0- 2907 us - 1784 rounds - 49 open - 1783 closed - CHR 0.0% - c1899(sc0, ts0, o0) --
Regions passed through: 105
dbg: [yapf] [YAPFw]- 2- 979 us - 2365 rounds - 710 open - 2364 closed - CHR 0.0% - c536(sc0, ts0, o0) --

the first line is the high-level pf (2ms) and the second the ships actual tile level pf (.9ms)

The code is very rough atm, I'll clean it up for a patch.

Just out of curiosity - how fast (slow) was original YAPF in this case?

[Rubidium]

I know ... 10 signals ahead by default, right? Still, finding path alone did not toggle any signals .... the movement of train later according to path found will

So you want to store the pathfinding result of some 2000 vehicles? And then do the vehicle movement so two trains want to go to the same direction so one has to wait, whereas it could just taken the other route that would have been free?

[JazzyJaffa]

Just out of curiosity - how fast (slow) was original YAPF in this case?

For that same route: 6114381 us = 6.1 seconds
dbg: [yapf] [YAPFw]- 2- 6114381 us - 2783615 rounds - 24198 open - 2783614 closed - CHR 0.0% - c18102(sc0, ts0, o0) --

[Rubidium]

dbg: [yapf] [YAPF^]- 0- 2907 us - 1784 rounds - 49 open - 1783 closed - CHR 0.0% - c1899(sc0, ts0, o0)
dbg: [yapf] [YAPFw]- 2- 979 us - 2365 rounds - 710 open - 2364 closed - CHR 0.0% - c536(sc0, ts0, o0)
--
dbg: [yapf] [YAPFw]- 2- 6114381 us - 2783615 rounds - 24198 open - 2783614 closed - CHR 0.0% - c18102(sc0, ts0, o0)

4 ms vs 6100 ms. That's looks like a *very* nice improvement for people who want to use ships and can't be bothered with buoys.

[JazzyJaffa]

4 ms vs 6100 ms

Hopefully theres even more to be gained by caching the macro route, only updating on terraform, canals etc. Although this will be some work to identify all changes that affect the routing - so I'm leaning more in the direction of updating 1 ship every 10 ticks or something as a (hopefully short term) comprimise.
Also all ships that share orders share a macro route, so you only have to do it once.

[Bilbo]

I know ... 10 signals ahead by default, right? Still, finding path alone did not toggle any signals .... the movement of train later according to path found will

So you want to store the pathfinding result of some 2000 vehicles? And then do the vehicle movement so two trains want to go to the same direction so one has to wait, whereas it could just taken the other route that would have been free?

Since pathfinding is called only in junctions, there will be less thatn 2000 vehicles per tick in need of PF .... still, storing 100 or PF results (which way to go now...) should not be problem.

I have not studied YAPF code, so correct me if I'm wrong, but YAPF can see only signals, not the trains directly (well, it can see them indirectly via the signals). So if next signal is say 2 tiles from the junction, until the train actually pass one of these signals, the PF from other trains won't know which of the routes was actually taken by that train, right? And once another train goes to that junction, it will decide again - based also on which path the previous train used, as it is some way ahead and now visible to the train trying to decide which way to go. So if the Random() problem would be dealt with somehow (well, that alone may be a bit difficult, though it may be solved by having per-train random seed, with the seed being equal to the current seed before starting the parallel pathfindning, with train ID added to it. This would give predictable results independent of the order the paths are found), I think PF probably could be run in parallel in one tick. Once the parallel execution is complete, all trains will be moved, according to the path found.

Although PBS (if it is going to be implemented some day) may complicate this a lot, as parallel deterministic repeatable reservation of tracks would be very complicated to do...

Well, with current system it may work, but this may block adding new features in future ... so better stay singlethreaded here too ...

[KUDr]

Run pathfinding for all vehicles that need it in appropriate number of threads (based on number of CPU's/cores) at once. For very large and busy networks (like 500 trains) chance of 2 or more vehicles reaching juction and needing pathfinding in same frame is quite high.

This is not an option. As Rubidium explained you already, the results of PFing must be deterministic and can't be in conflict with each other. Each PF run for train can influence signal states for the next run (for other trains). And this next run must read correctly updated signal states. So it could help only if running one thread for each player. But in most of cases this would not help.

Loading or unloading write anything to map array?

Not to map array, but to vehicles, so it is exactly the same issue. Any data structure can't be accessed by more threads if at least one is writing there. But using simple event queue for vehicle state changes it can run in parallel to vehicle movements/pathfindings. Of course Random() use needs to be eliminated from one of them or there must be seed fork done before (which is easy to do). YAPF itself doesn't use Random().

...it could work IF the PF can handle inconsistent tile...

Oh my god!

PF only uses map accessor APIs written for that purpose. And if you enclose all those functions into try/catch block you:
1. will have all accessors much slower
2. will need to do sophisticated decisions based on exception cought. This is called "exception driven programing" and it is really bad idea.
3. will not catch all such situations. Sometimes you will simply work with incorrect information.

I would never do that on purpose. Only by mistake.

[Bilbo]

So it could help only if running one thread for each player. But in most of cases this would not help.

Unless the top player have much larger network than others, it may help considerably.

Loading or unloading write anything to map array?

Not to map array, but to vehicles, so it is exactly the same issue. Any data structure can't be accessed by more threads if at least one is writing there.

For array where writing elements is atomic it could work. Unfortunately writing map tiles is not atomic, as the tile consist from more variables than 1. Also, while loading and unloading won't work parallel, it could work parallel with pathfinding, as loading will not write to map array (1 thread PF, second loading/unloading)
Maybe. I have not studied OTTD's PF and loading code extensively enough to tell if this is actually possible or not.

But using simple event queue for vehicle state changes it can run in parallel to vehicle movements/pathfindings. Of course Random() use needs to be eliminated from one of them or there must be seed fork done before (which is easy to do). YAPF itself doesn't use Random().

Yes, the question is how difficult it will get and what will be the speedup...

...it could work IF the PF can handle inconsistent tile...

...
PF only uses map accessor APIs written for that purpose. And if you enclose all those functions into try/catch block you:
...

Ok. Bad idea.

[Rubidium]

So it could help only if running one thread for each player. But in most of cases this would not help.

Unless the top player have much larger network than others, it may help considerably.

Lets think about the interweaving that then happens: on my computer my bus' vehicle controller is ran before your train's vehicle controller. On your computer it is vice-versa; this happens because you've got one thread per player. On my computer the bus makes it across the level crossing, on your computer the bus crashes because the train's controller is called first.

This does not only happen with crashing, but also with turning the signals of a level crossing on, or clearing up road vehicles. You will even desync when you've got several road vehicles of different players queued on a road and they start moving; on some machine the first vehicle in the queue gets processed before the second. On the other it's the other way around -> on one computer the second vehicle starts moving, on the other it does not.

Note: what I have described here is only a *very* *small* subset of places where you would get issues when you are using multiple threads to perform all kinds of vehicle movement stuff. Not to talk about all the other stuff that might go wrong.

Also, while loading and unloading won't work parallel, it could work parallel with pathfinding, as loading will not write to map array (1 thread PF, second loading/unloading)

Problem is that the pathfinding depends on the vehicles that need to travel to somewhere and those vehicle controllers use random and ... the loading/unloading does also use random (or at least will so when newindustries is complete).

[Bilbo]

So it could help only if running one thread for each player. But in most of cases this would not help.

Unless the top player have much larger network than others, it may help considerably.

Lets think about the interweaving that then happens: on my computer my bus' vehicle controller is ran before your train's vehicle controller. On your computer it is vice-versa; this happens because you've got one thread per player. On my computer the bus makes it across the level crossing, on your computer the bus crashes because the train's controller is called first.

So you end up probably with tons of limitations like "buses move before trains" making the multithreading rather unusable or you'll end up rewriting whole code to be MT safe ...

Also, while loading and unloading won't work parallel, it could work parallel with pathfinding, as loading will not write to map array (1 thread PF, second loading/unloading)

Problem is that the pathfinding depends on the vehicles that need to travel to somewhere and those vehicle controllers use random and ... the loading/unloading does also use random (or at least will so when newindustries is complete).

Random everywhere ... well, for MT to work, it may end up that each vehicle, station or any object in game will need to have its own random seed ...

I guess any attempt to put MT there will just bring heap of troubles ...

And since vehicle movement is major CPU eater (most CPU time is spent in vehicle movement code), trying to parallelize anything else is a bit futile ...

[KUDr]

Lets think about the interweaving that then happens: on my computer my bus' vehicle controller is ran before your train's vehicle controller....

Yes, RVs must be handled singlethreaded. Sorry, i was thinking of trains only. Trains from different players can still run in parallel.

Problem is that the pathfinding depends on the vehicles that need to travel to somewhere and those vehicle controllers use random and ... the loading/unloading does also use random (or at least will so when newindustries is complete).

Random() is not so big problem. Before starting some tasks in parallel we only need to fork the Random() seed. So they all start at the same seed and will use the same sequence. One of them (hardcoded which one) will then be used and others must be destroyed.

And since vehicle movement is major CPU eater (most CPU time is spent in vehicle movement code), trying to parallelize anything else is a bit futile ...

Not so bad. Still there are ways how to do it. I.e. whole train controller can be split into smaller tasks and they can run in parallel. I.e. train acceleration can be precomputed as max_accel based on train positions/speed. They can be computed at the same time as the rest of controllers. Only what is needed for such approach is to split the game into simple so called 'streams'. You can generate multiple streams of inputs (i.e. train indices) based on owner or on state (moving/loading) that can be processed in parallel, then you can send them to different threads and wait until they are completed, then apply their outputs (also streams, i.e. new vehicle states or max_accel values) onto game objects. This is how modern games are designed.

[Bilbo]

Lets think about the interweaving that then happens: on my computer my bus' vehicle controller is ran before your train's vehicle controller....

Yes, RVs must be handled singlethreaded. Sorry, i was thinking of trains only. Trains from different players can still run in parallel.

RV's are simpler. No signals, generally they are used for lesser distances and they are less favorite than train, so there is usually more trains than RV's in the game ... although introductuion of trams may change that a bit, since technically tram is RV too ...

And since vehicle movement is major CPU eater (most CPU time is spent in vehicle movement code), trying to parallelize anything else is a bit futile ...

Not so bad. Still there are ways how to do it. I.e. whole train controller can be split into smaller tasks and they can run in parallel. I.e. train acceleration can be precomputed as max_accel based on train positions/speed. They can be computed at the same time as the rest of controllers. Only what is needed for such approach is to split the game into simple so called 'streams'. You can generate multiple streams of inputs (i.e. train indices) based on owner or on state (moving/loading) that can be processed in parallel, then you can send them to different threads and wait until they are completed, then apply their outputs (also streams, i.e. new vehicle states) onto game objects. This is how modern games are designed.

Perhaps using OpenMP may make this a bit easier. Since this is basically an extension of C/C++, things can be parallelizable gradually - for some for cycles, etc that can be parallelized, you specify that they are parallelizable by stic,king appropriate #pragma somewhere. Gcc 4.2 should support it and since it is controlled by bunch of pragmas, non-openMP supportive compiler will simply build OpenTTD singlethreaded and ignore all the #pragmas...
With OpenMP, the compiler will put in all the synchronization and such stuff in for you automatically.

So you'll end up with something like this:

Code: Select all

#pragma omp parallel for
 for (i=0;i<num_trains;i++) 
     train[i].accel=CalculateAccel(train[i]);

Without openMP its ordinary for cycle, with OpenMP it may run in parallel with some luck ...