find closest reachable ship depot patch
Moderator: OpenTTD Developers
find closest reachable ship depot patch
When ships are asked to find the closest depot, the depot that is provided is not always reachable. This patch provides the closest reachable ship depot, by utilizing the pathfinder (Original, NPF or Yapf) first. Only if it fails, it would then be provided by the original method, distance manhattan based.
I suspect it can bug out in some situations or get undesired side effects, with ships going to weird places or whatnot. If it does so, please report.
Download latest version v7 here -> viewtopic.php?p=1194306#p1194306
v7:
Updated to r27931 to resolve a conflict when patching againt r27912 or above.
Videos valid for v7, v6, v5:
https://1drv.ms/v/s!Ah9vX-Q9n7IjiljfZWVyMk1dMD4U
https://1drv.ms/v/s!Ah9vX-Q9n7Ijile8JgtYwsXGdj-1
https://1drv.ms/v/s!Ah9vX-Q9n7IjilmEyqtpkPTIPcWD
https://1drv.ms/v/s!Ah9vX-Q9n7IjilbCYvOwjrUqH_u5
I suspect it can bug out in some situations or get undesired side effects, with ships going to weird places or whatnot. If it does so, please report.
Download latest version v7 here -> viewtopic.php?p=1194306#p1194306
v7:
Updated to r27931 to resolve a conflict when patching againt r27912 or above.
Videos valid for v7, v6, v5:
https://1drv.ms/v/s!Ah9vX-Q9n7IjiljfZWVyMk1dMD4U
https://1drv.ms/v/s!Ah9vX-Q9n7Ijile8JgtYwsXGdj-1
https://1drv.ms/v/s!Ah9vX-Q9n7IjilmEyqtpkPTIPcWD
https://1drv.ms/v/s!Ah9vX-Q9n7IjilbCYvOwjrUqH_u5
Last edited by xarick on 21 Nov 2017 01:13, edited 11 times in total.
Formerly known as Samu
Re: find closest reachable ship depot patch
v6
Last edited by xarick on 02 Apr 2017 22:51, edited 1 time in total.
Formerly known as Samu
Re: find closest reachable ship depot patch
Your patch is about 700 lines long with lots of chunks and it is difficult to review.
Adding a default value for max_penalty (uint max_penalty = 0) will make things easier. Also, you are adding a max_penalty, which should be a separated patch. I already suggested using the max_penalty some months ago.
Is this a bug in the original code? Or is it a change you need for your patch?
I don't see why you need that. I don't see depottile used in that function.
I haven't reviewed the rest. The patch is too long but it looks ok for what you are trying to solve.
Last year I tried implementing this same feature and I ended up with something very similar to what you have. Have you tested whether it can cause heavy lag in a game with lots of ships with breakdowns enabled?
Code: Select all
@@ -961,12 +966,13 @@
* multiple targets that are spread around, we should perform a breadth first
* search by specifiying CalcZero as our heuristic.
*/
-static NPFFoundTargetData NPFRouteInternal(AyStarNode *start1, bool ignore_start_tile1, AyStarNode *start2, bool ignore_start_tile2, NPFFindStationOrTileData *target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, AyStarUserData *user, uint reverse_penalty)
+static NPFFoundTargetData NPFRouteInternal(AyStarNode *start1, bool ignore_start_tile1, AyStarNode *start2, bool ignore_start_tile2, NPFFindStationOrTileData *target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, AyStarUserData *user, uint reverse_penalty, uint max_penalty)
{
int r;
NPFFoundTargetData result;
/* Initialize procs */
+ _npf_aystar.max_path_cost = max_penalty;
_npf_aystar.CalculateH = heuristic_proc;
_npf_aystar.EndNodeCheck = target_proc;
_npf_aystar.FoundEndNode = NPFSaveTargetData;
Code: Select all
--- src/pathfinder/npf/npf.cpp (revision 27840)
+++ src/pathfinder/npf/npf.cpp (working copy)
@@ -536,8 +536,13 @@
AyStarUserData *user = (AyStarUserData *)as->user_data;
/* It's not worth caching the result with NPF_FLAG_IS_TARGET here as below,
* since checking the cache not that much faster than the actual check */
- return IsDepotTypeTile(current->path.node.tile, user->type) ?
- AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
+ if (user->type != TRANSPORT_WATER) {
+ return IsDepotTypeTile(current->path.node.tile, user->type) ?
+ AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
+ } else {
+ return IsShipDepotTile(current->path.node.tile) && GetShipDepotPart(current->path.node.tile) == DEPOT_PART_NORTH && IsTileOwner(current->path.node.tile, user->owner) ?
+ AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
+ }
}
/** Find any safe and free tile. */
Code: Select all
@@ -187,7 +194,7 @@
* reverse. The tile given is the tile we are about to enter, enterdir is the
* direction in which we are entering the tile
*/
-Track OPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)
+Track OPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, TileIndex depottile = INVALID_TILE)
{
assert(IsValidDiagDirection(enterdir));
I haven't reviewed the rest. The patch is too long but it looks ok for what you are trying to solve.
Last year I tried implementing this same feature and I ended up with something very similar to what you have. Have you tested whether it can cause heavy lag in a game with lots of ships with breakdowns enabled?
Formerly known as Juanjo
Re: find closest reachable ship depot patch
Using a default value is a good idea. I don't know why everyone prefers separate patches, it's a mess for me, why not have everything together if it only makes sense together. Now I have to undo what I've done, only to have 2 or more patches that don't make sense without each other. Oh well, I'll see what I can do.Adding a default value for max_penalty (uint max_penalty = 0) will make things easier. Also, you are adding a max_penalty, which should be a separated patch. I already suggested using the max_penalty some months ago.
The original code is not bugged, as it doesn't deal with ship depots. Ship depots differs from the others as they are 2 tiles wide, and vehicles from different companies can traverse on ship depots of other companies. It's a change needed for my patch.Is this a bug in the original code? Or is it a change you need for your patch?
Thanks for noticing. Indeed I don't use it. Will fix it for the next version.I don't see why you need that. I don't see depottile used in that function.
I've tested with a savegame from a vanilla openttd version, with 89 ships in it, played under Yapf conditions. Changing it to OPF might not be the best testing conditions, as it can generate lost ships, due to them ships not being able to reach some docks.Have you tested whether it can cause heavy lag in a game with lots of ships with breakdowns enabled?
I'm not entirely sure how I'm methodicaly measuring cpu performance between 1.7.0 and a build with this patch. I thought of fastforwarding both games at the same time and see which one went further in-game after 10 minutes or such, but this might be an unreliable method.
Formerly known as Samu
Re: find closest reachable ship depot patch
The real mess is having to review a patch that attempts to do several things at the same time. Use git or svn for separating them (it takes time and practice to know how they work).xarick wrote:I don't know why everyone prefers separate patches, it's a mess for me, why not have everything together if it only makes sense together.
It took me less than 5 minutes separating your patch, compiling and finding two errors in your code. And with less effort than having to do it manually.
- Attachments
-
- commit-1.diff
- Max penalties
- (7.26 KiB) Downloaded 157 times
-
- commit-2.diff
- Ship depot pathfinding
- (20.63 KiB) Downloaded 155 times
-
- commit-3.diff
- Two amends
- (1.58 KiB) Downloaded 155 times
Formerly known as Juanjo
Re: find closest reachable ship depot patch
Hmm, now that I look at commit-3, I see that "inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)" is not even used. I am removing it.
Nice finding. Sometimes I pass max_penalty as 0, some other times i pass as OPF_MAX_LENGTH, but some other times I don't pass anything, but I suppose it's defaulted to OPF_MAX_LENGTH, or is it passed as NULL?
Damn, I'm a terrible coder.
I found some other error I made.
Line 371 on my patch file is repeated on line 362. The one at 371 is to be removed. When I compare the location you placed this piece of code to yours, it differs.
I used this savegame and fastforwarded to 2051, then looked at the resulting CPU Time (via Process Explorer).
https://bugs.openttd.org/task/5531/getf ... -09-07.sav
Original: 1h20m54s with v6 (~1.15% slower)
Original: 1h19m59s without
NPF: 40m34s with v6 (~7.94% slower)
NPF: 37m35s without
Yapf: 28m21s with v6 (~1.13% slower)
Yapf: 28m02s without
Code: Select all
- pfs.max_length = (max_penalty == NULL || max_penalty > OPF_MAX_LENGTH) ? OPF_MAX_LENGTH : max_penalty;
+ pfs.max_length = (max_penalty == 0 || max_penalty > OPF_MAX_LENGTH) ? OPF_MAX_LENGTH : max_penalty;
Damn, I'm a terrible coder.
I found some other error I made.
Line 371 on my patch file is repeated on line 362. The one at 371 is to be removed. When I compare the location you placed this piece of code to yours, it differs.
I used this savegame and fastforwarded to 2051, then looked at the resulting CPU Time (via Process Explorer).
https://bugs.openttd.org/task/5531/getf ... -09-07.sav
Original: 1h20m54s with v6 (~1.15% slower)
Original: 1h19m59s without
NPF: 40m34s with v6 (~7.94% slower)
NPF: 37m35s without
Yapf: 28m21s with v6 (~1.13% slower)
Yapf: 28m02s without
Formerly known as Samu
Re: find closest reachable ship depot patch
- Updated to r27931 to resolve a conflict when patching againt r27912 or above.
Formerly known as Samu
Who is online
Users browsing this forum: No registered users and 14 guests