WIP: Rail/Road/Tram/Canal Planner patch

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

Post Reply
Hexus_One
Engineer
Engineer
Posts: 6
Joined: 22 Mar 2019 00:02

WIP: Rail/Road/Tram/Canal Planner patch

Post by Hexus_One »

Hello!

I am working on a series of route planners, which will let you quickly build rail, road, tram and ship routes between two points. 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 before you build, and can be cancelled with the shift key. This saves a lot of effort in building long or complex routes 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 of the Rail Planner in action (WIP)
Here is the Ship Planner (WIP). It can build locks!
You can view the pull request here, where I keep the most up-to-date notes on my work. I have ported my dev branch(es) from the CityMania client to the OpenTTD vanilla client.

I look forward to your feedback/suggestions :)
Last edited by Hexus_One on 06 Jul 2020 12:17, edited 4 times in total.
User avatar
odisseus
Director
Director
Posts: 552
Joined: 01 Nov 2017 21:19

Re: WIP: Rail Planner patch

Post 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.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: WIP: Rail Planner patch

Post 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.
Being a retired OpenTTD developer does not mean I know what I am doing.
Hexus_One
Engineer
Engineer
Posts: 6
Joined: 22 Mar 2019 00:02

Re: WIP: Rail Planner patch

Post 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 :)
Eddi
Tycoon
Tycoon
Posts: 8258
Joined: 17 Jan 2007 00:14

Re: WIP: Rail Planner patch

Post 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)
Hexus_One
Engineer
Engineer
Posts: 6
Joined: 22 Mar 2019 00:02

Re: WIP: Rail Planner patch

Post by Hexus_One »

Bump - I'm thinking about restarting work on this patch.
Here's a gif of an implementation for canals, including locks (WIP from ages ago, a bit bugged since it only builds locks on slopes with trees)
https://gfycat.com/soupymisguidedelver
odisseus wrote: 26 May 2019 01:03 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.
We could implement a window where you can adjust values such as pathfinding weight for slopes, curves, bridges and such.
odisseus wrote: 26 May 2019 01:03However, 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.
I think this is identical to the function of polyline track tool.
Alberth wrote: 26 May 2019 06:01So 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*.
I like this idea - although I think this could be implemented by just limiting the max planning distance from start to end.
Hexus_One
Engineer
Engineer
Posts: 6
Joined: 22 Mar 2019 00:02

Re: WIP: Build Planner patch

Post by Hexus_One »

I've implemented the build planner for canals and locks, using BFS/Dijkstra path search.
You can check out the Github repository here.
See a gif of it in action here
It's just in a basic stage right now - please provide feedback, suggestions and bug reports :D
User avatar
odisseus
Director
Director
Posts: 552
Joined: 01 Nov 2017 21:19

Re: WIP: Build Planner patch

Post by odisseus »

In your very example, the planner blocked an existing canal by building a lock over it.
_dp_
Transport Coordinator
Transport Coordinator
Posts: 277
Joined: 18 Dec 2013 12:32

Re: WIP: Build Planner patch

Post by _dp_ »

I kind of made mine work the way I envisioned it. Still needs a lot of tuning and testing to be usable though. https://gfycat.com/hastyfaintlark
Hexus_One
Engineer
Engineer
Posts: 6
Joined: 22 Mar 2019 00:02

Re: WIP: Build Planner patch

Post by Hexus_One »

odisseus wrote: 04 Jul 2020 06:12 In your very example, the planner blocked an existing canal by building a lock over it.
Ah indeed it does, I'll see if there's a way to avoid that.
_dp_ wrote: 04 Jul 2020 08:57 I kind of made mine work the way I envisioned it. Still needs a lot of tuning and testing to be usable though. https://gfycat.com/hastyfaintlark
Thats a brilliant idea :0 Does that path-search to your cursor but then each click only builds the first straight segment?
_dp_
Transport Coordinator
Transport Coordinator
Posts: 277
Joined: 18 Dec 2013 12:32

Re: WIP: Build Planner patch

Post by _dp_ »

Hexus_One wrote: 04 Jul 2020 17:07
_dp_ wrote: 04 Jul 2020 08:57 I kind of made mine work the way I envisioned it. Still needs a lot of tuning and testing to be usable though. https://gfycat.com/hastyfaintlark
Thats a brilliant idea :0 Does that path-search to your cursor but then each click only builds the first straight segment?
Yes, basically a polyrail with pathfinding. Didn't I already exlain it to you long ago?
Hexus_One
Engineer
Engineer
Posts: 6
Joined: 22 Mar 2019 00:02

Re: WIP: Build Planner patch

Post by Hexus_One »

_dp_ wrote: 04 Jul 2020 18:18
Hexus_One wrote: 04 Jul 2020 17:07
_dp_ wrote: 04 Jul 2020 08:57 I kind of made mine work the way I envisioned it. Still needs a lot of tuning and testing to be usable though. https://gfycat.com/hastyfaintlark
Thats a brilliant idea :0 Does that path-search to your cursor but then each click only builds the first straight segment?
Yes, basically a polyrail with pathfinding. Didn't I already exlain it to you long ago?
Ah, you did indeed :p sorry I forgot
Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 13 guests