Page 1 of 1

WIP: Rail Planner patch

Posted: 24 May 2019 10:48
by Hexus_One

I am working on this Rail Planner tool, a rail building tool which lets you designate a start point and a goal point. It is based on the Factorio Rail Planner, and it uses A* path search algorithm to find the shortest route from the start to the goal. It previews the track . This saves a lot of effort in "planning" your route between two points, and I think it will make it easier for mobile/console/laptop players to play the game.

Here's a demo video if it in action

There's still some work to do, though:
  1. Implement a proper DoCommand protocol for this tool - currently it just chains together BuildRail commands which is compatible with 1.9.1 servers but is otherwise undesirable given the network load it causes.
  2. Currently the algorithm uses a LOT of memory (up to 4GiB for 1024x2048, corner to corner) so I'm trying to find less memory-intensive algorithms (IDA*, SMA* are candidates)
  3. The algorithm doesn't account for dynamic environment (i.e. the environment changing, such as town growth, other players building, water spread etc.), D* lite could be a solution to this
  4. The algorithm doesn't account for curve size limitations - eg. minimum curve length for a route. Ideally the player would be able to give a train length and the rail planner will find a path that has no slowdowns
  5. Similarly, accounting for slopes
  6. Bridge and tunnel building would be nice but can be potentially complicated
  7. An option for the rail planner to make use of existing track or to treat them as obstructions - there are lots of ways to do this (eg. should it take one-way signal into account?) so this will probably be left to later
For now I am going to implement this for 1. ship canals and then 2. roads as they have simpler mechanics compared to rails.

For now, you can view and compile the source here. So far, I've developed this against the CityMania client codebase, but the rest of my progress will be made using the OpenTTD/OpenTTD GitHub codebase.

As far as I know, there are no search algorithms which are memory-bound and can work in a dynamic environment. If you know of any, please message me!

I look forward to your feedback/suggestions :)

Re: WIP: Rail Planner patch

Posted: 26 May 2019 01:03
by odisseus
I think a tool like this will be of very limited use to human players. Sometimes, terraforming a couple tiles or building a bridge can eliminate massive detours. But other time you will be willing to make a detour in order to avoid expensive terrain like farmland. When your trains are heavy, you'll want to avoid long slopes at all costs, lest it takes them forever to climb that slope. When your trains are powerful, you can build a straight line right over the mountain peak to save distance. When your station has low supply rate and/or your trains are extremely fast, very long bridges become a viable option. There are just too many factors that decide which track route will be the best.

However, it could be useful in simple tasks like building a 10-tile stretch of track between two given points over uniform terrain. Unless the route is perfectly straight, this requires at least two click+drag actions, which your tool can reduce to one.

Re: WIP: Rail Planner patch

Posted: 26 May 2019 06:01
by Alberth
Pretty much "retired developer" at the moment, but

A 2-click laying-rail option doesn't feel fitting to me in a very rail-oriented transport game with lots of detail decisions wrt to tracks (unlike Factorio, which is not centered around trains afaik). It would become much like airports, plop down 2 airports in the middle of nowhere, buy a few aircraft, and done.

So I'd suggest you see it more like an advanced "lay some track" tool (but not always from end-to-end), ie a more generic version of the current "lay straight track in some direction" tool. That allows the user to tell the planner more precisely where to put the tracks down (around the mountain left, right, to the bottom (for making a tunnel), over it, etc). You can do this by allowing intermediate points in the planned trajectory, possibly interrupted by the user to insert a tunnel bridges, signals, etc.
This gives a lot of control back to the user, while your planner takes care of the "boring" parts.

Stepwise creating a trajectory can also be used to solve your memory problem. Limit the A* by number of stored intermediate points. Result of the path-search is the location nearest to the end-point within the limits of A*.

Finally, you may want to switch to the Jump Point Search (JPS) algorithm by Daniel Harabor and Alban Grastien presented their paper "Online Graph Pruning for Pathfinding on Grid Maps", as it performs better in grid-spaces, and has reduced storage requirements. I think there are follow-up papers which I haven't looked at in case you want further improvements. The paper assumes that the crossing points of tracks is at the center of a tile, rather than at the edge as in OpenTTD, but that looks adaptable at first sight. JPS should also work great for ship path-finding.

EDIT: My recommendation about JPS is wrong, costs need to be uniform, which is likely not the case in OpenTTD. For flat areas (ie ship path-finding) it might work though.

Re: WIP: Rail Planner patch

Posted: 27 May 2019 11:13
by Hexus_One
Alberth wrote:For flat areas (ie ship path-finding) it might work though.
I had a look at ships moving aong N/S/E/W directions, and they travel faster along those compared to the x/y directions (I'll put a picture up illustrating this).

I'll have a look at JPS cause that'll definitely make it easier for canal planning :)

Re: WIP: Rail Planner patch

Posted: 28 May 2019 14:10
by Eddi
Hexus_One wrote: I had a look at ships moving aong N/S/E/W directions, and they travel faster along those compared to the x/y directions
that happens the same way with trains, and has nothing to do with pathfinding. it has partly to do with the weird stretching of dimension and perspective that the game does, and partly with trying to avoid floating point operations (which would kill multiplayer, and back when TT was originally programmed, probably also was bad for performance)