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