(svn r11940) -Codechange: Store short filename once per open file instead of once per sprite cache entry. Not all file types need this, but most of the time no sprite cache entry needed it either.
/* $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_func.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 = 128, ///< number of open blocks (block can be opened more times until detected)
SIG_GLOB_UPDATE = 64, ///< how many items need to be in _globset to force update
};
/* need to typecast to compile with MorphOS */
assert_compile((int)SIG_GLOB_UPDATE <= (int)SIG_GLOB_SIZE);
/** 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);
}
/**
* Reads the number of items
* @return current number of items
*/
uint Items()
{
return this->n;
}
/**
* 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;
TileIndex tile;
DiagDirection enterdir;
while (_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)
{
TileIndex tile;
Trackdir trackdir;
while (_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
*
* @param owner player whose signals we are updating
* @return false iff presignal entry would be green (needed for trains leaving depot)
* @pre IsValidPlayer(owner)
*/
static bool UpdateSignalsInBuffer(Owner owner)
{
assert(IsValidPlayer(owner));
bool first = true; // first block?
bool state = false; // value to return
TileIndex tile;
DiagDirection dir;
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 ((TrackBits)(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 ((TrackBits)(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;
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) {
ResetSets(); // free all sets
break;
}
UpdateSignalsAroundSegment(flags);
}
return state;
}
static Owner _last_owner = INVALID_OWNER; ///< last owner whose track was put into _globset
/**
* Update signals in buffer
* Called from 'outside'
*/
void UpdateSignalsInBuffer()
{
if (!_globset.IsEmpty()) {
UpdateSignalsInBuffer(_last_owner);
_last_owner = INVALID_OWNER; // invalidate
}
}
/**
* Add track to signal update buffer
*
* @param tile tile where we start
* @param track track at which ends we will update signals
* @param owner owner whose signals we will update
*/
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 players 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;
}
}
/**
* Add side of tile to signal update buffer
*
* @param tile tile where we start
* @param side side of tile
* @param owner owner whose signals we will update
*/
void AddSideToSignalBuffer(TileIndex tile, DiagDirection side, Owner owner)
{
/* do not allow signal updates for two players 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;
}
}
/**
* 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
* @param owner owner whose signals we will update
* @return false iff train can leave depot
*/
bool UpdateSignalsOnSegment(TileIndex tile, DiagDirection side, Owner owner)
{
assert(_globset.IsEmpty());
_globset.Add(tile, side);
return UpdateSignalsInBuffer(owner);
}
/**
* 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
* @param owner owner whose signals we will update
*/
void SetSignalsOnBothDir(TileIndex tile, Track track, Owner owner)
{
assert(_globset.IsEmpty());
AddTrackToSignalBuffer(tile, track, owner);
UpdateSignalsInBuffer(owner);
}