Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature: Rail/Road/Tram/Canal-Planner (WIP) #7607

Closed
wants to merge 4 commits into from

Conversation

Hexus-One
Copy link
Contributor

@Hexus-One Hexus-One commented May 25, 2019

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 canal planner (WIP). It can build locks!

There's still some work to do, though:

  • Implement a proper DoCommand protocol for this tool - currently it just chains together BuildRail commands which is compatible with trunk servers but is otherwise undesirable given the network load it causes.
  • 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)
  • 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
  • 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
  • Similarly, accounting for slopes
  • Bridge and tunnel building would be nice but can be potentially complicated
  • 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 2. roads as they have simpler mechanics compared to rails. The current codebase is a mess so I will try clean it up and modularise it so it uses a single class file for the A* algorithm, with separate functions for node expansion/creation.

I look forward to your feedback/suggestions :)

@kiwitreekor
Copy link
Contributor

The demo video page says Access denied... :(

@Hexus-One
Copy link
Contributor Author

Thanks, fixed!

@andythenorth
Copy link
Contributor

Thanks for this. The video is pretty neat, but I don't know if this is something that would be accepted for vanilla OpenTTD.

As there has been no activity on this PR for some, I'm proposing closing it in a few weeks if nothing more has changed, as we try to keep the PR count low. Thanks for contributing!

@andythenorth andythenorth added the stale Stale issues label Nov 2, 2019
@Hexus-One
Copy link
Contributor Author

Hi sorry for the hiatus - I've been very busy with school.

I'm going to work on this in January, if not earlier :)

@Hexus-One
Copy link
Contributor Author

Hello
I've implemented the build planner for canals and locks, using BFS/Dijkstra path search.
Github branch is here, I'm unsure how to handle it being a different branch name to this one.
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

@Hexus-One
Copy link
Contributor Author

I had an existing implementation last year (on CMClient repo fork), ported to this repo just now.

@Moth-Tolias
Copy link

wow! this is absolutely fascinating. are you able to set how long it prefers curves to be?

@Hexus-One
Copy link
Contributor Author

wow! this is absolutely fascinating. are you able to set how long it prefers curves to be?

Thanks :) Curve length is WIP, I believe @ldpl has a similar tool in development and he has implemented curve length limits.

Also @andythenorth could you un-stale this PR?

@Hexus-One Hexus-One changed the title Feature Request/WIP: Rail Planner track builder Feature: Rail/Road/Tram/Canal-Planner (WIP) Jul 6, 2020
@TrueBrain TrueBrain added candidate: most likely This Pull Request is probably going to be accepted size: large This Pull Request is large in size; review will take a while labels Dec 14, 2020
@TrueBrain
Copy link
Member

Hi @Hexus-One ! I was wondering if you were still working on this? It looks really interesting .. have not looked at the code yet, or if it fits in vanilla OpenTTD, but I like the concept and idea :)

If there is something we can help you with, do let us know! Otherwise see this as a friendly reminder you have an open Pull Request in draft mode :)

Tnx!

@TrueBrain
Copy link
Member

For now I am going to close this PR. Not because we are not interested, but because it appears this PR is sitting idle :) Please feel free to re-open this PR if I am in the wrong here, not a problem at all! (just tidying up the Pull Request list :)).

@TrueBrain TrueBrain closed this Dec 29, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
candidate: most likely This Pull Request is probably going to be accepted size: large This Pull Request is large in size; review will take a while
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

5 participants