Experimental RoutePlanner Patch

[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.

[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.

[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.

[MagicBuzz]

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.

[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.

[JazzyJaffa]

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.

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)

[dylf]

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 )

[JazzyJaffa]

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.

[dylf]

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....

[JazzyJaffa]

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

[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.

[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.

[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

[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.

[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

[DaleStan]

He's not suggesting reusing tracks. He's suggesting reusing tiles. Two entirely independent diagonal tracks may be placed on the same tile.

[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)

[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"

[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.