Ship pathfinding (no buoys!) [WIP]

[JazzyJaffa]

This patch adds long-range ship pathfinding (no buoys needed).
It does this by modifying the existing YAPF ship pathfinder to first find the route to the destination over 'regions' of water. By using regions instead of tiles the pathfinder is orders of magnitude faster. The tile based pathfinder is then used to only find the route over the next couple of regions.

Use:

• Your pathfinder needs to be set to yapf before loading/generating as I haven't yet tested switching pathfinders mid-game.
• Starting openttd with '-d yapf=5' will show the regions on the sea and highlight the regions ships are going to (for a performance hit). Its fun to demolish a load of water and watch the regions grow back.

Technical points:

• I'm using m2 on water tiles to store the region index. For depots,docks and buoys this is used so I had to use (m3|(m4 >> 8 )).
• The tradeoff for faster route finding is that initial region find is done on world generation, then updated on any water terrain change. The extra ram usage is probably just under 2 bits per tile as the regions store their tiles via a bit array not as a list of TileIndex. (An idea from KUDr many moons ago)
• Region paths are not yet cached, but this could be done for even less CPU usage
• A similar approach could be used to find rail/road routes over land for the AIs, though this would be more complex.

Comments and testing very much appreciated.

[Leanden]

This hasnt been done, and anyway to make ship pathfinding better compared its current CPU munching is fine by me

[Terkhen]

It's an interesting idea

SmatZ improved the YAPF pathfinder performance enough to make it the default pathfinder for ships. Check r22350, r22351 and r22352 for details. This made the situation better, but ship pathfinding still takes many resources in comparison to other vehicle types.

[JazzyJaffa]

Thanks for the pointers. Despite the years that have passed the patch looks like it will merge in ok!

[JazzyJaffa]

I've done a first pass at merging this in at http://github.com/benjeffery/openttd (branch region)

Haven't done extensive testing yet but it routes a ship from corner to corner of a 2048x2048 in about the time the old one took to do 150 tiles.

[JazzyJaffa]

Top post updated with patchfile and details.

[koos147]

i am a regular windows user
how can i apply the patch?

[Supercheese]

i am a regular windows user
how can i apply the patch?

You don't, really. You need to be somewhat of a "super-"user to patch the source code and compile. Even I don't bother with it -- but that's because other folks (or a compile farm) will often provide compiled binaries for me (well, for all of us). Not so with this patch, however...

[FooBar]

Read this: http://wiki.openttd.org/Patches
Then decide if you still want to apply a patch (any patch) yourself.

[koos147]

thanks for the information
i will continue in my own topic
http://www.tt-forums.net/viewtopic.php?f=31&t=58872

[HackaLittleBit]

JazzyJaffa This is a awesome patch.
I played for a while with 250 ships on 256x256 map.
Were going from one side to the other without a hitch.

Found you a bug though, launch ship without orders and you get a crash.

In your patch could you please include below patch, it are the files you add to source.list

P.S. If you merge with my patch "distance between ships" it gets even better (just launch 250 ships at once)

Regards and thanks

[andythenorth]

How well does it handle pathological cases, like thin peninsulas, or large bays with a small exit?

I've seen ships bamboozled by these using the stock pathfinders...(solved with bouys)...

(Can't test for myself right now)

[HackaLittleBit]

I've seen ships bamboozled by these using the stock pathfinders

Just to give you an idea.

Map with ships (see map.png)

and detailded situation in se corner (see riv.png)
used 250 ships

[Quast65]

very interesting!

Maybe a bit offtopic because I'm not sure this issue is caused by the pathfinder. But when ships leave from a harbour they often run into the harbour first and then turn. Is it possible that they turn on the spot? So to prevent things like this:

ferry02.png (13.2 KiB) Viewed 6358 times

[Hyronymus]

very interesting!

Maybe a bit offtopic because I'm not sure this issue is caused by the pathfinder. But when ships leave from a harbour they often run into the harbour first and then turn. Is it possible that they turn on the spot? So to prevent things like this:

ferry02.png

Italians captains I presume , but is this perhaps similar to trains reverting on stations?

EDIT:No, it's as you described (of course): they move forwards for a few ticks.

[Expresso]

I suggested this a while ago... nice to see somebody working on it, here's for hoping your patch gets into trunk.

[Quast65]

EDIT:No, it's as you described (of course): they move forwards for a few ticks.

Sorry again for the possibility of this being off topic, maybe another (simpeler) solution could be to change the properties of the waterpart of the dock.

As I see it, the dock consists of 2 parts. 1 landbased (build on the slope of the shore), 1 waterbased (placed next to the landbased one). Ships seem to look at the waterbased one as a normal watertile that can be navigated over (regardless what graphics are on that). They only turn when they reach the landbased tile.

So is it maybe possible to change the properties of the waterbasedtile and give it properties of a landbased tile? Maybe ships will then recognise it as a tile that cannot be navigated on and will then turn before they run over that tile?

[HackaLittleBit]

Quast65

You have to look at vehicles as a moving point.
When u use sprite longer than standard length or sprite center point is not well chosen by the designer
the game does not know that.

[Quast65]

The original ships also have this behavior, so to me it looks like a general flaw in the game programming and not the fault of a designer of ships.

Is this fixable, or should there be a new approach to designing ships?

[Eddi]

this is fixable when docks get movement state machines. but this is a very long path...