/* Make the ship move around aimlessly. This prevents repeated pathfinder calls and clearly indicates that the ship is lost. */

			return CreateRandomPath(v, src_tile, trackdir, path_cache, SHIP_LOST_PATH_LENGTH);

		}

		/* Try one time without restricting the search area, which generally results in better and more natural looking paths.

		 * However the pathfinder can hit the node limit in certain situations such as long aqueducts or maze-like terrain.

		 * If that happens we run the pathfinder again, but restricted only to the regions provided by the region pathfinder. */

		for (int attempt = 0; attempt < 2; ++attempt) {

			Tpf pf(MAX_SHIP_PF_NODES);

			/* Set origin and destination nodes */

			pf.SetOrigin(src_tile, trackdirs);

			pf.SetDestination(v);

			const bool is_intermediate_destination = static_cast<int>(high_level_path.size()) >= NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1;

			if (is_intermediate_destination) pf.SetIntermediateDestination(high_level_path.back());

			/* Restrict the search area to prevent the low level pathfinder from expanding too many nodes. This can happen

			 * when the terrain is very "maze-like" or when the high level path "teleports" via a very long aqueduct. */

			if (attempt > 0) pf.RestrictSearch(high_level_path);

			/* Find best path. */

			path_found = pf.FindPath(v);

			Node *node = pf.GetBestNode();

			if (attempt == 0 && !path_found) continue; // Try again with restricted search area.

			/* Return only the path within the current water region if an intermediate destination was returned. If not, cache the entire path

			 * to the final destination tile. The low-level pathfinder might actually prefer a different docking tile in a nearby region. Without

			 * caching the full path the ship can get stuck in a loop. */

			const WaterRegionPatchDesc end_water_patch = GetWaterRegionPatchInfo(node->GetTile());

			const WaterRegionPatchDesc start_water_patch = GetWaterRegionPatchInfo(tile);

			while (node->m_parent) {

				const WaterRegionPatchDesc node_water_patch = GetWaterRegionPatchInfo(node->GetTile());

				if (node_water_patch == start_water_patch || (!is_intermediate_destination && node_water_patch != end_water_patch)) {

					path_cache.push_front(node->GetTrackdir());

				}

				node = node->m_parent;

			}

			assert(!path_cache.empty());

			/* Take out the last trackdir as the result. */

			const Trackdir result = path_cache.front();

			path_cache.pop_front();

			/* Clear path cache when in final water region patch. This is to allow ships to spread over different docking tiles dynamically. */

			if (start_water_patch == end_water_patch) path_cache.clear();

			return result;

		}