Transport Tycoon Forums

Posted: **27 Mar 2017 22:31**

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 146 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 139 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 117 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.

Posted: **31 Mar 2017 10:50**

find closest reachable ship depot v6 r27840.patch: (26.41 KiB) Downloaded 168 times

v6
Minor code fixes and some redundant code removed.

[+] Spoiler

find closest reachable ship depot v5 r27840.patch: (27.35 KiB) Downloaded 146 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 155 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.

Posted: **02 Apr 2017 12:42**

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?

Posted: **02 Apr 2017 14:19**

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.

Posted: **02 Apr 2017 15:03**

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.

Posted: **02 Apr 2017 15:36**

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

Posted: **21 Nov 2017 01:11**

find closest reachable ship depot v7 r27931.patch: (26.96 KiB) Downloaded 128 times

v7
- Updated to r27931 to resolve a conflict when patching againt r27912 or above.

Transport Tycoon Forums

find closest reachable ship depot patch

find closest reachable ship depot patch

Re: find closest reachable ship depot patch

Re: find closest reachable ship depot patch

Re: find closest reachable ship depot patch

Re: find closest reachable ship depot patch

Re: find closest reachable ship depot patch

Re: find closest reachable ship depot patch