WIP: Rail/Road/Tram/Canal Planner patch
Moderator: OpenTTD Developers
WIP: Rail/Road/Tram/Canal Planner patch
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
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.
Re: WIP: Rail Planner patch
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.
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
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.
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.
Re: WIP: Rail Planner patch
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).Alberth wrote:For flat areas (ie ship path-finding) it might work though.
I'll have a look at JPS cause that'll definitely make it easier for canal planning
Re: WIP: Rail Planner patch
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 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
Re: WIP: Rail Planner patch
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
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
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: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.
I think this is identical to the function of polyline track tool.
I like this idea - although I think this could be implemented by just limiting the max planning distance from start to end.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*.
Re: WIP: Build Planner patch
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
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
Re: WIP: Build Planner patch
In your very example, the planner blocked an existing canal by building a lock over it.
Re: WIP: Build Planner patch
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
Re: WIP: Build Planner patch
Ah indeed it does, I'll see if there's a way to avoid that.
Thats a brilliant idea :0 Does that path-search to your cursor but then each click only builds the first straight segment?_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
Re: WIP: Build Planner patch
Yes, basically a polyrail with pathfinding. Didn't I already exlain it to you long ago?Hexus_One wrote: ↑04 Jul 2020 17:07Thats a brilliant idea :0 Does that path-search to your cursor but then each click only builds the first straight segment?_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
Re: WIP: Build Planner patch
Ah, you did indeed sorry I forgot_dp_ wrote: ↑04 Jul 2020 18:18Yes, basically a polyrail with pathfinding. Didn't I already exlain it to you long ago?Hexus_One wrote: ↑04 Jul 2020 17:07Thats a brilliant idea :0 Does that path-search to your cursor but then each click only builds the first straight segment?_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
Who is online
Users browsing this forum: No registered users and 13 guests