src/pathfinder/follow_track.hpp

   1 /* $Id$ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * 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.
   6  * 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.
   7  * 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/>.
   8  */
   9
  10 /** @file follow_track.hpp Template function for track followers */
  11
  12 #ifndef  FOLLOW_TRACK_HPP
  13 #define  FOLLOW_TRACK_HPP
  14
  15 #include "../map/road.h"
  16 #include "../pbs.h"
  17 #include "../roadveh.h"
  18 #include "../station_base.h"
  19 #include "../train.h"
  20 #include "../tunnelbridge.h"
  21 #include "../depot_func.h"
  22 #include "../bridge.h"
  23 #include "../ship.h"
  24 #include "pathfinder_type.h"
  25 #include "pf_performance_timer.hpp"
  26
  27 /**
  28  * Track follower common base class
  29  */
  30 struct CFollowTrackBase
  31 {
  32         enum TileFlag {
  33                 TF_NONE,
  34                 TF_STATION,
  35                 TF_TUNNEL,
  36                 TF_BRIDGE,
  37         };
  38
  39         enum ErrorCode {
  40                 EC_NONE,
  41                 EC_OWNER,
  42                 EC_RAIL_TYPE,
  43                 EC_90DEG,
  44                 EC_NO_WAY,
  45                 EC_RESERVED,
  46         };
  47
  48         enum TileResult {
  49                 TR_NORMAL,
  50                 TR_NO_WAY,
  51                 TR_REVERSE,
  52         };
  53
  54         PFPos               m_old;           ///< the origin (vehicle moved from) before move
  55         PFNewPos            m_new;           ///< the new tile (the vehicle has entered)
  56         DiagDirection       m_exitdir;       ///< exit direction (leaving the old tile)
  57         TileFlag            m_flag;          ///< last turn passed station, tunnel or bridge
  58         int                 m_tiles_skipped; ///< number of skipped tunnel or station tiles
  59         ErrorCode           m_err;
  60 };
  61
  62
  63 /**
  64  * Track follower rail base class
  65  */
  66 struct CFollowTrackRailBase : CFollowTrackBase
  67 {
  68         static inline bool StepWormhole() { return true; }
  69
  70         const Owner               m_veh_owner;     ///< owner of the vehicle
  71         const bool                m_allow_90deg;
  72         const RailTypes           m_railtypes;
  73         CPerformanceTimer  *const m_pPerf;
  74
  75         inline bool Allow90deg() const { return m_allow_90deg; }
  76
  77         inline CFollowTrackRailBase(const Train *v, bool allow_90deg = true, RailTypes railtype_override = INVALID_RAILTYPES, CPerformanceTimer *pPerf = NULL)
  78                 : m_veh_owner(v->owner), m_allow_90deg(allow_90deg), m_railtypes(railtype_override == INVALID_RAILTYPES ? v->compatible_railtypes : railtype_override), m_pPerf(pPerf)
  79         {
  80                 assert(v != NULL);
  81                 assert(m_railtypes != INVALID_RAILTYPES);
  82         }
  83
  84         inline CFollowTrackRailBase(Owner o, bool allow_90deg = true, RailTypes railtype_override = INVALID_RAILTYPES, CPerformanceTimer *pPerf = NULL)
  85                 : m_veh_owner(o), m_allow_90deg(allow_90deg), m_railtypes(railtype_override), m_pPerf(pPerf)
  86         {
  87                 assert(railtype_override != INVALID_RAILTYPES);
  88         }
  89
  90         static inline bool IsTrackBridgeTile(TileIndex tile)
  91         {
  92                 return IsRailBridgeTile(tile);
  93         }
  94
  95         inline TrackdirBits GetTrackStatusTrackdirBits(TileIndex tile) const
  96         {
  97                 return TrackStatusToTrackdirBits(GetTileRailwayStatus(tile));
  98         }
  99
 100         /** check old tile */
 101         inline TileResult CheckOldTile()
 102         {
 103                 assert((GetTrackStatusTrackdirBits(m_old.tile) & TrackdirToTrackdirBits(m_old.td)) != 0);
 104
 105                 /* depots cause reversing */
 106                 if (IsRailDepotTile(m_old.tile)) {
 107                         DiagDirection exitdir = GetGroundDepotDirection(m_old.tile);
 108                         if (exitdir != m_exitdir) {
 109                                 assert(exitdir == ReverseDiagDir(m_exitdir));
 110                                 return TR_REVERSE;
 111                         }
 112                 }
 113
 114                 return TR_NORMAL;
 115         }
 116
 117         /** stores track status (available trackdirs) for the new tile into m_new.trackdirs */
 118         inline bool CheckNewTile()
 119         {
 120                 CPerfStart perf(*m_pPerf);
 121
 122                 if (IsNormalRailTile(m_new.tile)) {
 123                         m_new.trackdirs = TrackBitsToTrackdirBits(GetTrackBits(m_new.tile));
 124                 } else {
 125                         m_new.trackdirs = GetTrackStatusTrackdirBits(m_new.tile);
 126                 }
 127
 128                 if (m_new.trackdirs == TRACKDIR_BIT_NONE) return false;
 129
 130                 perf.Stop();
 131
 132                 if (IsRailDepotTile(m_new.tile)) {
 133                         DiagDirection exitdir = GetGroundDepotDirection(m_new.tile);
 134                         if (ReverseDiagDir(exitdir) != m_exitdir) {
 135                                 m_err = EC_NO_WAY;
 136                                 return false;
 137                         }
 138                 }
 139
 140                 /* rail transport is possible only on tiles with the same owner as vehicle */
 141                 if (GetTileOwner(m_new.tile) != m_veh_owner) {
 142                         /* different owner */
 143                         m_err = EC_NO_WAY;
 144                         return false;
 145                 }
 146
 147                 /* rail transport is possible only on compatible rail types */
 148                 RailType rail_type;
 149                 if (IsRailwayTile(m_new.tile)) {
 150                         rail_type = GetSideRailType(m_new.tile, ReverseDiagDir(m_exitdir));
 151                         if (rail_type == INVALID_RAILTYPE) {
 152                                 m_err = EC_NO_WAY;
 153                                 return false;
 154                         }
 155                 } else {
 156                         rail_type = GetRailType(m_new.tile);
 157                 }
 158
 159                 if (!HasBit(m_railtypes, rail_type)) {
 160                         /* incompatible rail type */
 161                         m_err = EC_RAIL_TYPE;
 162                         return false;
 163                 }
 164
 165                 /* tunnel holes and bridge ramps can be entered only from proper direction */
 166                 if (IsTunnelTile(m_new.tile)) {
 167                         if (m_flag != TF_TUNNEL) {
 168                                 DiagDirection tunnel_enterdir = GetTunnelBridgeDirection(m_new.tile);
 169                                 if (tunnel_enterdir != m_exitdir) {
 170                                         m_err = EC_NO_WAY;
 171                                         return false;
 172                                 }
 173                         }
 174                 } else if (IsRailBridgeTile(m_new.tile)) {
 175                         if (m_flag != TF_BRIDGE) {
 176                                 DiagDirection ramp_enderdir = GetTunnelBridgeDirection(m_new.tile);
 177                                 if (ramp_enderdir == ReverseDiagDir(m_exitdir)) {
 178                                         m_err = EC_NO_WAY;
 179                                         return false;
 180                                 }
 181                         }
 182                 }
 183
 184                 /* special handling for rail stations - get to the end of platform */
 185                 if (m_flag == TF_STATION) {
 186                         /* entered railway station
 187                          * get platform length */
 188                         uint length = BaseStation::GetByTile(m_new.tile)->GetPlatformLength(m_new.tile, TrackdirToExitdir(m_old.td));
 189                         /* how big step we must do to get to the last platform tile; */
 190                         m_tiles_skipped = length - 1;
 191                         /* move to the platform end */
 192                         TileIndexDiff diff = TileOffsByDiagDir(m_exitdir);
 193                         diff *= m_tiles_skipped;
 194                         m_new.tile = TILE_ADD(m_new.tile, diff);
 195                 }
 196
 197                 return true;
 198         }
 199
 200         /** return true if we successfully reversed at end of road/track */
 201         inline bool CheckEndOfLine()
 202         {
 203                 m_err = EC_NO_WAY;
 204                 return false;
 205         }
 206
 207         inline bool CheckStation()
 208         {
 209                 return HasStationTileRail(m_new.tile);
 210         }
 211
 212         /** Helper for pathfinders - get min/max speed on m_old */
 213         int GetSpeedLimit(int *pmin_speed = NULL) const
 214         {
 215                 /* Check for on-bridge and railtype speed limit */
 216                 TileIndex bridge_tile;
 217                 RailType rt;
 218
 219                 if (!m_old.InWormhole()) {
 220                         bridge_tile = IsRailBridgeTile(m_old.tile) ? m_old.tile : INVALID_TILE;
 221                         rt = GetRailType(m_old.tile, TrackdirToTrack(m_old.td));
 222                 } else if (IsTileSubtype(m_old.wormhole, TT_BRIDGE)) {
 223                         bridge_tile = m_old.wormhole;
 224                         rt = GetBridgeRailType(bridge_tile);
 225                 } else {
 226                         bridge_tile = INVALID_TILE;
 227                         rt = GetRailType(m_old.wormhole);
 228                 }
 229
 230                 int max_speed;
 231
 232                 /* Check for on-bridge speed limit */
 233                 if (bridge_tile != INVALID_TILE) {
 234                         max_speed = GetBridgeSpec(GetRailBridgeType(bridge_tile))->speed;
 235                 } else {
 236                         max_speed = INT_MAX; // no limit
 237                 }
 238
 239                 /* Check for speed limit imposed by railtype */
 240                 uint16 rail_speed = GetRailTypeInfo(rt)->max_speed;
 241                 if (rail_speed > 0) max_speed = min(max_speed, rail_speed);
 242
 243                 /* if min speed was requested, return it */
 244                 if (pmin_speed != NULL) *pmin_speed = 0;
 245                 return max_speed;
 246         }
 247 };
 248
 249 struct CFollowTrackAnyRailBase : CFollowTrackRailBase
 250 {
 251         inline CFollowTrackAnyRailBase(const Train *v, bool allow_90deg = true, RailTypes railtype_override = INVALID_RAILTYPES, CPerformanceTimer *pPerf = NULL)
 252                 : CFollowTrackRailBase(v, allow_90deg, railtype_override, pPerf)
 253         {
 254         }
 255
 256         inline CFollowTrackAnyRailBase(Owner o, bool allow_90deg = true, RailTypes railtype_override = INVALID_RAILTYPES, CPerformanceTimer *pPerf = NULL)
 257                 : CFollowTrackRailBase(o, allow_90deg, railtype_override, pPerf)
 258         {
 259         }
 260
 261         inline static bool DoTrackMasking() { return false; }
 262
 263         inline bool MaskReservedTracks() { return true; }
 264 };
 265
 266 struct CFollowTrackFreeRailBase : CFollowTrackRailBase
 267 {
 268         inline CFollowTrackFreeRailBase(const Train *v, bool allow_90deg = true, RailTypes railtype_override = INVALID_RAILTYPES, CPerformanceTimer *pPerf = NULL)
 269                 : CFollowTrackRailBase(v, allow_90deg, railtype_override, pPerf)
 270         {
 271         }
 272
 273         inline CFollowTrackFreeRailBase(Owner o, bool allow_90deg = true, RailTypes railtype_override = INVALID_RAILTYPES, CPerformanceTimer *pPerf = NULL)
 274                 : CFollowTrackRailBase(o, allow_90deg, railtype_override, pPerf)
 275         {
 276         }
 277
 278         inline static bool DoTrackMasking() { return true; }
 279
 280         inline bool MaskReservedTracks()
 281         {
 282                 if (m_flag == TF_STATION) {
 283                         /* Check skipped station tiles as well. */
 284                         TileIndexDiff diff = TileOffsByDiagDir(m_exitdir);
 285                         for (TileIndex tile = m_new.tile - diff * m_tiles_skipped; tile != m_new.tile; tile += diff) {
 286                                 if (HasStationReservation(tile)) {
 287                                         m_new.td = INVALID_TRACKDIR;
 288                                         m_new.trackdirs = TRACKDIR_BIT_NONE;
 289                                         m_err = EC_RESERVED;
 290                                         return false;
 291                                 }
 292                         }
 293                 }
 294
 295                 if (m_new.InWormhole()) {
 296                         assert(m_new.IsTrackdirSet());
 297                         if (HasReservedPos(m_new)) {
 298                                 m_new.td = INVALID_TRACKDIR;
 299                                 m_new.trackdirs = TRACKDIR_BIT_NONE;
 300                                 m_err = EC_RESERVED;
 301                                 return false;
 302                         } else {
 303                                 return true;
 304                         }
 305                 }
 306
 307                 TrackBits reserved = GetReservedTrackbits(m_new.tile);
 308                 /* Mask already reserved trackdirs. */
 309                 m_new.trackdirs &= ~TrackBitsToTrackdirBits(reserved);
 310                 /* Mask out all trackdirs that conflict with the reservation. */
 311                 Track t;
 312                 FOR_EACH_SET_TRACK(t, TrackdirBitsToTrackBits(m_new.trackdirs)) {
 313                         if (TracksOverlap(reserved | TrackToTrackBits(t))) m_new.trackdirs &= ~TrackToTrackdirBits(t);
 314                 }
 315                 if (m_new.trackdirs == TRACKDIR_BIT_NONE) {
 316                         m_new.td = INVALID_TRACKDIR;
 317                         m_err = EC_RESERVED;
 318                         return false;
 319                 }
 320                 /* Check if the resulting trackdirs is a single trackdir */
 321                 m_new.SetTrackdir();
 322                 return true;
 323         }
 324 };
 325
 326 /**
 327  * Track follower road base class
 328  */
 329 struct CFollowTrackRoadBase : CFollowTrackBase
 330 {
 331         static inline bool StepWormhole() { return false; }
 332
 333         const RoadVehicle *const m_veh; ///< moving vehicle
 334
 335         static inline bool Allow90deg() { return true; }
 336
 337         inline CFollowTrackRoadBase(const RoadVehicle *v)
 338                 : m_veh(v)
 339         {
 340                 assert(v != NULL);
 341         }
 342
 343         static inline bool IsTrackBridgeTile(TileIndex tile)
 344         {
 345                 return IsRoadBridgeTile(tile);
 346         }
 347
 348         inline TrackdirBits GetTrackStatusTrackdirBits(TileIndex tile) const
 349         {
 350                 return TrackStatusToTrackdirBits(GetTileRoadStatus(tile, m_veh->compatible_roadtypes));
 351         }
 352
 353         inline bool IsTram() { return HasBit(m_veh->compatible_roadtypes, ROADTYPE_TRAM); }
 354
 355         /** Tests if a tile is a road tile with a single tramtrack (tram can reverse) */
 356         inline DiagDirection GetSingleTramBit(TileIndex tile)
 357         {
 358                 assert(IsTram()); // this function shouldn't be called in other cases
 359
 360                 if (IsRoadTile(tile)) {
 361                         RoadBits rb = GetRoadBits(tile, ROADTYPE_TRAM);
 362                         switch (rb) {
 363                                 case ROAD_NW: return DIAGDIR_NW;
 364                                 case ROAD_SW: return DIAGDIR_SW;
 365                                 case ROAD_SE: return DIAGDIR_SE;
 366                                 case ROAD_NE: return DIAGDIR_NE;
 367                                 default: break;
 368                         }
 369                 }
 370                 return INVALID_DIAGDIR;
 371         }
 372
 373         /** check old tile */
 374         inline TileResult CheckOldTile()
 375         {
 376                 assert(((GetTrackStatusTrackdirBits(m_old.tile) & TrackdirToTrackdirBits(m_old.td)) != 0) ||
 377                        (IsTram() && GetSingleTramBit(m_old.tile) != INVALID_DIAGDIR)); // Disable the assertion for single tram bits
 378
 379                 /* depots cause reversing */
 380                 if (IsRoadDepotTile(m_old.tile)) {
 381                         DiagDirection exitdir = GetGroundDepotDirection(m_old.tile);
 382                         if (exitdir != m_exitdir) {
 383                                 assert(exitdir == ReverseDiagDir(m_exitdir));
 384                                 return TR_REVERSE;
 385                         }
 386                 }
 387
 388                 /* road stop can be left at one direction only unless it's a drive-through stop */
 389                 if (IsStandardRoadStopTile(m_old.tile)) {
 390                         DiagDirection exitdir = GetRoadStopDir(m_old.tile);
 391                         if (exitdir != m_exitdir) {
 392                                 return TR_NO_WAY;
 393                         }
 394                 }
 395
 396                 if (IsTram()) {
 397                         DiagDirection single_tram = GetSingleTramBit(m_old.tile);
 398                         /* single tram bits cause reversing */
 399                         if (single_tram == ReverseDiagDir(m_exitdir)) {
 400                                 return TR_REVERSE;
 401                         }
 402                         /* single tram bits can only be left in one direction */
 403                         if (single_tram != INVALID_DIAGDIR && single_tram != m_exitdir) {
 404                                 return TR_NO_WAY;
 405                         }
 406                 }
 407
 408                 return TR_NORMAL;
 409         }
 410
 411         /** stores track status (available trackdirs) for the new tile into m_new.trackdirs */
 412         inline bool CheckNewTile()
 413         {
 414                 m_new.trackdirs = GetTrackStatusTrackdirBits(m_new.tile);
 415
 416                 if (m_new.trackdirs == TRACKDIR_BIT_NONE) {
 417                         if (!IsTram()) return false;
 418
 419                         /* GetTileRoadStatus() returns 0 for single tram bits.
 420                          * As we cannot change it there (easily) without breaking something, change it here */
 421                         DiagDirection single_tram = GetSingleTramBit(m_new.tile);
 422                         if (single_tram == ReverseDiagDir(m_exitdir)) {
 423                                 m_new.trackdirs = DiagDirToAxis(single_tram) == AXIS_X ? TRACKDIR_BIT_X_NE | TRACKDIR_BIT_X_SW : TRACKDIR_BIT_Y_NW | TRACKDIR_BIT_Y_SE;
 424                                 return true;
 425                         } else {
 426                                 m_err = EC_NO_WAY;
 427                                 return false;
 428                         }
 429                 }
 430
 431                 if (IsStandardRoadStopTile(m_new.tile)) {
 432                         /* road stop can be entered from one direction only unless it's a drive-through stop */
 433                         DiagDirection exitdir = GetRoadStopDir(m_new.tile);
 434                         if (ReverseDiagDir(exitdir) != m_exitdir) {
 435                                 m_err = EC_NO_WAY;
 436                                 return false;
 437                         }
 438                 }
 439
 440                 /* depots can also be entered from one direction only */
 441                 if (IsRoadDepotTile(m_new.tile)) {
 442                         DiagDirection exitdir = GetGroundDepotDirection(m_new.tile);
 443                         if (ReverseDiagDir(exitdir) != m_exitdir) {
 444                                 m_err = EC_NO_WAY;
 445                                 return false;
 446                         }
 447                         /* don't try to enter other company's depots */
 448                         if (GetTileOwner(m_new.tile) != m_veh->owner) {
 449                                 m_err = EC_OWNER;
 450                                 return false;
 451                         }
 452                 }
 453
 454                 /* tunnel holes and bridge ramps can be entered only from proper direction */
 455                 if (IsTunnelTile(m_new.tile)) {
 456                         if (m_flag != TF_TUNNEL) {
 457                                 DiagDirection tunnel_enterdir = GetTunnelBridgeDirection(m_new.tile);
 458                                 if (tunnel_enterdir != m_exitdir) {
 459                                         m_err = EC_NO_WAY;
 460                                         return false;
 461                                 }
 462                         }
 463                 } else if (IsRoadBridgeTile(m_new.tile)) {
 464                         if (m_flag != TF_BRIDGE) {
 465                                 DiagDirection ramp_enderdir = GetTunnelBridgeDirection(m_new.tile);
 466                                 if (ramp_enderdir == ReverseDiagDir(m_exitdir)) {
 467                                         m_err = EC_NO_WAY;
 468                                         return false;
 469                                 }
 470                         }
 471                 }
 472
 473                 return true;
 474         }
 475
 476         /** return true if we successfully reversed at end of road/track */
 477         inline bool CheckEndOfLine()
 478         {
 479                 /* In case we can't enter the next tile, but are
 480                  * a normal road vehicle, then we can actually
 481                  * try to reverse as this is the end of the road.
 482                  * Trams can only turn on the appropriate bits in
 483                  * which case reaching this would mean a dead end
 484                  * near a building and in that case there would
 485                  * a "false" QueryNewTileTrackStatus result and
 486                  * as such reversing is already tried. The fact
 487                  * that function failed can have to do with a
 488                  * missing road bit, or inability to connect the
 489                  * different bits due to slopes. */
 490                 if (!IsTram()) {
 491                         /* if we reached the end of road, we can reverse the RV and continue moving */
 492                         m_exitdir = ReverseDiagDir(m_exitdir);
 493                         /* new tile will be the same as old one */
 494                         m_new.tile = m_old.tile;
 495                         m_new.wormhole = INVALID_TILE;
 496                         /* set new trackdir bits to all reachable trackdirs */
 497                         m_new.trackdirs = GetTrackStatusTrackdirBits(m_new.tile);
 498                         m_new.trackdirs &= DiagdirReachesTrackdirs(m_exitdir);
 499                         /* we always have some trackdirs reachable after reversal */
 500                         assert(m_new.trackdirs != TRACKDIR_BIT_NONE);
 501                         /* check if the resulting trackdirs is a single trackdir */
 502                         m_new.SetTrackdir();
 503                         return true;
 504                 }
 505                 m_err = EC_NO_WAY;
 506                 return false;
 507         }
 508
 509         inline bool CheckStation()
 510         {
 511                 return IsRoadStopTile(m_new.tile);
 512         }
 513
 514         /** Helper for pathfinders - get min/max speed on m_old */
 515         int GetSpeedLimit(int *pmin_speed = NULL) const
 516         {
 517                 int max_speed;
 518
 519                 /* Check for on-bridge speed limit */
 520                 if (IsRoadBridgeTile(m_old.tile)) {
 521                         max_speed = 2 * GetBridgeSpec(GetRoadBridgeType(m_old.tile))->speed;
 522                 } else {
 523                         max_speed = INT_MAX; // no limit
 524                 }
 525
 526                 /* if min speed was requested, return it */
 527                 if (pmin_speed != NULL) *pmin_speed = 0;
 528                 return max_speed;
 529         }
 530 };
 531
 532 /**
 533  * Track follower water base class
 534  */
 535 struct CFollowTrackWaterBase : CFollowTrackBase
 536 {
 537         static inline bool StepWormhole() { return false; }
 538
 539         const bool m_allow_90deg;
 540
 541         inline bool Allow90deg() const { return m_allow_90deg; }
 542
 543         inline CFollowTrackWaterBase(bool allow_90deg = true)
 544                 : m_allow_90deg(allow_90deg)
 545         {
 546         }
 547
 548         static inline bool IsTrackBridgeTile(TileIndex tile)
 549         {
 550                 return IsAqueductTile(tile);
 551         }
 552
 553         inline TrackdirBits GetTrackStatusTrackdirBits(TileIndex tile) const
 554         {
 555                 return TrackStatusToTrackdirBits(GetTileWaterwayStatus(tile));
 556         }
 557
 558         /** check old tile */
 559         inline TileResult CheckOldTile()
 560         {
 561                 assert((GetTrackStatusTrackdirBits(m_old.tile) & TrackdirToTrackdirBits(m_old.td)) != 0);
 562
 563                 return TR_NORMAL;
 564         }
 565
 566         /** stores track status (available trackdirs) for the new tile into m_new.trackdirs */
 567         inline bool CheckNewTile()
 568         {
 569                 m_new.trackdirs = GetTrackStatusTrackdirBits(m_new.tile);
 570
 571                 if (m_new.trackdirs == TRACKDIR_BIT_NONE) return false;
 572
 573                 /* tunnel holes and bridge ramps can be entered only from proper direction */
 574                 if (IsAqueductTile(m_new.tile)) {
 575                         if (m_flag != TF_BRIDGE) {
 576                                 DiagDirection ramp_enderdir = GetTunnelBridgeDirection(m_new.tile);
 577                                 if (ramp_enderdir == ReverseDiagDir(m_exitdir)) {
 578                                         m_err = EC_NO_WAY;
 579                                         return false;
 580                                 }
 581                         }
 582                 }
 583
 584                 return true;
 585         }
 586
 587         /** return true if we successfully reversed at end of road/track */
 588         inline bool CheckEndOfLine()
 589         {
 590                 m_err = EC_NO_WAY;
 591                 return false;
 592         }
 593
 594         inline bool CheckStation()
 595         {
 596                 return false;
 597         }
 598 };
 599
 600
 601 /**
 602  * Track follower helper template class (can serve pathfinders and vehicle
 603  *  controllers). See 6 different typedefs below for 3 different transport
 604  *  types w/ or w/o 90-deg turns allowed
 605  */
 606 template <class Base>
 607 struct CFollowTrack : Base
 608 {
 609         /* MSVC does not support variadic templates. Oh well... */
 610
 611         inline CFollowTrack() : Base() { }
 612
 613         template <typename T1>
 614         inline CFollowTrack (T1 t1) : Base (t1) { }
 615
 616         template <typename T1, typename T2>
 617         inline CFollowTrack (T1 t1, T2 t2) : Base (t1, t2) { }
 618
 619         template <typename T1, typename T2, typename T3>
 620         inline CFollowTrack (T1 t1, T2 t2, T3 t3) : Base (t1, t2, t3) { }
 621
 622         template <typename T1, typename T2, typename T3, typename T4>
 623         inline CFollowTrack (T1 t1, T2 t2, T3 t3, T4 t4) : Base (t1, t2, t3, t4) { }
 624
 625         /**
 626          * main follower routine. Fills all members and return true on success.
 627          *  Otherwise returns false if track can't be followed.
 628          */
 629         inline bool Follow(const PFPos &pos)
 630         {
 631                 Base::m_old = pos;
 632                 Base::m_err = Base::EC_NONE;
 633                 Base::m_exitdir = TrackdirToExitdir(Base::m_old.td);
 634
 635                 if (Base::m_old.InWormhole()) {
 636                         FollowWormhole();
 637                 } else {
 638                         switch (Base::CheckOldTile()) {
 639                                 case Base::TR_NO_WAY:
 640                                         Base::m_err = Base::EC_NO_WAY;
 641                                         return false;
 642                                 case Base::TR_REVERSE:
 643                                         Base::m_new.tile = Base::m_old.tile;
 644                                         Base::m_new.wormhole = INVALID_TILE;
 645                                         Base::m_new.td = ReverseTrackdir(Base::m_old.td);
 646                                         Base::m_new.trackdirs = TrackdirToTrackdirBits(Base::m_new.td);
 647                                         Base::m_exitdir = ReverseDiagDir(Base::m_exitdir);
 648                                         Base::m_tiles_skipped = 0;
 649                                         Base::m_flag = Base::TF_NONE;
 650                                         return true;
 651                                 default:
 652                                         break;
 653                         }
 654                         FollowTileExit();
 655                 }
 656
 657                 if (Base::m_new.InWormhole()) {
 658                         assert(Base::StepWormhole());
 659                         Base::m_new.td = DiagDirToDiagTrackdir(Base::m_exitdir);
 660                         Base::m_new.trackdirs = TrackdirToTrackdirBits(Base::m_new.td);
 661                         return true;
 662                 }
 663
 664                 if (!Base::CheckNewTile() || (Base::m_new.trackdirs &= DiagdirReachesTrackdirs(Base::m_exitdir)) == TRACKDIR_BIT_NONE) {
 665                         return Base::CheckEndOfLine();
 666                 }
 667                 if (!Base::Allow90deg()) {
 668                         Base::m_new.trackdirs &= (TrackdirBits)~(int)TrackdirCrossesTrackdirs(Base::m_old.td);
 669                         if (Base::m_new.trackdirs == TRACKDIR_BIT_NONE) {
 670                                 Base::m_err = Base::EC_90DEG;
 671                                 return false;
 672                         }
 673                 }
 674                 /* Check if the resulting trackdirs is a single trackdir */
 675                 Base::m_new.SetTrackdir();
 676                 return true;
 677         }
 678
 679         inline bool FollowNext()
 680         {
 681                 assert(Base::m_new.tile != INVALID_TILE);
 682                 assert(Base::m_new.IsTrackdirSet());
 683                 return Follow(Base::m_new);
 684         }
 685
 686         inline void SetPos(const PFPos &pos)
 687         {
 688                 Base::m_new.PFPos::operator = (pos);
 689                 Base::m_new.trackdirs = TrackdirToTrackdirBits(pos.td);
 690         }
 691
 692 protected:
 693         /** Follow m_exitdir from m_old and fill m_new.tile and m_tiles_skipped */
 694         inline void FollowTileExit()
 695         {
 696                 assert(!Base::m_old.InWormhole());
 697                 /* extra handling for bridges in our direction */
 698                 if (Base::IsTrackBridgeTile(Base::m_old.tile)) {
 699                         if (Base::m_exitdir == GetTunnelBridgeDirection(Base::m_old.tile)) {
 700                                 /* we are entering the bridge */
 701                                 Base::m_flag = Base::TF_BRIDGE;
 702                                 Base::m_new.tile = GetOtherBridgeEnd(Base::m_old.tile);
 703                                 Base::m_tiles_skipped = GetTunnelBridgeLength(Base::m_new.tile, Base::m_old.tile);
 704                                 if (Base::StepWormhole() && Base::m_tiles_skipped > 0) {
 705                                         Base::m_tiles_skipped--;
 706                                         Base::m_new.wormhole = Base::m_new.tile;
 707                                         Base::m_new.tile = TILE_ADD(Base::m_new.tile, TileOffsByDiagDir(ReverseDiagDir(Base::m_exitdir)));
 708                                 } else {
 709                                         Base::m_new.wormhole = INVALID_TILE;
 710                                 }
 711                                 return;
 712                         }
 713                 /* extra handling for tunnels in our direction */
 714                 } else if (IsTunnelTile(Base::m_old.tile)) {
 715                         DiagDirection enterdir = GetTunnelBridgeDirection(Base::m_old.tile);
 716                         if (enterdir == Base::m_exitdir) {
 717                                 /* we are entering the tunnel */
 718                                 Base::m_flag = Base::TF_TUNNEL;
 719                                 Base::m_new.tile = GetOtherTunnelEnd(Base::m_old.tile);
 720                                 Base::m_tiles_skipped = GetTunnelBridgeLength(Base::m_new.tile, Base::m_old.tile);
 721                                 if (Base::StepWormhole() && Base::m_tiles_skipped > 0) {
 722                                         Base::m_tiles_skipped--;
 723                                         Base::m_new.wormhole = Base::m_new.tile;
 724                                         Base::m_new.tile = TILE_ADD(Base::m_new.tile, TileOffsByDiagDir(ReverseDiagDir(Base::m_exitdir)));
 725                                 } else {
 726                                         Base::m_new.wormhole = INVALID_TILE;
 727                                 }
 728                                 return;
 729                         }
 730                         assert(ReverseDiagDir(enterdir) == Base::m_exitdir);
 731                 }
 732
 733                 /* normal or station tile, do one step */
 734                 TileIndexDiff diff = TileOffsByDiagDir(Base::m_exitdir);
 735                 Base::m_new.tile = TILE_ADD(Base::m_old.tile, diff);
 736                 Base::m_new.wormhole = INVALID_TILE;
 737
 738                 /* special handling for stations */
 739                 Base::m_flag = Base::CheckStation() ? Base::TF_STATION : Base::TF_NONE;
 740
 741                 Base::m_tiles_skipped = 0;
 742         }
 743
 744         /** Follow m_old when in a wormhole */
 745         inline void FollowWormhole()
 746         {
 747                 assert(Base::m_old.InWormhole());
 748                 assert(Base::IsTrackBridgeTile(Base::m_old.wormhole) || IsTunnelTile(Base::m_old.wormhole));
 749
 750                 Base::m_new.tile = Base::m_old.wormhole;
 751                 Base::m_new.wormhole = INVALID_TILE;
 752                 Base::m_flag = IsTileSubtype(Base::m_old.wormhole, TT_BRIDGE) ? Base::TF_BRIDGE : Base::TF_TUNNEL;
 753                 Base::m_tiles_skipped = GetTunnelBridgeLength(Base::m_new.tile, Base::m_old.tile);
 754         }
 755 };
 756
 757 template <bool T90deg_turns_allowed>
 758 struct CFollowTrackWaterT : CFollowTrack<CFollowTrackWaterBase>
 759 {
 760         inline CFollowTrackWaterT(const Ship *v)
 761                 : CFollowTrack<CFollowTrackWaterBase>(T90deg_turns_allowed)
 762         {
 763         }
 764
 765         inline static bool Allow90degTurns() { return T90deg_turns_allowed; }
 766 };
 767
 768 typedef CFollowTrackWaterT<true>  CFollowTrackWater90;
 769 typedef CFollowTrackWaterT<false> CFollowTrackWaterNo90;
 770
 771 typedef CFollowTrack<CFollowTrackRoadBase> CFollowTrackRoad;
 772
 773 template <class Base, bool T90deg_turns_allowed>
 774 struct CFollowTrackRailT : CFollowTrack<Base>
 775 {
 776         inline CFollowTrackRailT(const Train *v)
 777                 : CFollowTrack<Base>(v, T90deg_turns_allowed)
 778         {
 779         }
 780
 781         inline CFollowTrackRailT(const Train *v, RailTypes railtype_override, CPerformanceTimer *pPerf = NULL)
 782                 : CFollowTrack<Base>(v, T90deg_turns_allowed, railtype_override, pPerf)
 783         {
 784         }
 785
 786         inline static bool Allow90degTurns() { return T90deg_turns_allowed; }
 787 };
 788
 789 typedef CFollowTrackRailT<CFollowTrackAnyRailBase,  true > CFollowTrackRail90;
 790 typedef CFollowTrackRailT<CFollowTrackAnyRailBase,  false> CFollowTrackRailNo90;
 791 typedef CFollowTrackRailT<CFollowTrackFreeRailBase, true > CFollowTrackFreeRail90;
 792 typedef CFollowTrackRailT<CFollowTrackFreeRailBase, false> CFollowTrackFreeRailNo90;
 793
 794 struct CFollowTrackRail : CFollowTrack<CFollowTrackAnyRailBase>
 795 {
 796         inline CFollowTrackRail(const Train *v = NULL, bool allow_90deg = true, bool railtype_override = false)
 797                 : CFollowTrack<CFollowTrackAnyRailBase>(v, allow_90deg, railtype_override ? GetRailTypeInfo(v->railtype)->compatible_railtypes : INVALID_RAILTYPES)
 798         {
 799         }
 800
 801         inline CFollowTrackRail(Owner o, bool allow_90deg = true, RailTypes railtype_override = INVALID_RAILTYPES)
 802                 : CFollowTrack<CFollowTrackAnyRailBase>(o, allow_90deg, railtype_override)
 803         {
 804         }
 805 };
 806
 807 #endif /* FOLLOW_TRACK_HPP */