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