Experimental RoutePlanner Patch

[JazzyJaffa]

Thanks for the comments, although I'm afraid features like multi-track won't be done till the pathfinder is improved. Solving the performance for longer and more complex routes is the same as solving the performance problem for global routing for ships. To this end I have started implementing a region based finder. (again using YAPF) The idea being that the ship first finds a route in terms of macro regions, and this is then used to do short routing between regions. (Essentially the player is acting as our macro routing at the moment by placing bouys!)

The first step in this is region finding, this can be done with a area-limited floodfill.
In the attached screenshot you can see the regions on water (the red tile is used to route to the region)

Currently for a 1024x1024 map the region finding from scratch takes 90ms for a high sea-level rough map and 35ms for a low-level smooth map on a 1.5GHz celeron, hopefully that will come down with some optimization. The idea is that when the terrain changes only the effected regions are updated, so the full thing is only done at game start.

The map in the screenshot had 2000 regions, routing between these is much faster than for every tile. Fingers crossed that the final result will be fast enough for bouys to be history!! (unless you want to force a route)

All this is experimental and may come to nothing, next step: write YAPF code for region routing.

[Bilbo]

Yes, what you describe is basically very similar to hierarchical A* pathfinding, you can have generally many levels, first level may consist of chunks 256x256 tiles, second level will decompose those chunks into 16x16 subchunks and third level will decompose it to individual tiles....

The Hieararchival pathfinding is described for example in this:

http://www.cs.ualberta.ca/~bulitko/F06/ ... -29-ML.pdf

With this you can find optimal path for ships and very good path for tracks (probably not optimal, due to possibility of all the terraforming, bridges, tunnels, razing way thru cities and such, which would be hard to consider all the options)

While very good for navigating ships, it my not perform as well (calculatiing really optimal path will take too long) with the track pathfinding in general once you add terraforming, tunnels and bridges, since with these you can go almost everywhere, ...

But if you stick with some reasonable limits, like maximum length of bridge/tunnel = 3 or 4 tiles (longer is bad anyway due to impossibility to place signals there, etc ... ), it may work well. I think it is better to find a path that may be slightly unoptimal in a moment than finding path that is optimal, but wait 1 minute for computing it....

Also one note to the GUI. When path is found, it would be useful if both distance of path found and "how many percent larger is that than ideal straight path" will be shown. If the percentage will be too high, you can then examine the path and bulldoze something in the way to get shorter path ... if the percentage is fine, build it. This will be useful expecially for longer paths where you will examine just the number and you immediately see how good the path is without need to examine it all.

[JazzyJaffa]

Thanks for the pdf, I'd read a few papers on hierarchical A*, and one article on how this was done for age of empires, but the one you posted is a very clear explination.
I think with the right region size (yet to be determined) just a two level hierarchy should do, its a trade of of complexity vs speed vs memory requirement as usual. I think regions over land may have to be a bit different (haven't thought too much about that) And as for terraforming, you're right thats going to be more guess-work and iterative stuff than "find the absolute optimal".

[Bilbo]

Thanks for the pdf, I'd read a few papers on hierarchical A*, and one article on how this was done for age of empires, but the one you posted is a very clear explination.
I think with the right region size (yet to be determined) just a two level hierarchy should do, its a trade of of complexity vs speed vs memory requirement as usual. I think regions over land may have to be a bit different (haven't thought too much about that) And as for terraforming, you're right thats going to be more guess-work and iterative stuff than "find the absolute optimal".

For small levels like 128x128 even one level may be enough, for large like 2048x2048 three or four levels may help ... I think that such tuning will require some testing to decide how many levels of hierarchy to use.

Also, I think that more important is get at least "quite good" route fast ... you build station, then place routes, send trains ... and once the network is working and player have enough time, he can look at he routes and try to make them shorter by using some city bulldozing, long tunnels or other tricks. Perhaps speed should be priority, as pathfinding over 250-1000ms may get you disconnected in multiplayer for not being able to cope up with server:)

[JazzyJaffa]

Also, I think that more important is get at least "quite good" route fast ...

It may be that by time-splicing the route finding code you could let the user/AI wait longer if they want a more optimal route, or stop if they were happy enough with it with out further iteration. (Based on an (found "cost")/(ideal "cost") ratio or something)

As usual lots of possibilities to consider (maybe I need to write a pathfinder to find a path through pathfinding?? meta-pathfinding! w00t!)

[Bilbo]

Also, I think that more important is get at least "quite good" route fast ...

It may be that by time-splicing the route finding code you could let the user/AI wait longer if they want a more optimal route, or stop if they were happy enough with it with out further iteration. (Based on an (found "cost")/(ideal "cost") ratio or something)

As usual lots of possibilities to consider (maybe I need to write a pathfinder to find a path through pathfinding?? meta-pathfinding! w00t!)

That may be good - you will get some route fast and then it will iteratively find a better route, while GUI remains responsive ... once you're happy with quality of the route, you press "build" and voila :-) there is the route

[prissi]

If you have time for a flood fill, then you would have time for a brute force way search (or more for a breath search, which is essentially an A* without weights.) THerefore, I am a little irritated by your comment.

However, if you dividing into regions must be done only once, it may help. (Although then you may loose the A* advantage of the minimum length route, especially when curves have a penalty.)

[Bilbo]

Also, the thing may be done by finding the track regardless of curves and once it is found, try to locally remove the curves by straightening the track where possible.

Since when you include curve penalties, you can end up with path "A->B->C" and "A->D->C" having same length, but "A->B->C->X" being "longer" than "A->D->C->X" if tracks from B and D join at C and toute B->C->X contain one sharp corner, while D->C->X is straight. This may break A* a bit :)

And once you put in terraforming, this will go even worse :)

[JazzyJaffa]

If you have time for a flood fill, then you would have time for a brute force way search

Not quite as the flood fill is linear in tiles and pf is not. (A* over all of 1024x1024 takes many seconds, floodfill less than 100ms)
Anyway the floodfill is done at map start, after that you only have to update regions affected by events such as terraforming (should only take micro-seconds)

Although then you may loose the A* advantage of the minimum length route

I'm hoping this effect will be very small as you usually pathfind to at least 2 regions ahead
A big effect is that unreachable destinations are no longer a problem, you only have to search over ~2k reachable regions not ~4M tiles!

[prissi]

Concerning Flood Fill, some remarks. Correct me, if I am wrong:

Flood fill is the same as a breath search (if you think nodes) pathfinder: Find all four neightbours, fill (mark) them if not filled (marked), start again. If you add (store link to previous tile node) and (stop, when reaching destination) is does the same as any pathfinder. If YAPF take 10 times longer than breath search, then there is something severiously wrong with the A* implementation.

And it does not matter, whatever implementation of flood fill you are using. It reperesents the crudest possible wayfinder, that can find a shortest path (by nearly checking all tiles).

Both, flood fill (resp. breath search) are similar: breath search is o(nodes+edges) and A* has o(node*log(nodes)+edges). Concerning this, A* should be always slower, would it not for thefact that it considers less nodes. Therefore, if A* takes longer than flood fill, A* has a problem.

[Nickman]

to make sure the GUI dusn't stop functioning, or the game has to wait until the path is calculated, you should use another thread to make those calculations, you will need a C++ threading library though...

[KUDr]

prissi: you wrote (summarized):
- FloodFill: o(nodes+edges)
- A*: o(node*log(nodes)+edges)

So FloodFill with 1M visited tiles can be compared to A* with 180k visited nodes (45k visited tiles) which also takes around 50 ms. So where is the problem with A*?



Nickman: I would rather try to teach YAPF how break/resume and visit i.e. 4000 nodes each frame until done.

[Bilbo]

Nickman: I would rather try to teach YAPF to know how break/resume and visit i.e. 4000 nodes each frame until done.

Saving is done in a background thread, so when doing pathfinding for purpose of rail building in other thread too, this could more effectively use multiprocessor/multicore machines (since usually only 1 processor core is used during openttd run) There is already code for multithreading in OpenTTD ... but I am not sure how much are the other data structures "resistant" to concurrent read access from another thread (game thread start modifying something while PF thread tries to find path for your rail tracks). At worse you'll have to copy entire map array and let the pathfinding thread run on the copy. I think when looking only at the map array, concurrent access should be safe (at worse you risk that somebody build something in the way while you search for the best path, in that case you have to recalculate)

[Nickman]

Indeed, if you only read from the map array, it should be that much of a problem, but you will need huards to make sure nothing can modify the array at the exact same time you want to read some data of it. (just basic thread safety .

When the path has been calculated, you could do a check if the calculated path is still valid or not and if not, recalculate a part or the whole track (I think recalculating a short piece should be sufficent.

I like the multithreaded approuch more than making YAPF break and resume... Could you maybe axplain why you prefere the other method KUDr?

[JazzyJaffa]

Prissi:
I'm sorry I wasn't thinking hard enough, you are correct about the algorithms. In the example I gave YAPF is looking at tiles and trackdirs, flood fill just at tiles hence the difference. (Plus YAPF is allocating huge amounts of RAM to remember all the nodes, FF is not)

Anyway, flood fill is not being used as a pathfinder here, its just used to delimit areas for macro
pathfinding.

[KUDr]

Nickman: because break/resume is simpler. Concurrent access to the map array would be a nightmare and taking a snapshot of whole map makes no sense (would also take remarkable time and a lot of memory). I must think not only about how to use all your cores but also about stability, maintenance cost, etc.

[JazzyJaffa]

I agree with the time splicing, its easier to control, manage and maintain. Perticularly when first developing. Threading can be looked at when everything else is stable and if it is needed.

[Bilbo]

Nickman: because break/resume is simpler. Concurrent access to the map array would be a nightmare and taking a snapshot of whole map makes no sense (would also take remarkable time and a lot of memory). I must think not only about how to use all your cores but also about stability, maintenance cost, etc.

Considering the PF thread will only read from the map array, it won't affect the main thread in any way. And once the path is found & ready, it could be verified & built in the main thread. There is the risk that PF will find way that will become invalid in meantime, but that can be solved by verifying the path (with iterative pathfinding in the main thread, path that was found could be also blocked in the meantime, so verification is necessary in both cases)
Even if the pathfinder will read map array in half of some tile being updated, it will end up as either valid tile when verifying (and so will be entire path if it goes thru that tile) or not valid tile (and verification will fail for paths thru there). At worst case you'll find suboptimal path.

Aside to that, only things you need to care about is shutting down the planning thread when new map is loaded or game is ended, etc ...

[MHTransport]

It would be helpful if this route calculation was encapsulate in a simple API, so AI and towns could easily build rail/road between two points.

Specifically, I would like to be able to make towns build a road to another town as the years getter later.

And using existing route calculation would save me from having to code it myself.

[KUDr]

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.

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.

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

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.

MHTransport: Yes, such API is the goal. I have some road planner, JazzyJaffa is working on track planner, and they both should be useful for AIs as well. But if you want to test/debug them, you need some GUI. At the moment they are waiting for the region based YAPF to be complete because they are very slow for large maps (same as YAPF for ships).