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 "station_func.h"
  17 #include "pathfinder/follow_track.hpp"
  18
  19 /**
  20  * Get the reserved trackbits for any tile, regardless of type.
  21  * @param t the tile
  22  * @return the reserved trackbits. TRACK_BIT_NONE on nothing reserved or
  23  *     a tile without rail.
  24  */
  25 TrackBits GetReservedTrackbits(TileIndex t)
  26 {
  27         switch (GetTileType(t)) {
  28                 case TT_RAILWAY:
  29                         return GetRailReservationTrackBits(t);
  30
  31                 case TT_MISC:
  32                         switch (GetTileSubtype(t)) {
  33                                 case TT_MISC_CROSSING: return GetCrossingReservationTrackBits(t);
  34                                 case TT_MISC_TUNNEL:
  35                                         if (GetTunnelTransportType(t) == TRANSPORT_RAIL) return GetTunnelReservationTrackBits(t);
  36                                         break;
  37                                 case TT_MISC_DEPOT:
  38                                         if (IsRailDepot(t)) return GetDepotReservationTrackBits(t);
  39                                         break;
  40                                 default:
  41                                         break;
  42                         }
  43                         break;
  44
  45                 case TT_STATION:
  46                         if (HasStationRail(t)) return GetStationReservationTrackBits(t);
  47                         break;
  48
  49                 default:
  50                         break;
  51         }
  52         return TRACK_BIT_NONE;
  53 }
  54
  55 /**
  56  * Check whether a non-wormhole position is reserved.
  57  * @param pos the position
  58  * @return true if the track is reserved
  59  */
  60 bool HasReservedMapPos (const RailPathPos &pos)
  61 {
  62         assert (!pos.in_wormhole());
  63
  64         TileIndex tile = pos.tile;
  65         switch (GetTileType (tile)) {
  66                 case TT_RAILWAY: {
  67                         TrackBits res = GetRailReservationTrackBits (tile);
  68                         return (res & TrackToTrackBits (TrackdirToTrack (pos.td))) != TRACK_BIT_NONE;
  69                 }
  70
  71                 case TT_MISC:
  72                         switch (GetTileSubtype (tile)) {
  73                                 case TT_MISC_CROSSING:
  74                                         assert (TrackdirToTrack (pos.td) == GetCrossingRailTrack (tile));
  75                                         return HasCrossingReservation (tile);
  76
  77                                 case TT_MISC_TUNNEL:
  78                                         assert (GetTunnelTransportType (tile) == TRANSPORT_RAIL);
  79                                         return HasTunnelHeadReservation (tile);
  80
  81                                 case TT_MISC_DEPOT:
  82                                         assert (IsRailDepot (tile));
  83                                         return HasDepotReservation (tile);
  84
  85                                 default:
  86                                         NOT_REACHED();
  87                         }
  88
  89                 case TT_STATION:
  90                         assert (HasStationRail (tile));
  91                         return HasStationReservation (tile);
  92
  93                 default:
  94                         NOT_REACHED();
  95         }
  96 }
  97
  98
  99 /**
 100  * Set the reservation for a complete station platform.
 101  * @pre IsRailStationTile(start)
 102  * @param start starting tile of the platform
 103  * @param dir the direction in which to follow the platform
 104  * @param b the state the reservation should be set to
 105  */
 106 void SetRailStationPlatformReservation(TileIndex start, DiagDirection dir, bool b)
 107 {
 108         assert(IsRailStationTile(start));
 109         assert(GetRailStationAxis(start) == DiagDirToAxis(dir));
 110
 111         TileIndex     tile = start;
 112         TileIndexDiff diff = TileOffsByDiagDir(dir);
 113
 114         do {
 115                 SetRailStationReservation(tile, b);
 116                 MarkTileDirtyByTile(tile);
 117                 tile = TILE_ADD(tile, diff);
 118         } while (IsCompatibleTrainStationTile(tile, start));
 119 }
 120
 121 /**
 122  * Set the reservation for a complete station platform.
 123  * @pre !pos.in_wormhole() && IsRailStationTile(pos.tile)
 124  * @param pos starting tile and direction of the platform
 125  * @param b the state the reservation should be set to
 126  */
 127 void SetRailStationPlatformReservation(const RailPathPos &pos, bool b)
 128 {
 129         assert(!pos.in_wormhole());
 130
 131         SetRailStationPlatformReservation(pos.tile, TrackdirToExitdir(pos.td), b);
 132 }
 133
 134 /**
 135  * Try to reserve a specific track on a tile
 136  * @param tile the tile
 137  * @param t the track
 138  * @param trigger_stations whether to call station randomisation trigger
 139  * @return \c true if reservation was successful, i.e. the track was
 140  *     free and didn't cross any other reserved tracks.
 141  */
 142 bool TryReserveRailTrack(TileIndex tile, Track t, bool trigger_stations)
 143 {
 144         assert((GetTileRailwayStatus(tile) & TrackToTrackBits(t)) != 0);
 145
 146         if (_settings_client.gui.show_track_reservation) {
 147                 /* show the reserved rail if needed */
 148                 MarkTileDirtyByTile(tile);
 149         }
 150
 151         switch (GetTileType(tile)) {
 152                 case TT_RAILWAY: {
 153                         assert (HasTrack (tile, t));
 154                         TrackBits bit = TrackToTrackBits (t);
 155                         TrackBits res = GetRailReservationTrackBits (tile);
 156                         if ((res & bit) != TRACK_BIT_NONE) return false;  // already reserved
 157                         res |= bit;
 158                         if (TracksOverlap (res)) return false;  // crossing reservation present
 159                         SetTrackReservation (tile, res);
 160                         return true;
 161                 }
 162
 163                 case TT_MISC:
 164                         switch (GetTileSubtype(tile)) {
 165                                 case TT_MISC_CROSSING:
 166                                         if (HasCrossingReservation(tile)) break;
 167                                         SetCrossingReservation(tile, true);
 168                                         BarCrossing(tile);
 169                                         MarkTileDirtyByTile(tile); // crossing barred, make tile dirty
 170                                         return true;
 171
 172                                 case TT_MISC_TUNNEL:
 173                                         if (GetTunnelTransportType(tile) == TRANSPORT_RAIL && !HasTunnelHeadReservation(tile)) {
 174                                                 SetTunnelHeadReservation(tile, true);
 175                                                 return true;
 176                                         }
 177                                         break;
 178
 179                                 case TT_MISC_DEPOT:
 180                                         if (IsRailDepotTile(tile) && !HasDepotReservation(tile)) {
 181                                                 SetDepotReservation(tile, true);
 182                                                 MarkTileDirtyByTile(tile); // some GRFs change their appearance when tile is reserved
 183                                                 return true;
 184                                         }
 185                                         break;
 186
 187                                 default: break;
 188                         }
 189                         break;
 190
 191                 case TT_STATION:
 192                         if (HasStationRail(tile) && !HasStationReservation(tile)) {
 193                                 SetRailStationReservation(tile, true);
 194                                 if (trigger_stations && IsRailStation(tile)) TriggerStationRandomisation(NULL, tile, SRT_PATH_RESERVATION);
 195                                 MarkTileDirtyByTile(tile); // some GRFs need redraw after reserving track
 196                                 return true;
 197                         }
 198                         break;
 199
 200                 default:
 201                         break;
 202         }
 203         return false;
 204 }
 205
 206 /**
 207  * Lift the reservation of a specific track on a tile
 208  * @param tile the tile
 209  * @param t the track
 210  */
 211 void UnreserveRailTrack(TileIndex tile, Track t)
 212 {
 213         assert((GetTileRailwayStatus(tile) & TrackToTrackBits(t)) != 0);
 214
 215         if (_settings_client.gui.show_track_reservation) {
 216                 MarkTileDirtyByTile(tile);
 217         }
 218
 219         switch (GetTileType(tile)) {
 220                 case TT_RAILWAY: {
 221                         assert (HasTrack (tile, t));
 222                         TrackBits res = GetRailReservationTrackBits (tile);
 223                         res &= ~TrackToTrackBits (t);
 224                         SetTrackReservation (tile, res);
 225                         break;
 226                 }
 227
 228                 case TT_MISC:
 229                         switch (GetTileSubtype(tile)) {
 230                                 case TT_MISC_CROSSING:
 231                                         SetCrossingReservation(tile, false);
 232                                         UpdateLevelCrossing(tile);
 233                                         break;
 234
 235                                 case TT_MISC_TUNNEL:
 236                                         if (GetTunnelTransportType(tile) == TRANSPORT_RAIL) SetTunnelHeadReservation(tile, false);
 237                                         break;
 238
 239                                 case TT_MISC_DEPOT:
 240                                         if (IsRailDepot(tile)) {
 241                                                 SetDepotReservation(tile, false);
 242                                                 MarkTileDirtyByTile(tile);
 243                                         }
 244                                         break;
 245
 246                                 default:
 247                                         break;
 248                         }
 249                         break;
 250
 251                 case TT_STATION:
 252                         if (HasStationRail(tile)) {
 253                                 SetRailStationReservation(tile, false);
 254                                 MarkTileDirtyByTile(tile);
 255                         }
 256                         break;
 257
 258                 default:
 259                         break;
 260         }
 261 }
 262
 263
 264 /** Follow a reservation starting from a specific tile to the end. */
 265 static bool FollowReservation(Owner o, RailTypes rts, RailPathPos *pos, bool ignore_oneway = false)
 266 {
 267         assert(HasReservedPos(*pos));
 268
 269         /* Do not disallow 90 deg turns as the setting might have changed between reserving and now. */
 270         CFollowTrackRail ft(o, true, rts);
 271         ft.SetPos(*pos);
 272         RailPathPos cur = *pos;
 273         RailPathPos start;
 274
 275         while (ft.FollowNext()) {
 276                 /* No reservation --> path end found */
 277                 if (ft.m_new.in_wormhole()) {
 278                         if (!HasReservedPos(ft.m_new)) break;
 279                 } else if (ft.m_flag != ft.TF_STATION) {
 280                         TrackdirBits trackdirs = ft.m_new.trackdirs & TrackBitsToTrackdirBits(GetReservedTrackbits(ft.m_new.tile));
 281                         if (trackdirs == TRACKDIR_BIT_NONE) break;
 282
 283                         /* Can't have more than one reserved trackdir */
 284                         ft.m_new.set_trackdirs (trackdirs);
 285                 } else if (!HasStationReservation(ft.m_new.tile)) {
 286                         /* Check skipped station tiles as well, maybe our reservation ends inside the station. */
 287                         TileIndexDiff diff = TileOffsByDiagDir(ft.m_exitdir);
 288                         while (ft.m_tiles_skipped-- > 0) {
 289                                 ft.m_new.tile -= diff;
 290                                 if (HasStationReservation(ft.m_new.tile)) {
 291                                         cur = ft.m_new;
 292                                         break;
 293                                 }
 294                         }
 295                         break;
 296                 }
 297
 298                 /* One-way signal against us. The reservation can't be ours as it is not
 299                  * a safe position from our direction and we can never pass the signal. */
 300                 if (!ignore_oneway && ft.m_new.has_blocking_signal()) break;
 301
 302                 cur = ft.m_new;
 303
 304                 if (!start.is_valid_tile()) {
 305                         /* Update the start tile after we followed the track the first
 306                          * time. This is necessary because the track follower can skip
 307                          * tiles (in stations for example) which means that we might
 308                          * never visit our original starting tile again. */
 309                         start = cur;
 310                 } else {
 311                         /* Loop encountered? */
 312                         if (cur == start) break;
 313                 }
 314                 /* Depot tile? Can't continue. */
 315                 if (!cur.in_wormhole() && IsRailDepotTile(cur.tile)) break;
 316                 /* Non-pbs signal? Reservation can't continue. */
 317                 if (cur.has_signal_along() && !IsPbsSignal(cur.get_signal_type())) break;
 318         }
 319
 320         *pos = cur;
 321         /* return whether there was any further reservation at all */
 322         return start.is_valid_tile();
 323 }
 324
 325 /** Find a train on a specific tile track. */
 326 static Train *FindTrainOnTrack (TileIndex tile, Track track)
 327 {
 328         Train *best = NULL;
 329         VehicleTileIterator iter (tile);
 330         while (!iter.finished()) {
 331                 Vehicle *v = iter.next();
 332                 if (v->type != VEH_TRAIN || (v->vehstatus & VS_CRASHED)) continue;
 333
 334                 Train *t = Train::From(v);
 335                 if (TrackdirToTrack(t->trackdir) != track) continue;
 336
 337                 t = t->First();
 338
 339                 /* ALWAYS return the lowest ID (anti-desync!) */
 340                 if (best == NULL || t->index < best->index) best = t;
 341         }
 342         return best;
 343 }
 344
 345 /** Find a train in a wormhole. */
 346 static Train *FindTrainInWormhole (TileIndex tile)
 347 {
 348         Train *best = NULL;
 349         VehicleTileIterator iter (tile);
 350         while (!iter.finished()) {
 351                 Vehicle *v = iter.next();
 352                 if (v->type != VEH_TRAIN || (v->vehstatus & VS_CRASHED)) continue;
 353
 354                 Train *t = Train::From(v);
 355                 if (t->trackdir != TRACKDIR_WORMHOLE) continue;
 356
 357                 t = t->First();
 358
 359                 /* ALWAYS return the lowest ID (anti-desync!) */
 360                 if (best == NULL || t->index < best->index) best = t;
 361         }
 362         return best;
 363 }
 364
 365 /** Find a train on a reserved path end */
 366 static Train *FindTrainOnPathEnd(const RailPathPos &pos)
 367 {
 368         if (pos.in_wormhole()) {
 369                 Train *t = FindTrainInWormhole (pos.wormhole);
 370                 if (t != NULL) return t;
 371                 return FindTrainInWormhole (GetOtherTunnelBridgeEnd(pos.wormhole));
 372         } else {
 373                 Train *t = FindTrainOnTrack (pos.tile, TrackdirToTrack(pos.td));
 374                 if (t != NULL) return t;
 375
 376                 /* Special case for stations: check the whole platform for a vehicle. */
 377                 if (IsRailStationTile(pos.tile)) {
 378                         TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(pos.td)));
 379                         for (TileIndex tile = pos.tile + diff; IsCompatibleTrainStationTile(tile, pos.tile); tile += diff) {
 380                                 Train *t = FindTrainOnTrack (tile, TrackdirToTrack(pos.td));
 381                                 if (t != NULL) return t;
 382                         }
 383                 }
 384
 385                 return NULL;
 386         }
 387 }
 388
 389 /**
 390  * Follow a train reservation to the last tile.
 391  *
 392  * @param v the vehicle
 393  * @param pos Pointer to receive the last tile of the reservation or the current train tile if no reservation present
 394  * @param check Whether to check if there is another train on the reservation
 395  * @return Whether the reservation is free (no other train on it) if check was true; undefined if check was false
 396  */
 397 bool FollowTrainReservation (const Train *v, RailPathPos *pos, bool check)
 398 {
 399         assert(v->type == VEH_TRAIN);
 400
 401         /* Start track not reserved? This can happen if two trains
 402          * are on the same tile, on trackdirs ending on the same side.
 403          * The reservation on the next tile is not ours in this case.
 404          * Also, if the reservation ends on the starting position, we
 405          * will not look for a train on it, or else a train behind us
 406          * on the same track can appear to block our way, because it
 407          * would seem that our reservation ends in an occupied position. */
 408         RailPathPos res = v->GetPos();
 409         if (HasReservedPos (res)) {
 410                 bool ext = FollowReservation(v->owner, GetRailTypeInfo(v->railtype)->compatible_railtypes, &res);
 411                 assert(HasReservedPos(res));
 412                 if (ext && check) {
 413                         Train *t = FindTrainOnPathEnd(res);
 414                         if (t != NULL && t->First()->index != v->index) check = false;
 415                 }
 416         }
 417
 418         *pos = res;
 419         return check;
 420 }
 421
 422 /**
 423  * Find the train which has reserved a specific path.
 424  *
 425  * @param tile A tile on the path.
 426  * @param track A reserved track on the tile.
 427  * @param free Whether to free the reservation.
 428  * @return The vehicle holding the reservation if not heading into a depot, else NULL.
 429  */
 430 Train *GetTrainForReservation (TileIndex tile, Track track, bool free)
 431 {
 432         assert(HasReservedTrack(tile, track));
 433         Trackdir  trackdir = TrackToTrackdir(track);
 434
 435         RailTypes rts = GetRailTypeInfo(GetRailType(tile, track))->compatible_railtypes;
 436
 437         /* Follow the path from tile to both ends, one of the end tiles should
 438          * have a train on it. We need FollowReservation to ignore one-way signals
 439          * here, as one of the two search directions will be the "wrong" way. */
 440         for (int i = 0; i < 2; ++i, trackdir = ReverseTrackdir(trackdir)) {
 441                 /* If the tile has a one-way block signal in the current trackdir, skip the
 442                  * search in this direction as the reservation can't come from this side.*/
 443                 if (HasSignalOnTrackdir (tile, trackdir) &&
 444                         !HasSignalOnTrackdir (tile, ReverseTrackdir(trackdir)) &&
 445                         !IsPbsSignal (GetSignalType (tile, TrackdirToTrack (trackdir)))) continue;
 446
 447                 RailPathPos pos = RailPathPos(tile, trackdir);
 448                 FollowReservation(GetTileOwner(tile), rts, &pos, true);
 449                 Train *t = FindTrainOnPathEnd(pos);
 450                 if (t != NULL) {
 451                         assert (t->IsFrontEngine());
 452                         if (IsRailDepotTile (t->tile)) {
 453                                 Trackdir depot_td = DiagDirToDiagTrackdir (GetGroundDepotDirection (t->tile));
 454                                 if (t->trackdir != depot_td) return NULL;
 455                         }
 456                         if (free) FreeTrainTrackReservation (t);
 457                         return t;
 458                 }
 459         }
 460
 461         /* Stray reservation? */
 462         return NULL;
 463 }
 464
 465
 466 /**
 467  * Analyse a waiting position, to check if it is safe and/or if it is free.
 468  *
 469  * @param v the vehicle to test for
 470  * @param pos The position
 471  * @param forbid_90deg Don't allow trains to make 90 degree turns
 472  * @param cb Checking behaviour
 473  * @return Depending on cb:
 474  *  * PBS_CHECK_FULL: Do a full check. Return PBS_UNSAFE, PBS_BUSY, PBS_FREE
 475  *    depending on the waiting position state.
 476  *  * PBS_CHECK_SAFE: Only check if the position is safe. Return PBS_UNSAFE
 477  *    iff it is not.
 478  *  * PBS_CHECK_FREE: Assume that the position is safe, and check if it is
 479  *    free. Return PBS_FREE iff it is. The behaviour is undefined if the
 480  *    position is actually not safe.
 481  *  * PBS_CHECK_SAFE_FREE: Check if the position is both safe and free.
 482  *    Return PBS_FREE iff it is.
 483  */
 484 PBSPositionState CheckWaitingPosition(const Train *v, const RailPathPos &pos, bool forbid_90deg, PBSCheckingBehaviour cb)
 485 {
 486         PBSPositionState state;
 487         if (pos.in_wormhole()) {
 488                 if ((cb != PBS_CHECK_SAFE) && HasReservedPos(pos)) {
 489                         /* Track reserved? Can never be a free waiting position. */
 490                         if (cb != PBS_CHECK_FULL) return PBS_BUSY;
 491                         state = PBS_BUSY;
 492                 } else {
 493                         /* Track not reserved or we do not care (PBS_CHECK_SAFE). */
 494                         state = PBS_FREE;
 495                 }
 496         } else {
 497                 /* Depots are always safe, and free iff unreserved. */
 498                 if (IsRailDepotTile(pos.tile) && pos.td == DiagDirToDiagTrackdir(ReverseDiagDir(GetGroundDepotDirection(pos.tile)))) return HasDepotReservation(pos.tile) ? PBS_BUSY : PBS_FREE;
 499
 500                 if (pos.has_signal_along() && !IsPbsSignal(pos.get_signal_type())) {
 501                         /* For non-pbs signals, stop on the signal tile. */
 502                         if (cb == PBS_CHECK_SAFE) return PBS_FREE;
 503                         return HasReservedTrack(pos.tile, TrackdirToTrack(pos.td)) ? PBS_BUSY : PBS_FREE;
 504                 }
 505
 506                 if ((cb != PBS_CHECK_SAFE) && TrackOverlapsTracks(GetReservedTrackbits(pos.tile), TrackdirToTrack(pos.td))) {
 507                         /* Track reserved? Can never be a free waiting position. */
 508                         if (cb != PBS_CHECK_FULL) return PBS_BUSY;
 509                         state = PBS_BUSY;
 510                 } else {
 511                         /* Track not reserved or we do not care (PBS_CHECK_SAFE). */
 512                         state = PBS_FREE;
 513                 }
 514         }
 515
 516         /* Check next tile. */
 517         CFollowTrackRail ft(v, !forbid_90deg, v->railtype);
 518
 519         /* End of track? Safe position. */
 520         if (!ft.Follow(pos)) return state;
 521
 522         assert(!ft.m_new.is_empty());
 523         assert((state == PBS_FREE) || (cb == PBS_CHECK_FULL));
 524
 525         if (cb != PBS_CHECK_FREE) {
 526                 if (!ft.m_new.is_single()) return PBS_UNSAFE;
 527
 528                 if (ft.m_new.has_signal_along()) {
 529                         /* PBS signal on next trackdir? Safe position. */
 530                         if (!IsPbsSignal(ft.m_new.get_signal_type())) return PBS_UNSAFE;
 531                 } else if (ft.m_new.has_signal_against()) {
 532                         /* One-way PBS signal against us? Safe position. */
 533                         if (ft.m_new.get_signal_type() != SIGTYPE_PBS_ONEWAY) return PBS_UNSAFE;
 534                 } else {
 535                         /* No signal at all? Unsafe position. */
 536                         return PBS_UNSAFE;
 537                 }
 538
 539                 if (cb == PBS_CHECK_SAFE) return PBS_FREE;
 540                 if (state != PBS_FREE) return PBS_BUSY;
 541         } else if (!IsStationTile(pos.tile)) {
 542                 /* With PBS_CHECK_FREE, all these should be true. */
 543                 assert(ft.m_new.is_single());
 544                 assert(ft.m_new.has_signals());
 545                 assert(IsPbsSignal(ft.m_new.get_signal_type()));
 546         }
 547
 548         assert(state == PBS_FREE);
 549
 550         return HasReservedPos(ft.m_new) ? PBS_BUSY : PBS_FREE;
 551 }