1 /* $Id$ */

     2 

     3 #include "../stdafx.h"

     4 

     5 #include "yapf.hpp"

     6 #include "yapf_node_road.hpp"

     7 

     8 

     9 template <class Types>

    10 class CYapfCostRoadT

    11 {

    12 public:

    13 	typedef typename Types::Tpf Tpf;

    14 	typedef typename Types::TrackFollower TrackFollower;

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

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

    17 

    18 protected:

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

    20 

    21 	int SlopeCost(TileIndex tile, TileIndex next_tile, Trackdir trackdir)

    22 	{

    23 		// height of the center of the current tile

    24 		int x1 = TileX(tile) * TILE_SIZE;

    25 		int y1 = TileY(tile) * TILE_SIZE;

    26 		int z1 = GetSlopeZ(x1 + TILE_HEIGHT, y1 + TILE_HEIGHT);

    27 

    28 		// height of the center of the next tile

    29 		int x2 = TileX(next_tile) * TILE_SIZE;

    30 		int y2 = TileY(next_tile) * TILE_SIZE;

    31 		int z2 = GetSlopeZ(x2 + TILE_HEIGHT, y2 + TILE_HEIGHT);

    32 

    33 		if (z2 - z1 > 1) {

    34 			/* Slope up */

    35 			return Yapf().PfGetSettings().rail_slope_penalty;

    36 		}

    37 		return 0;

    38 	}

    39 

    40 	/** return one tile cost */

    41 	FORCEINLINE int OneTileCost(TileIndex tile, Trackdir trackdir)

    42 	{

    43 		int cost = 0;

    44 		// set base cost

    45 		if (IsDiagonalTrackdir(trackdir)) {

    46 			cost += 10;

    47 			switch (GetTileType(tile)) {

    48 				case MP_STREET:

    49 					/* Increase the cost for level crossings */

    50 					if (IsLevelCrossing(tile))

    51 						cost += Yapf().PfGetSettings().rail_crossing_penalty;

    52 					break;

    53 

    54 				default:

    55 					break;

    56 			}

    57 		} else {

    58 			// non-diagonal trackdir

    59 			cost = 7;

    60 		}

    61 		return cost;

    62 	}

    63 

    64 public:

    65 	FORCEINLINE bool PfCalcCost(Node& n)

    66 	{

    67 		int segment_cost = 0;

    68 		// start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment

    69 		TileIndex tile = n.m_key.m_tile;

    70 		Trackdir trackdir = n.m_key.m_td;

    71 		while (true) {

    72 			// base tile cost depending on distance between edges

    73 			segment_cost += Yapf().OneTileCost(tile, trackdir);

    74 

    75 			// if there are no reachable trackdirs n new tile, we have end of road

    76 			TrackFollower F;

    77 			if (!F.Follow(tile, trackdir)) break;

    78 

    79 			// if there are more trackdirs available & reachable, we are at the end of segment

    80 			if (KillFirstBit2x64(F.m_new_td_bits) != 0) break;

    81 

    82 			Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits);

    83 

    84 			// stop if RV is on simple loop with no junctions

    85 			if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) return false;

    86 

    87 			// if we skipped some tunnel tiles, add their cost

    88 			segment_cost += 10 * F.m_tunnel_tiles_skipped;

    89 

    90 			// add hilly terrain penalty

    91 			segment_cost += Yapf().SlopeCost(tile, F.m_new_tile, trackdir);

    92 

    93 			// add min/max speed penalties

    94 			int min_speed = 0;

    95 			int max_speed = F.GetSpeedLimit(&min_speed);

    96 			Vehicle* v = Yapf().GetVehicle();

    97 			if (max_speed < v->max_speed) segment_cost += 1 * (v->max_speed - max_speed);

    98 			if (min_speed > v->max_speed) segment_cost += 10 * (min_speed - v->max_speed);

    99 

   100 			// move to the next tile

   101 			tile = F.m_new_tile;

   102 			trackdir = new_td;

   103 		};

   104 

   105 		// save end of segment back to the node

   106 		n.m_segment_last_tile = tile;

   107 		n.m_segment_last_td = trackdir;

   108 

   109 		// save also tile cost

   110 		int parent_cost = (n.m_parent != NULL) ? n.m_parent->m_cost : 0;

   111 		n.m_cost = parent_cost + segment_cost;

   112 		return true;

   113 	}

   114 };

   115 

   116 

   117 template <class Types>

   118 class CYapfDestinationAnyDepotRoadT

   119 {

   120 public:

   121 	typedef typename Types::Tpf Tpf;

   122 	typedef typename Types::TrackFollower TrackFollower;

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

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

   125 

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

   127 

   128 	FORCEINLINE bool PfDetectDestination(Node& n)

   129 	{

   130 		bool bDest = IsTileDepotType(n.m_segment_last_tile, TRANSPORT_ROAD);

   131 		return bDest;

   132 	}

   133 

   134 	FORCEINLINE bool PfCalcEstimate(Node& n)

   135 	{

   136 		n.m_estimate = n.m_cost;

   137 		return true;

   138 	}

   139 };

   140 

   141 

   142 template <class Types>

   143 class CYapfDestinationTileRoadT

   144 {

   145 public:

   146 	typedef typename Types::Tpf Tpf;

   147 	typedef typename Types::TrackFollower TrackFollower;

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

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

   150 

   151 protected:

   152 	TileIndex    m_destTile;

   153 	TrackdirBits m_destTrackdirs;

   154 

   155 public:

   156 	void SetDestination(TileIndex tile, TrackdirBits trackdirs)

   157 	{

   158 		m_destTile = tile;

   159 		m_destTrackdirs = trackdirs;

   160 	}

   161 

   162 protected:

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

   164 

   165 public:

   166 	FORCEINLINE bool PfDetectDestination(Node& n)

   167 	{

   168 		bool bDest = (n.m_segment_last_tile == m_destTile) && ((m_destTrackdirs & TrackdirToTrackdirBits(n.m_segment_last_td)) != TRACKDIR_BIT_NONE);

   169 		return bDest;

   170 	}

   171 

   172 	inline bool PfCalcEstimate(Node& n)

   173 	{

   174 		static int dg_dir_to_x_offs[] = {-1, 0, 1, 0};

   175 		static int dg_dir_to_y_offs[] = {0, 1, 0, -1};

   176 		if (PfDetectDestination(n)) {

   177 			n.m_estimate = n.m_cost;

   178 			return true;

   179 		}

   180 

   181 		TileIndex tile = n.m_segment_last_tile;

   182 		DiagDirection exitdir = TrackdirToExitdir(n.m_segment_last_td);

   183 		int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];

   184 		int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];

   185 		int x2 = 2 * TileX(m_destTile);

   186 		int y2 = 2 * TileY(m_destTile);

   187 		int dx = abs(x1 - x2);

   188 		int dy = abs(y1 - y2);

   189 		int dmin = min(dx, dy);

   190 		int dxy = abs(dx - dy);

   191 		int d = dmin * 7 + (dxy - 1) * 5;

   192 		n.m_estimate = n.m_cost + d;

   193 		assert(n.m_estimate >= n.m_parent->m_estimate);

   194 		return true;

   195 	}

   196 };

   197 

   198 

   199 

   200 template <class Types>

   201 class CYapfFollowRoadT

   202 {

   203 public:

   204 	typedef typename Types::Tpf Tpf;

   205 	typedef typename Types::TrackFollower TrackFollower;

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

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

   208 

   209 protected:

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

   211 

   212 public:

   213 

   214 	inline void PfFollowNode(Node& old_node)

   215 	{

   216 		TrackFollower F;

   217 		if (F.Follow(old_node.m_segment_last_tile, old_node.m_segment_last_td))

   218 			Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits);

   219 	}

   220 

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

   222 

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

   224 	{

   225 		Tpf pf;

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

   227 	}

   228 

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

   230 	{

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

   232 		if (tile == v->dest_tile) {

   233 			// choose diagonal trackdir reachable from enterdir

   234 			return (Trackdir)DiagdirToDiagTrackdir(enterdir);

   235 		}

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

   237 		TileIndex src_tile = tile;

   238 		// get available trackdirs on the start tile

   239 		uint ts = GetTileTrackStatus(tile, TRANSPORT_ROAD);

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

   241 		// select reachable trackdirs only

   242 		src_trackdirs &= DiagdirReachesTrackdirs(enterdir);

   243 

   244 		// get available trackdirs on the destination tile

   245 		TileIndex dest_tile = v->dest_tile;

   246 		uint dest_ts = GetTileTrackStatus(dest_tile, TRANSPORT_ROAD);

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

   248 

   249 		// set origin and destination nodes

   250 		Yapf().SetOrigin(src_tile, src_trackdirs);

   251 		Yapf().SetDestination(dest_tile, dest_trackdirs);

   252 

   253 		// find the best path

   254 		Yapf().FindPath(v);

   255 

   256 		// if path not found - return INVALID_TRACKDIR

   257 		Trackdir next_trackdir = INVALID_TRACKDIR;

   258 		Node* pNode = &Yapf().GetBestNode();

   259 		if (pNode != NULL) {

   260 			// path was found or at least suggested

   261 			// walk through the path back to its origin

   262 			while (pNode->m_parent != NULL) {

   263 				pNode = pNode->m_parent;

   264 			}

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

   266 			Node& best_next_node = *pNode;

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

   268 			next_trackdir = best_next_node.GetTrackdir();

   269 		}

   270 		return next_trackdir;

   271 	}

   272 

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

   274 	{

   275 		Tpf pf;

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

   277 	}

   278 

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

   280 	{

   281 		// set origin and destination nodes

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

   283 

   284 		// find the best path

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

   286 		if (!bFound) return false;

   287 

   288 		// some path found

   289 		// get found depot tile

   290 		Node& n = Yapf().GetBestNode();

   291 		TileIndex depot_tile = n.m_segment_last_tile;

   292 		assert(IsTileDepotType(depot_tile, TRANSPORT_ROAD));

   293 		Depot* ret = GetDepotByTile(depot_tile);

   294 		return ret;

   295 	}

   296 };

   297 

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

   299 struct CYapfRoad_TypesT

   300 {

   301 	typedef CYapfRoad_TypesT<Tpf_, Tnode_list, Tdestination>  Types;

   302 

   303 	typedef Tpf_                              Tpf;

   304 	typedef CFollowTrackRoad                  TrackFollower;

   305 	typedef Tnode_list                        NodeList;

   306 	typedef CYapfBaseT<Types>                 PfBase;

   307 	typedef CYapfFollowRoadT<Types>           PfFollow;

   308 	typedef CYapfOriginTileT<Types>           PfOrigin;

   309 	typedef Tdestination<Types>               PfDestination;

   310 	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;

   311 	typedef CYapfCostRoadT<Types>             PfCost;

   312 };

   313 

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

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

   316 

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

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

   319 

   320 

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

   322 {

   323 	// default is YAPF type 2

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

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

   326 

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

   328 	if (_patches.yapf.disable_node_optimization)

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

   330 

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

   332 	return td_ret;

   333 }

   334 

   335 Depot* YapfFindNearestRoadDepot(const Vehicle *v)

   336 {

   337 	TileIndex tile = v->tile;

   338 	if (v->u.road.state == 255) tile = GetVehicleOutOfTunnelTile(v);

   339 	Trackdir trackdir = GetVehicleTrackdir(v);

   340 	if ((GetTileTrackStatus(tile, TRANSPORT_ROAD) & TrackdirToTrackdirBits(trackdir)) == 0)

   341 		return NULL;

   342 

   343 	// default is YAPF type 2

   344 	typedef Depot* (*PfnFindNearestDepot)(Vehicle*, TileIndex, Trackdir);

   345 	PfnFindNearestDepot pfnFindNearestDepot = &CYapfRoadAnyDepot2::stFindNearestDepot;

   346 

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

   348 	if (_patches.yapf.disable_node_optimization)

   349 		pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot; // Trackdir, allow 90-deg

   350 

   351 	Depot* ret = pfnFindNearestDepot(const_cast<Vehicle*>(v), tile, trackdir);

   352 	return ret;

   353 }