(svn r11802) -Fix [FS#716]: do not crash trains when leaving depot to a very long track

-Codechange: use dedicated pathfinder for signal updating, resulting in better performance and possible future improvements

16 files changed, 643 insertions, 244 deletions

diff --git a/projects/openttd.vcproj b/projects/openttd.vcproj
index b9c53cb7b..15ac028a0 100644
--- a/projects/openttd.vcproj
+++ b/projects/openttd.vcproj
@@ -345,6 +345,9 @@
 				RelativePath=".\..\src\settings.cpp">
 			</File>
 			<File
+				RelativePath=".\..\src\signal.cpp">
+			</File>
+			<File
 				RelativePath=".\..\src\signs.cpp">
 			</File>
 			<File
@@ -649,6 +652,9 @@
 				RelativePath=".\..\src\signs.h">
 			</File>
 			<File
+				RelativePath=".\..\src\signal_func.h">
+			</File>
+			<File
 				RelativePath=".\..\src\slope.h">
 			</File>
 			<File
diff --git a/projects/openttd_vs80.vcproj b/projects/openttd_vs80.vcproj
index a7762d24e..dbeceafe9 100644
--- a/projects/openttd_vs80.vcproj
+++ b/projects/openttd_vs80.vcproj
@@ -692,6 +692,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\signal.cpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\signs.cpp"
 				>
 			</File>
@@ -1096,6 +1100,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\signal_func.h"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\slope.h"
 				>
 			</File>
diff --git a/projects/openttd_vs90.vcproj b/projects/openttd_vs90.vcproj
index 1a074660f..c7a4c4948 100644
--- a/projects/openttd_vs90.vcproj
+++ b/projects/openttd_vs90.vcproj
@@ -689,6 +689,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\signal.cpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\signs.cpp"
 				>
 			</File>
@@ -1093,6 +1097,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\signal_func.h"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\slope.h"
 				>
 			</File>
diff --git a/source.list b/source.list
index c7a5224c1..06beb45fe 100644
--- a/source.list
+++ b/source.list
@@ -66,6 +66,7 @@ screenshot.cpp
 	sdl.cpp
 #end
 settings.cpp
+signal.cpp
 signs.cpp
 sound.cpp
 spritecache.cpp
@@ -182,6 +183,7 @@ sound/sdl_s.h
 video/sdl_v.h
 settings.h
 signs.h
+signal_func.h
 slope.h
 sound.h
 sprite.h
diff --git a/src/economy.cpp b/src/economy.cpp
index bdef0a6c1..ca6177c34 100644
--- a/src/economy.cpp
+++ b/src/economy.cpp
@@ -43,6 +43,7 @@
 #include "track_type.h"
 #include "track_func.h"
 #include "rail_map.h"
+#include "signal_func.h"
 #include "gfx_func.h"
 
 /**
diff --git a/src/rail.h b/src/rail.h
index a789b57eb..5f91490c9 100644
--- a/src/rail.h
+++ b/src/rail.h
@@ -96,14 +96,6 @@ struct RailtypeInfo {
 };
 
 
-/** these are the maximums used for updating signal blocks, and checking if a depot is in a pbs block */
-enum {
-	NUM_SSD_ENTRY = 256, ///< max amount of blocks
-	NUM_SSD_STACK =  32, ///< max amount of blocks to check recursively
-};
-
-
-
 /**
  * Returns a pointer to the Railtype information for a given railtype
  * @param railtype the rail type which the information is requested for
@@ -188,6 +180,7 @@ static inline Money RailConvertCost(RailType from, RailType to)
 void *UpdateTrainPowerProc(Vehicle *v, void *data);
 void DrawTrainDepotSprite(int x, int y, int image, RailType railtype);
 void DrawDefaultWaypointSprite(int x, int y, RailType railtype);
+void *EnsureNoTrainOnTrackProc(Vehicle *v, void *data);
 
 /**
  * Draws overhead wires and pylons for electric railways.
diff --git a/src/rail_cmd.cpp b/src/rail_cmd.cpp
index b86616ba5..78e8766a8 100644
--- a/src/rail_cmd.cpp
+++ b/src/rail_cmd.cpp
@@ -42,6 +42,7 @@
 #include "window_func.h"
 #include "vehicle_func.h"
 #include "sound_func.h"
+#include "signal_func.h"
 
 
 const byte _track_sloped_sprites[14] = {
@@ -84,7 +85,7 @@ const byte _track_sloped_sprites[14] = {
  */
 
 
-static void *EnsureNoTrainOnTrackProc(Vehicle *v, void *data)
+void *EnsureNoTrainOnTrackProc(Vehicle *v, void *data)
 {
 	TrackBits rail_bits = *(TrackBits *)data;
 
@@ -740,7 +741,7 @@ CommandCost CmdBuildTrainDepot(TileIndex tile, uint32 flags, uint32 p1, uint32 p
 
 		d->town_index = ClosestTownFromTile(tile, (uint)-1)->index;
 
-		UpdateSignalsOnSegment(tile, dir);
+		UpdateSignalsOnSegment(tile, INVALID_DIAGDIR);
 		YapfNotifyTrackLayoutChange(tile, TrackdirToTrack(DiagdirToDiagTrackdir(dir)));
 		d_auto_delete.Detach();
 	}
@@ -1846,227 +1847,6 @@ void DrawDefaultWaypointSprite(int x, int y, RailType railtype)
 	DrawTileSequence(x, y, dts->ground_sprite + offset, dts->seq, 0);
 }
 
-struct SetSignalsData {
-	int cur;
-	int cur_stack;
-	bool stop;
-	bool has_presignal;
-
-	/* presignal info */
-	int presignal_exits;
-	int presignal_exits_free;
-
-	/* these are used to keep track of the signals that change. */
-	TrackdirByte bit[NUM_SSD_ENTRY];
-	TileIndex tile[NUM_SSD_ENTRY];
-
-	/* these are used to keep track of the stack that modifies presignals recursively */
-	TileIndex next_tile[NUM_SSD_STACK];
-	DiagDirectionByte next_dir[NUM_SSD_STACK];
-
-};
-
-static bool SetSignalsEnumProc(TileIndex tile, void* data, Trackdir trackdir, uint length, byte* state)
-{
-	SetSignalsData* ssd = (SetSignalsData*)data;
-	Track track = TrackdirToTrack(trackdir);
-
-	if (!IsTileType(tile, MP_RAILWAY)) return false;
-
-	/* the tile has signals? */
-	if (HasSignalOnTrack(tile, track)) {
-		if (HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir))) {
-			/* yes, add the signal to the list of signals */
-			if (ssd->cur != NUM_SSD_ENTRY) {
-				ssd->tile[ssd->cur] = tile; // remember the tile index
-				ssd->bit[ssd->cur] = trackdir; // and the controlling bit number
-				ssd->cur++;
-			}
-
-			/* remember if this block has a presignal. */
-			ssd->has_presignal |= IsPresignalEntry(tile, track);
-		}
-
-		if (HasSignalOnTrackdir(tile, trackdir) && IsPresignalExit(tile, track)) {
-			/* this is an exit signal that points out from the segment */
-			ssd->presignal_exits++;
-			if (GetSignalStateByTrackdir(tile, trackdir) != SIGNAL_STATE_RED)
-				ssd->presignal_exits_free++;
-		}
-
-		return true;
-	} else if (IsTileDepotType(tile, TRANSPORT_RAIL)) {
-		return true; // don't look further if the tile is a depot
-	}
-
-	return false;
-}
-
-static void *SignalVehicleCheckProc(Vehicle *v, void *data)
-{
-	uint track = *(uint*)data;
-
-	if (v->type != VEH_TRAIN) return NULL;
-
-	/* Are we on the same piece of track? */
-	if (track & v->u.rail.track * 0x101) return v;
-
-	return NULL;
-}
-
-/* Special check for SetSignalsAfterProc, to see if there is a vehicle on this tile */
-static bool SignalVehicleCheck(TileIndex tile, uint track)
-{
-	if (IsTileType(tile, MP_TUNNELBRIDGE)) {
-		/* Locate vehicles in tunnels or on bridges */
-		return GetVehicleTunnelBridge(tile, GetOtherTunnelBridgeEnd(tile)) != NULL;
-	} else {
-		return VehicleFromPos(tile, &track, &SignalVehicleCheckProc) != NULL;
-	}
-}
-
-static void SetSignalsAfterProc(TrackPathFinder *tpf)
-{
-	SetSignalsData *ssd = (SetSignalsData*)tpf->userdata;
-	const TrackPathFinderLink* link;
-	uint offs;
-	uint i;
-
-	ssd->stop = false;
-
-	/* Go through all the PF tiles */
-	for (i = 0; i < lengthof(tpf->hash_head); i++) {
-		/* Empty hash item */
-		if (tpf->hash_head[i] == 0) continue;
-
-		/* If 0x8000 is not set, there is only 1 item */
-		if (!(tpf->hash_head[i] & 0x8000)) {
-			/* Check if there is a vehicle on this tile */
-			if (SignalVehicleCheck(tpf->hash_tile[i], tpf->hash_head[i])) {
-				ssd->stop = true;
-				return;
-			}
-		} else {
-			/* There are multiple items, where hash_tile points to the first item in the list */
-			offs = tpf->hash_tile[i];
-			do {
-				/* Find the next item */
-				link = PATHFIND_GET_LINK_PTR(tpf, offs);
-				/* Check if there is a vehicle on this tile */
-				if (SignalVehicleCheck(link->tile, link->flags)) {
-					ssd->stop = true;
-					return;
-				}
-				/* Goto the next item */
-			} while ((offs = link->next) != 0xFFFF);
-		}
-	}
-}
-
-static void ChangeSignalStates(SetSignalsData *ssd)
-{
-	int i;
-
-	/* thinking about presignals...
-	 * the presignal is green if,
-	 *   if no train is in the segment AND
-	 *   there is at least one green exit signal OR
-	 *   there are no exit signals in the segment */
-
-	/* then mark the signals in the segment accordingly */
-	for (i = 0; i != ssd->cur; i++) {
-		TileIndex tile = ssd->tile[i];
-		byte bit = SignalAgainstTrackdir(ssd->bit[i]);
-		uint signals = GetSignalStates(tile);
-		Track track = TrackdirToTrack(ssd->bit[i]);
-
-		/* presignals don't turn green if there is at least one presignal exit and none are free */
-		if (IsPresignalEntry(tile, track)) {
-			int ex = ssd->presignal_exits, exfree = ssd->presignal_exits_free;
-
-			/* subtract for dual combo signals so they don't count themselves */
-			if (IsPresignalExit(tile, track) && HasSignalOnTrackdir(tile, ssd->bit[i])) {
-				ex--;
-				if (GetSignalStateByTrackdir(tile, ssd->bit[i]) != SIGNAL_STATE_RED) exfree--;
-			}
-
-			/* if we have exits and none are free, make red. */
-			if (ex && !exfree) goto make_red;
-		}
-
-		/* check if the signal is unaffected. */
-		if (ssd->stop) {
-make_red:
-			/* turn red */
-			if ((bit & signals) == 0) continue;
-		} else {
-			/* turn green */
-			if ((bit & signals) != 0) continue;
-		}
-
-		/* Update signals on the other side of this exit-combo signal; it changed. */
-		if (IsPresignalExit(tile, track)) {
-			if (ssd->cur_stack != NUM_SSD_STACK) {
-				ssd->next_tile[ssd->cur_stack] = tile;
-				ssd->next_dir[ssd->cur_stack] = TrackdirToExitdir(ssd->bit[i]);
-				ssd->cur_stack++;
-			} else {
-				DEBUG(misc, 0, "NUM_SSD_STACK too small"); /// @todo WTF is this???
-			}
-		}
-
-		/* it changed, so toggle it */
-		SetSignalStates(tile, signals ^ bit);
-		MarkTileDirtyByTile(tile);
-	}
-}
-
-
-bool UpdateSignalsOnSegment(TileIndex tile, DiagDirection direction)
-{
-	SetSignalsData ssd;
-	int result = -1;
-
-	ssd.cur_stack = 0;
-
-	for (;;) {
-		/* go through one segment and update all signals pointing into that segment. */
-		ssd.cur = ssd.presignal_exits = ssd.presignal_exits_free = 0;
-		ssd.has_presignal = false;
-
-		FollowTrack(tile, 0xC000 | TRANSPORT_RAIL, 0, direction, SetSignalsEnumProc, SetSignalsAfterProc, &ssd);
-		ChangeSignalStates(&ssd);
-
-		/* remember the result only for the first iteration. */
-		if (result < 0) {
-			/* stay in depot while segment is occupied or while all presignal exits are blocked */
-			result = ssd.stop || (ssd.presignal_exits > 0 && ssd.presignal_exits_free == 0);
-		}
-
-		/* if any exit signals were changed, we need to keep going to modify the stuff behind those. */
-		if (ssd.cur_stack == 0) break;
-
-		/* one or more exit signals were changed, so we need to update another segment too. */
-		tile = ssd.next_tile[--ssd.cur_stack];
-		direction = ssd.next_dir[ssd.cur_stack];
-	}
-
-	return result != 0;
-}
-
-void SetSignalsOnBothDir(TileIndex tile, byte 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
-	};
-
-	UpdateSignalsOnSegment(tile, _search_dir_1[track]);
-	UpdateSignalsOnSegment(tile, _search_dir_2[track]);
-}
-
 static uint GetSlopeZ_Track(TileIndex tile, uint x, uint y)
 {
 	uint z;
diff --git a/src/rail_map.h b/src/rail_map.h
index 9b9bc16ef..d4f63c72b 100644
--- a/src/rail_map.h
+++ b/src/rail_map.h
@@ -375,6 +375,18 @@ static inline SignalState GetSignalStateByTrackdir(TileIndex tile, Trackdir trac
 		SIGNAL_STATE_GREEN : SIGNAL_STATE_RED;
 }
 
+/**
+ * Sets the state of the signal along the given trackdir.
+ */
+static inline void SetSignalStateByTrackdir(TileIndex tile, Trackdir trackdir, SignalState state)
+{
+	if (state == SIGNAL_STATE_GREEN) { // set 1
+		SetSignalStates(tile, GetSignalStates(tile) | SignalAlongTrackdir(trackdir));
+	} else {
+		SetSignalStates(tile, GetSignalStates(tile) & ~SignalAlongTrackdir(trackdir));
+	}
+}
+
 
 /**
  * Return the rail type of tile, or INVALID_RAILTYPE if this is no rail tile.
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();
+}
diff --git a/src/signal_func.h b/src/signal_func.h
index 1dff79429..cc70dcb08 100644
--- a/src/signal_func.h
+++ b/src/signal_func.h
@@ -6,6 +6,9 @@
 #define SIGNAL_FUNC_H
 
 #include "track_type.h"
+#include "tile_type.h"
+#include "direction_type.h"
+#include "track_type.h"
 
 /**
  * Maps a trackdir to the bit that stores its status in the map arrays, in the
@@ -37,4 +40,7 @@ static inline byte SignalOnTrack(Track track)
 	return _signal_on_track[track];
 }
 
+bool UpdateSignalsOnSegment(TileIndex tile, DiagDirection side);
+void SetSignalsOnBothDir(TileIndex tile, Track track);
+
 #endif /* SIGNAL_FUNC_H */
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
index dbe6808a4..a57784b58 100644
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -45,6 +45,8 @@
 #include "date_func.h"
 #include "vehicle_func.h"
 #include "string_func.h"
+#include "signal_func.h"
+
 
 DEFINE_OLD_POOL_GENERIC(Station, Station)
 DEFINE_OLD_POOL_GENERIC(RoadStop, RoadStop)
diff --git a/src/train_cmd.cpp b/src/train_cmd.cpp
index 190bf5ae2..4ae2ddca6 100644
--- a/src/train_cmd.cpp
+++ b/src/train_cmd.cpp
@@ -43,6 +43,7 @@
 #include "date_func.h"
 #include "vehicle_func.h"
 #include "sound_func.h"
+#include "signal_func.h"
 #include "variables.h"
 #include "autoreplace_gui.h"
 #include "gfx_func.h"
@@ -2156,7 +2157,7 @@ static bool CheckTrainStayInDepot(Vehicle *v)
 
 		v->load_unload_time_rem = 0;
 
-		if (UpdateSignalsOnSegment(v->tile, DirToDiagDir(v->direction))) {
+		if (UpdateSignalsOnSegment(v->tile, INVALID_DIAGDIR)) {
 			InvalidateWindowClasses(WC_TRAINS_LIST);
 			return true;
 		}
@@ -2175,7 +2176,7 @@ static bool CheckTrainStayInDepot(Vehicle *v)
 	v->UpdateDeltaXY(v->direction);
 	v->cur_image = v->GetImage(v->direction);
 	VehiclePositionChanged(v);
-	UpdateSignalsOnSegment(v->tile, DirToDiagDir(v->direction));
+	UpdateSignalsOnSegment(v->tile, INVALID_DIAGDIR);
 	UpdateTrainAcceleration(v);
 	InvalidateWindowData(WC_VEHICLE_DEPOT, v->tile);
 
@@ -3114,7 +3115,7 @@ static void DeleteLastWagon(Vehicle *v)
 	delete v;
 
 	if (v->u.rail.track != TRACK_BIT_DEPOT && v->u.rail.track != TRACK_BIT_WORMHOLE)
-		SetSignalsOnBothDir(v->tile, FIND_FIRST_BIT(v->u.rail.track));
+		SetSignalsOnBothDir(v->tile, (Track)(FIND_FIRST_BIT(v->u.rail.track)));
 
 	/* Check if the wagon was on a road/rail-crossing and disable it if no
 	 * others are on it */
@@ -3125,11 +3126,8 @@ static void DeleteLastWagon(Vehicle *v)
 
 		if (GetVehicleTunnelBridge(v->tile, endtile) != NULL) return; // tunnel / bridge is busy
 
-		DiagDirection dir = GetTunnelBridgeDirection(v->tile);
-
 		/* v->direction is "random", so it cannot be used to determine the direction of the track */
-		UpdateSignalsOnSegment(v->tile, dir);
-		UpdateSignalsOnSegment(endtile, ReverseDiagDir(dir));
+		UpdateSignalsOnSegment(v->tile, INVALID_DIAGDIR);
 	}
 }
 
diff --git a/src/tunnelbridge_cmd.cpp b/src/tunnelbridge_cmd.cpp
index 2b8964e78..26e43e872 100644
--- a/src/tunnelbridge_cmd.cpp
+++ b/src/tunnelbridge_cmd.cpp
@@ -35,6 +35,7 @@
 #include "functions.h"
 #include "vehicle_func.h"
 #include "sound_func.h"
+#include "signal_func.h"
 
 
 const Bridge orig_bridge[] = {
@@ -419,7 +420,7 @@ not_valid_below:;
 
 	if (flags & DC_EXEC && railtype != INVALID_RAILTYPE) {
 		Track track = AxisToTrack(direction);
-		SetSignalsOnBothDir(tile_start, track);
+		UpdateSignalsOnSegment(tile_start, INVALID_DIAGDIR);
 		YapfNotifyTrackLayoutChange(tile_start, track);
 	}
 
@@ -549,7 +550,7 @@ CommandCost CmdBuildTunnel(TileIndex start_tile, uint32 flags, uint32 p1, uint32
 		if (GB(p1, 9, 1) == TRANSPORT_RAIL) {
 			MakeRailTunnel(start_tile, _current_player, direction,                 (RailType)GB(p1, 0, 4));
 			MakeRailTunnel(end_tile,   _current_player, ReverseDiagDir(direction), (RailType)GB(p1, 0, 4));
-			UpdateSignalsOnSegment(start_tile, direction);
+			UpdateSignalsOnSegment(start_tile, INVALID_DIAGDIR);
 			YapfNotifyTrackLayoutChange(start_tile, AxisToTrack(DiagDirToAxis(direction)));
 		} else {
 			MakeRoadTunnel(start_tile, _current_player, direction,                 (RoadTypes)GB(p1, 0, 3));
diff --git a/src/vehicle.cpp b/src/vehicle.cpp
index d4fac590b..5f9ea2472 100644
--- a/src/vehicle.cpp
+++ b/src/vehicle.cpp
@@ -43,6 +43,7 @@
 #include "date_func.h"
 #include "window_func.h"
 #include "vehicle_func.h"
+#include "signal_func.h"
 #include "sound_func.h"
 #include "variables.h"
 #include "autoreplace_func.h"
@@ -2175,7 +2176,7 @@ void VehicleEnterDepot(Vehicle *v)
 		case VEH_TRAIN:
 			InvalidateWindowClasses(WC_TRAINS_LIST);
 			if (!IsFrontEngine(v)) v = v->First();
-			UpdateSignalsOnSegment(v->tile, GetRailDepotDirection(v->tile));
+			UpdateSignalsOnSegment(v->tile, INVALID_DIAGDIR);
 			v->load_unload_time_rem = 0;
 			break;
 
diff --git a/src/vehicle_func.h b/src/vehicle_func.h
index 2925f0602..728d2c723 100644
--- a/src/vehicle_func.h
+++ b/src/vehicle_func.h
@@ -50,9 +50,6 @@ StringID VehicleInTheWayErrMsg(const Vehicle* v);
 Vehicle *FindVehicleBetween(TileIndex from, TileIndex to, byte z, bool without_crashed = false);
 Vehicle *GetVehicleTunnelBridge(TileIndex tile, TileIndex endtile);
 
-bool UpdateSignalsOnSegment(TileIndex tile, DiagDirection direction);
-void SetSignalsOnBothDir(TileIndex tile, byte track);
-
 Vehicle *CheckClickOnVehicle(const ViewPort *vp, int x, int y);
 
 void DecreaseVehicleValue(Vehicle *v);
diff --git a/src/waypoint.cpp b/src/waypoint.cpp
index 39d44981a..b228b0671 100644
--- a/src/waypoint.cpp
+++ b/src/waypoint.cpp
@@ -29,8 +29,10 @@
 #include "vehicle_func.h"
 #include "vehicle_base.h"
 #include "string_func.h"
+#include "signal_func.h"
 #include "player.h"
 
+
 enum {
 	MAX_WAYPOINTS_PER_TOWN = 64,
 };