signal.cpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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/>.
 */
 
#include "stdafx.h"
#include "debug.h"
#include "station_map.h"
#include "tunnelbridge_map.h"
#include "vehicle_func.h"
#include "viewport_func.h"
#include "train.h"
#include "company_base.h"
#include "pbs.h"
 
#include "safeguards.h"
 
 
static const uint SIG_TBU_SIZE    =  64; 
static const uint SIG_TBD_SIZE    = 256; 
static const uint SIG_GLOB_SIZE   = 128; 
static const uint SIG_GLOB_UPDATE =  64; 
 
static_assert(SIG_GLOB_UPDATE <= SIG_GLOB_SIZE);
 
static const TrackBits _enterdir_to_trackbits[DIAGDIR_END] = {
  TRACK_BIT_3WAY_NE,
  TRACK_BIT_3WAY_SE,
  TRACK_BIT_3WAY_SW,
  TRACK_BIT_3WAY_NW
};
 
static const TrackdirBits _enterdir_to_trackdirbits[DIAGDIR_END] = {
  TRACKDIR_BIT_X_SW | TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_RIGHT_S,
  TRACKDIR_BIT_Y_NW | TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_RIGHT_N,
  TRACKDIR_BIT_X_NE | TRACKDIR_BIT_LOWER_E | TRACKDIR_BIT_LEFT_N,
  TRACKDIR_BIT_Y_SE | TRACKDIR_BIT_UPPER_E | TRACKDIR_BIT_LEFT_S
};
 
template <typename Tdir, uint items>
struct SmallSet {
private:
  uint n;           // actual number of units
  bool overflowed;  // did we try to overflow the set?
  const char *name; // name, used for debugging purposes...
 
  struct SSdata {
    TileIndex tile;
    Tdir dir;
  } data[items];
 
public:
  SmallSet(const char *name) : n(0), overflowed(false), name(name) { }
 
  void Reset()
  {
    this->n = 0;
    this->overflowed = false;
  }
 
  bool Overflowed()
  {
    return this->overflowed;
  }
 
  bool IsEmpty()
  {
    return this->n == 0;
  }
 
  bool IsFull()
  {
    return this->n == lengthof(data);
  }
 
  uint Items()
  {
    return this->n;
  }
 
 
  bool Remove(TileIndex tile, Tdir dir)
  {
    for (uint i = 0; i < this->n; i++) {
      if (this->data[i].tile == tile && this->data[i].dir == dir) {
        this->data[i] = this->data[--this->n];
        return true;
      }
    }
 
    return false;
  }
 
  bool IsIn(TileIndex tile, Tdir dir)
  {
    for (uint i = 0; i < this->n; i++) {
      if (this->data[i].tile == tile && this->data[i].dir == dir) return true;
    }
 
    return false;
  }
 
  bool Add(TileIndex tile, Tdir dir)
  {
    if (this->IsFull()) {
      overflowed = true;
      Debug(misc, 0, "SignalSegment too complex. Set {} is full (maximum {})", name, items);
      return false; // set is full
    }
 
    this->data[this->n].tile = tile;
    this->data[this->n].dir = dir;
    this->n++;
 
    return true;
  }
 
  bool Get(TileIndex *tile, Tdir *dir)
  {
    if (this->n == 0) return false;
 
    this->n--;
    *tile = this->data[this->n].tile;
    *dir = this->data[this->n].dir;
 
    return true;
  }
};
 
static SmallSet<Trackdir, SIG_TBU_SIZE> _tbuset("_tbuset");         
static SmallSet<DiagDirection, SIG_TBD_SIZE> _tbdset("_tbdset");    
static SmallSet<DiagDirection, SIG_GLOB_SIZE> _globset("_globset"); 
 
 
static Vehicle *TrainOnTileEnum(Vehicle *v, void *)
{
  if (v->type != VEH_TRAIN || Train::From(v)->track == TRACK_BIT_DEPOT) return nullptr;
 
  return v;
}
 
 
static inline bool CheckAddToTodoSet(TileIndex t1, DiagDirection d1, TileIndex t2, DiagDirection d2)
{
  _globset.Remove(t1, d1); // it can be in Global but not in Todo
  _globset.Remove(t2, d2); // remove in all cases
 
  assert(!_tbdset.IsIn(t1, d1)); // it really shouldn't be there already
 
  return !_tbdset.Remove(t2, d2);
}
 
 
static inline bool MaybeAddToTodoSet(TileIndex t1, DiagDirection d1, TileIndex t2, DiagDirection d2)
{
  if (!CheckAddToTodoSet(t1, d1, t2, d2)) return true;
 
  return _tbdset.Add(t1, d1);
}
 
 
enum class SigFlag : uint8_t {
  Train, 
  Exit, 
  MultiExit, 
  Green, 
  MultiGreen, 
  Full, 
  Pbs, 
  Split, 
  Enter, 
  MultiEnter, 
};
using SigFlags = EnumBitSet<SigFlag, uint16_t>;
 
static SigFlags ExploreSegment(Owner owner)
{
  SigFlags flags{};
 
  TileIndex tile = INVALID_TILE; // Stop GCC from complaining about a possibly uninitialized variable (issue #8280).
  DiagDirection enterdir = INVALID_DIAGDIR;
 
  while (_tbdset.Get(&tile, &enterdir)) { // tile and enterdir are initialized here, unless I'm mistaken.
    TileIndex oldtile = tile; // tile we are leaving
    DiagDirection exitdir = enterdir == INVALID_DIAGDIR ? INVALID_DIAGDIR : ReverseDiagDir(enterdir); // expected new exit direction (for straight line)
 
    switch (GetTileType(tile)) {
      case MP_RAILWAY: {
        if (GetTileOwner(tile) != owner) continue; // do not propagate signals on others' tiles (remove for tracksharing)
 
        if (IsRailDepot(tile)) {
          if (enterdir == INVALID_DIAGDIR) { // from 'inside' - train just entered or left the depot
            if (!flags.Test(SigFlag::Train) && HasVehicleOnPos(tile, nullptr, &TrainOnTileEnum)) flags.Set(SigFlag::Train);
            exitdir = GetRailDepotDirection(tile);
            tile += TileOffsByDiagDir(exitdir);
            enterdir = ReverseDiagDir(exitdir);
            break;
          } else if (enterdir == GetRailDepotDirection(tile)) { // entered a depot
            if (!flags.Test(SigFlag::Train) && HasVehicleOnPos(tile, nullptr, &TrainOnTileEnum)) flags.Set(SigFlag::Train);
            continue;
          } else {
            continue;
          }
        }
 
        assert(IsValidDiagDirection(enterdir));
        TrackBits tracks = GetTrackBits(tile); // trackbits of tile
        TrackBits tracks_masked = (TrackBits)(tracks & _enterdir_to_trackbits[enterdir]); // only incidating trackbits
 
        if (tracks == TRACK_BIT_HORZ || tracks == TRACK_BIT_VERT) { // there is exactly one incidating track, no need to check
          tracks = tracks_masked;
          /* If no train detected yet, and there is not no train -> there is a train -> set the flag */
          if (!flags.Test(SigFlag::Train) && EnsureNoTrainOnTrackBits(tile, tracks).Failed()) flags. Set(SigFlag::Train);
        } else {
          if (tracks_masked == TRACK_BIT_NONE) continue; // no incidating track
          if (!flags.Test(SigFlag::Train) && HasVehicleOnPos(tile, nullptr, &TrainOnTileEnum)) flags.Set(SigFlag::Train);
        }
 
        /* Is this a track merge or split? */
        if (!HasAtMostOneBit(tracks)) flags.Set(SigFlag::Split);
 
        if (HasSignals(tile)) { // there is exactly one track - not zero, because there is exit from this tile
          Track track = TrackBitsToTrack(tracks_masked); // mask TRACK_BIT_X and Y too
          if (HasSignalOnTrack(tile, track)) { // now check whole track, not trackdir
            SignalType sig = GetSignalType(tile, track);
            Trackdir trackdir = (Trackdir)FindFirstBit((tracks * 0x101U) & _enterdir_to_trackdirbits[enterdir]);
            Trackdir reversedir = ReverseTrackdir(trackdir);
            /* add (tile, reversetrackdir) to 'to-be-updated' set when there is
             * ANY conventional signal in REVERSE direction
             * (if it is a presignal EXIT and it changes, it will be added to 'to-be-done' set later) */
            if (HasSignalOnTrackdir(tile, reversedir)) {
              if (IsPbsSignal(sig)) flags.Set(SigFlag::Pbs);
              if (flags.Test(SigFlag::Enter)) flags.Set(SigFlag::MultiEnter);
              flags.Set(SigFlag::Enter);
 
              if (!_tbuset.Add(tile, reversedir)) return flags | SigFlag::Full;
            }
            if (HasSignalOnTrackdir(tile, trackdir) && !IsOnewaySignal(tile, track)) flags.Set(SigFlag::Pbs);
 
            /* if it is a presignal EXIT in OUR direction and we haven't found 2 green exits yes, do special check */
            if (!flags.Test(SigFlag::MultiGreen) && IsPresignalExit(tile, track) && HasSignalOnTrackdir(tile, trackdir)) { // found presignal exit
              if (flags.Test(SigFlag::Exit)) flags.Set(SigFlag::MultiExit); // found two (or more) exits
              flags.Set(SigFlag::Exit); // found at least one exit - allow for compiler optimizations
              if (GetSignalStateByTrackdir(tile, trackdir) == SIGNAL_STATE_GREEN) { // found green presignal exit
                if (flags.Test(SigFlag::Green)) flags.Set(SigFlag::MultiGreen);
                flags.Set(SigFlag::Green);
              }
            }
 
            continue;
          }
        }
 
        for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) { // test all possible exit directions
          if (dir != enterdir && (tracks & _enterdir_to_trackbits[dir])) { // any track incidating?
            TileIndex newtile = tile + TileOffsByDiagDir(dir);  // new tile to check
            DiagDirection newdir = ReverseDiagDir(dir); // direction we are entering from
            if (!MaybeAddToTodoSet(newtile, newdir, tile, dir)) return flags | SigFlag::Full;
          }
        }
 
        continue; // continue the while() loop
        }
 
      case MP_STATION:
        if (!HasStationRail(tile)) continue;
        if (GetTileOwner(tile) != owner) continue;
        if (DiagDirToAxis(enterdir) != GetRailStationAxis(tile)) continue; // different axis
        if (IsStationTileBlocked(tile)) continue; // 'eye-candy' station tile
 
        if (!flags.Test(SigFlag::Train) && HasVehicleOnPos(tile, nullptr, &TrainOnTileEnum)) flags.Set(SigFlag::Train);
        tile += TileOffsByDiagDir(exitdir);
        break;
 
      case MP_ROAD:
        if (!IsLevelCrossing(tile)) continue;
        if (GetTileOwner(tile) != owner) continue;
        if (DiagDirToAxis(enterdir) == GetCrossingRoadAxis(tile)) continue; // different axis
 
        if (!flags.Test(SigFlag::Train) && HasVehicleOnPos(tile, nullptr, &TrainOnTileEnum)) flags.Set(SigFlag::Train);
        tile += TileOffsByDiagDir(exitdir);
        break;
 
      case MP_TUNNELBRIDGE: {
        if (GetTileOwner(tile) != owner) continue;
        if (GetTunnelBridgeTransportType(tile) != TRANSPORT_RAIL) continue;
        DiagDirection dir = GetTunnelBridgeDirection(tile);
 
        if (enterdir == INVALID_DIAGDIR) { // incoming from the wormhole
          if (!flags.Test(SigFlag::Train) && HasVehicleOnPos(tile, nullptr, &TrainOnTileEnum)) flags.Set(SigFlag::Train);
          enterdir = dir;
          exitdir = ReverseDiagDir(dir);
          tile += TileOffsByDiagDir(exitdir); // just skip to next tile
        } else { // NOT incoming from the wormhole!
          if (ReverseDiagDir(enterdir) != dir) continue;
          if (!flags.Test(SigFlag::Train) && HasVehicleOnPos(tile, nullptr, &TrainOnTileEnum)) flags.Set(SigFlag::Train);
          tile = GetOtherTunnelBridgeEnd(tile); // just skip to exit tile
          enterdir = INVALID_DIAGDIR;
          exitdir = INVALID_DIAGDIR;
        }
        }
        break;
 
      default:
        continue; // continue the while() loop
    }
 
    if (!MaybeAddToTodoSet(tile, enterdir, oldtile, exitdir)) return flags | SigFlag::Full;
  }
 
  return flags;
}
 
 
static void UpdateSignalsAroundSegment(SigFlags flags)
{
  TileIndex tile = INVALID_TILE; // Stop GCC from complaining about a possibly uninitialized variable (issue #8280).
  Trackdir trackdir = INVALID_TRACKDIR;
 
  while (_tbuset.Get(&tile, &trackdir)) {
    assert(HasSignalOnTrackdir(tile, trackdir));
 
    Track track = TrackdirToTrack(trackdir);
    SignalType sig = GetSignalType(tile, track);
    SignalState newstate = SIGNAL_STATE_GREEN;
 
    /* Signal state of reserved path signals is handled by the reserve/unreserve process. */
    if (IsPbsSignal(sig) && (GetRailReservationTrackBits(tile) & TrackToTrackBits(track)) != TRACK_BIT_NONE) continue;
 
    /* determine whether the new state is red */
    if (flags.Test(SigFlag::Train)) {
      /* train in the segment */
      newstate = SIGNAL_STATE_RED;
    } else if (IsPbsSignal(sig) && flags.Any({SigFlag::Split, SigFlag::MultiEnter})) {
      /* Turn path signals red if the segment has a junction or more than one way in. */
      newstate = SIGNAL_STATE_RED;
    } else {
      /* is it a bidir combo? - then do not count its other signal direction as exit */
      if (sig == SIGTYPE_COMBO && HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir))) {
        /* at least one more exit */
        if (flags.Test(SigFlag::MultiExit) &&
            /* no green exit */
            (!flags.Test(SigFlag::Green) ||
            /* only one green exit, and it is this one - so all other exits are red */
            (!flags.Test(SigFlag::MultiGreen) && GetSignalStateByTrackdir(tile, ReverseTrackdir(trackdir)) == SIGNAL_STATE_GREEN))) {
          newstate = SIGNAL_STATE_RED;
        }
      } else { // entry, at least one exit, no green exit
        if (IsPresignalEntry(tile, TrackdirToTrack(trackdir)) && flags.Test(SigFlag::Exit) && !flags.Test(SigFlag::Green)) newstate = SIGNAL_STATE_RED;
      }
    }
 
    /* only when the state changes */
    if (newstate != GetSignalStateByTrackdir(tile, trackdir)) {
      if (IsPresignalExit(tile, TrackdirToTrack(trackdir))) {
        /* for pre-signal exits, add block to the global set */
        DiagDirection exitdir = TrackdirToExitdir(ReverseTrackdir(trackdir));
        _globset.Add(tile, exitdir); // do not check for full global set, first update all signals
      }
      SetSignalStateByTrackdir(tile, trackdir, newstate);
      MarkTileDirtyByTile(tile);
    }
  }
 
}
 
 
static inline void ResetSets()
{
  _tbuset.Reset();
  _tbdset.Reset();
  _globset.Reset();
}
 
 
static SigSegState UpdateSignalsInBuffer(Owner owner)
{
  assert(Company::IsValidID(owner));
 
  bool first = true;  // first block?
  SigSegState state = SIGSEG_FREE; // value to return
 
  TileIndex tile = INVALID_TILE; // Stop GCC from complaining about a possibly uninitialized variable (issue #8280).
  DiagDirection dir = INVALID_DIAGDIR;
 
  while (_globset.Get(&tile, &dir)) {
    assert(_tbuset.IsEmpty());
    assert(_tbdset.IsEmpty());
 
    /* After updating signal, data stored are always MP_RAILWAY with signals.
     * Other situations happen when data are from outside functions -
     * modification of railbits (including both rail building and removal),
     * train entering/leaving block, train leaving depot...
     */
    switch (GetTileType(tile)) {
      case MP_TUNNELBRIDGE:
        /* 'optimization assert' - do not try to update signals when it is not needed */
        assert(GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL);
        assert(dir == INVALID_DIAGDIR || dir == ReverseDiagDir(GetTunnelBridgeDirection(tile)));
        _tbdset.Add(tile, INVALID_DIAGDIR);  // we can safely start from wormhole centre
        _tbdset.Add(GetOtherTunnelBridgeEnd(tile), INVALID_DIAGDIR);
        break;
 
      case MP_RAILWAY:
        if (IsRailDepot(tile)) {
          /* 'optimization assert' do not try to update signals in other cases */
          assert(dir == INVALID_DIAGDIR || dir == GetRailDepotDirection(tile));
          _tbdset.Add(tile, INVALID_DIAGDIR); // start from depot inside
          break;
        }
        [[fallthrough]];
 
      case MP_STATION:
      case MP_ROAD:
        if ((TrackStatusToTrackBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)) & _enterdir_to_trackbits[dir]) != TRACK_BIT_NONE) {
          /* only add to set when there is some 'interesting' track */
          _tbdset.Add(tile, dir);
          _tbdset.Add(tile + TileOffsByDiagDir(dir), ReverseDiagDir(dir));
          break;
        }
        [[fallthrough]];
 
      default:
        /* jump to next tile */
        tile = tile + TileOffsByDiagDir(dir);
        dir = ReverseDiagDir(dir);
        if ((TrackStatusToTrackBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)) & _enterdir_to_trackbits[dir]) != TRACK_BIT_NONE) {
          _tbdset.Add(tile, dir);
          break;
        }
        /* happens when removing a rail that wasn't connected at one or both sides */
        continue; // continue the while() loop
    }
 
    assert(!_tbdset.Overflowed()); // it really shouldn't overflow by these one or two items
    assert(!_tbdset.IsEmpty()); // it wouldn't hurt anyone, but shouldn't happen too
 
    SigFlags flags = ExploreSegment(owner);
 
    if (first) {
      first = false;
      /* SIGSEG_FREE is set by default */
      if (flags.Test(SigFlag::Pbs)) {
        state = SIGSEG_PBS;
      } else if (flags.Test(SigFlag::Train) || (flags.Test(SigFlag::Exit) && !flags.Test(SigFlag::Green)) || flags.Test(SigFlag::Full)) {
        state = SIGSEG_FULL;
      }
    }
 
    /* do not do anything when some buffer was full */
    if (flags.Test(SigFlag::Full)) {
      ResetSets(); // free all sets
      break;
    }
 
    UpdateSignalsAroundSegment(flags);
  }
 
  return state;
}
 
 
static Owner _last_owner = INVALID_OWNER; 
 
 
void UpdateSignalsInBuffer()
{
  if (!_globset.IsEmpty()) {
    UpdateSignalsInBuffer(_last_owner);
    _last_owner = INVALID_OWNER; // invalidate
  }
}
 
 
void AddTrackToSignalBuffer(TileIndex tile, Track track, Owner owner)
{
  static const DiagDirection _search_dir_1[] = {
    DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SW, DIAGDIR_SE
  };
  static const DiagDirection _search_dir_2[] = {
    DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE
  };
 
  /* do not allow signal updates for two companies in one run */
  assert(_globset.IsEmpty() || owner == _last_owner);
 
  _last_owner = owner;
 
  _globset.Add(tile, _search_dir_1[track]);
  _globset.Add(tile, _search_dir_2[track]);
 
  if (_globset.Items() >= SIG_GLOB_UPDATE) {
    /* too many items, force update */
    UpdateSignalsInBuffer(_last_owner);
    _last_owner = INVALID_OWNER;
  }
}
 
 
void AddSideToSignalBuffer(TileIndex tile, DiagDirection side, Owner owner)
{
  /* do not allow signal updates for two companies in one run */
  assert(_globset.IsEmpty() || owner == _last_owner);
 
  _last_owner = owner;
 
  _globset.Add(tile, side);
 
  if (_globset.Items() >= SIG_GLOB_UPDATE) {
    /* too many items, force update */
    UpdateSignalsInBuffer(_last_owner);
    _last_owner = INVALID_OWNER;
  }
}
 
SigSegState UpdateSignalsOnSegment(TileIndex tile, DiagDirection side, Owner owner)
{
  assert(_globset.IsEmpty());
  _globset.Add(tile, side);
 
  return UpdateSignalsInBuffer(owner);
}
 
 
void SetSignalsOnBothDir(TileIndex tile, Track track, Owner owner)
{
  assert(_globset.IsEmpty());
 
  AddTrackToSignalBuffer(tile, track, owner);
  UpdateSignalsInBuffer(owner);
}