NPFFoundTargetData ftd = NPFRouteToStationOrTile(v->tile, trackdir, true, &fstd, &user);

	assert(ftd.best_trackdir != INVALID_TRACKDIR);

	/* If ftd.best_bird_dist is 0, we found our target and ftd.best_trackdir contains

	 * the direction we need to take to get there, if ftd.best_bird_dist is not 0,

	 * we did not find our target, but ftd.best_trackdir contains the direction leading

	 * to the tile closest to our target. */

	path_found = (ftd.best_bird_dist == 0);

	return TrackdirToTrack(ftd.best_trackdir);

}

{

	NPFFindStationOrTileData fstd;

	NPFFoundTargetData ftd;

	NPFFillWithOrderData(&fstd, v);

	Trackdir trackdir = v->GetVehicleTrackdir();

	Trackdir trackdir_rev = ReverseTrackdir(trackdir);

	assert(trackdir != INVALID_TRACKDIR);

	assert(trackdir_rev != INVALID_TRACKDIR);

	AyStarUserData user = { v->owner, TRANSPORT_WATER, RAILTYPES_NONE, ROADTYPES_NONE, 0 };

	/* If we didn't find anything, just keep on going straight ahead, otherwise take the reverse flag */

	return ftd.best_bird_dist == 0 && NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE);

}

/*** Trains ***/

FindDepotData NPFTrainFindNearestDepot(const Train *v, int max_penalty)

{

	const Train *last = v->Last();

	Trackdir trackdir = v->GetVehicleTrackdir();

	Trackdir trackdir_rev = ReverseTrackdir(last->GetVehicleTrackdir());

	NPFFindStationOrTileData fstd;

/**

 * Finds the best path for given ship using NPF.

 * @param v        the ship that needs to find a path

 * @param path_found [out] Whether a path has been found (true) or has been guessed (false)

 * @return         the best trackdir for next turn or INVALID_TRACK if the path could not be found

 */

Track NPFShipChooseTrack(const Ship *v, bool &path_found);

/**

 * Returns true if it is better to reverse the ship before leaving depot using NPF.

 * @param v the ship leaving the depot

 * @return true if reversing is better

 */

/**

 * Used when user sends train to the nearest depot or if train needs servicing using NPF

 * @param v            train that needs to go to some depot

 * @param max_penalty  max max_penalty (in pathfinder penalty) from the current train position

 *                     (used also as optimization - the pathfinder can stop path finding if max_penalty

 *                     was reached and no depot was seen)

 * @return             the data about the depot

 */

FindDepotData NPFTrainFindNearestDepot(const Train *v, int max_penalty);

/**

 * @param v        the ship that needs to find a path

 * @param tile     the tile to find the path from (should be next tile the ship is about to enter)

 * @param enterdir diagonal direction which the ship will enter this new tile from

 * @param tracks   available tracks on the new tile (to choose from)

 * @param path_found [out] Whether a path has been found (true) or has been guessed (false)

 * @return         the best trackdir for next turn or INVALID_TRACK if the path could not be found

 */

Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache);

/**

 * Returns true if it is better to reverse the ship before leaving depot using YAPF.

 * @param v the ship leaving the depot

 * @return true if reversing is better

 */

/**

 * Finds the best path for given road vehicle using YAPF.

 * @param v         the RV that needs to find a path

 * @param tile      the tile to find the path from (should be next tile the RV is about to enter)

 * @param enterdir  diagonal direction which the RV will enter this new tile from

 * @param trackdirs available trackdirs on the new tile (to choose from)

 * @param path_found [out] Whether a path has been found (true) or has been guessed (false)

 * @return          the best trackdir for next turn or INVALID_TRACKDIR if the path could not be found

 */

Trackdir YapfRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found, RoadVehPathCache &path_cache);

			if (path_found && !path_cache.empty()) path_cache.pop_back();

		}

		return next_trackdir;

	}

	/**

	 * Check whether a ship should reverse to reach its destination.

	 * Called when leaving depot.

	 * @param v Ship

	 * @param tile Current position

	 * @param td1 Forward direction

	 * @param td2 Reverse direction

	 * @return true if the reverse direction is better

	 */

	{

		/* create pathfinder instance */

		Tpf pf;

		/* set origin and destination nodes */

		pf.SetDestination(v);

		/* find best path */

		if (!pf.FindPath(v)) return false;

		Node *pNode = pf.GetBestNode();

		if (pNode == nullptr) return false;

		/* path was found

		 * walk through the path back to the origin */

		while (pNode->m_parent != nullptr) {

			pNode = pNode->m_parent;

		}

		Trackdir best_trackdir = pNode->GetTrackdir();

	}

};

/** Cost Provider module of YAPF for ships */

template <class Types>

class CYapfCostShipT

{

public:

	typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)

	typedef typename Types::TrackFollower TrackFollower;

	typedef typename Types::NodeList::Titem Node; ///< this will be our node type

	typedef typename Node::Key Key;               ///< key to hash tables

	typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackBits, bool &path_found, ShipPathCache &path_cache);

	PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir

	/* check if non-default YAPF type needed */

	if (_settings_game.pf.yapf.disable_node_optimization) {

		pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir

	}

	Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found, path_cache);

	return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;

}

{

	Trackdir td = v->GetVehicleTrackdir();

	Trackdir td_rev = ReverseTrackdir(td);

	TileIndex tile = v->tile;

	PfnCheckReverseShip pfnCheckReverseShip = CYapfShip2::CheckShipReverse; // default: ExitDir

	/* check if non-default YAPF type needed */

	if (_settings_game.pf.yapf.disable_node_optimization) {

		pfnCheckReverseShip = &CYapfShip1::CheckShipReverse; // Trackdir

	}

	return reverse;

}

		this->y_offs -= this->y_pos - this->rotation_y_pos;

	}

}

/**

 * Test-procedure for HasVehicleOnPos to check for any ships which are visible and not stopped by the player.

 */

static Vehicle *EnsureNoMovingShipProc(Vehicle *v, void *data)

{

	return v->type == VEH_SHIP && (v->vehstatus & (VS_HIDDEN | VS_STOPPED)) == 0 ? v : nullptr;

}

{

	/* Ask pathfinder for best direction */

	bool reverse = false;

	switch (_settings_game.pf.pathfinder_for_ships) {

		default: NOT_REACHED();

	}

	return reverse;

}

static bool CheckShipLeaveDepot(Ship *v)

{

	if (!v->IsChainInDepot()) return false;

	/* We are leaving a depot, but have to go to the exact same one; re-enter */

	if (v->current_order.IsType(OT_GOTO_DEPOT) &&

			IsShipDepotTile(v->tile) && GetDepotIndex(v->tile) == v->current_order.GetDestination()) {

							}

						}

					}

				}

			}

		} else {

			/* New tile */

			if (!IsValidTile(gp.new_tile)) goto reverse_direction;

			DiagDirection diagdir = DiagdirBetweenTiles(gp.old_tile, gp.new_tile);

			assert(diagdir != INVALID_DIAGDIR);

			tracks = GetAvailShipTracks(gp.new_tile, diagdir);

			/* Choose a direction, and continue if we find one */

			track = ChooseShipTrack(v, gp.new_tile, diagdir, tracks);

			if (track == INVALID_TRACK) goto reverse_direction;

			b = _ship_subcoord[diagdir][track];

			gp.x = (gp.x & ~0xF) | b[0];

			gp.y = (gp.y & ~0xF) | b[1];

			/* Call the landscape function and tell it that the vehicle entered the tile */

			r = VehicleEnterTile(v, gp.new_tile, gp.x, gp.y);

	/* update image of ship, as well as delta XY */

	v->x_pos = gp.x;

	v->y_pos = gp.y;

getout:

	v->UpdatePosition();

	v->UpdateViewport(true, true);

	return;

reverse_direction:

	v->direction = ReverseDir(v->direction);

	/* Remember our current location to avoid movement glitch */

	v->rotation_x_pos = v->x_pos;

	v->rotation_y_pos = v->y_pos;

	v->cur_speed = 0;

	v->path.clear();

	goto getout;

}

bool Ship::Tick()

{

	PerformanceAccumulator framerate(PFE_GL_SHIPS);