Experimental RoutePlanner 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

User avatar
prissi
Chief Executive
Chief Executive
Posts: 647
Joined: 15 Nov 2004 19:46
Location: Berlin, Germany
Contact:

Re: Experimental RoutePlanner Patch

Post by prissi »

I played a little around with a hirachical pathfinder (for Simutrans). It is really fast, although the routes tend to be a little long (maybe I do not optimal path smoothing yet). But during playing around with the code I found it quite memory consuming.

- First one need an array holding for each tile a region number. (Lets say 16*16 regions and map size 2048 so the path is not too bad.) For any reasonable map size this requires at most 16384 tile numbers, thus I need an array map_x*map_y*2 = 8 MB. (Or increasing the map array by 20% for the sole purpose of ship pathfinding.)

- Next I need nodes. Using an array or array, with each of the 16384 entries storing the usually four neighbours makes 16384*(center_pos(for pathfinding)+pointer_to_array+4*sizeof(uint16)+size_of_array) = 16384*17 = 272kB, ok, not so bad.

The only way out without the huge lookup table I see, would be to repeat the flood fille and find the borders each time for start- and endpoint of a search and then search the list for entries with same center coordinates which connects to the same nodes. Should be not too bad, be requires additional 8192 checks (on average). Doing the tiling in a clever way (i.e. for left top to lower right), thus all identical center coordinates are subsequent one may even use a binary search. In this case the lookup should be really fast.
I like to look at great maps and see how things flow. A little like a finished model railway, but it is evolving and actually never finished. http://www.simutrans.com

User avatar
JazzyJaffa
Engineer
Engineer
Posts: 35
Joined: 13 Jul 2007 13:41
Location: Oxford, UK

Re: Experimental RoutePlanner Patch

Post by JazzyJaffa »

Thanks for recounting your experience, hopefully we'll be able to do this without too much memory usage - at the moment I'm cleaning up the patch and minimising its memory usage by recycling unused bits in the map array (there are about 50 unused for water tiles). I'm also hoping to not have regions remember what tiles they contain. However if they do this can be done efficiently thanks to an idea from KUDr (using a rectangle to bound the region then flagging if a tile in the rectangle is in the region). Fingers crossed this can all be done in an acceptable way in terms of memory and cpu, it may require a few iterations of the code to get it right.

User avatar
dylf
Engineer
Engineer
Posts: 30
Joined: 14 Dec 2006 14:13

Re: Experimental RoutePlanner Patch

Post by dylf »

Could it be posible to implement a "direct path" rather that the vehicle schould find the way every time. Im thinking about something like when you making a compiler you are translating the written into intermediate representations stored in binary trees... I dont know if it hasn't been tryed before and if this is a crap idea...

Thanks for the work you already have done.

User avatar
MagicBuzz
Tycoon
Tycoon
Posts: 1226
Joined: 15 Feb 2003 17:32
Location: Villefranche-sur-Saône, France

Re: Experimental RoutePlanner Patch

Post by MagicBuzz »

dylf wrote:Could it be posible to implement a "direct path" rather that the vehicle schould find the way every time.
I wouldn't like this.
Advantage of TTD is that the vehicules can find a better path as soon as there are changes on the rail/road network.
This allow vehicules to immediately find an alternate path when you are doing some work on you network.
Also, this help on heavy loaded rail traffic : if there is a traffic jam blocking a path, then new arriving trains will try to find an alternate path also.

You can manage with route markers and waypoints in order to ask the trains to prefer some path of setting mandatory waypoints.

User avatar
prissi
Chief Executive
Chief Executive
Posts: 647
Joined: 15 Nov 2004 19:46
Location: Berlin, Germany
Contact:

Re: Experimental RoutePlanner Patch

Post by prissi »

Ships can hardly jam. Therefore, a route search just at start of a new route (either from a harbour or from a bouy) is probably still acceptable and will not noticed by the player.

The rectangular regions do not help in cases, when there are more than one region in a a rectangle. Then, instead of a flag, you would need the region. (And the array of array of connections is needed anyway; or a similar structure for the nodes.)

However, I am currently playing around with a flood fill pathfinder, where each node is a "filled" line. Because smoothing the routes in the end with rough shores until a similar path to the normal pathfinder was achieved, ate up most of the time saving. Flood fill with the scanline algorithm reduce the nodes to be stored dramtically and will automatically return a corridor where just staright lines have to be put into.
I like to look at great maps and see how things flow. A little like a finished model railway, but it is evolving and actually never finished. http://www.simutrans.com

User avatar
JazzyJaffa
Engineer
Engineer
Posts: 35
Joined: 13 Jul 2007 13:41
Location: Oxford, UK

Re: Experimental RoutePlanner Patch

Post by JazzyJaffa »

dylf wrote:Could it be possible to implement a "direct path" rather that the vehicle should find the way every time..
I intended to implement the caching of ship routes after the pf is done (they are too big too combine in one patch). don't worry though, if a shorter route appears, the ship will still take it.
prissi wrote:The rectangular regions do not help in cases, when there are more than one region in a a rectangle. Then, instead of a flag, you would need the region.
The region bounding rectangles overlap, so there are never any cases where more than a flag is needed. (This is only for region->tile lookup, not tile->region)
Last edited by JazzyJaffa on 23 Jul 2007 10:49, edited 1 time in total.

User avatar
dylf
Engineer
Engineer
Posts: 30
Joined: 14 Dec 2006 14:13

Re: Experimental RoutePlanner Patch

Post by dylf »

prissi wrote:Ships can hardly jam. Therefore, a route search just at start of a new route (either from a harbour or from a bouy) is probably still acceptable and will not noticed by the player.
Yes but my intentions was to try not to have this lookup, or atleest no more than if there is any changes to the route. One thing is for ships, that could be a problem, but with a train where you will have a defined route on a track, then you could implement a intermediate representation of the route where the train only knows eg. the coordinated that it has to run through.

(sorry for my bad english :) )

User avatar
JazzyJaffa
Engineer
Engineer
Posts: 35
Joined: 13 Jul 2007 13:41
Location: Oxford, UK

Re: Experimental RoutePlanner Patch

Post by JazzyJaffa »

dylf wrote:but with a train where you will have a defined route on a track, then you could implement a intermediate representation of the route where the train only knows eg. the coordinated that it has to run through.
Before commenting on the train pathfinding/caching I recommend you read the code already in place. I believe its near optimal.

User avatar
dylf
Engineer
Engineer
Posts: 30
Joined: 14 Dec 2006 14:13

Re: Experimental RoutePlanner Patch

Post by dylf »

JazzyJaffa wrote:Before commenting on the train pathfinding/caching I recommend you read the code already in place. I believe its near optimal.
:) I beleave that the one that has implemented the existing algo has done a great job! It works very fine, but as anything else there is room for improvement. Hope that is ok.... :)

User avatar
JazzyJaffa
Engineer
Engineer
Posts: 35
Joined: 13 Jul 2007 13:41
Location: Oxford, UK

Re: Experimental RoutePlanner Patch

Post by JazzyJaffa »

Does anyone have a save game with lots of ships? Would be useful for testing. thanks.

User avatar
athanasios
Tycoon
Tycoon
Posts: 3138
Joined: 23 Jun 2005 00:09
Contact:

Re: Experimental RoutePlanner Patch

Post by athanasios »

I 've got the one I am curently playing with 104 ships. That's not much. Check in the saved games thread, there may be some with more. If not, tell me and I'll upload it.
http://members.fortunecity.com/gamesart
"If no one is a fool I am also a fool." -The TTD maniac.


I prefer to be contacted through PMs. Thanks.

User avatar
JazzyJaffa
Engineer
Engineer
Posts: 35
Joined: 13 Jul 2007 13:41
Location: Oxford, UK

Re: Experimental RoutePlanner Patch

Post by JazzyJaffa »

If they are on many different routes that would be great, I can clone ships for CPU testing, but making lots of different routes for testing takes more time.

User avatar
Bilbo
Tycoon
Tycoon
Posts: 1710
Joined: 06 Jun 2007 21:07
Location: Czech Republic

Re: Experimental RoutePlanner Patch

Post by Bilbo »

I have found two minor bugs in the routeplanner:

It is unable to use second half of tile when one half is used by diagonal track - demonstrated on first two images

Routeplanner found shortet way all around the village, but once I bulldozed the tile ith dialogal track, rtouteplanner found the "correct" way. I think it should do so even without bulldozing, since if the track is yours, you can build another diagonally next to it.

Also, routeplannes seems not being able to build crossings ... as shown on the last image
Attachments
Bug #1, before bulldozing
Bug #1, before bulldozing
Routeplanner bug, 19th Jan 2025.png (20.42 KiB) Viewed 3296 times
Bug #1, after bulldozing
Bug #1, after bulldozing
Routeplanner bug, 23rd Jan 2025.png (21.14 KiB) Viewed 3296 times
No crossings?
No crossings?
Routeplanner bug, 25th Jan 1983.png (17.84 KiB) Viewed 3297 times
If you need something, do it yourself or it will be never done.

My patches: Extra large maps (1048576 high, 1048576 wide) (FS#1059), Vehicle + Town + Industry console commands (FS#1060), few minor patches (FS#2820, FS#1521, FS#2837, FS#2843), AI debugging facility

Other: Very large ships NewGRF, Bilbo's multiplayer patch pack v5 (for OpenTTD 0.7.3)

User avatar
JazzyJaffa
Engineer
Engineer
Posts: 35
Joined: 13 Jul 2007 13:41
Location: Oxford, UK

Re: Experimental RoutePlanner Patch

Post by JazzyJaffa »

Yep, at the moment it doesn't consider any thing but clear tiles.
Its not difficult to change that behavior but I have been distracted implementing the region based pf. To edit what paths are allowed look at src/yapf/follow_routeplanner.hpp One cool thing that is possible with this is to get it to use sections of exisiting track!!
I'll come back to the routeplanner when I have a robust, stable, fast region pf.

User avatar
Bilbo
Tycoon
Tycoon
Posts: 1710
Joined: 06 Jun 2007 21:07
Location: Czech Republic

Re: Experimental RoutePlanner Patch

Post by Bilbo »

Hm ... well, I think region pf is more important, these bugs could be probably fixed quite easily :)

Also sometime it may not be good idea to reuse the tracks, since PF won't know if such reusing will create jams or so

But it may be nice if it would be some feature that could be tunred on or off ... although I think most people will turn it off
If you need something, do it yourself or it will be never done.

My patches: Extra large maps (1048576 high, 1048576 wide) (FS#1059), Vehicle + Town + Industry console commands (FS#1060), few minor patches (FS#2820, FS#1521, FS#2837, FS#2843), AI debugging facility

Other: Very large ships NewGRF, Bilbo's multiplayer patch pack v5 (for OpenTTD 0.7.3)

DaleStan
TTDPatch Developer
TTDPatch Developer
Posts: 10285
Joined: 18 Feb 2004 03:06
Contact:

Re: Experimental RoutePlanner Patch

Post by DaleStan »

He's not suggesting reusing tracks. He's suggesting reusing tiles. Two entirely independent diagonal tracks may be placed on the same tile.
To get a good answer, ask a Smart Question. Similarly, if you want a bug fixed, write a Useful Bug Report. No TTDPatch crashlog? Then follow directions.
Projects: NFORenum (download) | PlaneSet (Website) | grfcodec (download) | grfdebug.log parser

User avatar
JazzyJaffa
Engineer
Engineer
Posts: 35
Joined: 13 Jul 2007 13:41
Location: Oxford, UK

Re: Experimental RoutePlanner Patch

Post by JazzyJaffa »

I was actually suggesting reusing tracks, obviously its not that easy, you'd have to add signals on the created junctions, and have directional route planning but I think it would be a useful option (esp for the ai to make true networks)

User avatar
athanasios
Tycoon
Tycoon
Posts: 3138
Joined: 23 Jun 2005 00:09
Contact:

Re: Experimental RoutePlanner Patch

Post by athanasios »

Here is my savegame and grfs it uses. Not many ship routes though. :(
I heard of someone using many hundreds of vehicles in his game but I don't remember if he is using ships also. Hope you can find what you need.
Ah. Don't bother about Tourists. With development of new industry support they are a mess. I 've played this game long and reedited in editor many times, so if you experience something weird it will be "normal" :mrgreen:
Attachments
St. Finfield Transport, 2nd Dec 2013.sav
(1.52 MiB) Downloaded 79 times
St._Finfield_Transport_GRFs.png
St._Finfield_Transport_GRFs.png (6.3 KiB) Viewed 3144 times
http://members.fortunecity.com/gamesart
"If no one is a fool I am also a fool." -The TTD maniac.


I prefer to be contacted through PMs. Thanks.

User avatar
JazzyJaffa
Engineer
Engineer
Posts: 35
Joined: 13 Jul 2007 13:41
Location: Oxford, UK

Re: Experimental RoutePlanner Patch

Post by JazzyJaffa »

Here is as far as I got with the region pathfinder for ships, its all working and should be network safe.
You don't have to use bouys for long routes now. To veiw the regions run with "-d yapf9"

However I have to stop here as I am spending more time than I can afford on it.
Attachments
region_pf_ships_2807_r10717.patch
(65.93 KiB) Downloaded 209 times

Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: 2TallTyler, Bing [Bot] and 4 guests