Fix: pathfinders always tried to avoid docking tiles (even if nothing was on them) #9522
Conversation
… was on them) When coming across any docking tile (for example, all tiles around an oilrig are docking tiles), it always at least added a penalty of 3 times a normal tile, even when there are no ships on them. In result, the pathfinder got suggested to always go around docking tiles. This was most likely not the intention of the change made in 31db4f8.
|
I was finally able to make yapf place signs just in time to visualize the difference in number of open+closed nodes searched for this PR. One ship in destination's docking tile: No ship in destination's docking tile: EDIT: Notice the "thicker" line in the first image, as it needs to search more nodes due to the docking tile occupancy penalty. Also notice in the viewport that there are already some "x"'s past the dock, indicating it is searching past the goal. In the second image, since there's no penalty, it doesn't do that. |
|
How bad of a performance hit are we looking at here? Actually noticeable in real play? There's a few extra tiles searched in Samu's screenshot, but not enough that I would expect would make a significant difference (especially since these are all being cached anyway) |
Strongly depends on the scenario. I have had routes that went from ~5000 tiles search-space to over ~10000 (after which the PF gives up). The reason why it does this is because of another lurking issue which I didn't want to address in this PR: Basically the change 31db4f8 makes the path "3 wider" for each time it encounters a docking tile on its route (the penalty is 3x a normal tile, so up to 3 tiles out of the route has an equal penalty). Given we use a node that combines position & trackdir, it means the amount of nodes considered vastly booms. But in a nut-shell, for routes that were already hefty, like 5000 tiles, encountering (empty) docking tiles all of a sudden means it booms in the amount of tiles it checks. That all said and done, mainly why I address this issue, is because it is faulty to overshoot your destination. When there is a single docking tile that is empty, the PF still tried to look for 3 tiles left and right for a better match. It simply doesn't make sense to me to always give a docking tile this penalty, even if it is empty. Edit: so to be clear, it has little to do with performance hit, but more with the PF limit of 10k nodes. |
|
What might be a useful addition, the images shown above are a 2D image of a hyper-plane-based pathfinder. With that I mean: a Node is a Tile + TrackDir combo. So each tile on the map can have several nodes attached to it. So flatten this in an image might give an unrealistic view of how many nodes are actually tested :) |
|
Did my best to update the original description, to hopefully be a bit more understandable what is going on. I noticed I did mention in the motivation I consider this a bug, but my description went into details of the "ship is lost" part. The new description hopefully makes it more clear it foremost resolves what I consider a bug, but additionally makes some savegames that now report "ship is lost" and didn't before, not do it now again. In short: an empty water-tile should not yield a penalty for ships, even if they are docking tiles. PS: the solution is for "ship is lost" is and always has been: use more buoys ;) |
Motivation / Problem
While reading up on #9514 (and being confused about what it tries to address) and checking out #8001 and getting a bit annoyed by the fact people confuse cause with causality, I looked into the multi-dock stuff for pathfinders.
A few things I figured out I did not know:
But mainly, and that is the reason for this PR: I noticed that even if a tile is empty, it was being avoided. Basically the pathfinder always tried to avoid going through a docking tile, empty or not.
Description
There is something to say for avoiding docking tiles in general, as it is a bad thing for a ship to enter such tiles. Sadly, in the way our ship pathfinder works, this is not something that will result in good routes. Also, it is kinda weird we do this for docking tiles, and not for ships in general. As that would of course be the ultimate dream, that ships don't go over the same tile at the same time.
So personally, I consider ships avoiding docking tiles that are empty a bug, and this PR sets out to resolve that.
In more detail:
When a ship navigates through open waters with a lot of oilrigs / depots, it is not only avoiding the rig / depot, but it also tries to stay away from the docking tiles. In fact, if the best route would be through a docking tile, it scans for 3 more tiles in the width of its path, making it scan a lot more tiles for a better route. This, I guess, is an unintentional side-effect of 31db4f8 .
As I wrote in the commit message:
This makes routes that were "barely cutting it" in the allowed amount of nodes we can scan to "surely not going to make it". This means people get "ship is lost" in situations they didn't get before.
This PR mitigates "ship is lost" slightly by reducing the amount of nodes we need to scan to before 31db4f8 in case no ship occupies any of those docking tiles. If any ship does, it still does the same stuff, and can still give "ship is lost".
In the screenshots below you can see this happening because of the depot. The ship has to navigate around it, but instead of going 1 around it in search-space, it checks out 3 wide, because of this additional penalty. Despite there not being any ship.
This means this PR addresses the original savegame in #8001, and basically makes the game similar to before 31db4f8 for those savegames (while still having the benefits of that change). However, there are still many cases where you get "ship is lost". This is not a solution to that; this is only addressing the regression created by 31db4f8 for the most common use-case. And it is solving the fact that I think it is wrong ships avoid a perfectly valid tile to pass through, just because it can also be used as docking tile ;)
Limitations
Checklist for review
Some things are not automated, and forgotten often. This list is a reminder for the reviewers.