src/pbs.cpp

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