summaryrefslogtreecommitdiff
path: root/src/signal.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/signal.cpp')
-rw-r--r--src/signal.cpp582
1 files changed, 582 insertions, 0 deletions
diff --git a/src/signal.cpp b/src/signal.cpp
new file mode 100644
index 000000000..79997461c
--- /dev/null
+++ b/src/signal.cpp
@@ -0,0 +1,582 @@
+/* $Id$ */
+
+/** @file signal.cpp functions related to rail signals updating */
+
+#include "stdafx.h"
+#include "openttd.h"
+#include "debug.h"
+#include "tile_cmd.h"
+#include "rail_map.h"
+#include "road_map.h"
+#include "station_map.h"
+#include "tunnelbridge_map.h"
+#include "vehicle_func.h"
+#include "train.h"
+#include "newgrf_station.h"
+#include "functions.h"
+#include "track_type.h"
+#include "track_func.h"
+#include "signal_func.h"
+#include "player.h"
+
+
+/** these are the maximums used for updating signal blocks */
+enum {
+ SIG_TBU_SIZE = 64, ///< number of signals entering to block
+ SIG_TBD_SIZE = 256, ///< number of intersections - open nodes in current block
+ SIG_GLOB_SIZE = 64, ///< number of open blocks (block can be opened more times until detected)
+};
+
+/** incidating trackbits with given enterdir */
+static const TrackBitsByte _enterdir_to_trackbits[DIAGDIR_END] = {
+ {TRACK_BIT_3WAY_NE},
+ {TRACK_BIT_3WAY_SE},
+ {TRACK_BIT_3WAY_SW},
+ {TRACK_BIT_3WAY_NW}
+};
+
+/** incidating trackdirbits with given enterdir */
+static const TrackdirBitsShort _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}
+};
+
+/**
+ * Set containing 'items' items of 'tile and Tdir'
+ * No tree structure is used because it would cause
+ * slowdowns in most usual cases
+ */
+template <typename Tdir, uint items>
+struct SmallSet {
+private:
+ uint n; // actual number of units
+ bool overflowed; // did we try to oveflow the set?
+ const char *name; // name, used for debugging purposes...
+
+ /** Element of set */
+ struct SSdata {
+ TileIndex tile;
+ Tdir dir;
+ } data[items];
+
+public:
+ /** Constructor - just set default values and 'name' */
+ SmallSet(const char *name) : n(0), overflowed(false), name(name) { }
+
+ /** Reset variables to default values */
+ void Reset()
+ {
+ this->n = 0;
+ this->overflowed = false;
+ }
+
+ /**
+ * Returns value of 'oveflowed'
+ * @return did we try to overflow the set?
+ */
+ bool Overflowed()
+ {
+ return this->overflowed;
+ }
+
+ /**
+ * Checks for empty set
+ * @return is the set empty?
+ */
+ bool IsEmpty()
+ {
+ return this->n == 0;
+ }
+
+ /**
+ * Checks for full set
+ * @return is the set full?
+ */
+ bool IsFull()
+ {
+ return this->n == lengthof(data);
+ }
+
+ /**
+ * Tries to remove first instance of given tile and dir
+ * @param tile tile
+ * @param dir and dir to remove
+ * @return element was found and removed
+ */
+ 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;
+ }
+
+ /**
+ * Tries to find given tile and dir in the set
+ * @param tile tile
+ * @param dir and dir to find
+ * @return true iff the tile & dir elemnt was found
+ */
+ 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;
+ }
+
+ /**
+ * Adds tile & dir into the set, checks for full set
+ * Sets the 'overflowed' flag if the set was full
+ * @param tile tile
+ * @param dir and dir to add
+ * @return true iff the item could be added (set wasn't full)
+ */
+ bool Add(TileIndex tile, Tdir dir)
+ {
+ if (this->IsFull()) {
+ overflowed = true;
+ DEBUG(misc, 0, "SignalSegment too complex. Set %s is full (maximum %d)", name, items);
+ return false; // set is full
+ }
+
+ this->data[this->n].tile = tile;
+ this->data[this->n].dir = dir;
+ this->n++;
+
+ return true;
+ }
+
+ /**
+ * Reads the last added element into the set
+ * @param tile pointer where tile is written to
+ * @param dir pointer where dir is written to
+ * @return false iff the set was empty
+ */
+ 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"); ///< set of signals that will be updated
+static SmallSet<DiagDirection, SIG_TBD_SIZE> _tbdset("_tbdset"); ///< set of open nodes in current signal block
+static SmallSet<DiagDirection, SIG_GLOB_SIZE> _globset("_globset"); ///< set of places to be updated in following runs
+
+
+/** Check whether there is a train on rail, not in a depot */
+static void *TrainOnTileEnum(Vehicle *v, void *)
+{
+ if (v->type != VEH_TRAIN || v->u.rail.track == TRACK_BIT_DEPOT) return NULL;
+
+ return v;
+}
+
+
+/**
+ * Perform some operations before adding data into Todo set
+ * The new and reverse direction is removed from _globset, because we are sure
+ * it doesn't need to be checked again
+ * Also, remove reverse direction from _tbdset
+ * This is the 'core' part so the graph seaching won't enter any tile twice
+ *
+ * @param t1 tile we are entering
+ * @param d1 direction (tile side) we are entering
+ * @param t2 tile we are leaving
+ * @param d2 direction (tile side) we are leaving
+ * @return false iff reverse direction was in Todo set
+ */
+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
+
+ if (_tbdset.Remove(t2, d2)) return false;
+
+ return true;
+}
+
+
+/**
+ * Perform some operations before adding data into Todo set
+ * The new and reverse direction is removed from Global set, because we are sure
+ * it doesn't need to be checked again
+ * Also, remove reverse direction from Todo set
+ * This is the 'core' part so the graph seaching won't enter any tile twice
+ *
+ * @param t1 tile we are entering
+ * @param d1 direction (tile side) we are entering
+ * @param t2 tile we are leaving
+ * @param d2 direction (tile side) we are leaving
+ * @return false iff the Todo buffer would be overrun
+ */
+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);
+}
+
+
+/** Current signal block state flags */
+enum SigFlags {
+ SF_NONE = 0,
+ SF_TRAIN = 1 << 0, ///< train found in segment
+ SF_EXIT = 1 << 1, ///< exitsignal found
+ SF_EXIT2 = 1 << 2, ///< two or more exits found
+ SF_GREEN = 1 << 3, ///< green exitsignal found
+ SF_GREEN2 = 1 << 4, ///< two or more green exits found
+ SF_FULL = 1 << 5, ///< some of buffers was full, do not continue
+};
+
+DECLARE_ENUM_AS_BIT_SET(SigFlags)
+
+
+/**
+ * Search signal block
+ *
+ * @param owner owner whose signals we are updating
+ * @return SigFlags
+ */
+static SigFlags ExploreSegment(Owner owner)
+{
+ SigFlags flags = SF_NONE;
+
+ while (!_tbdset.IsEmpty()) {
+ TileIndex tile;
+ DiagDirection enterdir;
+
+ _tbdset.Get(&tile, &enterdir);
+
+ 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 & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
+ exitdir = GetRailDepotDirection(tile);
+ tile += TileOffsByDiagDir(exitdir);
+ enterdir = ReverseDiagDir(exitdir);
+ break;
+ } else if (enterdir == GetRailDepotDirection(tile)) { // entered a depot
+ if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
+ continue;
+ } else {
+ continue;
+ }
+ }
+
+ if (GetRailTileType(tile) == RAIL_TILE_WAYPOINT) {
+ if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
+ tile += TileOffsByDiagDir(exitdir);
+ /* enterdir and exitdir stay the same */
+ break;
+ }
+
+ 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 (!(flags & SF_TRAIN) && VehicleFromPos(tile, &tracks, &EnsureNoTrainOnTrackProc)) flags |= SF_TRAIN;
+ } else {
+ if (tracks_masked == TRACK_BIT_NONE) continue; // no incidating track
+ if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
+ }
+
+ 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 * 0x101) & _enterdir_to_trackdirbits[enterdir]);
+ Trackdir reversedir = ReverseTrackdir(trackdir);
+ /* add (tile, reversetrackdir) to 'to-be-updated' set when there is
+ * ANY 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 (!_tbuset.Add(tile, reversedir)) return flags | SF_FULL;
+ }
+ /* if it is a presignal EXIT in OUR direction and we haven't found 2 green exits yes, do special check */
+ if (!(flags & SF_GREEN2) && (sig & SIGTYPE_EXIT) && HasSignalOnTrackdir(tile, trackdir)) { // found presignal exit
+ if (flags & SF_EXIT) flags |= SF_EXIT2; // found two (or more) exits
+ flags |= SF_EXIT; // found at least one exit - allow for compiler optimizations
+ if (GetSignalStateByTrackdir(tile, trackdir) == SIGNAL_STATE_GREEN) { // found green presignal exit
+ if (flags & SF_GREEN) flags |= SF_GREEN2;
+ flags |= SF_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 | SF_FULL;
+ }
+ }
+
+ continue; // continue the while() loop
+ }
+
+ case MP_STATION:
+ if (!IsRailwayStation(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 & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_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 & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_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 & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_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 & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_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 | SF_FULL;
+ }
+
+ return flags;
+}
+
+
+/**
+ * Update signals around segment in _tbuset
+ *
+ * @param flags info about segment
+ */
+static void UpdateSignalsAroundSegment(SigFlags flags)
+{
+ while (!_tbuset.IsEmpty()) {
+ TileIndex tile;
+ Trackdir trackdir;
+ _tbuset.Get(&tile, &trackdir);
+
+ assert(HasSignalOnTrackdir(tile, trackdir));
+
+ SignalType sig = GetSignalType(tile, TrackdirToTrack(trackdir));
+ SignalState newstate = SIGNAL_STATE_GREEN;
+
+ /* determine whether the new state is red */
+ if (flags & SF_TRAIN) {
+ /* train in the segment */
+ 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 & SF_EXIT2 &&
+ /* no green exit */
+ (!(flags & SF_GREEN) ||
+ /* only one green exit, and it is this one - so all other exits are red */
+ (!(flags & SF_GREEN2) && GetSignalStateByTrackdir(tile, ReverseTrackdir(trackdir)) == SIGNAL_STATE_GREEN))) {
+ newstate = SIGNAL_STATE_RED;
+ }
+ } else { // entry, at least one exit, no green exit
+ if (sig & SIGTYPE_ENTRY && (flags & SF_EXIT && !(flags & SF_GREEN))) newstate = SIGNAL_STATE_RED;
+ }
+ }
+
+ /* only when the state changes */
+ if (newstate != GetSignalStateByTrackdir(tile, trackdir)) {
+ if (sig & SIGTYPE_EXIT) {
+ /* 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);
+ }
+ }
+
+}
+
+
+/** Reset all sets after one set overflowed */
+static inline void ResetSets()
+{
+ _tbuset.Reset();
+ _tbdset.Reset();
+ _globset.Reset();
+}
+
+
+/**
+ * Updates blocks in _globset buffer
+ *
+ * @return false iff presignal entry would be green (needed for trains leaving depot)
+ */
+static bool UpdateSignalsInBuffer()
+{
+ bool first = true; // first block?
+ bool state = false; // value to return
+
+ Owner owner = OWNER_NONE; // owner whose signals we are updating
+
+ while (!_globset.IsEmpty()) {
+ assert(_tbuset.IsEmpty());
+ assert(_tbdset.IsEmpty());
+
+ TileIndex tile;
+ DiagDirection dir;
+
+ _globset.Get(&tile, &dir);
+
+ /* 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)));
+ if (first) owner = GetTileOwner(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));
+ if (first) owner = GetTileOwner(tile);
+ _tbdset.Add(tile, INVALID_DIAGDIR); // start from depot inside
+ break;
+ }
+ /* FALLTHROUGH */
+ case MP_STATION:
+ case MP_ROAD:
+ if ((TrackBits)(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0) & _enterdir_to_trackbits[dir]) != TRACK_BIT_NONE) {
+ /* only add to set when there is some 'interesting' track */
+ if (first) owner = GetTileOwner(tile);
+ _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 ((TrackBits)(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0) & _enterdir_to_trackbits[dir]) != TRACK_BIT_NONE) {
+ if (first) owner = GetTileOwner(tile);
+ _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(IsValidPlayer(owner));
+ 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;
+ state = (flags & SF_TRAIN) || (flags & SF_EXIT && !(flags & SF_GREEN)) || (flags & SF_FULL); // true iff train CAN'T leave the depot
+ }
+
+ /* do not do anything when some buffer was full */
+ if (flags & SF_FULL) break;
+
+ UpdateSignalsAroundSegment(flags);
+ }
+
+ return state;
+}
+
+
+/**
+ * Update signals, starting at one side of a tile
+ * Will check tile next to this at opposite side too
+ *
+ * @see UpdateSignalsInBuffer()
+ * @param tile tile where we start
+ * @param side side of tile
+ * @return false iff train can leave depot
+ */
+bool UpdateSignalsOnSegment(TileIndex tile, DiagDirection side)
+{
+ assert(_globset.IsEmpty());
+ _globset.Add(tile, side);
+
+ return UpdateSignalsInBuffer();
+}
+
+
+/**
+ * Update signals at segments that are at both ends of
+ * given (existent or non-existent) track
+ *
+ * @see UpdateSignalsInBuffer()
+ * @param tile tile where we start
+ * @param track track at which ends we will update signals
+ */
+void SetSignalsOnBothDir(TileIndex tile, Track track)
+{
+ 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
+ };
+
+ assert(_globset.IsEmpty());
+
+ _globset.Add(tile, _search_dir_1[track]);
+ _globset.Add(tile, _search_dir_2[track]);
+ UpdateSignalsInBuffer();
+}