So I think this is happening because FindPath (yapf_base.hpp) is returning that it didn't find a path, but is nevertheless returning a path - possibly as far as it can find? YAPF has never been the clearest thing in the world...

Not clear what should be done here - if the pathfinder can't find a complete path, there's no way to know whether the destination is just too far away, or it genuinely can't find a route.

Tuningville Transport, 1973-04-22.zip
On this savegame, with default pf.yapf.ship_curve90_penalty = 600, ship is lost, when going from oil rig to dock. If the penalty is 100, ship won't be lost.

90 degree penalties are a recent addition as well as docking tile penalties, but it seems they're both causing the required number of search nodes to find a path to be substantially increased, going past the default limit of pf.yapf.max_search_nodes = 10000.

some test results - if rounds needed are above 10000, the ship will report it's lost

ship_curve45_penalty = 100 | 0     | 100   | 0
ship_curve90_penalty = 600 | 600   | 100   | 0
---------------------------+-------+-------+------

-Savegame 2: Tuningville Transport, 1973-04-22.sav
rounds needed:       13899 |  9589 |  5070 |  3641    (added docking tile cost)
rounds needed:       13341 |  7870 |  4943 |  3172  (removed docking tile cost, with PR) 

-Savegame 1: ships_temperate.sav (with 1 ship docked at the destination dock)
rounds needed:       24938 | 34903 | 12119 | 13287    (added docking tile cost)
rounds needed:        3483 |  8269 |  3483 |  5219  (removed docking tile cost, with PR)

I think ship_curve90_penalty must be higher than ship_curve45_penalty (more than 2 times) but 600 may be too much

if rounds needed are above 10000, the ship will report it's lost

Does this also apply in any way to trains and road vehicles? (i.e. even if a train or road vehicle is able to find its path despite thousands of different turns or hundreds of junctions in the way, it will still report itself as lost)

Yes, though in normal situations it's much less likely to happen.

Does YAPF have any optimizations for dealing with wide-open spaces and long routes; such as subdividing the map into small regions and independently solving the edges of each region to find high-level connections between neighboring regions? Is this perhaps an idea that has been tried and rejected in the past?

I don't believe such optimizations are currently present. Ships have often been a neglected area in the game. The advice is generally to add more buoys to not have to deal with pathfinding long routes.

The advice is generally to add more buoys to not have to deal with pathfinding long routes.

In former versions the user was informed if a leg was too long when adding a waypoint to the route. So it was obvious that a buoy has to be added.
These days the user has to find out afterwards the route has been set up. So the user either has to place /a buoy/s and alter the waypoints retrospectively (of possibly many ships) OR decide to get spammed by a lot of "Ship is lost" messages (and then probably misses some real important messages).
Conclusion, from my point of view, is that there has been a regression.

Because of this bug it would be useful to split the "Warn if vehicle is lost" setting into one setting per vehicle type, so that there are 4 settings: "Warn if road vehicle is lost", "Warn if train is lost", "Warn if ship is lost" and "Warn if aircraft is lost".

I've turned off the "Warn if vehicle is lost" setting because I'm tired of getting false positives saying my ships are lost, but then I accidentally destroyed a piece of rail and all my trains got lost, which I didn't notice until much later when I saw a train doing something weird.

So getting a warning when a train is lost would be very useful, but getting a warning when a ship is lost is just annoying since those are always false positives, and in any case ships almost never actually get lost so getting a warning if a ship is lost is not very useful.

So I would like to turn off these warnings for ships and not for trains, which currently is not possible. I've currently turned it off for all vehicles in order not to get all those annoying "Ship X is lost" messages, but that has the side effect that I won't notice if there is something wrong with my railway system.

Did some testing during the past few days using the git bisect-tool. Tracked it down to version OpenTTD 1.10.0-beta1~138:

31db4f8 is the first bad commit

commit 31db4f8
Author: peter1138 ...@openttd.org
Date: Mon Mar 11 13:08:11 2019 +0000

Add: Penalty for occupied docking points.

:040000 040000 d4e5466e551eff7c059aab5088936bcfac1fe327 119646827e3fc738549005515ad0b9ad2cd5f076 M src

HOWEVER, I am not a developer and am not familiar with OTTD's internals. This could be a corrupt result.

After I've been told on IRC what that commit actually does I did some more testing. As long as ports have two docking points (have not tested with more yet) the messages disappear. This, of course, does not work for Oil Rigs. Ships serving these still report being lost occasionally.

So I've been thinking, maybe an IF could somehow be applied to that commit, so it does not affect ports, oil rigs or other special industries with only one docking point.

In the upcoming nightly, the OP's savegame behaves again as it did before 31db4f8.

For the other savegames (and modification of OP's savegame), and in general tbh, the advise still stands: please add buoys if ships get lost. Our pathfinder is not really optimized for water, and its limits are pretty strict. In result, if it needs to navigate too much open water, it is likely to give up, and show a "ship is lost" message.
In OP's savegame for example, it is already on the limit of what it can handle; any chance tops it over.

I created #9523 to address that you only get the news report about it being lost once, instead of having a persistent place you can see that ships are getting lost.
I created #9525 as I think it is a very solid idea to report the impossibility of the order you have setup before the ship leaves. That makes it easier to notice you have to add buoys etc. (the "it did it in earlier versions" was a very stupid "max distance" check, and didn't really had anything to do with if the pathfinder could connect the two places. This rightfully got removed).

With those two tickets, this ticket can be closed, I think. Let me know if there are any additional problems. Tnx for the report!

Edit: made it a bit more clear what is addressed in the nightly and what is not.

In the upcoming nightly, the OP's savegame behaves again as it did before 31db4f8.

Yes, but only if there's no ship at the destination's docking tile.

The following steps still trigger "ship is lost":

• load ships_temperate.sav
• stop ship 3, which is unloading at Würzbrücken Docks (equivalent to simulating a full load, which often requires time)
• watch ship 1 and 2 report "ship is lost" when starting from Vorbrücken Docks

I admit that my wording could have been better, but that is exactly what I tried to say with "For the other savegames". This includes any variation of the given savegame.

There are tons of different ways to trigger a "ship is lost" in any savegame (with ships). You (Samu) are hyperfocused on the docking tiles, but there are many other ways that same savegame could cause "ship is lost". For example a town that decides to landscape a single water tile. Or the user that decides to do this. How ever minor, even a single tile, can cause a "ship is lost" cascade. In this case it is triggered by docking tiles, but it is really important to separate what the direct cause is, and what the actual issue is.

As mentioned in #9522, this specific route in question is already very close to the limit of what the pathfinder can handle. Any negative disruption causes it to top over, and start spitting out "ship is lost". This is why I created two follow-up tickets to make this more clear to the end-user. Currently this information is rather hidden, and that makes users surprised that a minor change can cascade into "ship is lost". This includes stopping a ship on a docking tile.

So to phrase it in a different way: there is nothing we can do to fix all cases of ship is lost, without redesigning the pathfinder completely. This is a known limitation of the pathfinder. By accident #9522 addresses the immediate issue for the OP's savegame, and that is a nice bonus. But the true solution (with the current pathfinder) is to add more buoys. And for the game to be much more clear when this issue is (about to) arise, so the user understands that adding buoys is the way to go.

I am not sure where to report now with all them commits for attempts to fix this are going on.

Sorry to report that after some testing I am rather disappointed. The "Ship is lost" reports seem to occur a tad less now. But far less than I hoped they would be. At this point I think it'd be easier to just revert commit 31db4f8 since its benefit, mere eye-candy, is much less than its downside, mostly annoying messages.

Just to repeat what I tried to write earlier: it doesn't really help. Any other change to the ship PF will trigger this problem again, or any change to landscape. The solution really is to add one or two buoys to your route. And of course there are now some tickets to make it clear to the user when they should do this, as I 100% agree this is very hidden :)

I am really sorry, but this is just the ship PF being a dick :(