Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Ship finds path but reports it is lost #8001

Open
debdog opened this issue Feb 14, 2020 · 9 comments
Open

Ship finds path but reports it is lost #8001

debdog opened this issue Feb 14, 2020 · 9 comments
Labels
Milestone

Comments

@debdog
Copy link

@debdog debdog commented Feb 14, 2020

Version of OpenTTD

1.10.0-RC1 and master-g2196cd3cf8
Pathfinder: YAPF
OS: Devuan ASCII (conforms Debian Stretch)

Expected result

Ship finds path and all is well.

Actual result

Ship does find path but a message appears "Ship # is lost".
This seems to happen on longer distance routes only and where the ships do not have to alter course much. On short distances this does not happen.

Steps to reproduce

The enclosed save game provides an example. Ships 1 to 3, on the long route, report being lost each time they leave the first waypoint in the Orders list.
Ship 4, on the short route, never issues such a message.

Let me know what more info is required and I'd be happy to provide it.

ships_temperate.sav.txt

@LordAro LordAro added this to the 1.10.0 milestone Feb 14, 2020
@LordAro
Copy link
Member

@LordAro LordAro commented Feb 15, 2020

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.

SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 18, 2020
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 19, 2020
@SamuXarick
Copy link
Contributor

@SamuXarick SamuXarick commented Feb 24, 2020

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.

@SamuXarick
Copy link
Contributor

@SamuXarick SamuXarick commented Feb 24, 2020

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)
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 24, 2020
@glx22
Copy link
Contributor

@glx22 glx22 commented Feb 24, 2020

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

SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 25, 2020
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 27, 2020
@James103
Copy link
Contributor

@James103 James103 commented Mar 4, 2020

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)

@SamuXarick
Copy link
Contributor

@SamuXarick SamuXarick commented Mar 4, 2020

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

@techgeeknz
Copy link
Contributor

@techgeeknz techgeeknz commented Jun 6, 2020

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?

@Yexo
Copy link
Contributor

@Yexo Yexo commented Jun 8, 2020

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.

@debdog
Copy link
Author

@debdog debdog commented Jun 8, 2020

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.