find closest reachable ship depot patch

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

Post Reply
xarick
Transport Coordinator
Transport Coordinator
Posts: 335
Joined: 26 Feb 2015 00:52

find closest reachable ship depot patch

Post by xarick »

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
[+] Spoiler
v6:
Minor code fixes and some redundant code removed.

v5:
Implemented a maximum path cost penalty when searching for ship depots for all pathfinders. As an extra, this penalty was also implemented for NPF road vehicle depots and train depots, and YAPF road vehicle depots (was already implemented for train depots).

v4:
Implemented for OPF (Original).
find closest reachable ship depot v3 r27833.patch
(14.01 KiB) Downloaded 143 times
v3:
Implemented for NPF. Only OPF is missing this feature, and still resorts to locating depots using distance manhattan.
find closest reachable ship depot v2 r27833.patch
(9.99 KiB) Downloaded 136 times
v2:
I've learned a few things, learned that I could stack trackdirbits, which allows me to use only 1 path finding, not 2. This saves cpu resources, still gets depot location (finds a path) and the ship still maintains its expected behaviour (moves forward).
find closest reachable ship depot v1 r27832.patch
(10.88 KiB) Downloaded 112 times
v1:
So, here's how I've thought of implementing this:

First, ask the pathfinder:
Yapf will run 2 path findings. One with the direction the ship is pointing at as the origin, the other with the reversed direction as the origin. The reason I've made it run 2 path findings is because the ship can at times, not find a path in the direction it's pointing at (tile in front is a dock or a dead end), but it can in the opposite direction (tile behind the ship).

The location of the depot is retrieved from either path finder 1 or path finder 2, but the ship behaviour will follow the track of path finder 1 even it it doesn't find a depot in it. I did it this way to maintain the same expected ship movement behaviour (move forward, not backward) and to actually retrieve the location of a depot (which would otherwise not be found if it failed on path finder 1).

Fallback to the old method:
If the 2 pathfinders do not locate any depot, it resorts to finding with the old original method, which is distance manhattan based, exactly how openttd is doing right now without this patch, but that means it may find an unreachable depot.

There's still NPF and OPF to work on, but I haven't done anything on them. It falls back to distance manhattan based searching for now.
Last edited by xarick on 21 Nov 2017 01:13, edited 11 times in total.
Formerly known as Samu
xarick
Transport Coordinator
Transport Coordinator
Posts: 335
Joined: 26 Feb 2015 00:52

Re: find closest reachable ship depot patch

Post by xarick »

find closest reachable ship depot v6 r27840.patch
(26.41 KiB) Downloaded 163 times
v6
Minor code fixes and some redundant code removed.
[+] Spoiler
find closest reachable ship depot v5 r27840.patch
(27.35 KiB) Downloaded 143 times
v5

Implemented a maximum path cost (max_penalty) for all pathfinders when finding the nearest depot. This optimization should improve cpu usage when computing for depots, as it caps the search up to this limit, instead of continuing the search.

Original:
This max_penalty on OPF is the max length that the pathfinder can follow a track before it gives up. Everytime it follows a track, its count goes up by one. At best, this counting can become the same as distance manhattan from ship to depot. At worse, it can go over it. Thus, I've opted to make this penalty the same as the value of distance manhattan, which is 20 for automatic services, or 50 when not.

NPF:
This pathfinder uses Aystar algorithm and when Aystar is computing the search, everything becomes too obscure. I still managed to find where and when Aystar computes track and tile costs. The max_penalty is thus feeded to Aystar. Since NPF does not only deal with ships, but also trains and road vehicles, I had to implement this penalty for them as well. The penalty is a value that is set on openttd.cfg (npf.maximum_go_to_depot_penalty) and the default is 2000 (roughly equivalent to 20 tiles) for automatic services, or unlimited when not.

Yapf:
Similar in nature to NPF, but with a higher degree of customization. The max_penalty was already implemented for trains, but not for ships or road vehicles. I've implemented it for ships and took this opportunity to also do it for road vehicles. The penalty is a value that is set on openttd.cfg (yapf.maximum_go_to_depot_penalty) and the default is 2000 (roughly equivalent to 20 tiles) for automatic services, or unlimited when not.


Previous version (v4)
find closest reachable ship depot v4 r27837.patch
(18.15 KiB) Downloaded 151 times
v4
Implemented for OPF. This implementation is a bit different that the others.

For automatic services, the maximum distance a depot can be further away from the ship has been increased to 20, from 12.

When asking OPF to locate the closest reachable ship depot, it first iterates over all depots within 20 distance manhattan tiles away for automatic services, or within an unlimited distance when service is forced. For each iteration, OPF comes up with either the path length required to reach it or an invalid path.

For every depot that OPF can pathfind to, the lowest calculated path length will be the chosen closest reachable ship depot.


But in the case that OPF can't pathfind to any depot, it then resorts to finding with the old original method, which is distance manhattan based, the same way as the others when they can't, NPF and Yapf.
Last edited by xarick on 02 Apr 2017 22:51, edited 1 time in total.
Formerly known as Samu
J0anJosep
Traffic Manager
Traffic Manager
Posts: 139
Joined: 06 Aug 2011 15:51
Location: Spain

Re: find closest reachable ship depot patch

Post by J0anJosep »

Your patch is about 700 lines long with lots of chunks and it is difficult to review.

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;
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.

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. */
Is this a bug in the original code? Or is it a change you need for your patch?

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 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?
Formerly known as Juanjo
xarick
Transport Coordinator
Transport Coordinator
Posts: 335
Joined: 26 Feb 2015 00:52

Re: find closest reachable ship depot patch

Post by xarick »

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.
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.
Is this a bug in the original code? Or is it a change you need for your patch?
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.
I don't see why you need that. I don't see depottile used in that function.
Thanks for noticing. Indeed I don't use it. Will fix it for the next version.

Have you tested whether it can cause heavy lag in a game with lots of ships with breakdowns enabled?
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.

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
J0anJosep
Traffic Manager
Traffic Manager
Posts: 139
Joined: 06 Aug 2011 15:51
Location: Spain

Re: find closest reachable ship depot patch

Post by J0anJosep »

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.
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).
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 154 times
commit-2.diff
Ship depot pathfinding
(20.63 KiB) Downloaded 152 times
commit-3.diff
Two amends
(1.58 KiB) Downloaded 150 times
Formerly known as Juanjo
xarick
Transport Coordinator
Transport Coordinator
Posts: 335
Joined: 26 Feb 2015 00:52

Re: find closest reachable ship depot patch

Post by xarick »

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.

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;
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
Formerly known as Samu
xarick
Transport Coordinator
Transport Coordinator
Posts: 335
Joined: 26 Feb 2015 00:52

Re: find closest reachable ship depot patch

Post by xarick »

find closest reachable ship depot v7 r27931.patch
(26.96 KiB) Downloaded 125 times
v7
- Updated to r27931 to resolve a conflict when patching againt r27912 or above.
Formerly known as Samu
Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 2 guests