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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */

 
#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 "table/signal_data.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 constexpr DiagDirectionIndexArray<TrackBits> _enterdir_to_trackbits{
  TRACK_BIT_3WAY_NE,
  TRACK_BIT_3WAY_SE,
  TRACK_BIT_3WAY_SW,
  TRACK_BIT_3WAY_NW,
};

static constexpr DiagDirectionIndexArray<TrackdirBits> _enterdir_to_trackdirbits{{{
  {Trackdir::X_SW, Trackdir::Upper_W, Trackdir::Right_S},
  {Trackdir::Y_NW, Trackdir::Lower_W, Trackdir::Right_N},
  {Trackdir::X_NE, Trackdir::Lower_E, Trackdir::Left_N},
  {Trackdir::Y_SE, Trackdir::Upper_E, Trackdir::Left_S},
}}};

template <typename Tdir, uint items>
struct SmallSet {
private:
  uint n = 0; 
  bool overflowed = false; 
  const std::string_view name; 

  struct SSdata {
    TileIndex tile;
    Tdir dir;
  } data[items];
 
public:
  SmallSet(std::string_view name) : 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 bool IsTrainAndNotInDepot(const Vehicle *v)
{
  return v->type == VehicleType::Train && Train::From(v)->track != Track::Depot;
}
 

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 = DiagDirection::Invalid;
 
  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 == DiagDirection::Invalid ? DiagDirection::Invalid : ReverseDiagDir(enterdir); // expected new exit direction (for straight line)
 
    switch (GetTileType(tile)) {
      case TileType::Railway: {
        if (GetTileOwner(tile) != owner) continue; // do not propagate signals on others' tiles (remove for tracksharing)
 
        if (IsRailDepot(tile)) {
          if (enterdir == DiagDirection::Invalid) { // from 'inside' - train just entered or left the depot
            if (!flags.Test(SigFlag::Train) && HasVehicleOnTile(tile, IsTrainAndNotInDepot)) 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) && HasVehicleOnTile(tile, IsTrainAndNotInDepot)) flags.Set(SigFlag::Train);
            continue;
          } else {
            continue;
          }
        }
 
        assert(IsValidDiagDirection(enterdir));
        TrackBits tracks = GetTrackBits(tile); // trackbits of tile
        TrackBits tracks_masked = tracks & _enterdir_to_trackbits[enterdir]; // only accessible trackbits
 
        if (tracks == TRACK_BIT_HORZ || tracks == TRACK_BIT_VERT) { // there is exactly one accessible 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.None()) continue; // no accessible track
          if (!flags.Test(SigFlag::Train) && HasVehicleOnTile(tile, IsTrainAndNotInDepot)) flags.Set(SigFlag::Train);
        }
 
        /* Is this a track merge or split? */
        if (tracks.Count() > 1) 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 = (TrackBitsToTrackdirBits(tracks) & _enterdir_to_trackdirbits[enterdir]).GetNthSetBit(0).value();
            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) == SignalState::Green) { // found green presignal exit
                if (flags.Test(SigFlag::Green)) flags.Set(SigFlag::MultiGreen);
                flags.Set(SigFlag::Green);
              }
            }
 
            continue;
          }
        }
 
        for (DiagDirection dir : EnumRange(DiagDirection::End)) { // test all possible exit directions
          if (dir != enterdir && tracks.Any(_enterdir_to_trackbits[dir])) { // any accessible track?
            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 TileType::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) && HasVehicleOnTile(tile, IsTrainAndNotInDepot)) flags.Set(SigFlag::Train);
        tile += TileOffsByDiagDir(exitdir);
        break;
 
      case TileType::Road:
        if (!IsLevelCrossing(tile)) continue;
        if (GetTileOwner(tile) != owner) continue;
        if (DiagDirToAxis(enterdir) == GetCrossingRoadAxis(tile)) continue; // different axis
 
        if (!flags.Test(SigFlag::Train) && HasVehicleOnTile(tile, IsTrainAndNotInDepot)) flags.Set(SigFlag::Train);
        tile += TileOffsByDiagDir(exitdir);
        break;
 
      case TileType::TunnelBridge: {
        if (GetTileOwner(tile) != owner) continue;
        if (GetTunnelBridgeTransportType(tile) != TRANSPORT_RAIL) continue;
        DiagDirection dir = GetTunnelBridgeDirection(tile);
 
        if (enterdir == DiagDirection::Invalid) { // incoming from the wormhole
          if (!flags.Test(SigFlag::Train) && HasVehicleOnTile(tile, IsTrainAndNotInDepot)) 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) && HasVehicleOnTile(tile, IsTrainAndNotInDepot)) flags.Set(SigFlag::Train);
          tile = GetOtherTunnelBridgeEnd(tile); // just skip to exit tile
          enterdir = DiagDirection::Invalid;
          exitdir = DiagDirection::Invalid;
        }
        }
        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 = Trackdir::Invalid;
 
  while (_tbuset.Get(&tile, &trackdir)) {
    assert(HasSignalOnTrackdir(tile, trackdir));
 
    Track track = TrackdirToTrack(trackdir);
    SignalType sig = GetSignalType(tile, track);
    SignalState newstate = SignalState::Green;
 
    /* Signal state of reserved path signals is handled by the reserve/unreserve process. */
    if (IsPbsSignal(sig) && GetRailReservationTrackBits(tile).Test(track)) continue;
 
    /* determine whether the new state is red */
    if (flags.Test(SigFlag::Train)) {
      /* train in the segment */
      newstate = SignalState::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 = SignalState::Red;
    } else {
      /* is it a bidir combo? - then do not count its other signal direction as exit */
      if (sig == SignalType::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)) == SignalState::Green))) {
          newstate = SignalState::Red;
        }
      } else { // entry, at least one exit, no green exit
        if (IsPresignalEntry(tile, TrackdirToTrack(trackdir)) && flags.Test(SigFlag::Exit) && !flags.Test(SigFlag::Green)) newstate = SignalState::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 = SigSegState::Free; // value to return
 
  TileIndex tile = INVALID_TILE; // Stop GCC from complaining about a possibly uninitialized variable (issue #8280).
  DiagDirection dir = DiagDirection::Invalid;
 
  while (_globset.Get(&tile, &dir)) {
    assert(_tbuset.IsEmpty());
    assert(_tbdset.IsEmpty());
 
    /* After updating signal, data stored are always TileType::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 TileType::TunnelBridge:
        /* 'optimization assert' - do not try to update signals when it is not needed */
        assert(GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL);
        assert(dir == DiagDirection::Invalid || dir == ReverseDiagDir(GetTunnelBridgeDirection(tile)));
        _tbdset.Add(tile, DiagDirection::Invalid);  // we can safely start from wormhole centre
        _tbdset.Add(GetOtherTunnelBridgeEnd(tile), DiagDirection::Invalid);
        break;
 
      case TileType::Railway:
        if (IsRailDepot(tile)) {
          /* 'optimization assert' do not try to update signals in other cases */
          assert(dir == DiagDirection::Invalid || dir == GetRailDepotDirection(tile));
          _tbdset.Add(tile, DiagDirection::Invalid); // start from depot inside
          break;
        }
        [[fallthrough]];
 
      case TileType::Station:
      case TileType::Road:
        if (TrackdirBitsToTrackBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, RoadTramType::Invalid).trackdirs).Any(_enterdir_to_trackbits[dir])) {
          /* 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 (TrackdirBitsToTrackBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, RoadTramType::Invalid).trackdirs).Any(_enterdir_to_trackbits[dir])) {
          _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;
      /* SigSegState::Free is set by default */
      if (flags.Test(SigFlag::Pbs)) {
        state = SigSegState::Path;
      } else if (flags.Test(SigFlag::Train) || (flags.Test(SigFlag::Exit) && !flags.Test(SigFlag::Green)) || flags.Test(SigFlag::Full)) {
        state = SigSegState::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[] = {
    DiagDirection::NE, DiagDirection::SE, DiagDirection::NE, DiagDirection::SE, DiagDirection::SW, DiagDirection::SE
  };
  static const DiagDirection _search_dir_2[] = {
    DiagDirection::SW, DiagDirection::NW, DiagDirection::NW, DiagDirection::SW, DiagDirection::NW, DiagDirection::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[to_underlying(track)]);
  _globset.Add(tile, _search_dir_2[to_underlying(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);
}