NPFFindStationOrTileData fstd;

	NPFFillWithOrderData(&fstd, v);

	Trackdir trackdir = DiagDirToDiagTrackdir(enterdir);

	NPFFoundTargetData ftd = NPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_ROAD, v->compatible_roadtypes, v->owner, INVALID_RAILTYPES);

	if (ftd.best_trackdir == INVALID_TRACKDIR) {

		/* We are already at our target. Just do something

		 * @todo: maybe display error?

		 * @todo: go straight ahead if possible? */

		path_found = true;

		return (Trackdir)FindFirstBit2x64(trackdirs);

	}

	/* 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 ftd.best_trackdir;

}

/*** Ships ***/

{

	NPFFindStationOrTileData fstd;

	Trackdir trackdir = v->GetVehicleTrackdir();

	assert(trackdir != INVALID_TRACKDIR); // Check that we are not in a depot

	NPFFillWithOrderData(&fstd, v);

	NPFFoundTargetData ftd = NPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_WATER, 0, v->owner, INVALID_RAILTYPES);

	/* 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. */

	if (ftd.best_trackdir == 0xff) return INVALID_TRACK;

	return TrackdirToTrack(ftd.best_trackdir);

}

/*** 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;

	fstd.v = v;

	fstd.reserve_path = false;

	assert(trackdir != INVALID_TRACKDIR);

	NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, &fstd, TRANSPORT_RAIL, 0, v->owner, v->compatible_railtypes, NPF_INFINITE_PENALTY);

	if (ftd.best_bird_dist != 0) return FindDepotData();

	/* Found target */

	/* Our caller expects a number of tiles, so we just approximate that

	 * number by this. It might not be completely what we want, but it will

	 * work for now :-) We can possibly change this when the old pathfinder

	 * is removed. */

 * @param max_penalty  max distance (in pathfinder penalty) from the current vehicle 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 NPFRoadVehicleFindNearestDepot(const RoadVehicle *v, int max_penalty);

/**

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

 * @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 NPFRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found);

/**

 * Finds the best path for given ship using NPF.

 * @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)

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

 */

/**

 * 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);

/**

 * Try to extend the reserved path of a train to the nearest safe tile using NPF.

 *

 * @param v    The train that needs to find a safe tile.

 * @param tile Last tile of the current reserved path.

 * @param td   Last trackdir of the current reserved path.

 * @param override_railtype Should all physically compatible railtypes be searched, even if the vehicle can't run on them on its own?

 * @return True if the path could be extended to a safe tile.

 */

bool NPFTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype);

/**

 * Returns true if it is better to reverse the train before leaving station using NPF.

			/* if we reach this position, there's two paths of equal value so far.

			 * pick one randomly. */

			uint r = GB(Random(), 0, 8);

			if (_pick_shiptrack_table[i] == ship_dir) r += 80;

			if (_pick_shiptrack_table[best_track] == ship_dir) r -= 80;

			if (r <= 127) goto bad;

		}

good:;

		best_track = i;

		best_bird_dist = pfs.best_bird_dist;

		best_length = pfs.best_length;

bad:;

	} while (bits != 0);

	*track = best_track;

	return best_bird_dist;

}

/**

 * returns the track to choose on the next tile, or -1 when it's better to

 * reverse. The tile given is the tile we are about to enter, enterdir is the

 * direction in which we are entering the tile

 */

{

	assert(IsValidDiagDirection(enterdir));

	TileIndex tile2 = TILE_ADD(tile, -TileOffsByDiagDir(enterdir));

	Track track;

	/* Let's find out how far it would be if we would reverse first */

	TrackBits b = TrackStatusToTrackBits(GetTileTrackStatus(tile2, TRANSPORT_WATER, 0)) & DiagdirReachesTracks(ReverseDiagDir(enterdir)) & v->state;

	uint distr = UINT_MAX; // distance if we reversed

	if (b != 0) {

		distr = FindShipTrack(v, tile2, ReverseDiagDir(enterdir), b, tile, &track);

		if (distr != UINT_MAX) distr++; // penalty for reversing

	}

	/* And if we would not reverse? */

	uint dist = FindShipTrack(v, tile, enterdir, tracks, 0, &track);

	if (dist <= distr) return track;

	return INVALID_TRACK; // We could better reverse

}

/*

 * This file is part of OpenTTD.

 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.

 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.

 */

/** @file opf_ship.h Original pathfinder for ships; very simple. */

#ifndef OPF_SHIP_H

#define OPF_SHIP_H

#include "../../direction_type.h"

#include "../../tile_type.h"

#include "../../track_type.h"

#include "../../vehicle_type.h"

/**

 * Finds the best path for given ship using OPF.

 * @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)

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

 */

#endif /* OPF_SHIP_H */

/*

 * This file is part of OpenTTD.

 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.

 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.

 */

/** @file yapf.h Entry point for OpenTTD to YAPF. */

#ifndef  YAPF_H

#define  YAPF_H

#include "../../direction_type.h"

#include "../../track_type.h"

#include "../../vehicle_type.h"

#include "../pathfinder_type.h"

/**

 * Finds the best path for given ship using YAPF.

 * @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)

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

 */

/**

 * 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);

/**

 * Finds the best path for given train using YAPF.

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

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

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

 * @param tracks   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)

 * @param reserve_track indicates whether YAPF should try to reserve the found path

 * @param target   [out] the target tile of the reservation, free is set to true if path was reserved

 * @return         the best track for next turn

 */

Track YapfTrainChooseTrack(const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, bool reserve_track, struct PBSTileInfo *target);

	{

		return *static_cast<Tpf*>(this);

	}

public:

	/**

	 * Called by YAPF to move from the given node to the next tile. For each

	 *  reachable trackdir on the new tile creates new node, initializes it

	 *  and adds it to the open list by calling Yapf().AddNewNode(n)

	 */

	inline void PfFollowNode(Node& old_node)

	{

		TrackFollower F(Yapf().GetVehicle());

		if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) {

			Yapf().AddMultipleNodes(&old_node, F);

		}

	}

	/** return debug report character to identify the transportation type */

	FORCEINLINE char TransportTypeChar() const

	{

		return 'w';

	}

	{

		/* handle special case - when next tile is destination tile */

		if (tile == v->dest_tile) {

			/* convert tracks to trackdirs */

			TrackdirBits trackdirs = (TrackdirBits)(tracks | ((int)tracks << 8));

			/* choose any trackdir reachable from enterdir */

			trackdirs &= DiagdirReachesTrackdirs(enterdir);

			return (Trackdir)FindFirstBit2x64(trackdirs);

		}

		/* move back to the old tile/trackdir (where ship is coming from) */

		TileIndex src_tile = TILE_ADD(tile, TileOffsByDiagDir(ReverseDiagDir(enterdir)));

		Trackdir trackdir = v->GetVehicleTrackdir();

		assert(IsValidTrackdir(trackdir));

		/* convert origin trackdir to TrackdirBits */

		TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);

		/* get available trackdirs on the destination tile */

		TrackdirBits dest_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER, 0));

		/* create pathfinder instance */

		Tpf pf;

		/* set origin and destination nodes */

		pf.SetOrigin(src_tile, trackdirs);

		pf.SetDestination(v->dest_tile, dest_trackdirs);

		/* find best path */

		Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"

		Node *pNode = pf.GetBestNode();

		if (pNode != NULL) {

			/* walk through the path back to the origin */

			Node *pPrevNode = NULL;

			while (pNode->m_parent != NULL) {

				pPrevNode = pNode;

				pNode = pNode->m_parent;

			}

			/* return trackdir from the best next node (direct child of origin) */

			Node& best_next_node = *pPrevNode;

			assert(best_next_node.GetTile() == tile);

			next_trackdir = best_next_node.GetTrackdir();

		}

		return next_trackdir;

	}

};

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

template <class Types>

class CYapfCostShipT

{

	/** Tpf - pathfinder type */

	typedef Tpf_                              Tpf;

	/** track follower helper class */

	typedef Ttrack_follower                   TrackFollower;

	/** node list type */

	typedef Tnode_list                        NodeList;

	typedef Ship                              VehicleType;

	/** pathfinder components (modules) */

	typedef CYapfBaseT<Types>                 PfBase;        // base pathfinder class

	typedef CYapfFollowShipT<Types>           PfFollow;      // node follower

	typedef CYapfOriginTileT<Types>           PfOrigin;      // origin provider

	typedef CYapfDestinationTileT<Types>      PfDestination; // destination/distance provider

	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;       // segment cost cache provider

	typedef CYapfCostShipT<Types>             PfCost;        // cost provider

};

/* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */

struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};

/* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */

struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};

/* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */

struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};

/** Ship controller helper - path finder invoker */

{

	/* default is YAPF type 2 */

	PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg

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

	if (_settings_game.pf.forbid_90_deg) {

		pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg

	} else if (_settings_game.pf.yapf.disable_node_optimization) {

		pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg

	}

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

}

 */

static void ShipArrivesAt(const Vehicle *v, Station *st)

{

	/* Check if station was ever visited before */

	if (!(st->had_vehicle_of_type & HVOT_SHIP)) {

		st->had_vehicle_of_type |= HVOT_SHIP;

		SetDParam(0, st->index);

		AddVehicleNewsItem(

			STR_NEWS_FIRST_SHIP_ARRIVAL,

			(v->owner == _local_company) ? NS_ARRIVAL_COMPANY : NS_ARRIVAL_OTHER,

			v->index,

			st->index

		);

		AI::NewEvent(v->owner, new AIEventStationFirstVehicle(st->index, v->index));

	}

}

/**

 * returns the track to choose on the next tile, or -1 when it's better to

 * reverse. The tile given is the tile we are about to enter, enterdir is the

 * direction in which we are entering the tile

 */

{

	assert(IsValidDiagDirection(enterdir));

	switch (_settings_game.pf.pathfinder_for_ships) {

		default: NOT_REACHED();

	}

}

static const Direction _new_vehicle_direction_table[] = {

	DIR_N , DIR_NW, DIR_W , INVALID_DIR,

	DIR_NE, DIR_N , DIR_SW, INVALID_DIR,

	DIR_E , DIR_SE, DIR_S

};

static Direction ShipGetNewDirectionFromTiles(TileIndex new_tile, TileIndex old_tile)

{

	uint offs = (TileY(new_tile) - TileY(old_tile) + 1) * 4 +

							TileX(new_tile) - TileX(old_tile) + 1;

	assert(offs < 11 && offs != 3 && offs != 7);

	return _new_vehicle_direction_table[offs];

}

static Direction ShipGetNewDirection(Vehicle *v, int x, int y)

{

	uint offs = (y - v->y_pos + 1) * 4 + (x - v->x_pos + 1);

	assert(offs < 11 && offs != 3 && offs != 7);

	return _new_vehicle_direction_table[offs];

}

static inline TrackBits GetAvailShipTracks(TileIndex tile, DiagDirection dir)