1 /* 2 * This file is part of OpenTTD. 3 * 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. 4 * 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. 5 * 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/>. 6 */ 7 8 /** @file follow_track.hpp Template function for track followers */ 9 10 #ifndef FOLLOW_TRACK_HPP 11 #define FOLLOW_TRACK_HPP 12 13 #include "../pbs.h" 14 #include "../roadveh.h" 15 #include "../station_base.h" 16 #include "../train.h" 17 #include "../tunnelbridge.h" 18 #include "../tunnelbridge_map.h" 19 #include "../depot_map.h" 20 #include "pathfinder_func.h" 21 22 /** 23 * Track follower helper template class (can serve pathfinders and vehicle 24 * controllers). See 6 different typedefs below for 3 different transport 25 * types w/ or w/o 90-deg turns allowed 26 */ 27 template <TransportType Ttr_type_, typename VehicleType, bool T90deg_turns_allowed_ = true, bool Tmask_reserved_tracks = false> 28 struct CFollowTrackT 29 { 30 enum ErrorCode { 31 EC_NONE, 32 EC_OWNER, 33 EC_RAIL_ROAD_TYPE, 34 EC_90DEG, 35 EC_NO_WAY, 36 EC_RESERVED, 37 }; 38 39 const VehicleType *m_veh; ///< moving vehicle 40 Owner m_veh_owner; ///< owner of the vehicle 41 TileIndex m_old_tile; ///< the origin (vehicle moved from) before move 42 Trackdir m_old_td; ///< the trackdir (the vehicle was on) before move 43 TileIndex m_new_tile; ///< the new tile (the vehicle has entered) 44 TrackdirBits m_new_td_bits; ///< the new set of available trackdirs 45 DiagDirection m_exitdir; ///< exit direction (leaving the old tile) 46 bool m_is_tunnel; ///< last turn passed tunnel 47 bool m_is_bridge; ///< last turn passed bridge ramp 48 bool m_is_station; ///< last turn passed station 49 int m_tiles_skipped; ///< number of skipped tunnel or station tiles 50 ErrorCode m_err; 51 RailTypes m_railtypes; 52 CFollowTrackTCFollowTrackT53 inline CFollowTrackT(const VehicleType *v = nullptr, RailTypes railtype_override = INVALID_RAILTYPES) 54 { 55 Init(v, railtype_override); 56 } 57 CFollowTrackTCFollowTrackT58 inline CFollowTrackT(Owner o, RailTypes railtype_override = INVALID_RAILTYPES) 59 { 60 assert(IsRailTT()); 61 m_veh = nullptr; 62 Init(o, railtype_override); 63 } 64 InitCFollowTrackT65 inline void Init(const VehicleType *v, RailTypes railtype_override) 66 { 67 assert(!IsRailTT() || (v != nullptr && v->type == VEH_TRAIN)); 68 m_veh = v; 69 Init(v != nullptr ? v->owner : INVALID_OWNER, IsRailTT() && railtype_override == INVALID_RAILTYPES ? Train::From(v)->compatible_railtypes : railtype_override); 70 } 71 InitCFollowTrackT72 inline void Init(Owner o, RailTypes railtype_override) 73 { 74 assert(!IsRoadTT() || m_veh != nullptr); 75 assert(!IsRailTT() || railtype_override != INVALID_RAILTYPES); 76 m_veh_owner = o; 77 /* don't worry, all is inlined so compiler should remove unnecessary initializations */ 78 m_old_tile = INVALID_TILE; 79 m_old_td = INVALID_TRACKDIR; 80 m_new_tile = INVALID_TILE; 81 m_new_td_bits = TRACKDIR_BIT_NONE; 82 m_exitdir = INVALID_DIAGDIR; 83 m_is_station = m_is_bridge = m_is_tunnel = false; 84 m_tiles_skipped = 0; 85 m_err = EC_NONE; 86 m_railtypes = railtype_override; 87 } 88 TTCFollowTrackT89 inline static TransportType TT() { return Ttr_type_; } IsWaterTTCFollowTrackT90 inline static bool IsWaterTT() { return TT() == TRANSPORT_WATER; } IsRailTTCFollowTrackT91 inline static bool IsRailTT() { return TT() == TRANSPORT_RAIL; } IsTramCFollowTrackT92 inline bool IsTram() { return IsRoadTT() && RoadTypeIsTram(RoadVehicle::From(m_veh)->roadtype); } IsRoadTTCFollowTrackT93 inline static bool IsRoadTT() { return TT() == TRANSPORT_ROAD; } Allow90degTurnsCFollowTrackT94 inline static bool Allow90degTurns() { return T90deg_turns_allowed_; } DoTrackMaskingCFollowTrackT95 inline static bool DoTrackMasking() { return Tmask_reserved_tracks; } 96 97 /** Tests if a tile is a road tile with a single tramtrack (tram can reverse) */ GetSingleTramBitCFollowTrackT98 inline DiagDirection GetSingleTramBit(TileIndex tile) 99 { 100 assert(IsTram()); // this function shouldn't be called in other cases 101 102 if (IsNormalRoadTile(tile)) { 103 RoadBits rb = GetRoadBits(tile, RTT_TRAM); 104 switch (rb) { 105 case ROAD_NW: return DIAGDIR_NW; 106 case ROAD_SW: return DIAGDIR_SW; 107 case ROAD_SE: return DIAGDIR_SE; 108 case ROAD_NE: return DIAGDIR_NE; 109 default: break; 110 } 111 } 112 return INVALID_DIAGDIR; 113 } 114 115 /** 116 * main follower routine. Fills all members and return true on success. 117 * Otherwise returns false if track can't be followed. 118 */ FollowCFollowTrackT119 inline bool Follow(TileIndex old_tile, Trackdir old_td) 120 { 121 m_old_tile = old_tile; 122 m_old_td = old_td; 123 m_err = EC_NONE; 124 assert( 125 ((TrackStatusToTrackdirBits( 126 GetTileTrackStatus(m_old_tile, TT(), (IsRoadTT() && m_veh != nullptr) ? (this->IsTram() ? RTT_TRAM : RTT_ROAD) : 0) 127 ) & TrackdirToTrackdirBits(m_old_td)) != 0) || 128 (IsTram() && GetSingleTramBit(m_old_tile) != INVALID_DIAGDIR) // Disable the assertion for single tram bits 129 ); 130 m_exitdir = TrackdirToExitdir(m_old_td); 131 if (ForcedReverse()) return true; 132 if (!CanExitOldTile()) return false; 133 FollowTileExit(); 134 if (!QueryNewTileTrackStatus()) return TryReverse(); 135 m_new_td_bits &= DiagdirReachesTrackdirs(m_exitdir); 136 if (m_new_td_bits == TRACKDIR_BIT_NONE || !CanEnterNewTile()) { 137 /* In case we can't enter the next tile, but are 138 * a normal road vehicle, then we can actually 139 * try to reverse as this is the end of the road. 140 * Trams can only turn on the appropriate bits in 141 * which case reaching this would mean a dead end 142 * near a building and in that case there would 143 * a "false" QueryNewTileTrackStatus result and 144 * as such reversing is already tried. The fact 145 * that function failed can have to do with a 146 * missing road bit, or inability to connect the 147 * different bits due to slopes. */ 148 if (IsRoadTT() && !IsTram() && TryReverse()) return true; 149 150 /* CanEnterNewTile already set a reason. 151 * Do NOT overwrite it (important for example for EC_RAIL_ROAD_TYPE). 152 * Only set a reason if CanEnterNewTile was not called */ 153 if (m_new_td_bits == TRACKDIR_BIT_NONE) m_err = EC_NO_WAY; 154 155 return false; 156 } 157 if ((!IsRailTT() && !Allow90degTurns()) || (IsRailTT() && Rail90DegTurnDisallowed(GetTileRailType(m_old_tile), GetTileRailType(m_new_tile), !Allow90degTurns()))) { 158 m_new_td_bits &= (TrackdirBits)~(int)TrackdirCrossesTrackdirs(m_old_td); 159 if (m_new_td_bits == TRACKDIR_BIT_NONE) { 160 m_err = EC_90DEG; 161 return false; 162 } 163 } 164 return true; 165 } 166 MaskReservedTracksCFollowTrackT167 inline bool MaskReservedTracks() 168 { 169 if (!DoTrackMasking()) return true; 170 171 if (m_is_station) { 172 /* Check skipped station tiles as well. */ 173 TileIndexDiff diff = TileOffsByDiagDir(m_exitdir); 174 for (TileIndex tile = m_new_tile - diff * m_tiles_skipped; tile != m_new_tile; tile += diff) { 175 if (HasStationReservation(tile)) { 176 m_new_td_bits = TRACKDIR_BIT_NONE; 177 m_err = EC_RESERVED; 178 return false; 179 } 180 } 181 } 182 183 TrackBits reserved = GetReservedTrackbits(m_new_tile); 184 /* Mask already reserved trackdirs. */ 185 m_new_td_bits &= ~TrackBitsToTrackdirBits(reserved); 186 /* Mask out all trackdirs that conflict with the reservation. */ 187 for (Track t : SetTrackBitIterator(TrackdirBitsToTrackBits(m_new_td_bits))) { 188 if (TracksOverlap(reserved | TrackToTrackBits(t))) m_new_td_bits &= ~TrackToTrackdirBits(t); 189 } 190 if (m_new_td_bits == TRACKDIR_BIT_NONE) { 191 m_err = EC_RESERVED; 192 return false; 193 } 194 return true; 195 } 196 197 protected: 198 /** Follow the m_exitdir from m_old_tile and fill m_new_tile and m_tiles_skipped */ FollowTileExitCFollowTrackT199 inline void FollowTileExit() 200 { 201 m_is_station = m_is_bridge = m_is_tunnel = false; 202 m_tiles_skipped = 0; 203 204 /* extra handling for tunnels and bridges in our direction */ 205 if (IsTileType(m_old_tile, MP_TUNNELBRIDGE)) { 206 DiagDirection enterdir = GetTunnelBridgeDirection(m_old_tile); 207 if (enterdir == m_exitdir) { 208 /* we are entering the tunnel / bridge */ 209 if (IsTunnel(m_old_tile)) { 210 m_is_tunnel = true; 211 m_new_tile = GetOtherTunnelEnd(m_old_tile); 212 } else { // IsBridge(m_old_tile) 213 m_is_bridge = true; 214 m_new_tile = GetOtherBridgeEnd(m_old_tile); 215 } 216 m_tiles_skipped = GetTunnelBridgeLength(m_new_tile, m_old_tile); 217 return; 218 } 219 assert(ReverseDiagDir(enterdir) == m_exitdir); 220 } 221 222 /* normal or station tile, do one step */ 223 m_new_tile = TileAddByDiagDir(m_old_tile, m_exitdir); 224 225 /* special handling for stations */ 226 if (IsRailTT() && HasStationTileRail(m_new_tile)) { 227 m_is_station = true; 228 } else if (IsRoadTT() && IsRoadStopTile(m_new_tile)) { 229 m_is_station = true; 230 } 231 } 232 233 /** stores track status (available trackdirs) for the new tile into m_new_td_bits */ QueryNewTileTrackStatusCFollowTrackT234 inline bool QueryNewTileTrackStatus() 235 { 236 if (IsRailTT() && IsPlainRailTile(m_new_tile)) { 237 m_new_td_bits = (TrackdirBits)(GetTrackBits(m_new_tile) * 0x101); 238 } else if (IsRoadTT()) { 239 m_new_td_bits = GetTrackdirBitsForRoad(m_new_tile, this->IsTram() ? RTT_TRAM : RTT_ROAD); 240 } else { 241 m_new_td_bits = TrackStatusToTrackdirBits(GetTileTrackStatus(m_new_tile, TT(), 0)); 242 } 243 return (m_new_td_bits != TRACKDIR_BIT_NONE); 244 } 245 246 /** return true if we can leave m_old_tile in m_exitdir */ CanExitOldTileCFollowTrackT247 inline bool CanExitOldTile() 248 { 249 /* road stop can be left at one direction only unless it's a drive-through stop */ 250 if (IsRoadTT() && IsStandardRoadStopTile(m_old_tile)) { 251 DiagDirection exitdir = GetRoadStopDir(m_old_tile); 252 if (exitdir != m_exitdir) { 253 m_err = EC_NO_WAY; 254 return false; 255 } 256 } 257 258 /* single tram bits can only be left in one direction */ 259 if (IsTram()) { 260 DiagDirection single_tram = GetSingleTramBit(m_old_tile); 261 if (single_tram != INVALID_DIAGDIR && single_tram != m_exitdir) { 262 m_err = EC_NO_WAY; 263 return false; 264 } 265 } 266 267 /* road depots can be also left in one direction only */ 268 if (IsRoadTT() && IsDepotTypeTile(m_old_tile, TT())) { 269 DiagDirection exitdir = GetRoadDepotDirection(m_old_tile); 270 if (exitdir != m_exitdir) { 271 m_err = EC_NO_WAY; 272 return false; 273 } 274 } 275 return true; 276 } 277 278 /** return true if we can enter m_new_tile from m_exitdir */ CanEnterNewTileCFollowTrackT279 inline bool CanEnterNewTile() 280 { 281 if (IsRoadTT() && IsStandardRoadStopTile(m_new_tile)) { 282 /* road stop can be entered from one direction only unless it's a drive-through stop */ 283 DiagDirection exitdir = GetRoadStopDir(m_new_tile); 284 if (ReverseDiagDir(exitdir) != m_exitdir) { 285 m_err = EC_NO_WAY; 286 return false; 287 } 288 } 289 290 /* single tram bits can only be entered from one direction */ 291 if (IsTram()) { 292 DiagDirection single_tram = GetSingleTramBit(m_new_tile); 293 if (single_tram != INVALID_DIAGDIR && single_tram != ReverseDiagDir(m_exitdir)) { 294 m_err = EC_NO_WAY; 295 return false; 296 } 297 } 298 299 /* road and rail depots can also be entered from one direction only */ 300 if (IsRoadTT() && IsDepotTypeTile(m_new_tile, TT())) { 301 DiagDirection exitdir = GetRoadDepotDirection(m_new_tile); 302 if (ReverseDiagDir(exitdir) != m_exitdir) { 303 m_err = EC_NO_WAY; 304 return false; 305 } 306 /* don't try to enter other company's depots */ 307 if (GetTileOwner(m_new_tile) != m_veh_owner) { 308 m_err = EC_OWNER; 309 return false; 310 } 311 } 312 if (IsRailTT() && IsDepotTypeTile(m_new_tile, TT())) { 313 DiagDirection exitdir = GetRailDepotDirection(m_new_tile); 314 if (ReverseDiagDir(exitdir) != m_exitdir) { 315 m_err = EC_NO_WAY; 316 return false; 317 } 318 } 319 320 /* rail transport is possible only on tiles with the same owner as vehicle */ 321 if (IsRailTT() && GetTileOwner(m_new_tile) != m_veh_owner) { 322 /* different owner */ 323 m_err = EC_NO_WAY; 324 return false; 325 } 326 327 /* rail transport is possible only on compatible rail types */ 328 if (IsRailTT()) { 329 RailType rail_type = GetTileRailType(m_new_tile); 330 if (!HasBit(m_railtypes, rail_type)) { 331 /* incompatible rail type */ 332 m_err = EC_RAIL_ROAD_TYPE; 333 return false; 334 } 335 } 336 337 /* road transport is possible only on compatible road types */ 338 if (IsRoadTT()) { 339 const RoadVehicle *v = RoadVehicle::From(m_veh); 340 RoadType roadtype = GetRoadType(m_new_tile, GetRoadTramType(v->roadtype)); 341 if (!HasBit(v->compatible_roadtypes, roadtype)) { 342 /* incompatible road type */ 343 m_err = EC_RAIL_ROAD_TYPE; 344 return false; 345 } 346 } 347 348 /* tunnel holes and bridge ramps can be entered only from proper direction */ 349 if (IsTileType(m_new_tile, MP_TUNNELBRIDGE)) { 350 if (IsTunnel(m_new_tile)) { 351 if (!m_is_tunnel) { 352 DiagDirection tunnel_enterdir = GetTunnelBridgeDirection(m_new_tile); 353 if (tunnel_enterdir != m_exitdir) { 354 m_err = EC_NO_WAY; 355 return false; 356 } 357 } 358 } else { // IsBridge(m_new_tile) 359 if (!m_is_bridge) { 360 DiagDirection ramp_enderdir = GetTunnelBridgeDirection(m_new_tile); 361 if (ramp_enderdir != m_exitdir) { 362 m_err = EC_NO_WAY; 363 return false; 364 } 365 } 366 } 367 } 368 369 /* special handling for rail stations - get to the end of platform */ 370 if (IsRailTT() && m_is_station) { 371 /* entered railway station 372 * get platform length */ 373 uint length = BaseStation::GetByTile(m_new_tile)->GetPlatformLength(m_new_tile, TrackdirToExitdir(m_old_td)); 374 /* how big step we must do to get to the last platform tile; */ 375 m_tiles_skipped = length - 1; 376 /* move to the platform end */ 377 TileIndexDiff diff = TileOffsByDiagDir(m_exitdir); 378 diff *= m_tiles_skipped; 379 m_new_tile = TILE_ADD(m_new_tile, diff); 380 return true; 381 } 382 383 return true; 384 } 385 386 /** return true if we must reverse (in depots and single tram bits) */ ForcedReverseCFollowTrackT387 inline bool ForcedReverse() 388 { 389 /* rail and road depots cause reversing */ 390 if (!IsWaterTT() && IsDepotTypeTile(m_old_tile, TT())) { 391 DiagDirection exitdir = IsRailTT() ? GetRailDepotDirection(m_old_tile) : GetRoadDepotDirection(m_old_tile); 392 if (exitdir != m_exitdir) { 393 /* reverse */ 394 m_new_tile = m_old_tile; 395 m_new_td_bits = TrackdirToTrackdirBits(ReverseTrackdir(m_old_td)); 396 m_exitdir = exitdir; 397 m_tiles_skipped = 0; 398 m_is_tunnel = m_is_bridge = m_is_station = false; 399 return true; 400 } 401 } 402 403 /* Single tram bits and standard road stops cause reversing. */ 404 if (IsRoadTT() && ((IsTram() && GetSingleTramBit(m_old_tile) == ReverseDiagDir(m_exitdir)) || 405 (IsStandardRoadStopTile(m_old_tile) && GetRoadStopDir(m_old_tile) == ReverseDiagDir(m_exitdir)))) { 406 /* reverse */ 407 m_new_tile = m_old_tile; 408 m_new_td_bits = TrackdirToTrackdirBits(ReverseTrackdir(m_old_td)); 409 m_exitdir = ReverseDiagDir(m_exitdir); 410 m_tiles_skipped = 0; 411 m_is_tunnel = m_is_bridge = m_is_station = false; 412 return true; 413 } 414 415 return false; 416 } 417 418 /** return true if we successfully reversed at end of road/track */ TryReverseCFollowTrackT419 inline bool TryReverse() 420 { 421 if (IsRoadTT() && !IsTram()) { 422 /* if we reached the end of road, we can reverse the RV and continue moving */ 423 m_exitdir = ReverseDiagDir(m_exitdir); 424 /* new tile will be the same as old one */ 425 m_new_tile = m_old_tile; 426 /* set new trackdir bits to all reachable trackdirs */ 427 QueryNewTileTrackStatus(); 428 m_new_td_bits &= DiagdirReachesTrackdirs(m_exitdir); 429 if (m_new_td_bits != TRACKDIR_BIT_NONE) { 430 /* we have some trackdirs reachable after reversal */ 431 return true; 432 } 433 } 434 m_err = EC_NO_WAY; 435 return false; 436 } 437 438 public: 439 /** Helper for pathfinders - get min/max speed on the m_old_tile/m_old_td */ GetSpeedLimitCFollowTrackT440 int GetSpeedLimit(int *pmin_speed = nullptr) const 441 { 442 int min_speed = 0; 443 int max_speed = INT_MAX; // no limit 444 445 /* Check for on-bridge speed limit */ 446 if (!IsWaterTT() && IsBridgeTile(m_old_tile)) { 447 int spd = GetBridgeSpec(GetBridgeType(m_old_tile))->speed; 448 if (IsRoadTT()) spd *= 2; 449 max_speed = std::min(max_speed, spd); 450 } 451 /* Check for speed limit imposed by railtype */ 452 if (IsRailTT()) { 453 uint16 rail_speed = GetRailTypeInfo(GetRailType(m_old_tile))->max_speed; 454 if (rail_speed > 0) max_speed = std::min<int>(max_speed, rail_speed); 455 } 456 if (IsRoadTT()) { 457 /* max_speed is already in roadvehicle units, no need to further modify (divide by 2) */ 458 uint16 road_speed = GetRoadTypeInfo(GetRoadType(m_old_tile, GetRoadTramType(RoadVehicle::From(m_veh)->roadtype)))->max_speed; 459 if (road_speed > 0) max_speed = std::min<int>(max_speed, road_speed); 460 } 461 462 /* if min speed was requested, return it */ 463 if (pmin_speed != nullptr) *pmin_speed = min_speed; 464 return max_speed; 465 } 466 }; 467 468 typedef CFollowTrackT<TRANSPORT_WATER, Ship, true > CFollowTrackWater; 469 typedef CFollowTrackT<TRANSPORT_ROAD, RoadVehicle, true > CFollowTrackRoad; 470 typedef CFollowTrackT<TRANSPORT_RAIL, Train, true > CFollowTrackRail; 471 472 typedef CFollowTrackT<TRANSPORT_RAIL, Train, false> CFollowTrackRailNo90; 473 474 typedef CFollowTrackT<TRANSPORT_RAIL, Train, true, true > CFollowTrackFreeRail; 475 typedef CFollowTrackT<TRANSPORT_RAIL, Train, false, true > CFollowTrackFreeRailNo90; 476 477 #endif /* FOLLOW_TRACK_HPP */ 478