/// default constructor

	FORCEINLINE CYapfBaseT()

		: m_pBestDestNode(NULL)

		, m_pBestIntermediateNode(NULL)

		, m_settings(&_patches.yapf)

		, m_max_search_nodes(PfGetSettings().max_search_nodes)

		, m_veh(NULL)

		, m_stats_cost_calcs(0)

		, m_stats_cache_hits(0)

		, m_num_steps(0)

	{

	}

	/// default destructor

	~CYapfBaseT() {}

protected:

	/// to access inherited path finder

	FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}

public:

	/// return current settings (can be custom - player based - but later)

	FORCEINLINE const YapfSettings& PfGetSettings() const

	{

		return *m_settings;

	}

	/** Main pathfinder routine:

	 *   - set startup node(s)

	 *   - main loop that stops if:

	 *      - the destination was found

	 *      - or the open list is empty (no route to destination).

	 *      - or the maximum amount of loops reached - m_max_search_nodes (default = 10000)

	 * @return true if the path was found */

	inline bool FindPath(const Vehicle *v)

	{

		m_veh = v;

#ifndef NO_DEBUG_MESSAGES

		CPerformanceTimer perf;

		perf.Start();

#endif /* !NO_DEBUG_MESSAGES */

		Yapf().PfSetStartupNodes();

		while (true) {

			m_num_steps++;

			Node *n = m_nodes.GetBestOpenNode();

			// if the best open node was worse than the best path found, we can finish

			if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n->GetCostEstimate())

				break;

			Yapf().PfFollowNode(*n);

			if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) {

				m_nodes.PopOpenNode(n->GetKey());

				m_nodes.InsertClosedNode(*n);

			} else {

				m_pBestDestNode = m_pBestIntermediateNode;

				break;

			}

		}

		bool bDestFound = (m_pBestDestNode != NULL) && (m_pBestDestNode != m_pBestIntermediateNode);

#ifndef NO_DEBUG_MESSAGES

		perf.Stop();

		if (_debug_yapf_level >= 3) {

			int t = perf.Get(1000000);

			_total_pf_time_us += t;

			UnitID veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0;

			char ttc = Yapf().TransportTypeChar();

			float cache_hit_ratio = (m_stats_cache_hits == 0) ? 0.0f : ((float)m_stats_cache_hits / (float)(m_stats_cache_hits + m_stats_cost_calcs) * 100.0f);

			int cost = bDestFound ? m_pBestDestNode->m_cost : -1;

			int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;

			DEBUG(yapf, 3, "[YAPF%c]%c%4d- %d us - %d rounds - %d open - %d closed - CHR %4.1f%% - c%d(sc%d, ts%d, o%d) -- ",

			  ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(),

			  cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000),

			  m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000)

			);

		}

#endif /* !NO_DEBUG_MESSAGES */

		return bDestFound;

	}

	/** If path was found return the best node that has reached the destination. Otherwise

	 *  return the best visited node (which was nearest to the destination).

	 */

	{

	}

	/** Calls NodeList::CreateNewNode() - allocates new node that can be filled and used

	 *  as argument for AddStartupNode() or AddNewNode()

	 */

	FORCEINLINE Node& CreateNewNode()

	{

		Node& node = *m_nodes.CreateNewNode();

		return node;

	}

	/** Add new node (created by CreateNewNode and filled with data) into open list */

	FORCEINLINE void AddStartupNode(Node& n)

	{

		Yapf().PfNodeCacheFetch(n);

		// insert the new node only if it is not there

		if (m_nodes.FindOpenNode(n.m_key) == NULL) {

			m_nodes.InsertOpenNode(n);

		} else {

			// if we are here, it means that node is already there - how it is possible?

			//   probably the train is in the position that both its ends point to the same tile/exit-dir

			//   very unlikely, but it happened

		}

	}

	/** add multiple nodes - direct children of the given node */

	FORCEINLINE void AddMultipleNodes(Node* parent, const TrackFollower &tf)

	{

		bool is_choice = (KillFirstBit2x64(tf.m_new_td_bits) != 0);

		for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = (TrackdirBits)KillFirstBit2x64(rtds)) {

			Trackdir td = (Trackdir)FindFirstBit2x64(rtds);

			Node& n = Yapf().CreateNewNode();

			n.Set(parent, tf.m_new_tile, td, is_choice);

			Yapf().AddNewNode(n, tf);

		}

	}

	/** AddNewNode() - called by Tderived::PfFollowNode() for each child node.

	 *  Nodes are evaluated here and added into open list */

	void AddNewNode(Node &n, const TrackFollower &tf)

	{

		// evaluate the node

		bool bCached = Yapf().PfNodeCacheFetch(n);

		if (!bCached) {

			m_stats_cost_calcs++;

		} else {

			m_stats_cache_hits++;

		}

template <class Types>

class CYapfFollowAnyDepotRailT

{

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

protected:

	/// to access inherited path finder

	FORCEINLINE Tpf& Yapf() {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.GetLastTile(), old_node.GetLastTrackdir()))

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

	}

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

	FORCEINLINE char TransportTypeChar() const {return 't';}

	static bool stFindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)

	{

		Tpf pf;

		return pf.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, depot_tile, reversed);

	}

	FORCEINLINE bool FindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)

	{

		// set origin and destination nodes

		Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, true);

		Yapf().SetDestination(v);

		Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance);

		// find the best path

		bool bFound = Yapf().FindPath(v);

		if (!bFound) return false;

		// some path found

		// get found depot tile

		// walk through the path back to the origin

		while (pNode->m_parent != NULL) {

			pNode = pNode->m_parent;

		}

		// if the origin node is our front vehicle tile/Trackdir then we didn't reverse

		// but we can also look at the cost (== 0 -> not reversed, == reverse_penalty -> reversed)

		*reversed = (pNode->m_cost != 0);

		return true;

	}

};

template <class Types>

class CYapfFollowRailT

{

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

protected:

	/// to access inherited path finder

	FORCEINLINE Tpf& Yapf() {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.GetLastTile(), old_node.GetLastTrackdir()))

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

	}

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

	FORCEINLINE char TransportTypeChar() const {return 't';}

	static Trackdir stChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found)

	{

		// create pathfinder instance

		Tpf pf;

		return pf.ChooseRailTrack(v, tile, enterdir, tracks, path_not_found);

	}

	FORCEINLINE Trackdir ChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found)

	{

		// set origin and destination nodes

		Yapf().SetOrigin(v->tile, GetVehicleTrackdir(v), INVALID_TILE, INVALID_TRACKDIR, 1, true);

		Yapf().SetDestination(v);

		// find the best path

		bool path_found = Yapf().FindPath(v);

		if (path_not_found != NULL) {

			// tell controller that the path was only 'guessed'

			// treat the path as found if stopped on the first two way signal(s)

			*path_not_found = !(path_found || Yapf().m_stopped_on_first_two_way_signal);

		}

		// if path not found - return INVALID_TRACKDIR

		Trackdir next_trackdir = INVALID_TRACKDIR;

		if (pNode != NULL) {

			// path was found or at least suggested

			// walk through the path back to the origin

			Node* pPrev = NULL;

			while (pNode->m_parent != NULL) {

				pPrev = pNode;

				pNode = pNode->m_parent;

			}

			// return trackdir from the best origin node (one of start nodes)

			Node& best_next_node = *pPrev;

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

			next_trackdir = best_next_node.GetTrackdir();

		}

		return next_trackdir;

	}

	static bool stCheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2)

	{

		Tpf pf;

		return pf.CheckReverseTrain(v, t1, td1, t2, td2);

	}

	FORCEINLINE bool CheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2)

	{

		// create pathfinder instance

		// set origin and destination nodes

		Yapf().SetOrigin(t1, td1, t2, td2, 1, false);

		Yapf().SetDestination(v);

		// find the best path

		bool bFound = Yapf().FindPath(v);

		if (!bFound) return false;

		// path was found

		// walk through the path back to the origin

		while (pNode->m_parent != NULL) {

			pNode = pNode->m_parent;

		}

		// check if it was reversed origin

		Node& best_org_node = *pNode;

		bool reversed = (best_org_node.m_cost != 0);

		return reversed;

	}

};

template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class TdestinationT, template <class Types> class TfollowT>

struct CYapfRail_TypesT

{

	typedef CYapfRail_TypesT<Tpf_, Ttrack_follower, Tnode_list, TdestinationT, TfollowT>  Types;

	typedef Tpf_                                Tpf;

	typedef Ttrack_follower                     TrackFollower;

	typedef Tnode_list                          NodeList;

	typedef CYapfBaseT<Types>                   PfBase;

	typedef TfollowT<Types>                     PfFollow;

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

	typedef TdestinationT<Types>                PfDestination;

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

	typedef CYapfCostRailT<Types>               PfCost;

};

struct CYapfRail1         : CYapfT<CYapfRail_TypesT<CYapfRail1        , CFollowTrackRail    , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};

struct CYapfRail2         : CYapfT<CYapfRail_TypesT<CYapfRail2        , CFollowTrackRail    , CRailNodeListExitDir , CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};

struct CYapfRail3         : CYapfT<CYapfRail_TypesT<CYapfRail3        , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};

struct CYapfAnyDepotRail1 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail    , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};

struct CYapfAnyDepotRail2 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRail    , CRailNodeListExitDir , CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};

struct CYapfAnyDepotRail3 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail3, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};

Trackdir YapfChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found)

{

	// default is YAPF type 2

	typedef Trackdir (*PfnChooseRailTrack)(Vehicle*, TileIndex, DiagDirection, TrackBits, bool*);

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;

	// check if non-default YAPF type needed

	if (_patches.forbid_90_deg)

		pfnChooseRailTrack = &CYapfRail3::stChooseRailTrack; // Trackdir, forbid 90-deg

	else if (_patches.yapf.disable_node_optimization)

		pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack; // Trackdir, allow 90-deg

	/** 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_segment_last_tile, old_node.m_segment_last_td))

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

	}

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

	FORCEINLINE char TransportTypeChar() const {return 'r';}

	static Trackdir stChooseRoadTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir)

	{

		Tpf pf;

		return pf.ChooseRoadTrack(v, tile, enterdir);

	}

	FORCEINLINE Trackdir ChooseRoadTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir)

	{

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

		if (tile == v->dest_tile) {

			// choose diagonal trackdir reachable from enterdir

			return (Trackdir)DiagdirToDiagTrackdir(enterdir);

		}

		// our source tile will be the next vehicle tile (should be the given one)

		TileIndex src_tile = tile;

		// get available trackdirs on the start tile

		uint ts = GetTileTrackStatus(tile, TRANSPORT_ROAD);

		TrackdirBits src_trackdirs = (TrackdirBits)(ts & TRACKDIR_BIT_MASK);

		// select reachable trackdirs only

		src_trackdirs &= DiagdirReachesTrackdirs(enterdir);

		// get available trackdirs on the destination tile

		TileIndex dest_tile = v->dest_tile;

		uint dest_ts = GetTileTrackStatus(dest_tile, TRANSPORT_ROAD);

		TrackdirBits dest_trackdirs = (TrackdirBits)(dest_ts & TRACKDIR_BIT_MASK);

		// set origin and destination nodes

		Yapf().SetOrigin(src_tile, src_trackdirs);

		Yapf().SetDestination(dest_tile, dest_trackdirs);

		// find the best path

		Yapf().FindPath(v);

		// if path not found - return INVALID_TRACKDIR

		Trackdir next_trackdir = INVALID_TRACKDIR;

		if (pNode != NULL) {

			// path was found or at least suggested

			// walk through the path back to its origin

			while (pNode->m_parent != NULL) {

				pNode = pNode->m_parent;

			}

			// return trackdir from the best origin node (one of start nodes)

			Node& best_next_node = *pNode;

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

			next_trackdir = best_next_node.GetTrackdir();

		}

		return next_trackdir;

	}

	static uint stDistanceToTile(const Vehicle *v, TileIndex tile)

	{

		Tpf pf;

		return pf.DistanceToTile(v, tile);

	}

	FORCEINLINE uint DistanceToTile(const Vehicle *v, TileIndex dst_tile)

	{

		// handle special case - when current tile is the destination tile

		if (dst_tile == v->tile) {

			// distance is zero in this case

			return 0;

		}

		if (!SetOriginFromVehiclePos(v)) return UINT_MAX;

		// set destination tile, trackdir

		//   get available trackdirs on the destination tile

		uint dest_ts = GetTileTrackStatus(dst_tile, TRANSPORT_ROAD);

		TrackdirBits dst_td_bits = (TrackdirBits)(dest_ts & TRACKDIR_BIT_MASK);

		Yapf().SetDestination(dst_tile, dst_td_bits);

		// find the best path

		Yapf().FindPath(v);

		// if path not found - return distance = UINT_MAX

		uint dist = UINT_MAX;

		if (pNode != NULL) {

			// path was found or at least suggested

			// get the path cost estimate

			dist = pNode->GetCostEstimate();

		}

		return dist;

	}

	/** Return true if the valid origin (tile/trackdir) was set from the current vehicle position. */

	FORCEINLINE bool SetOriginFromVehiclePos(const Vehicle *v)

	{

		// set origin (tile, trackdir)

		TileIndex src_tile = v->tile;

		Trackdir src_td = GetVehicleTrackdir(v);

		if ((GetTileTrackStatus(src_tile, TRANSPORT_ROAD) & TrackdirToTrackdirBits(src_td)) == 0) {

			// sometimes the roadveh is not on the road (it resides on non-existing track)

			// how should we handle that situation?

			return false;

		}

		Yapf().SetOrigin(src_tile, TrackdirToTrackdirBits(src_td));

		return true;

	}

	static Depot* stFindNearestDepot(const Vehicle* v, TileIndex tile, Trackdir td)

	{

		Tpf pf;

		return pf.FindNearestDepot(v, tile, td);

	}

	FORCEINLINE Depot* FindNearestDepot(const Vehicle* v, TileIndex tile, Trackdir td)

	{

		// set origin and destination nodes

		Yapf().SetOrigin(tile, TrackdirToTrackdirBits(td));

		// find the best path

		bool bFound = Yapf().FindPath(v);

		if (!bFound) return false;

		// some path found

		// get found depot tile

		assert(IsTileDepotType(depot_tile, TRANSPORT_ROAD));

		Depot* ret = GetDepotByTile(depot_tile);

		return ret;

	}

};

template <class Tpf_, class Tnode_list, template <class Types> class Tdestination>

struct CYapfRoad_TypesT

{

	typedef CYapfRoad_TypesT<Tpf_, Tnode_list, Tdestination>  Types;

	typedef Tpf_                              Tpf;

	typedef CFollowTrackRoad                  TrackFollower;

	typedef Tnode_list                        NodeList;

	typedef CYapfBaseT<Types>                 PfBase;

	typedef CYapfFollowRoadT<Types>           PfFollow;

	typedef CYapfOriginTileT<Types>           PfOrigin;

	typedef Tdestination<Types>               PfDestination;

	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;

	typedef CYapfCostRoadT<Types>             PfCost;

};

struct CYapfRoad1         : CYapfT<CYapfRoad_TypesT<CYapfRoad1        , CRoadNodeListTrackDir, CYapfDestinationTileRoadT    > > {};

struct CYapfRoad2         : CYapfT<CYapfRoad_TypesT<CYapfRoad2        , CRoadNodeListExitDir , CYapfDestinationTileRoadT    > > {};

struct CYapfRoadAnyDepot1 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};

struct CYapfRoadAnyDepot2 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};

Trackdir YapfChooseRoadTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir)

{

	// default is YAPF type 2

	typedef Trackdir (*PfnChooseRoadTrack)(Vehicle*, TileIndex, DiagDirection);

	PfnChooseRoadTrack pfnChooseRoadTrack = &CYapfRoad2::stChooseRoadTrack; // default: ExitDir, allow 90-deg

	// check if non-default YAPF type should be used

	if (_patches.yapf.disable_node_optimization)

		pfnChooseRoadTrack = &CYapfRoad1::stChooseRoadTrack; // Trackdir, allow 90-deg

	Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir);

	return td_ret;

}

uint YapfRoadVehDistanceToTile(const Vehicle* v, TileIndex tile)

{

	// default is YAPF type 2

	typedef uint (*PfnDistanceToTile)(const Vehicle*, TileIndex);

	PfnDistanceToTile pfnDistanceToTile = &CYapfRoad2::stDistanceToTile; // default: ExitDir, allow 90-deg

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;

		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';}

	static Trackdir ChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)

	{

		// 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 = GetVehicleTrackdir(v);

		assert(IsValidTrackdir(trackdir));

		// convert origin trackdir to TrackdirBits

		TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);

		// get available trackdirs on the destination tile

		TrackdirBits dest_trackdirs = (TrackdirBits)(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER) & TRACKDIR_BIT_MASK);

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

		bool bFound = pf.FindPath(v);

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

		if (bFound) {

			// path was found

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

{

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

protected:

	/// to access inherited path finder

	Tpf& Yapf() {return *static_cast<Tpf*>(this);}

public:

	/** Called by YAPF to calculate the cost from the origin to the given node.

	 *  Calculates only the cost of given node, adds it to the parent node cost

	 *  and stores the result into Node::m_cost member */

	FORCEINLINE bool PfCalcCost(Node& n, const TrackFollower &tf)

	{

		// base tile cost depending on distance

		int c = IsDiagonalTrackdir(n.GetTrackdir()) ? 10 : 7;

		// additional penalty for curves

		if (n.m_parent != NULL && n.GetTrackdir() != n.m_parent->GetTrackdir()) c += 3;

		// apply it

		n.m_cost = n.m_parent->m_cost + c;

		return true;

	}

};

/** Config struct of YAPF for ships.

 *  Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.

 */

template <class Tpf_, class Ttrack_follower, class Tnode_list>