KUDr@3900: /* $Id$ */
KUDr@3900: 
KUDr@3900: #include "../stdafx.h"
KUDr@3900: 
KUDr@3900: #include "yapf.hpp"
KUDr@3900: #include "yapf_node_rail.hpp"
KUDr@3900: #include "yapf_costrail.hpp"
KUDr@3900: #include "yapf_destrail.hpp"
KUDr@3900: 
KUDr@3900: int _total_pf_time_us = 0;
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 
KUDr@3900: template <class Types>
KUDr@3900: class CYapfFollowAnyDepotRailT
KUDr@3900: {
KUDr@3900: public:
KUDr@3914: 	typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
KUDr@3900: 	typedef typename Types::TrackFollower TrackFollower;
KUDr@3914: 	typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
KUDr@3914: 	typedef typename Node::Key Key;                      ///< key to hash tables
KUDr@3900: 
KUDr@3900: protected:
KUDr@3914: 	/// to access inherited path finder
KUDr@3900: 	FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
KUDr@3900: 
KUDr@3900: public:
KUDr@3914: 	/** Called by YAPF to move from the given node to the next tile. For each
rubidium@4549: 	 *  reachable trackdir on the new tile creates new node, initializes it
rubidium@4549: 	 *  and adds it to the open list by calling Yapf().AddNewNode(n) */
KUDr@3900: 	inline void PfFollowNode(Node& old_node)
KUDr@3900: 	{
KUDr@3900: 		TrackFollower F(Yapf().GetVehicle());
KUDr@3900: 		if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()))
KUDr@3900: 			Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits);
KUDr@3900: 	}
KUDr@3900: 
KUDr@3914: 	/// return debug report character to identify the transportation type
KUDr@3900: 	FORCEINLINE char TransportTypeChar() const {return 't';}
KUDr@3900: 
KUDr@3900: 	static bool stFindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)
KUDr@3900: 	{
KUDr@3900: 		Tpf pf;
KUDr@3900: 		return pf.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, depot_tile, reversed);
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	FORCEINLINE bool FindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)
KUDr@3900: 	{
KUDr@3900: 		// set origin and destination nodes
KUDr@3900: 		Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, true);
KUDr@3900: 		Yapf().SetDestination(v);
KUDr@3923: 		Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance);
KUDr@3900: 
KUDr@3900: 		// find the best path
KUDr@3900: 		bool bFound = Yapf().FindPath(v);
KUDr@3900: 		if (!bFound) return false;
KUDr@3900: 
KUDr@3900: 		// some path found
KUDr@3900: 		// get found depot tile
KUDr@3900: 		Node& n = Yapf().GetBestNode();
KUDr@3900: 		*depot_tile = n.GetLastTile();
KUDr@3900: 
KUDr@3900: 		// walk through the path back to the origin
KUDr@3900: 		Node* pNode = &n;
KUDr@3900: 		while (pNode->m_parent != NULL) {
KUDr@3900: 			pNode = pNode->m_parent;
KUDr@3900: 		}
KUDr@3900: 
KUDr@3900: 		// if the origin node is our front vehicle tile/Trackdir then we didn't reverse
KUDr@3900: 		// but we can also look at the cost (== 0 -> not reversed, == reverse_penalty -> reversed)
KUDr@3900: 		*reversed = (pNode->m_cost != 0);
KUDr@3900: 
KUDr@3900: 		return true;
KUDr@3900: 	}
KUDr@3900: };
KUDr@3900: 
KUDr@3900: template <class Types>
KUDr@3900: class CYapfFollowRailT
KUDr@3900: {
KUDr@3900: public:
KUDr@3914: 	typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
KUDr@3900: 	typedef typename Types::TrackFollower TrackFollower;
KUDr@3914: 	typedef typename Types::NodeList::Titem Node;        ///< this will be our node type
KUDr@3914: 	typedef typename Node::Key Key;                      ///< key to hash tables
KUDr@3900: 
KUDr@3900: protected:
KUDr@3914: 	/// to access inherited path finder
KUDr@3900: 	FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
KUDr@3900: 
KUDr@3900: public:
KUDr@3914: 	/** Called by YAPF to move from the given node to the next tile. For each
rubidium@4549: 	 *  reachable trackdir on the new tile creates new node, initializes it
rubidium@4549: 	 *  and adds it to the open list by calling Yapf().AddNewNode(n) */
KUDr@3900: 	inline void PfFollowNode(Node& old_node)
KUDr@3900: 	{
KUDr@3900: 		TrackFollower F(Yapf().GetVehicle());
KUDr@3900: 		if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()))
KUDr@3900: 			Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits);
KUDr@3900: 	}
KUDr@3900: 
KUDr@3914: 	/// return debug report character to identify the transportation type
KUDr@3900: 	FORCEINLINE char TransportTypeChar() const {return 't';}
KUDr@3900: 
KUDr@4870: 	static Trackdir stChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found)
KUDr@3900: 	{
KUDr@3900: 		// create pathfinder instance
KUDr@3900: 		Tpf pf;
KUDr@4870: 		return pf.ChooseRailTrack(v, tile, enterdir, trackdirs, path_not_found);
KUDr@3900: 	}
KUDr@3900: 
KUDr@4870: 	FORCEINLINE Trackdir ChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found)
KUDr@3900: 	{
KUDr@3900: 		// set origin and destination nodes
KUDr@3900: 		Yapf().SetOrigin(v->tile, GetVehicleTrackdir(v), INVALID_TILE, INVALID_TRACKDIR, 1, true);
KUDr@3900: 		Yapf().SetDestination(v);
KUDr@3900: 
KUDr@3900: 		// find the best path
KUDr@4870: 		bool path_found = Yapf().FindPath(v);
KUDr@4870: 		if (!path_found && path_not_found != NULL) {
KUDr@4870: 			// tell controller that the path was only 'guessed'
KUDr@4870: 			*path_not_found = !path_found;
KUDr@4870: 		}
KUDr@3900: 
KUDr@3900: 		// if path not found - return INVALID_TRACKDIR
KUDr@3900: 		Trackdir next_trackdir = INVALID_TRACKDIR;
KUDr@3900: 		Node* pNode = &Yapf().GetBestNode();
KUDr@3900: 		if (pNode != NULL) {
KUDr@3900: 			// path was found or at least suggested
KUDr@3900: 			// walk through the path back to the origin
KUDr@3900: 			Node* pPrev = NULL;
KUDr@3900: 			while (pNode->m_parent != NULL) {
KUDr@3900: 				pPrev = pNode;
KUDr@3900: 				pNode = pNode->m_parent;
KUDr@3900: 			}
KUDr@3900: 			// return trackdir from the best origin node (one of start nodes)
KUDr@3900: 			Node& best_next_node = *pPrev;
KUDr@3900: 			assert(best_next_node.GetTile() == tile);
KUDr@3900: 			next_trackdir = best_next_node.GetTrackdir();
KUDr@3900: 		}
KUDr@3900: 		return next_trackdir;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	static bool stCheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2)
KUDr@3900: 	{
KUDr@3900: 		Tpf pf;
KUDr@3900: 		return pf.CheckReverseTrain(v, t1, td1, t2, td2);
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	FORCEINLINE bool CheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2)
KUDr@3900: 	{
KUDr@3900: 		// create pathfinder instance
KUDr@3900: 		// set origin and destination nodes
KUDr@3900: 		Yapf().SetOrigin(t1, td1, t2, td2, 1, false);
KUDr@3900: 		Yapf().SetDestination(v);
KUDr@3900: 
KUDr@3900: 		// find the best path
KUDr@3900: 		bool bFound = Yapf().FindPath(v);
KUDr@3900: 
KUDr@3900: 		if (!bFound) return false;
KUDr@3900: 
KUDr@3900: 		// path was found
KUDr@3900: 		// walk through the path back to the origin
KUDr@3900: 		Node* pNode = &Yapf().GetBestNode();
KUDr@3900: 		while (pNode->m_parent != NULL) {
KUDr@3900: 			pNode = pNode->m_parent;
KUDr@3900: 		}
KUDr@3900: 
KUDr@3900: 		// check if it was reversed origin
KUDr@3900: 		Node& best_org_node = *pNode;
KUDr@3900: 		bool reversed = (best_org_node.m_cost != 0);
KUDr@3900: 		return reversed;
KUDr@3900: 	}
KUDr@3900: };
KUDr@3900: 
KUDr@3900: template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class TdestinationT, template <class Types> class TfollowT>
KUDr@3900: struct CYapfRail_TypesT
KUDr@3900: {
KUDr@3900: 	typedef CYapfRail_TypesT<Tpf_, Ttrack_follower, Tnode_list, TdestinationT, TfollowT>  Types;
KUDr@3900: 
KUDr@3900: 	typedef Tpf_                                Tpf;
KUDr@3900: 	typedef Ttrack_follower                     TrackFollower;
KUDr@3900: 	typedef Tnode_list                          NodeList;
KUDr@3900: 	typedef CYapfBaseT<Types>                   PfBase;
KUDr@3900: 	typedef TfollowT<Types>                     PfFollow;
KUDr@3900: 	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;
KUDr@3900: 	typedef TdestinationT<Types>                PfDestination;
KUDr@3900: 	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;
KUDr@3900: 	typedef CYapfCostRailT<Types>               PfCost;
KUDr@3900: };
KUDr@3900: 
KUDr@3900: struct CYapfRail1         : CYapfT<CYapfRail_TypesT<CYapfRail1        , CFollowTrackRail    , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
KUDr@3900: struct CYapfRail2         : CYapfT<CYapfRail_TypesT<CYapfRail2        , CFollowTrackRail    , CRailNodeListExitDir , CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
KUDr@3900: struct CYapfRail3         : CYapfT<CYapfRail_TypesT<CYapfRail3        , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
KUDr@3900: 
KUDr@3900: struct CYapfAnyDepotRail1 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail    , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};
KUDr@3900: struct CYapfAnyDepotRail2 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRail    , CRailNodeListExitDir , CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};
KUDr@3900: struct CYapfAnyDepotRail3 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail3, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};
KUDr@3900: 
KUDr@3900: 
KUDr@4870: Trackdir YapfChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found)
KUDr@3900: {
KUDr@3900: 	// default is YAPF type 2
KUDr@4870: 	typedef Trackdir (*PfnChooseRailTrack)(Vehicle*, TileIndex, DiagDirection, TrackdirBits, bool*);
KUDr@3900: 	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;
KUDr@3900: 
KUDr@3900: 	// check if non-default YAPF type needed
KUDr@3900: 	if (_patches.forbid_90_deg)
KUDr@3900: 		pfnChooseRailTrack = &CYapfRail3::stChooseRailTrack; // Trackdir, forbid 90-deg
KUDr@3900: 	else if (_patches.yapf.disable_node_optimization)
KUDr@3900: 		pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack; // Trackdir, allow 90-deg
KUDr@3900: 
KUDr@4870: 	Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, trackdirs, path_not_found);
KUDr@3900: 
KUDr@3900: 	return td_ret;
KUDr@3900: }
KUDr@3900: 
KUDr@3900: bool YapfCheckReverseTrain(Vehicle* v)
KUDr@3900: {
KUDr@3900: 	// tile where the engine is
KUDr@3900: 	TileIndex tile = v->tile;
KUDr@3900: 	// tile where we have last wagon
KUDr@3900: 	Vehicle* last_veh = GetLastVehicleInChain(v);
KUDr@3900: 	// if we are in tunnel then give up
KUDr@3900: 	if (v->u.rail.track == 0x40 || last_veh->u.rail.track == 0x40) return false;
KUDr@3900: 	// get trackdirs of both ends
KUDr@3900: 	Trackdir td = GetVehicleTrackdir(v);
KUDr@3900: 	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 	typedef bool (*PfnCheckReverseTrain)(Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir);
KUDr@3900: 	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain;
KUDr@3900: 
KUDr@3900: 	// check if non-default YAPF type needed
KUDr@3900: 	if (_patches.forbid_90_deg)
KUDr@3900: 		pfnCheckReverseTrain = &CYapfRail3::stCheckReverseTrain; // Trackdir, forbid 90-deg
KUDr@3900: 	else if (_patches.yapf.disable_node_optimization)
KUDr@3900: 		pfnCheckReverseTrain = &CYapfRail1::stCheckReverseTrain; // Trackdir, allow 90-deg
KUDr@3900: 
KUDr@3900: 	bool reverse = pfnCheckReverseTrain(v, tile, td, last_veh->tile, td_rev);
KUDr@3900: 
KUDr@3900: 	return reverse;
KUDr@3900: }
KUDr@3900: 
KUDr@3900: bool YapfFindNearestRailDepotTwoWay(Vehicle *v, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)
KUDr@3900: {
KUDr@3900: 	*depot_tile = INVALID_TILE;
KUDr@3900: 	*reversed = false;
KUDr@3900: 
KUDr@3900: 	Vehicle* last_veh = GetLastVehicleInChain(v);
KUDr@3900: 
celestar@5573: 	TileIndex tile = v->tile;
celestar@5573: 	TileIndex last_tile = last_veh->tile;
KUDr@3900: 
KUDr@3900: 	// their trackdirs
KUDr@4865: 	Trackdir td = GetVehicleTrackdir(v);
KUDr@4865: 	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));
KUDr@3900: 
KUDr@3900: 	typedef bool (*PfnFindNearestDepotTwoWay)(Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir, int, int, TileIndex*, bool*);
KUDr@3900: 	PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;
KUDr@3900: 
KUDr@3900: 	// check if non-default YAPF type needed
KUDr@3900: 	if (_patches.forbid_90_deg)
KUDr@3900: 		pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail3::stFindNearestDepotTwoWay; // Trackdir, forbid 90-deg
KUDr@3900: 	else if (_patches.yapf.disable_node_optimization)
KUDr@3900: 		pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay; // Trackdir, allow 90-deg
KUDr@3900: 
KUDr@3900: 	bool ret = pfnFindNearestDepotTwoWay(v, tile, td, last_tile, td_rev, max_distance, reverse_penalty, depot_tile, reversed);
KUDr@3900: 	return ret;
KUDr@3900: }
KUDr@3900: 
KUDr@3910: /** if any track changes, this counter is incremented - that will invalidate segment cost cache */
KUDr@3900: int CSegmentCostCacheBase::s_rail_change_counter = 0;
KUDr@3900: 
KUDr@3900: void YapfNotifyTrackLayoutChange(TileIndex tile, Track track) {CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);}