summaryrefslogtreecommitdiff
path: root/src/signal.cpp
blob: d00931487edbdd883b8ec1d31447c2f88ee4bc7f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
/* $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 =  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

	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)));
				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) {
			ResetSets(); // free all sets
			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();
}