src/signal.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 signal.cpp functions related to rail signals updating */
  11
  12 #include "stdafx.h"
  13 #include "debug.h"
  14 #include "map/road.h"
  15 #include "map/bridge.h"
  16 #include "vehicle_func.h"
  17 #include "viewport_func.h"
  18 #include "train.h"
  19 #include "company_base.h"
  20 #include "signal_func.h"
  21 #include "station_func.h"
  22 #include "signal_map.h"
  23
  24
  25 /** these are the maximums used for updating signal blocks */
  26 static const uint SIG_TBU_SIZE    =  64; ///< number of signals entering to block
  27 static const uint SIG_TBD_SIZE    = 256; ///< number of intersections - open nodes in current block
  28 static const uint SIG_GLOB_SIZE   = 128; ///< number of open blocks (block can be opened more times until detected)
  29 static const uint SIG_GLOB_UPDATE =  64; ///< how many items need to be in _globset to force update
  30
  31 assert_compile(SIG_GLOB_UPDATE <= SIG_GLOB_SIZE);
  32
  33 /** incidating trackbits with given enterdir */
  34 static const TrackBits _enterdir_to_trackbits[DIAGDIR_END] = {
  35         TRACK_BIT_3WAY_NE,
  36         TRACK_BIT_3WAY_SE,
  37         TRACK_BIT_3WAY_SW,
  38         TRACK_BIT_3WAY_NW
  39 };
  40
  41 /** incidating trackdirbits with given enterdir */
  42 static const TrackdirBits _enterdir_to_trackdirbits[DIAGDIR_END] = {
  43         TRACKDIR_BIT_X_SW | TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_RIGHT_S,
  44         TRACKDIR_BIT_Y_NW | TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_RIGHT_N,
  45         TRACKDIR_BIT_X_NE | TRACKDIR_BIT_LOWER_E | TRACKDIR_BIT_LEFT_N,
  46         TRACKDIR_BIT_Y_SE | TRACKDIR_BIT_UPPER_E | TRACKDIR_BIT_LEFT_S
  47 };
  48
  49 /**
  50  * Set containing up to 'maxitems' items of 'T'
  51  * No tree structure is used because it would cause
  52  * slowdowns in most usual cases
  53  */
  54 template <typename T, uint maxitems>
  55 struct SmallSet {
  56 private:
  57         uint n;           // actual number of units
  58         bool overflowed;  // did we try to overflow the set?
  59         const char *name; // name, used for debugging purposes...
  60         T data[maxitems]; // elements of set
  61
  62 public:
  63         /** Constructor - just set default values and 'name' */
  64         SmallSet(const char *name) : n(0), overflowed(false), name(name) { }
  65
  66         /** Reset variables to default values */
  67         void Reset()
  68         {
  69                 this->n = 0;
  70                 this->overflowed = false;
  71         }
  72
  73         /**
  74          * Returns value of 'overflowed'
  75          * @return did we try to overflow the set?
  76          */
  77         bool Overflowed()
  78         {
  79                 return this->overflowed;
  80         }
  81
  82         /**
  83          * Checks for empty set
  84          * @return is the set empty?
  85          */
  86         bool IsEmpty()
  87         {
  88                 return this->n == 0;
  89         }
  90
  91         /**
  92          * Checks for full set
  93          * @return is the set full?
  94          */
  95         bool IsFull()
  96         {
  97                 return this->n == lengthof(data);
  98         }
  99
 100         /**
 101          * Reads the number of items
 102          * @return current number of items
 103          */
 104         uint Items()
 105         {
 106                 return this->n;
 107         }
 108
 109
 110         /**
 111          * Tries to remove first instance of given item
 112          * @param item item to remove
 113          * @return element was found and removed
 114          */
 115         bool Remove(const T &item)
 116         {
 117                 for (uint i = 0; i < this->n; i++) {
 118                         if (this->data[i] == item) {
 119                                 this->data[i] = this->data[--this->n];
 120                                 return true;
 121                         }
 122                 }
 123
 124                 return false;
 125         }
 126
 127         /**
 128          * Tries to find given item in the set
 129          * @param item item to find
 130          * @return true iff the item was found
 131          */
 132         bool IsIn(const T &item)
 133         {
 134                 for (uint i = 0; i < this->n; i++) {
 135                         if (this->data[i] == item) return true;
 136                 }
 137
 138                 return false;
 139         }
 140
 141         /**
 142          * Adds item into the set, checks for full set
 143          * Sets the 'overflowed' flag if the set was full
 144          * @param item item to add
 145          * @return true iff the item could be added (set wasn't full)
 146          */
 147         bool Add(const T &item)
 148         {
 149                 if (this->IsFull()) {
 150                         overflowed = true;
 151                         DEBUG(misc, 0, "SignalSegment too complex. Set %s is full (maximum %d)", name, maxitems);
 152                         return false; // set is full
 153                 }
 154
 155                 this->data[this->n] = item;
 156                 this->n++;
 157
 158                 return true;
 159         }
 160
 161         /**
 162          * Reads the last added element into the set
 163          * @param item pointer where the item is written to
 164          * @return false iff the set was empty
 165          */
 166         bool Get(T *item)
 167         {
 168                 if (this->n == 0) return false;
 169
 170                 this->n--;
 171                 *item = this->data[this->n];
 172
 173                 return true;
 174         }
 175 };
 176
 177
 178 struct SignalPos {
 179         TileIndex tile;
 180         Trackdir td;
 181
 182         bool operator == (const SignalPos &other) const {
 183                 return (tile == other.tile) && (td == other.td);
 184         }
 185 };
 186
 187 static SignalPos SignalPosFrom(TileIndex tile, Trackdir td)
 188 {
 189         SignalPos pos = { tile, td };
 190         return pos;
 191 }
 192
 193 enum SignalSideEnum {
 194         SIDE_NE = DIAGDIR_NE,
 195         SIDE_SE = DIAGDIR_SE,
 196         SIDE_SW = DIAGDIR_SW,
 197         SIDE_NW = DIAGDIR_NW,
 198         SIDE_INTO_BRIDGE,
 199         SIDE_FROM_BRIDGE,
 200         SIDE_INTO_TUNNEL,
 201         SIDE_FROM_TUNNEL,
 202         SIDE_DEPOT,
 203 };
 204
 205 /** Allow incrementing of SignalSideEnum variables */
 206 DECLARE_POSTFIX_INCREMENT(SignalSideEnum)
 207
 208 struct SignalSide {
 209         TileIndex tile;
 210         SignalSideEnum side;
 211
 212         bool operator == (const SignalSide &other) const {
 213                 return (tile == other.tile) && (side == other.side);
 214         }
 215 };
 216
 217 static SignalSide SignalSideFrom(TileIndex tile, SignalSideEnum side)
 218 {
 219         SignalSide ss = { tile, side };
 220         return ss;
 221 }
 222
 223 static SmallSet<SignalPos,  SIG_TBU_SIZE>  _tbuset("_tbuset");   ///< set of signals that will be updated
 224 static SmallSet<SignalSide, SIG_TBD_SIZE>  _tbdset("_tbdset");   ///< set of open nodes in current signal block
 225 static SmallSet<SignalSide, SIG_GLOB_SIZE> _globset("_globset"); ///< set of places to be updated in following runs
 226 static Owner _owner = INVALID_OWNER; ///< owner of tracks in _globset, or INVALID_OWNER if empty
 227
 228
 229 /** Check if there is a train on a tile, not in a depot. */
 230 static bool HasTrainOnTile (TileIndex tile)
 231 {
 232         VehicleTileFinder iter (tile);
 233         while (!iter.finished()) {
 234                 Vehicle *v = iter.next();
 235                 if (v->type == VEH_TRAIN && Train::From(v)->trackdir != TRACKDIR_DEPOT) {
 236                         iter.set_found();
 237                 }
 238         }
 239         return iter.was_found();
 240 }
 241
 242
 243 /**
 244  * Perform some operations before adding data into Todo set
 245  * The new and reverse direction is removed from Global set, because we are sure
 246  * it doesn't need to be checked again
 247  * Also, remove reverse direction from Todo set
 248  * This is the 'core' part so the graph searching won't enter any tile twice
 249  *
 250  * @param ss1 tile and side we are entering
 251  * @param ss2 tile and side we are leaving
 252  * @return false iff the Todo buffer would be overrun
 253  */
 254 static inline bool MaybeAddToTodoSet(const SignalSide &ss1, const SignalSide &ss2)
 255 {
 256         _globset.Remove(ss1); // it can be in Global but not in Todo
 257         _globset.Remove(ss2); // remove in all cases
 258
 259         assert(!_tbdset.IsIn(ss1)); // it really shouldn't be there already
 260
 261         if (_tbdset.Remove(ss2)) return true;
 262
 263         return _tbdset.Add(ss1);
 264 }
 265
 266
 267 /** Current signal block state flags */
 268 enum SigFlags {
 269         SF_NONE   = 0,
 270         SF_TRAIN  = 1 << 0, ///< train found in segment
 271         SF_EXIT   = 1 << 1, ///< exitsignal found
 272         SF_EXIT2  = 1 << 2, ///< two or more exits found
 273         SF_GREEN  = 1 << 3, ///< green exitsignal found
 274         SF_GREEN2 = 1 << 4, ///< two or more green exits found
 275         SF_FULL   = 1 << 5, ///< some of buffers was full, do not continue
 276         SF_PBS    = 1 << 6, ///< pbs signal found
 277 };
 278
 279 DECLARE_ENUM_AS_BIT_SET(SigFlags)
 280
 281
 282 /**
 283  * Search signal block
 284  *
 285  * @param owner owner whose signals we are updating
 286  * @return SigFlags
 287  */
 288 static SigFlags ExploreSegment(Owner owner)
 289 {
 290         SigFlags flags = SF_NONE;
 291
 292         SignalSide ss;
 293
 294         while (_tbdset.Get(&ss)) {
 295                 SignalSide newss;
 296                 newss.tile = ss.tile; // tile we will enter
 297
 298                 switch (GetTileType(ss.tile)) {
 299                         case TT_RAILWAY: {
 300                                 if (GetTileOwner(ss.tile) != owner) continue; // do not propagate signals on others' tiles (remove for tracksharing)
 301
 302                                 if (IsTileSubtype(ss.tile, TT_BRIDGE)) {
 303                                         DiagDirection dir = GetTunnelBridgeDirection(ss.tile);
 304                                         if (ss.side == (SignalSideEnum)dir) continue;
 305                                         if (ss.side == SIDE_INTO_BRIDGE) {
 306                                                 newss.tile = GetOtherBridgeEnd(ss.tile); // skip to exit tile
 307                                                 if (!(flags & SF_TRAIN) && EnsureNoTrainOnTunnelBridgeMiddle(ss.tile, newss.tile).Failed()) flags |= SF_TRAIN;
 308                                                 newss.side = SIDE_FROM_BRIDGE;
 309                                                 ss.tile = newss.tile;
 310                                                 ss.side = SIDE_INTO_BRIDGE;
 311                                                 break;
 312                                         }
 313                                         if (ss.side == SIDE_FROM_BRIDGE) ss.side = (SignalSideEnum)dir;
 314                                 }
 315
 316                                 assert(IsValidDiagDirection((DiagDirection)ss.side));
 317
 318                                 TrackBits tracks = GetTrackBits(ss.tile); // trackbits of tile
 319                                 TrackBits tracks_masked = (TrackBits)(tracks & _enterdir_to_trackbits[ss.side]); // only incidating trackbits
 320
 321                                 if (tracks == TRACK_BIT_HORZ || tracks == TRACK_BIT_VERT) { // there is exactly one incidating track, no need to check
 322                                         tracks = tracks_masked;
 323                                 } else {
 324                                         if (tracks_masked == TRACK_BIT_NONE) continue; // no incidating track
 325                                 }
 326
 327                                 assert((tracks_masked & ~tracks) == TRACK_BIT_NONE); // tracks_masked must be a subset of tracks
 328                                 assert(tracks_masked != TRACK_BIT_NONE);
 329                                 assert(tracks_masked != TRACK_BIT_HORZ);
 330                                 assert(tracks_masked != TRACK_BIT_VERT);
 331                                 assert(tracks != TRACK_BIT_HORZ);
 332                                 assert(tracks != TRACK_BIT_VERT);
 333
 334                                 if (HasAtMostOneBit(tracks)) { // only one track
 335                                         Track track = TrackBitsToTrack(tracks); // get the only track
 336                                         if (!(flags & SF_TRAIN) && EnsureNoTrainOnTrackBits(ss.tile, tracks).Failed()) flags |= SF_TRAIN;
 337
 338                                         // tile can only have signals if it only has one bit
 339                                         if (HasSignalOnTrack(ss.tile, track)) { // now check whole track, not trackdir
 340                                                 SignalType sig = GetSignalType(ss.tile, track);
 341                                                 Trackdir trackdir = FindFirstTrackdir(TrackBitsToTrackdirBits(tracks) & _enterdir_to_trackdirbits[ss.side]);
 342                                                 Trackdir reversedir = ReverseTrackdir(trackdir);
 343                                                 /* add (tile, reversetrackdir) to 'to-be-updated' set when there is
 344                                                  * ANY conventional signal in REVERSE direction
 345                                                  * (if it is a presignal EXIT and it changes, it will be added to 'to-be-done' set later) */
 346                                                 if (HasSignalOnTrackdir(ss.tile, reversedir)) {
 347                                                         if (IsPbsSignal(sig)) {
 348                                                                 flags |= SF_PBS;
 349                                                         } else if (!_tbuset.Add(SignalPosFrom(ss.tile, reversedir))) {
 350                                                                 return flags | SF_FULL;
 351                                                         }
 352                                                 }
 353                                                 if (HasSignalOnTrackdir(ss.tile, trackdir) && !IsOnewaySignal(sig)) flags |= SF_PBS;
 354
 355                                                 /* if it is a presignal EXIT in OUR direction and we haven't found 2 green exits yes, do special check */
 356                                                 if (!(flags & SF_GREEN2) && IsPresignalExit(sig) && HasSignalOnTrackdir(ss.tile, trackdir)) { // found presignal exit
 357                                                         if (flags & SF_EXIT) flags |= SF_EXIT2; // found two (or more) exits
 358                                                         flags |= SF_EXIT; // found at least one exit - allow for compiler optimizations
 359                                                         if (GetSignalStateByTrackdir(ss.tile, trackdir) == SIGNAL_STATE_GREEN) { // found green presignal exit
 360                                                                 if (flags & SF_GREEN) flags |= SF_GREEN2;
 361                                                                 flags |= SF_GREEN;
 362                                                         }
 363                                                 }
 364
 365                                                 continue;
 366                                         }
 367                                 } else { // tile has overlapping tracks
 368                                         if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 369                                 }
 370
 371                                 SignalSideEnum enterdir = ss.side;
 372                                 for (ss.side = (SignalSideEnum)DIAGDIR_BEGIN; ss.side < (SignalSideEnum)DIAGDIR_END; ss.side++) { // test all possible exit directions
 373                                         if (ss.side != enterdir && (tracks & _enterdir_to_trackbits[ss.side])) { // any track incidating?
 374                                                 if (IsTileSubtype(ss.tile, TT_BRIDGE) && (ss.side == (SignalSideEnum)GetTunnelBridgeDirection(ss.tile))) {
 375                                                         newss.tile = ss.tile;
 376                                                         newss.side = SIDE_INTO_BRIDGE;
 377                                                         if (!MaybeAddToTodoSet(newss, SignalSideFrom(ss.tile, SIDE_FROM_BRIDGE))) return flags | SF_FULL;
 378                                                 } else {
 379                                                         newss.tile = ss.tile + TileOffsByDiagDir((DiagDirection)ss.side);  // new tile to check
 380                                                         newss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side); // direction we are entering from
 381                                                         if (!MaybeAddToTodoSet(newss, ss)) return flags | SF_FULL;
 382                                                 }
 383                                         }
 384                                 }
 385
 386                                 continue; // continue the while() loop
 387                         }
 388
 389                         case TT_MISC:
 390                                 if (GetTileOwner(ss.tile) != owner) continue;
 391
 392                                 switch (GetTileSubtype(ss.tile)) {
 393                                         default: continue;
 394
 395                                         case TT_MISC_CROSSING:
 396                                                 assert(IsValidDiagDirection((DiagDirection)ss.side));
 397                                                 if (DiagDirToAxis((DiagDirection)ss.side) == GetCrossingRoadAxis(ss.tile)) continue; // different axis
 398                                                 if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 399                                                 newss.side = ss.side;
 400                                                 ss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side); // exitdir
 401                                                 newss.tile += TileOffsByDiagDir((DiagDirection)ss.side);
 402                                                 break;
 403
 404                                         case TT_MISC_TUNNEL: {
 405                                                 if (GetTunnelTransportType(ss.tile) != TRANSPORT_RAIL) continue;
 406                                                 DiagDirection dir = GetTunnelBridgeDirection(ss.tile);
 407
 408                                                 if (ss.side == SIDE_INTO_TUNNEL) { // going into the wormhole
 409                                                         newss.tile = GetOtherTunnelEnd(ss.tile); // skip to exit tile
 410                                                         if (!(flags & SF_TRAIN) && EnsureNoTrainOnTunnelBridgeMiddle(ss.tile, newss.tile).Failed()) flags |= SF_TRAIN;
 411                                                         newss.side = SIDE_FROM_TUNNEL;
 412                                                         ss.tile = newss.tile;
 413                                                         ss.side = SIDE_INTO_TUNNEL;
 414                                                 } else if (ss.side == SIDE_FROM_TUNNEL) { // incoming from the wormhole
 415                                                         if (!(flags & SF_TRAIN) && EnsureNoTrainOnTrackBits(ss.tile, TRACK_BIT_ALL).Failed()) flags |= SF_TRAIN;
 416                                                         if (maptile_has_tunnel_signals(ss.tile)) {
 417                                                                 /* Only one-way signals supported in tunnels. */
 418                                                                 assert(maptile_has_tunnel_signal(ss.tile, true) != maptile_has_tunnel_signal(ss.tile, false));
 419                                                                 if (maptile_has_tunnel_signal(ss.tile, true)) {
 420                                                                         /* Only normal signals supported into tunnels. */
 421                                                                         assert(maptile_get_tunnel_signal_type(ss.tile) == SIGTYPE_NORMAL);
 422                                                                         if (!_tbuset.Add(SignalPosFrom(ss.tile, DiagDirToDiagTrackdir(dir)))) {
 423                                                                                 return flags | SF_FULL;
 424                                                                         }
 425                                                                 }
 426                                                                 continue;
 427                                                         }
 428                                                         ss.side = (SignalSideEnum)ReverseDiagDir(dir); // exitdir
 429                                                         newss.tile += TileOffsByDiagDir((DiagDirection)ss.side); // just skip to next tile
 430                                                         newss.side = (SignalSideEnum)dir;
 431                                                 } else { // neither into nor from the wormhole
 432                                                         assert(IsValidDiagDirection((DiagDirection)ss.side));
 433                                                         if (ss.side != (SignalSideEnum)ReverseDiagDir(dir)) continue;
 434                                                         if (!(flags & SF_TRAIN) && EnsureNoTrainOnTrackBits(ss.tile, TRACK_BIT_ALL).Failed()) flags |= SF_TRAIN;
 435                                                         if (maptile_has_tunnel_signals(ss.tile)) {
 436                                                                 /* Only one-way signals supported in tunnels. */
 437                                                                 assert(maptile_has_tunnel_signal(ss.tile, true) != maptile_has_tunnel_signal(ss.tile, false));
 438                                                                 if (maptile_has_tunnel_signal(ss.tile, false)) {
 439                                                                         SignalType sig = maptile_get_tunnel_signal_type(ss.tile);
 440                                                                         /* Only normal and one-way path signals supported in tunnels. */
 441                                                                         assert(sig == SIGTYPE_NORMAL || sig == SIGTYPE_PBS_ONEWAY);
 442                                                                         if (sig != SIGTYPE_NORMAL) {
 443                                                                                 flags |= SF_PBS;
 444                                                                         } else if (!_tbuset.Add(SignalPosFrom(ss.tile, DiagDirToDiagTrackdir(ReverseDiagDir(dir))))) {
 445                                                                                 return flags | SF_FULL;
 446                                                                         }
 447                                                                 }
 448                                                                 continue;
 449                                                         }
 450                                                         ss.side = SIDE_FROM_TUNNEL;
 451                                                         newss.tile = ss.tile;
 452                                                         newss.side = SIDE_INTO_TUNNEL;
 453                                                 }
 454                                                 break;
 455                                         }
 456
 457                                         case TT_MISC_DEPOT:
 458                                                 if (!IsRailDepot(ss.tile)) continue;
 459                                                 if (ss.side == SIDE_DEPOT) { // from 'inside' - train just entered or left the depot
 460                                                         if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 461                                                         ss.side = (SignalSideEnum)GetGroundDepotDirection(ss.tile); // exitdir
 462                                                         newss.tile += TileOffsByDiagDir((DiagDirection)ss.side);
 463                                                         newss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side);
 464                                                         break;
 465                                                 } else if (ss.side == (SignalSideEnum)GetGroundDepotDirection(ss.tile)) { // entered a depot
 466                                                         if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 467                                                 }
 468                                                 continue;
 469                                 }
 470                                 break;
 471
 472                         case TT_STATION:
 473                                 assert(IsValidDiagDirection((DiagDirection)ss.side));
 474
 475                                 if (!HasStationRail(ss.tile)) continue;
 476                                 if (GetTileOwner(ss.tile) != owner) continue;
 477                                 if (DiagDirToAxis((DiagDirection)ss.side) != GetRailStationAxis(ss.tile)) continue; // different axis
 478                                 if (IsStationTileBlocked(ss.tile)) continue; // 'eye-candy' station tile
 479
 480                                 if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 481                                 newss.side = ss.side;
 482                                 ss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side); // exitdir
 483                                 newss.tile += TileOffsByDiagDir((DiagDirection)ss.side);
 484                                 break;
 485
 486                         default:
 487                                 continue; // continue the while() loop
 488                 }
 489
 490                 if (!MaybeAddToTodoSet(newss, ss)) return flags | SF_FULL;
 491         }
 492
 493         return flags;
 494 }
 495
 496
 497 /**
 498  * Determine the state for a signal heading into a tunnel when there is a train in it
 499  * @param tile the tunnel tile
 500  * @return the signal state to set
 501  */
 502 static SignalState GetTunnelSignalState(TileIndex tile)
 503 {
 504         assert(maptile_is_rail_tunnel(tile));
 505
 506         /* signal is red if there is a train on the initial tile */
 507         if (HasTrainOnTile(tile)) return SIGNAL_STATE_RED;
 508
 509         /* otherwise, signal is red iff there is a train near the entry */
 510         TileIndex tile2 = TileAddByDiagDir(tile, GetTunnelBridgeDirection(tile));
 511         VehicleTileFinder iter (GetOtherTunnelEnd(tile));
 512         while (!iter.finished()) {
 513                 Vehicle *v = iter.next();
 514                 if (v->type == VEH_TRAIN && TileVirtXY(v->x_pos, v->y_pos) == tile2) iter.set_found();
 515         }
 516         return iter.was_found() ? SIGNAL_STATE_RED : SIGNAL_STATE_GREEN;
 517 }
 518
 519 /**
 520  * Update signals around segment in _tbuset
 521  *
 522  * @param flags info about segment
 523  */
 524 static void UpdateSignalsAroundSegment(SigFlags flags)
 525 {
 526         SignalPos pos;
 527
 528         while (_tbuset.Get(&pos)) {
 529                 if (!IsRailwayTile(pos.tile)) {
 530                         /* Special signals */
 531                         assert(maptile_is_rail_tunnel(pos.tile));
 532                         assert(maptile_get_tunnel_signal_type(pos.tile) == SIGTYPE_NORMAL);
 533
 534                         bool inwards = pos.td == DiagDirToDiagTrackdir(GetTunnelBridgeDirection(pos.tile));
 535                         SignalState newstate = !(flags & SF_TRAIN) ? SIGNAL_STATE_GREEN :
 536                                 inwards ? GetTunnelSignalState(pos.tile) : SIGNAL_STATE_RED;
 537
 538                         if (newstate != maptile_get_tunnel_signal_state(pos.tile, inwards)) {
 539                                 maptile_set_tunnel_signal_state(pos.tile, inwards, newstate);
 540                                 MarkTileDirtyByTile(pos.tile);
 541                         }
 542
 543                         continue;
 544                 }
 545
 546                 assert(HasSignalOnTrackdir(pos.tile, pos.td));
 547
 548                 SignalType sig = GetSignalType(pos.tile, TrackdirToTrack(pos.td));
 549                 SignalState newstate = SIGNAL_STATE_GREEN;
 550
 551                 /* determine whether the new state is red */
 552                 if (flags & SF_TRAIN) {
 553                         /* train in the segment */
 554                         newstate = SIGNAL_STATE_RED;
 555                 } else {
 556                         /* is it a bidir combo? - then do not count its other signal direction as exit */
 557                         if (sig == SIGTYPE_COMBO && HasSignalOnTrackdir(pos.tile, ReverseTrackdir(pos.td))) {
 558                                 /* at least one more exit */
 559                                 if ((flags & SF_EXIT2) &&
 560                                                 /* no green exit */
 561                                                 (!(flags & SF_GREEN) ||
 562                                                 /* only one green exit, and it is this one - so all other exits are red */
 563                                                 (!(flags & SF_GREEN2) && GetSignalStateByTrackdir(pos.tile, ReverseTrackdir(pos.td)) == SIGNAL_STATE_GREEN))) {
 564                                         newstate = SIGNAL_STATE_RED;
 565                                 }
 566                         } else { // entry, at least one exit, no green exit
 567                                 if (IsPresignalEntry(sig) && (flags & SF_EXIT) && !(flags & SF_GREEN)) newstate = SIGNAL_STATE_RED;
 568                         }
 569                 }
 570
 571                 /* only when the state changes */
 572                 if (newstate != GetSignalStateByTrackdir(pos.tile, pos.td)) {
 573                         if (IsPresignalExit(sig)) {
 574                                 /* for pre-signal exits, add block to the global set */
 575                                 DiagDirection exitdir = TrackdirToExitdir(ReverseTrackdir(pos.td));
 576                                 SignalSideEnum side;
 577                                 if (IsRailBridgeTile(pos.tile)) {
 578                                         side = (exitdir == GetTunnelBridgeDirection(pos.tile)) ? SIDE_FROM_BRIDGE : (SignalSideEnum)exitdir;
 579                                 } else if (IsTunnelTile(pos.tile)) {
 580                                         side = (exitdir == GetTunnelBridgeDirection(pos.tile)) ? SIDE_FROM_TUNNEL : (SignalSideEnum)exitdir;
 581                                 } else {
 582                                         side = (SignalSideEnum)exitdir;
 583                                 }
 584                                 _globset.Add(SignalSideFrom(pos.tile, side)); // do not check for full global set, first update all signals
 585                         }
 586                         SetSignalStateByTrackdir(pos.tile, pos.td, newstate);
 587                         MarkTileDirtyByTile(pos.tile);
 588                 }
 589         }
 590
 591 }
 592
 593
 594 /** Reset all sets after one set overflowed */
 595 static inline void ResetSets()
 596 {
 597         _tbuset.Reset();
 598         _tbdset.Reset();
 599         _globset.Reset();
 600 }
 601
 602
 603 /**
 604  * Updates blocks in _globset buffer
 605  *
 606  * @param owner company whose signals we are updating
 607  * @return state of the first block from _globset
 608  * @pre _globset.IsEmpty() || Company::IsValidID(_owner)
 609  */
 610 SigSegState UpdateSignalsInBuffer()
 611 {
 612         assert(_globset.IsEmpty() || Company::IsValidID(_owner));
 613
 614         SigSegState state = SIGSEG_NONE; // value to return
 615
 616         SignalSide ss;
 617
 618         while (_globset.Get(&ss)) {
 619                 assert(_tbuset.IsEmpty());
 620                 assert(_tbdset.IsEmpty());
 621
 622                 /* After updating signal, data stored are always railway with signals.
 623                  * Other situations happen when data are from outside functions -
 624                  * modification of railbits (including both rail building and removal),
 625                  * train entering/leaving block, train leaving depot...
 626                  */
 627                 switch (GetTileType(ss.tile)) {
 628                         case TT_RAILWAY:
 629                                 if (IsTileSubtype(ss.tile, TT_TRACK)) {
 630                                         /* check if there was something here that got deleted */
 631                                         if (!IsValidDiagDirection((DiagDirection)ss.side)) continue;
 632                                         goto check_track;
 633                                 }
 634                                 assert(ss.side != (SignalSideEnum)GetTunnelBridgeDirection(ss.tile));
 635                                 if (IsValidDiagDirection((DiagDirection)ss.side)) goto check_track;
 636                                 assert(ss.side == SIDE_INTO_BRIDGE || ss.side == SIDE_FROM_BRIDGE);
 637                                 _tbdset.Add(SignalSideFrom(ss.tile, SIDE_INTO_BRIDGE));
 638                                 _tbdset.Add(SignalSideFrom(ss.tile, SIDE_FROM_BRIDGE));
 639                                 break;
 640
 641                         case TT_MISC:
 642                                 if (IsTunnelTile(ss.tile)) {
 643                                         /* 'optimization assert' - do not try to update signals when it is not needed */
 644                                         assert(GetTunnelTransportType(ss.tile) == TRANSPORT_RAIL);
 645                                         if (IsValidDiagDirection((DiagDirection)ss.side)) {
 646                                                 assert(ss.side == (SignalSideEnum)ReverseDiagDir(GetTunnelBridgeDirection(ss.tile)));
 647                                                 goto check_track;
 648                                         } else {
 649                                                 assert(ss.side == SIDE_INTO_TUNNEL || SIDE_FROM_TUNNEL);
 650                                                 _tbdset.Add(SignalSideFrom(ss.tile, SIDE_INTO_TUNNEL));
 651                                                 _tbdset.Add(SignalSideFrom(ss.tile, SIDE_FROM_TUNNEL));
 652                                         }
 653                                         break;
 654                                 }
 655                                 if (IsRailDepotTile(ss.tile)) {
 656                                         /* 'optimization assert' do not try to update signals in other cases */
 657                                         assert(ss.side == SIDE_DEPOT || ss.side == (SignalSideEnum)GetGroundDepotDirection(ss.tile));
 658                                         _tbdset.Add(SignalSideFrom(ss.tile, SIDE_DEPOT)); // start from depot inside
 659                                         break;
 660                                 }
 661                                 if (!IsLevelCrossingTile(ss.tile)) goto next_tile;
 662                                 /* fall through */
 663                         case TT_STATION:
 664                         check_track:
 665                                 assert(IsValidDiagDirection((DiagDirection)ss.side));
 666                                 if ((TrackStatusToTrackBits(GetTileRailwayStatus(ss.tile)) & _enterdir_to_trackbits[ss.side]) != TRACK_BIT_NONE) {
 667                                         /* only add to set when there is some 'interesting' track */
 668                                         _tbdset.Add(ss);
 669                                         _tbdset.Add(SignalSideFrom(ss.tile + TileOffsByDiagDir((DiagDirection)ss.side), (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side)));
 670                                         break;
 671                                 }
 672                                 /* FALL THROUGH */
 673                         default:
 674                                 /* jump to next tile */
 675                         next_tile:
 676                                 /* check if there was a bridge here but got deleted */
 677                                 if (!IsValidDiagDirection((DiagDirection)ss.side)) continue;
 678                                 ss.tile = ss.tile + TileOffsByDiagDir((DiagDirection)ss.side);
 679                                 ss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side);
 680                                 if ((TrackStatusToTrackBits(GetTileRailwayStatus(ss.tile)) & _enterdir_to_trackbits[ss.side]) != TRACK_BIT_NONE) {
 681                                         _tbdset.Add(ss);
 682                                         break;
 683                                 }
 684                                 /* happens when removing a rail that wasn't connected at one or both sides */
 685                                 continue; // continue the while() loop
 686                 }
 687
 688                 assert(!_tbdset.Overflowed()); // it really shouldn't overflow by these one or two items
 689                 assert(!_tbdset.IsEmpty()); // it wouldn't hurt anyone, but shouldn't happen too
 690
 691                 SigFlags flags = ExploreSegment(_owner);
 692
 693                 if (state == SIGSEG_NONE) {
 694                         if (flags & SF_PBS) {
 695                                 state = SIGSEG_PBS;
 696                         } else if ((flags & SF_TRAIN) || ((flags & SF_EXIT) && !(flags & SF_GREEN)) || (flags & SF_FULL)) {
 697                                 state = SIGSEG_FULL;
 698                         } else {
 699                                 state = SIGSEG_FREE;
 700                         }
 701                 }
 702
 703                 /* do not do anything when some buffer was full */
 704                 if (flags & SF_FULL) {
 705                         ResetSets(); // free all sets
 706                         break;
 707                 }
 708
 709                 UpdateSignalsAroundSegment(flags);
 710         }
 711
 712         _owner = INVALID_OWNER;
 713
 714         return state;
 715 }
 716
 717
 718 /**
 719  * Check if signal buffer is empty
 720  * @returns whether the signal buffer is empty
 721  */
 722 bool IsSignalBufferEmpty()
 723 {
 724         return _globset.IsEmpty();
 725 }
 726
 727 /**
 728  * Set signal buffer owner
 729  */
 730 static inline void SetBufferOwner(Owner owner)
 731 {
 732         /* do not allow signal updates for two companies in one run */
 733         assert(_globset.IsEmpty() || owner == _owner);
 734         _owner = owner;
 735 }
 736
 737 /**
 738  * Update signals in buffer if it has too many items
 739  */
 740 static inline void UpdateSignalsInBufferAuto()
 741 {
 742         if (_globset.Items() >= SIG_GLOB_UPDATE) {
 743                 /* too many items, force update */
 744                 UpdateSignalsInBuffer();
 745         }
 746 }
 747
 748
 749 /**
 750  * Add track to signal update buffer
 751  *
 752  * @param tile tile where we start
 753  * @param track track at which ends we will update signals
 754  * @param owner owner whose signals we will update
 755  */
 756 void AddTrackToSignalBuffer(TileIndex tile, Track track, Owner owner)
 757 {
 758         SetBufferOwner(owner);
 759
 760         if (IsRailBridgeTile(tile)) {
 761                 DiagDirection dir = GetTunnelBridgeDirection(tile);
 762                 DiagDirection side;
 763                 side = TrackdirToExitdir(TrackToTrackdir(track));
 764                 _globset.Add(SignalSideFrom(tile, (side == dir) ? SIDE_FROM_BRIDGE : (SignalSideEnum)side));
 765                 side = TrackdirToExitdir(ReverseTrackdir(TrackToTrackdir(track)));
 766                 _globset.Add(SignalSideFrom(tile, (side == dir) ? SIDE_FROM_BRIDGE : (SignalSideEnum)side));
 767         } else if (IsTunnelTile(tile)) {
 768                 DiagDirection dir = GetTunnelBridgeDirection(tile);
 769                 assert(track == DiagDirToDiagTrack(dir));
 770                 _globset.Add(SignalSideFrom(tile, (SignalSideEnum)ReverseDiagDir(dir)));
 771                 _globset.Add(SignalSideFrom(tile, SIDE_FROM_TUNNEL));
 772         } else {
 773                 _globset.Add(SignalSideFrom(tile, (SignalSideEnum)TrackdirToExitdir(TrackToTrackdir(track))));
 774                 _globset.Add(SignalSideFrom(tile, (SignalSideEnum)TrackdirToExitdir(ReverseTrackdir(TrackToTrackdir(track)))));
 775         }
 776
 777         UpdateSignalsInBufferAuto();
 778 }
 779
 780
 781 /**
 782  * Add side of tile to signal update buffer
 783  *
 784  * @param tile tile where we start
 785  * @param side side of tile
 786  * @param owner owner whose signals we will update
 787  */
 788 void AddSideToSignalBuffer(TileIndex tile, DiagDirection side, Owner owner)
 789 {
 790         SetBufferOwner(owner);
 791
 792         assert(IsValidDiagDirection(side));
 793         _globset.Add(SignalSideFrom(tile, (SignalSideEnum)side));
 794
 795         UpdateSignalsInBufferAuto();
 796 }
 797
 798 /**
 799  * Add depot tile to signal update buffer
 800  *
 801  * @param tile tile to add
 802  * @param owner owner whose signals we will update
 803  */
 804 void AddDepotToSignalBuffer(TileIndex tile, Owner owner)
 805 {
 806         SetBufferOwner(owner);
 807
 808         assert(IsDepotTile(tile));
 809         _globset.Add(SignalSideFrom(tile, SIDE_DEPOT));
 810
 811         UpdateSignalsInBufferAuto();
 812 }
 813
 814 /**
 815  * Add bridge tile to signal update buffer
 816  *
 817  * @param tile tile to add
 818  * @param owner owner whose signals we will update
 819  */
 820 void AddBridgeToSignalBuffer(TileIndex tile, Owner owner)
 821 {
 822         SetBufferOwner(owner);
 823
 824         assert(IsRailBridgeTile(tile));
 825         _globset.Add(SignalSideFrom(tile, SIDE_FROM_BRIDGE));
 826
 827         UpdateSignalsInBufferAuto();
 828 }
 829
 830 /**
 831  * Add tunnel tile to signal update buffer
 832  *
 833  * @param tile tile to add
 834  * @param owner owner whose signals we will update
 835  */
 836 void AddTunnelToSignalBuffer(TileIndex tile, Owner owner)
 837 {
 838         SetBufferOwner(owner);
 839
 840         assert(maptile_is_rail_tunnel(tile));
 841         _globset.Add(SignalSideFrom(tile, SIDE_FROM_TUNNEL));
 842
 843         UpdateSignalsInBufferAuto();
 844 }
 845
 846
 847 /**
 848  * Add a pathfinder position to signal update buffer
 849  *
 850  * @param pos position to add
 851  * @param owner owner whose signals we will update
 852  */
 853 void AddPosToSignalBuffer(const RailPathPos &pos, Owner owner)
 854 {
 855         SetBufferOwner(owner);
 856
 857         if (pos.in_wormhole()) {
 858                 _globset.Add(SignalSideFrom(pos.wormhole, IsRailwayTile(pos.wormhole) ? SIDE_INTO_BRIDGE : SIDE_INTO_TUNNEL));
 859         } else if (IsRailDepotTile(pos.tile)) {
 860                 _globset.Add(SignalSideFrom(pos.tile, SIDE_DEPOT));
 861         } else {
 862                 DiagDirection exitdir = TrackdirToExitdir(pos.td);
 863                 SignalSideEnum side;
 864                 if (IsRailBridgeTile(pos.tile)) {
 865                         side = (exitdir == GetTunnelBridgeDirection(pos.tile)) ? SIDE_FROM_BRIDGE : (SignalSideEnum)exitdir;
 866                 } else if (IsTunnelTile(pos.tile)) {
 867                         side = (exitdir == GetTunnelBridgeDirection(pos.tile)) ? SIDE_FROM_TUNNEL : (SignalSideEnum)exitdir;
 868                 } else {
 869                         side = (SignalSideEnum)exitdir;
 870                 }
 871                 _globset.Add(SignalSideFrom(pos.tile, side));
 872         }
 873
 874         UpdateSignalsInBufferAuto();
 875 }