KUDr@3900: /* $Id$ */
KUDr@3900: 
KUDr@3900: #include "../stdafx.h"
KUDr@3900: 
KUDr@3900: #include "yapf.hpp"
KUDr@3900: 
KUDr@3900: /** Node Follower module of YAPF for ships */
KUDr@3900: template <class Types>
KUDr@3900: class CYapfFollowShipT
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;
KUDr@3900: 		if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td))
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 'w';}
KUDr@3900: 
KUDr@3900: 	static Trackdir ChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
KUDr@3900: 	{
KUDr@3900: 		// handle special case - when next tile is destination tile
KUDr@3900: 		if (tile == v->dest_tile) {
KUDr@3900: 			// convert tracks to trackdirs
KUDr@3900: 			TrackdirBits trackdirs = (TrackdirBits)(tracks | ((int)tracks << 8));
KUDr@3900: 			// choose any trackdir reachable from enterdir
KUDr@3900: 			trackdirs &= DiagdirReachesTrackdirs(enterdir);
KUDr@3900: 			return (Trackdir)FindFirstBit2x64(trackdirs);
KUDr@3900: 		}
KUDr@3900: 
KUDr@3900: 		// move back to the old tile/trackdir (where ship is coming from)
Darkvater@4559: 		TileIndex src_tile = TILE_ADD(tile, TileOffsByDiagDir(ReverseDiagDir(enterdir)));
KUDr@3900: 		Trackdir trackdir = GetVehicleTrackdir(v);
KUDr@3900: 		assert(IsValidTrackdir(trackdir));
KUDr@3900: 
KUDr@3900: 		// convert origin trackdir to TrackdirBits
KUDr@3900: 		TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);
KUDr@3900: 		// get available trackdirs on the destination tile
KUDr@3900: 		TrackdirBits dest_trackdirs = (TrackdirBits)(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER) & TRACKDIR_BIT_MASK);
KUDr@3900: 
KUDr@3900: 		// create pathfinder instance
KUDr@3900: 		Tpf pf;
KUDr@3900: 		// set origin and destination nodes
KUDr@3900: 		pf.SetOrigin(src_tile, trackdirs);
KUDr@3900: 		pf.SetDestination(v->dest_tile, dest_trackdirs);
KUDr@3900: 		// find best path
KUDr@3900: 		bool bFound = pf.FindPath(v);
KUDr@3900: 
KUDr@3900: 		Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"
KUDr@3900: 		if (bFound) {
KUDr@3900: 			// path was found
KUDr@3900: 			// walk through the path back to the origin
KUDr@3900: 			Node* pNode = &pf.GetBestNode();
KUDr@3900: 			Node* pPrevNode = NULL;
KUDr@3900: 			while (pNode->m_parent != NULL) {
KUDr@3900: 				pPrevNode = pNode;
KUDr@3900: 				pNode = pNode->m_parent;
KUDr@3900: 			}
KUDr@3900: 			// return trackdir from the best next node (direct child of origin)
KUDr@3900: 			Node& best_next_node = *pPrevNode;
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: 
KUDr@3900: /** Cost Provider module of YAPF for ships */
KUDr@3900: template <class Types>
KUDr@3900: class CYapfCostShipT
KUDr@3900: {
KUDr@3900: public:
KUDr@3914: 	typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
KUDr@3900: 	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: 	Tpf& Yapf() {return *static_cast<Tpf*>(this);}
KUDr@3900: 
KUDr@3900: public:
KUDr@3914: 	/** Called by YAPF to calculate the cost from the origin to the given node.
rubidium@4549: 	 *  Calculates only the cost of given node, adds it to the parent node cost
rubidium@4549: 	 *  and stores the result into Node::m_cost member */
KUDr@3900: 	FORCEINLINE bool PfCalcCost(Node& n)
KUDr@3900: 	{
KUDr@3900: 		// base tile cost depending on distance
KUDr@3900: 		int c = IsDiagonalTrackdir(n.GetTrackdir()) ? 10 : 7;
KUDr@3900: 		// additional penalty for curves
KUDr@3900: 		if (n.m_parent != NULL && n.GetTrackdir() != n.m_parent->GetTrackdir()) c += 3;
KUDr@3900: 		// apply it
KUDr@3900: 		n.m_cost = n.m_parent->m_cost + c;
KUDr@3900: 		return true;
KUDr@3900: 	}
KUDr@3900: };
KUDr@3900: 
KUDr@3900: /** Config struct of YAPF for ships.
rubidium@4549:  *  Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
rubidium@4549:  */
KUDr@3900: template <class Tpf_, class Ttrack_follower, class Tnode_list>
KUDr@3900: struct CYapfShip_TypesT
KUDr@3900: {
KUDr@3900: 	/** Types - shortcut for this struct type */
KUDr@3900: 	typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;
KUDr@3900: 
KUDr@3900: 	/** Tpf - pathfinder type */
KUDr@3900: 	typedef Tpf_                              Tpf;
KUDr@3900: 	/** track follower helper class */
KUDr@3900: 	typedef Ttrack_follower                   TrackFollower;
KUDr@3900: 	/** node list type */
KUDr@3900: 	typedef Tnode_list                        NodeList;
KUDr@3900: 	/** pathfinder components (modules) */
KUDr@3900: 	typedef CYapfBaseT<Types>                 PfBase;        // base pathfinder class
KUDr@3900: 	typedef CYapfFollowShipT<Types>           PfFollow;      // node follower
KUDr@3900: 	typedef CYapfOriginTileT<Types>           PfOrigin;      // origin provider
KUDr@3900: 	typedef CYapfDestinationTileT<Types>      PfDestination; // destination/distance provider
KUDr@3900: 	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;       // segment cost cache provider
KUDr@3900: 	typedef CYapfCostShipT<Types>             PfCost;        // cost provider
KUDr@3900: };
KUDr@3900: 
KUDr@3900: // YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns
KUDr@3900: struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};
KUDr@3900: // YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns
KUDr@3900: struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};
KUDr@3900: // YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns
KUDr@3900: struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
KUDr@3900: 
KUDr@3900: /** Ship controller helper - path finder invoker */
KUDr@3900: Trackdir YapfChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
KUDr@3900: {
KUDr@3900: 	// default is YAPF type 2
KUDr@3900: 	typedef Trackdir (*PfnChooseShipTrack)(Vehicle*, TileIndex, DiagDirection, TrackBits);
KUDr@3900: 	PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg
KUDr@3900: 
KUDr@3900: 	// check if non-default YAPF type needed
KUDr@3900: 	if (_patches.forbid_90_deg)
KUDr@3900: 		pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg
KUDr@3900: 	else if (_patches.yapf.disable_node_optimization)
KUDr@3900: 		pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg
KUDr@3900: 
KUDr@3900: 	Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks);
KUDr@3900: 	return td_ret;
KUDr@3900: }
KUDr@3900: 
KUDr@3900: /** performance measurement helper */
KUDr@3900: void* NpfBeginInterval()
KUDr@3900: {
KUDr@3900: 	CPerformanceTimer& perf = *new CPerformanceTimer;
KUDr@3900: 	perf.Start();
KUDr@3900: 	return &perf;
KUDr@3900: }
KUDr@3900: 
KUDr@3900: /** performance measurement helper */
KUDr@3900: int NpfEndInterval(void* vperf)
KUDr@3900: {
KUDr@3900: 	CPerformanceTimer& perf = *(CPerformanceTimer*)vperf;
KUDr@3900: 	perf.Stop();
KUDr@3900: 	int t = perf.Get(1000000);
KUDr@3900: 	delete &perf;
KUDr@3900: 	return t;
KUDr@3900: }