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