Page 1 of 4

Experimental RoutePlanner Patch

Posted: 13 Jul 2007 14:48
by JazzyJaffa
This patch adds a YAPF based tool for automatically building a rail route between two points.
It orginally started as experimentation for an AI route finder, but the best way of testing that was to hook it up to a GUI.

To use Ctrl-Click the AutoRail tool to display the GUI, then click two empty tiles to set the start and end track segment. If the "AUTO" button is depressed then the route will be calculated and displayed, if not you have to click "Find Route".

There is also a slider for controlling how much hills should be avoided. (In the forward direction only) If AUTO is depressed then the route is recalculated as you slide the bar, but for longer routes this gets slow and chuggy and should be avoided.

Some warnings - this patch is very experimental. If there is no possible route (eg to an island) then the current algorithm does not cope well and the game will hang for a few seconds. Route calculation for all the way across a 1024x1024 map is about 8 seconds or so on my 1.5GHz celeron, using about 150MB ram.

Future ideas:
Cope better with longer routes (reduce ram and cpu usage)
Avoid curves of arbitrary radius.
Build bridges and tunnels
Terraforming

All credit goes to KUDr for the excellent YAPF, the modular nature of which made this quite easy.

Any comments or ideas, bugs would be great,
Thanks!

Posted: 13 Jul 2007 14:49
by JazzyJaffa
Windows build:

Posted: 13 Jul 2007 15:07
by Zephyris
What an awesome first 2 posts! Welcome JazzyJaffa, im going to enjoy playing with this...

Posted: 13 Jul 2007 15:29
by matryx
A suggestion - Of course you have hill-avoidance as your filter - but as shown the hilly-route is more expensive anyway. Could you introduce a few sliders (price, sharp-corners, altitude change) to further let people customise the route it picks?
It'd be interesting to see what routes it comes up with for cheapest, fastest, and most direct.

Another idea - is it just plain tracks at the moment? or does it cope with tunnels and/or bridges?

Posted: 13 Jul 2007 15:50
by JazzyJaffa
Bridges and tunnels are currently not built (see future plans above), but it does adjust for the "build on slopes" option.

Currently the only factors in determining the route (YAPF penalties) are:
  • Distance
    Change of direction
    Is this tile a hill (the slider)
    Double penalty if the last tile was also a hill
There are a few other things as you say that could be added as sliders and check-boxes:
  • Cost
    Corners of arbitary radius
    Minimum distance between altitude changes
    Allow to cross owned tracks
    Some clever hybrid which equals speed for a particular engine and cargo weight <- (hard!)
The main thing that limits me at the moment is that the gui framework only supports one slider!! :D
I think improving the resource usage is more important if it were to be used for AI building however.

Posted: 13 Jul 2007 15:53
by Bilbo
Great idea! I was thinking of maybe doing something like that myself in a month or two when I'll be less busy with other things, but you were faster :)

So now I'll rather concentrate on testing and perhaps improving your patch :)

Posted: 13 Jul 2007 15:53
by White Rabbit
Wow, like with Simutrans. :D

It occured to me that you can present sour local authorities with a route plan that end for example at an active goods producing industry, or another town, and they could allow you to build a station despite your low rating, because the proposed route would be beneficial to the town. The station would have to be part of the route, so that players cannot present a route, and then not build it, in order to place a station within the LA sphere of influence. I hope I made myself clear. Oh well, that would probably be too grand a patch anyway.

Posted: 13 Jul 2007 16:40
by chrissicom
Wow, this looks like an awesome patch, I'll definitely give it some testing :D

Posted: 13 Jul 2007 16:46
by Youri219
Looks great!

Maybe you should work together with TrueLight on the AI. It would be a shame if two people work on the same thing.

Posted: 13 Jul 2007 17:33
by Wolf01
impressive, i hope this would not end like the "build under slopes" patch :D

Posted: 13 Jul 2007 18:14
by matryx
Wolf01 wrote:impressive, i hope this would not end like the "build under slopes" patch :D
I've still got a hope that chrissicom will include that in the IN *crosses fingers*

Posted: 13 Jul 2007 18:36
by JazzyJaffa
Wow I just read though the under-slopes thread! :shock:
Comments on coding style are more than welcome, we're all continually learning right?

Posted: 13 Jul 2007 20:55
by l_Blue_l
Just wondering how 2 tracks would be built next to each other. Should there be an option to hug (stay next two a peaces of rail). Or should there be an option to build with a width of x amount of tracks.

On one of your future ideas there is Terraforming. I would be great if it would be able to do that but until there is a better terraforming in the code i think it would be pretty unless over large areas as the the cost estimations are wrong. (hint hint someone fix the terraforming :p ) I just wish i had more time so i could help. Keep up the good work.

Posted: 13 Jul 2007 21:33
by Bilbo
l_Blue_l wrote:Just wondering how 2 tracks would be built next to each other. Should there be an option to hug (stay next two a peaces of rail). Or should there be an option to build with a width of x amount of tracks.
When building doubletrack (two tracks running in same direction), it is quite important for both of the tracks to have same, or at least not very differing length, otherwise trains will prefer the shorter one so strongly, that they will use it even when it is occupied and the second one is free.
I think it should not be really a big problem to add constrain "require one extra space for the second track when finding", tho it will mean some work to do ...

Posted: 13 Jul 2007 21:38
by Tom0004
awesome stuff, can i just ask, if you plan on adding auto-signals, and if you could use it to selecy double track, or even a 4-way track ?
Zephyris wrote:What an awesome first 2 posts! Welcome JazzyJaffa, im going to enjoy playing with this...
i can agree, on both statements !!

it saves us the hard work of saving money in the early stages of a game

Posted: 13 Jul 2007 21:48
by Bilbo
0004tom wrote:awesome stuff, can i just ask, if you plan on adding auto-signals, and if you could use it to selecy double track, or even a 4-way track ?
Zephyris wrote:What an awesome first 2 posts! Welcome JazzyJaffa, im going to enjoy playing with this...
i can agree, on both statements !!

it saves us the hard work of saving money in the early stages of a game
Autosignals can be easily added with signal autocompletion (which is in trunk already), so IMHO it is unnecessary (you will need same number of clicks to select which signals you want to place as when placing signals with autocomplete afterwards.)

Posted: 13 Jul 2007 21:54
by Tom0004
what i mean,is could you use this, with the option to auto place the track and signals at the same time, a an opposite line, and maybe advance the patch into 4, 6, 8 way lines, plus signals, without having to extra clicks for siganls

as the auto complete signals patch as taken me from the stable to the nightlys, as i find this it as a hugh time saver

Re:

Posted: 14 Jul 2007 01:49
by Bilbo
0004tom wrote:what i mean,is could you use this, with the option to auto place the track and signals at the same time, a an opposite line, and maybe advance the patch into 4, 6, 8 way lines, plus signals, without having to extra clicks for siganls

as the auto complete signals patch as taken me from the stable to the nightlys, as i find this it as a hugh time saver
Im think it may be easily done, but coding intelligent GUI for that may be hell ... you can have 2,4,6,8 ... lines, sometimes you want one space between each two, sometimes you have LL_RR configuration, sometimes LR_LR, or RR_LL ... GUI to select correct signals may be a bit complex :)

Re: Experimental RoutePlanner Patch

Posted: 14 Jul 2007 07:51
by athanasios
I like this patch. OpenTTD is getting more pro. Not like commercial games...

Re: Experimental RoutePlanner Patch

Posted: 15 Jul 2007 20:04
by Lordmwa
This could end up being a useful tool for building realistic routes as well as a really great timesaver

excellent

TJ