src/pbs.cpp

   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 pbs.cpp PBS support routines */
   9
  10 #include "stdafx.h"
  11 #include "viewport_func.h"
  12 #include "vehicle_func.h"
  13 #include "newgrf_station.h"
  14 #include "pathfinder/follow_track.hpp"
  15
  16 #include "safeguards.h"
  17
  18 /**
  19  * Get the reserved trackbits for any tile, regardless of type.
  20  * @param t the tile
  21  * @return the reserved trackbits. TRACK_BIT_NONE on nothing reserved or
  22  *     a tile without rail.
  23  */
  24 TrackBits GetReservedTrackbits(TileIndex t)
  25 {
  26         switch (GetTileType(t)) {
  27                 case MP_RAILWAY:
  28                         if (IsRailDepot(t)) return GetDepotReservationTrackBits(t);
  29                         if (IsPlainRail(t)) return GetRailReservationTrackBits(t);
  30                         break;
  31
  32                 case MP_ROAD:
  33                         if (IsLevelCrossing(t)) return GetCrossingReservationTrackBits(t);
  34                         break;
  35
  36                 case MP_STATION:
  37                         if (HasStationRail(t)) return GetStationReservationTrackBits(t);
  38                         break;
  39
  40                 case MP_TUNNELBRIDGE:
  41                         if (GetTunnelBridgeTransportType(t) == TRANSPORT_RAIL) return GetTunnelBridgeReservationTrackBits(t);
  42                         break;
  43
  44                 default:
  45                         break;
  46         }
  47         return TRACK_BIT_NONE;
  48 }
  49
  50 /**
  51  * Set the reservation for a complete station platform.
  52  * @pre IsRailStationTile(start)
  53  * @param start starting tile of the platform
  54  * @param dir the direction in which to follow the platform
  55  * @param b the state the reservation should be set to
  56  */
  57 void SetRailStationPlatformReservation(TileIndex start, DiagDirection dir, bool b)
  58 {
  59         TileIndex     tile = start;
  60         TileIndexDiff diff = TileOffsByDiagDir(dir);
  61
  62         assert(IsRailStationTile(start));
  63         assert(GetRailStationAxis(start) == DiagDirToAxis(dir));
  64
  65         do {
  66                 SetRailStationReservation(tile, b);
  67                 MarkTileDirtyByTile(tile);
  68                 tile = TILE_ADD(tile, diff);
  69         } while (IsCompatibleTrainStationTile(tile, start));
  70 }
  71
  72 /**
  73  * Try to reserve a specific track on a tile
  74  * @param tile the tile
  75  * @param t the track
  76  * @param trigger_stations whether to call station randomisation trigger
  77  * @return \c true if reservation was successful, i.e. the track was
  78  *     free and didn't cross any other reserved tracks.
  79  */
  80 bool TryReserveRailTrack(TileIndex tile, Track t, bool trigger_stations)
  81 {
  82         assert(HasTrack(TrackStatusToTrackBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)), t));
  83
  84         if (_settings_client.gui.show_track_reservation) {
  85                 /* show the reserved rail if needed */
  86                 if (IsBridgeTile(tile)) {
  87                         MarkBridgeDirty(tile);
  88                 } else {
  89                         MarkTileDirtyByTile(tile);
  90                 }
  91         }
  92
  93         switch (GetTileType(tile)) {
  94                 case MP_RAILWAY:
  95                         if (IsPlainRail(tile)) return TryReserveTrack(tile, t);
  96                         if (IsRailDepot(tile)) {
  97                                 if (!HasDepotReservation(tile)) {
  98                                         SetDepotReservation(tile, true);
  99                                         MarkTileDirtyByTile(tile); // some GRFs change their appearance when tile is reserved
 100                                         return true;
 101                                 }
 102                         }
 103                         break;
 104
 105                 case MP_ROAD:
 106                         if (IsLevelCrossing(tile) && !HasCrossingReservation(tile)) {
 107                                 SetCrossingReservation(tile, true);
 108                                 UpdateLevelCrossing(tile, false);
 109                                 return true;
 110                         }
 111                         break;
 112
 113                 case MP_STATION:
 114                         if (HasStationRail(tile) && !HasStationReservation(tile)) {
 115                                 SetRailStationReservation(tile, true);
 116                                 if (trigger_stations && IsRailStation(tile)) TriggerStationRandomisation(nullptr, tile, SRT_PATH_RESERVATION);
 117                                 MarkTileDirtyByTile(tile); // some GRFs need redraw after reserving track
 118                                 return true;
 119                         }
 120                         break;
 121
 122                 case MP_TUNNELBRIDGE:
 123                         if (GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL && !GetTunnelBridgeReservationTrackBits(tile)) {
 124                                 SetTunnelBridgeReservation(tile, true);
 125                                 return true;
 126                         }
 127                         break;
 128
 129                 default:
 130                         break;
 131         }
 132         return false;
 133 }
 134
 135 /**
 136  * Lift the reservation of a specific track on a tile
 137  * @param tile the tile
 138  * @param t the track
 139  */
 140 void UnreserveRailTrack(TileIndex tile, Track t)
 141 {
 142         assert(HasTrack(TrackStatusToTrackBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)), t));
 143
 144         if (_settings_client.gui.show_track_reservation) {
 145                 if (IsBridgeTile(tile)) {
 146                         MarkBridgeDirty(tile);
 147                 } else {
 148                         MarkTileDirtyByTile(tile);
 149                 }
 150         }
 151
 152         switch (GetTileType(tile)) {
 153                 case MP_RAILWAY:
 154                         if (IsRailDepot(tile)) {
 155                                 SetDepotReservation(tile, false);
 156                                 MarkTileDirtyByTile(tile);
 157                                 break;
 158                         }
 159                         if (IsPlainRail(tile)) UnreserveTrack(tile, t);
 160                         break;
 161
 162                 case MP_ROAD:
 163                         if (IsLevelCrossing(tile)) {
 164                                 SetCrossingReservation(tile, false);
 165                                 UpdateLevelCrossing(tile);
 166                         }
 167                         break;
 168
 169                 case MP_STATION:
 170                         if (HasStationRail(tile)) {
 171                                 SetRailStationReservation(tile, false);
 172                                 MarkTileDirtyByTile(tile);
 173                         }
 174                         break;
 175
 176                 case MP_TUNNELBRIDGE:
 177                         if (GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL) SetTunnelBridgeReservation(tile, false);
 178                         break;
 179
 180                 default:
 181                         break;
 182         }
 183 }
 184
 185
 186 /** Follow a reservation starting from a specific tile to the end. */
 187 static PBSTileInfo FollowReservation(Owner o, RailTypes rts, TileIndex tile, Trackdir trackdir, bool ignore_oneway = false)
 188 {
 189         TileIndex start_tile = tile;
 190         Trackdir  start_trackdir = trackdir;
 191         bool      first_loop = true;
 192
 193         /* Start track not reserved? This can happen if two trains
 194          * are on the same tile. The reservation on the next tile
 195          * is not ours in this case, so exit. */
 196         if (!HasReservedTracks(tile, TrackToTrackBits(TrackdirToTrack(trackdir)))) return PBSTileInfo(tile, trackdir, false);
 197
 198         /* Do not disallow 90 deg turns as the setting might have changed between reserving and now. */
 199         CFollowTrackRail ft(o, rts);
 200         while (ft.Follow(tile, trackdir)) {
 201                 TrackdirBits reserved = ft.m_new_td_bits & TrackBitsToTrackdirBits(GetReservedTrackbits(ft.m_new_tile));
 202
 203                 /* No reservation --> path end found */
 204                 if (reserved == TRACKDIR_BIT_NONE) {
 205                         if (ft.m_is_station) {
 206                                 /* Check skipped station tiles as well, maybe our reservation ends inside the station. */
 207                                 TileIndexDiff diff = TileOffsByDiagDir(ft.m_exitdir);
 208                                 while (ft.m_tiles_skipped-- > 0) {
 209                                         ft.m_new_tile -= diff;
 210                                         if (HasStationReservation(ft.m_new_tile)) {
 211                                                 tile = ft.m_new_tile;
 212                                                 trackdir = DiagDirToDiagTrackdir(ft.m_exitdir);
 213                                                 break;
 214                                         }
 215                                 }
 216                         }
 217                         break;
 218                 }
 219
 220                 /* Can't have more than one reserved trackdir */
 221                 Trackdir new_trackdir = FindFirstTrackdir(reserved);
 222
 223                 /* One-way signal against us. The reservation can't be ours as it is not
 224                  * a safe position from our direction and we can never pass the signal. */
 225                 if (!ignore_oneway && HasOnewaySignalBlockingTrackdir(ft.m_new_tile, new_trackdir)) break;
 226
 227                 tile = ft.m_new_tile;
 228                 trackdir = new_trackdir;
 229
 230                 if (first_loop) {
 231                         /* Update the start tile after we followed the track the first
 232                          * time. This is necessary because the track follower can skip
 233                          * tiles (in stations for example) which means that we might
 234                          * never visit our original starting tile again. */
 235                         start_tile = tile;
 236                         start_trackdir = trackdir;
 237                         first_loop = false;
 238                 } else {
 239                         /* Loop encountered? */
 240                         if (tile == start_tile && trackdir == start_trackdir) break;
 241                 }
 242                 /* Depot tile? Can't continue. */
 243                 if (IsRailDepotTile(tile)) break;
 244                 /* Non-pbs signal? Reservation can't continue. */
 245                 if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) break;
 246         }
 247
 248         return PBSTileInfo(tile, trackdir, false);
 249 }
 250
 251 /**
 252  * Helper struct for finding the best matching vehicle on a specific track.
 253  */
 254 struct FindTrainOnTrackInfo {
 255         PBSTileInfo res; ///< Information about the track.
 256         Train *best;     ///< The currently "best" vehicle we have found.
 257
 258         /** Init the best location to nullptr always! */
 259         FindTrainOnTrackInfo() : best(nullptr) {}
 260 };
 261
 262 /** Callback for Has/FindVehicleOnPos to find a train on a specific track. */
 263 static Vehicle *FindTrainOnTrackEnum(Vehicle *v, void *data)
 264 {
 265         FindTrainOnTrackInfo *info = (FindTrainOnTrackInfo *)data;
 266
 267         if (v->type != VEH_TRAIN || (v->vehstatus & VS_CRASHED)) return nullptr;
 268
 269         Train *t = Train::From(v);
 270         if (t->track == TRACK_BIT_WORMHOLE || HasBit((TrackBits)t->track, TrackdirToTrack(info->res.trackdir))) {
 271                 t = t->First();
 272
 273                 /* ALWAYS return the lowest ID (anti-desync!) */
 274                 if (info->best == nullptr || t->index < info->best->index) info->best = t;
 275                 return t;
 276         }
 277
 278         return nullptr;
 279 }
 280
 281 /**
 282  * Follow a train reservation to the last tile.
 283  *
 284  * @param v the vehicle
 285  * @param train_on_res Is set to a train we might encounter
 286  * @returns The last tile of the reservation or the current train tile if no reservation present.
 287  */
 288 PBSTileInfo FollowTrainReservation(const Train *v, Vehicle **train_on_res)
 289 {
 290         assert(v->type == VEH_TRAIN);
 291
 292         TileIndex tile = v->tile;
 293         Trackdir  trackdir = v->GetVehicleTrackdir();
 294
 295         if (IsRailDepotTile(tile) && !GetDepotReservationTrackBits(tile)) return PBSTileInfo(tile, trackdir, false);
 296
 297         FindTrainOnTrackInfo ftoti;
 298         ftoti.res = FollowReservation(v->owner, GetRailTypeInfo(v->railtype)->compatible_railtypes, tile, trackdir);
 299         ftoti.res.okay = IsSafeWaitingPosition(v, ftoti.res.tile, ftoti.res.trackdir, true, _settings_game.pf.forbid_90_deg);
 300         if (train_on_res != nullptr) {
 301                 FindVehicleOnPos(ftoti.res.tile, &ftoti, FindTrainOnTrackEnum);
 302                 if (ftoti.best != nullptr) *train_on_res = ftoti.best->First();
 303                 if (*train_on_res == nullptr && IsRailStationTile(ftoti.res.tile)) {
 304                         /* The target tile is a rail station. The track follower
 305                          * has stopped on the last platform tile where we haven't
 306                          * found a train. Also check all previous platform tiles
 307                          * for a possible train. */
 308                         TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(ftoti.res.trackdir)));
 309                         for (TileIndex st_tile = ftoti.res.tile + diff; *train_on_res == nullptr && IsCompatibleTrainStationTile(st_tile, ftoti.res.tile); st_tile += diff) {
 310                                 FindVehicleOnPos(st_tile, &ftoti, FindTrainOnTrackEnum);
 311                                 if (ftoti.best != nullptr) *train_on_res = ftoti.best->First();
 312                         }
 313                 }
 314                 if (*train_on_res == nullptr && IsTileType(ftoti.res.tile, MP_TUNNELBRIDGE)) {
 315                         /* The target tile is a bridge/tunnel, also check the other end tile. */
 316                         FindVehicleOnPos(GetOtherTunnelBridgeEnd(ftoti.res.tile), &ftoti, FindTrainOnTrackEnum);
 317                         if (ftoti.best != nullptr) *train_on_res = ftoti.best->First();
 318                 }
 319         }
 320         return ftoti.res;
 321 }
 322
 323 /**
 324  * Find the train which has reserved a specific path.
 325  *
 326  * @param tile A tile on the path.
 327  * @param track A reserved track on the tile.
 328  * @return The vehicle holding the reservation or nullptr if the path is stray.
 329  */
 330 Train *GetTrainForReservation(TileIndex tile, Track track)
 331 {
 332         assert(HasReservedTracks(tile, TrackToTrackBits(track)));
 333         Trackdir  trackdir = TrackToTrackdir(track);
 334
 335         RailTypes rts = GetRailTypeInfo(GetTileRailType(tile))->compatible_railtypes;
 336
 337         /* Follow the path from tile to both ends, one of the end tiles should
 338          * have a train on it. We need FollowReservation to ignore one-way signals
 339          * here, as one of the two search directions will be the "wrong" way. */
 340         for (int i = 0; i < 2; ++i, trackdir = ReverseTrackdir(trackdir)) {
 341                 /* If the tile has a one-way block signal in the current trackdir, skip the
 342                  * search in this direction as the reservation can't come from this side.*/
 343                 if (HasOnewaySignalBlockingTrackdir(tile, ReverseTrackdir(trackdir)) && !HasPbsSignalOnTrackdir(tile, trackdir)) continue;
 344
 345                 FindTrainOnTrackInfo ftoti;
 346                 ftoti.res = FollowReservation(GetTileOwner(tile), rts, tile, trackdir, true);
 347
 348                 FindVehicleOnPos(ftoti.res.tile, &ftoti, FindTrainOnTrackEnum);
 349                 if (ftoti.best != nullptr) return ftoti.best;
 350
 351                 /* Special case for stations: check the whole platform for a vehicle. */
 352                 if (IsRailStationTile(ftoti.res.tile)) {
 353                         TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(ftoti.res.trackdir)));
 354                         for (TileIndex st_tile = ftoti.res.tile + diff; IsCompatibleTrainStationTile(st_tile, ftoti.res.tile); st_tile += diff) {
 355                                 FindVehicleOnPos(st_tile, &ftoti, FindTrainOnTrackEnum);
 356                                 if (ftoti.best != nullptr) return ftoti.best;
 357                         }
 358                 }
 359
 360                 /* Special case for bridges/tunnels: check the other end as well. */
 361                 if (IsTileType(ftoti.res.tile, MP_TUNNELBRIDGE)) {
 362                         FindVehicleOnPos(GetOtherTunnelBridgeEnd(ftoti.res.tile), &ftoti, FindTrainOnTrackEnum);
 363                         if (ftoti.best != nullptr) return ftoti.best;
 364                 }
 365         }
 366
 367         return nullptr;
 368 }
 369
 370 /**
 371  * Determine whether a certain track on a tile is a safe position to end a path.
 372  *
 373  * @param v the vehicle to test for
 374  * @param tile The tile
 375  * @param trackdir The trackdir to test
 376  * @param include_line_end Should end-of-line tiles be considered safe?
 377  * @param forbid_90deg Don't allow trains to make 90 degree turns
 378  * @return True if it is a safe position
 379  */
 380 bool IsSafeWaitingPosition(const Train *v, TileIndex tile, Trackdir trackdir, bool include_line_end, bool forbid_90deg)
 381 {
 382         if (IsRailDepotTile(tile)) return true;
 383
 384         if (IsTileType(tile, MP_RAILWAY)) {
 385                 /* For non-pbs signals, stop on the signal tile. */
 386                 if (HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) return true;
 387         }
 388
 389         /* Check next tile. For performance reasons, we check for 90 degree turns ourself. */
 390         CFollowTrackRail ft(v, GetRailTypeInfo(v->railtype)->compatible_railtypes);
 391
 392         /* End of track? */
 393         if (!ft.Follow(tile, trackdir)) {
 394                 /* Last tile of a terminus station is a safe position. */
 395                 if (include_line_end) return true;
 396         }
 397
 398         /* Check for reachable tracks. */
 399         ft.m_new_td_bits &= DiagdirReachesTrackdirs(ft.m_exitdir);
 400         if (Rail90DegTurnDisallowed(GetTileRailType(ft.m_old_tile), GetTileRailType(ft.m_new_tile), forbid_90deg)) ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(trackdir);
 401         if (ft.m_new_td_bits == TRACKDIR_BIT_NONE) return include_line_end;
 402
 403         if (ft.m_new_td_bits != TRACKDIR_BIT_NONE && KillFirstBit(ft.m_new_td_bits) == TRACKDIR_BIT_NONE) {
 404                 Trackdir td = FindFirstTrackdir(ft.m_new_td_bits);
 405                 /* PBS signal on next trackdir? Safe position. */
 406                 if (HasPbsSignalOnTrackdir(ft.m_new_tile, td)) return true;
 407                 /* One-way PBS signal against us? Safe if end-of-line is allowed. */
 408                 if (IsTileType(ft.m_new_tile, MP_RAILWAY) && HasSignalOnTrackdir(ft.m_new_tile, ReverseTrackdir(td)) &&
 409                                 GetSignalType(ft.m_new_tile, TrackdirToTrack(td)) == SIGTYPE_PBS_ONEWAY) {
 410                         return include_line_end;
 411                 }
 412         }
 413
 414         return false;
 415 }
 416
 417 /**
 418  * Check if a safe position is free.
 419  *
 420  * @param v the vehicle to test for
 421  * @param tile The tile
 422  * @param trackdir The trackdir to test
 423  * @param forbid_90deg Don't allow trains to make 90 degree turns
 424  * @return True if the position is free
 425  */
 426 bool IsWaitingPositionFree(const Train *v, TileIndex tile, Trackdir trackdir, bool forbid_90deg)
 427 {
 428         Track     track = TrackdirToTrack(trackdir);
 429         TrackBits reserved = GetReservedTrackbits(tile);
 430
 431         /* Tile reserved? Can never be a free waiting position. */
 432         if (TrackOverlapsTracks(reserved, track)) return false;
 433
 434         /* Not reserved and depot or not a pbs signal -> free. */
 435         if (IsRailDepotTile(tile)) return true;
 436         if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, track))) return true;
 437
 438         /* Check the next tile, if it's a PBS signal, it has to be free as well. */
 439         CFollowTrackRail ft(v, GetRailTypeInfo(v->railtype)->compatible_railtypes);
 440
 441         if (!ft.Follow(tile, trackdir)) return true;
 442
 443         /* Check for reachable tracks. */
 444         ft.m_new_td_bits &= DiagdirReachesTrackdirs(ft.m_exitdir);
 445         if (Rail90DegTurnDisallowed(GetTileRailType(ft.m_old_tile), GetTileRailType(ft.m_new_tile), forbid_90deg)) ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(trackdir);
 446
 447         return !HasReservedTracks(ft.m_new_tile, TrackdirBitsToTrackBits(ft.m_new_td_bits));
 448 }