2 * This file is part of OpenTTD.
3 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
8 /** @file signal.cpp functions related to rail signals updating */
12 #include "station_map.h"
13 #include "tunnelbridge_map.h"
14 #include "vehicle_func.h"
15 #include "viewport_func.h"
17 #include "company_base.h"
19 #include "safeguards.h"
22 /** these are the maximums used for updating signal blocks */
23 static const uint SIG_TBU_SIZE
= 64; ///< number of signals entering to block
24 static const uint SIG_TBD_SIZE
= 256; ///< number of intersections - open nodes in current block
25 static const uint SIG_GLOB_SIZE
= 128; ///< number of open blocks (block can be opened more times until detected)
26 static const uint SIG_GLOB_UPDATE
= 64; ///< how many items need to be in _globset to force update
28 static_assert(SIG_GLOB_UPDATE
<= SIG_GLOB_SIZE
);
30 /** incidating trackbits with given enterdir */
31 static const TrackBits _enterdir_to_trackbits
[DIAGDIR_END
] = {
38 /** incidating trackdirbits with given enterdir */
39 static const TrackdirBits _enterdir_to_trackdirbits
[DIAGDIR_END
] = {
40 TRACKDIR_BIT_X_SW
| TRACKDIR_BIT_UPPER_W
| TRACKDIR_BIT_RIGHT_S
,
41 TRACKDIR_BIT_Y_NW
| TRACKDIR_BIT_LOWER_W
| TRACKDIR_BIT_RIGHT_N
,
42 TRACKDIR_BIT_X_NE
| TRACKDIR_BIT_LOWER_E
| TRACKDIR_BIT_LEFT_N
,
43 TRACKDIR_BIT_Y_SE
| TRACKDIR_BIT_UPPER_E
| TRACKDIR_BIT_LEFT_S
47 * Set containing 'items' items of 'tile and Tdir'
48 * No tree structure is used because it would cause
49 * slowdowns in most usual cases
51 template <typename Tdir
, uint items
>
54 uint n
; // actual number of units
55 bool overflowed
; // did we try to overflow the set?
56 const char *name
; // name, used for debugging purposes...
65 /** Constructor - just set default values and 'name' */
66 SmallSet(const char *name
) : n(0), overflowed(false), name(name
) { }
68 /** Reset variables to default values */
72 this->overflowed
= false;
76 * Returns value of 'overflowed'
77 * @return did we try to overflow the set?
81 return this->overflowed
;
85 * Checks for empty set
86 * @return is the set empty?
95 * @return is the set full?
99 return this->n
== lengthof(data
);
103 * Reads the number of items
104 * @return current number of items
113 * Tries to remove first instance of given tile and dir
115 * @param dir and dir to remove
116 * @return element was found and removed
118 bool Remove(TileIndex tile
, Tdir dir
)
120 for (uint i
= 0; i
< this->n
; i
++) {
121 if (this->data
[i
].tile
== tile
&& this->data
[i
].dir
== dir
) {
122 this->data
[i
] = this->data
[--this->n
];
131 * Tries to find given tile and dir in the set
133 * @param dir and dir to find
134 * @return true iff the tile & dir element was found
136 bool IsIn(TileIndex tile
, Tdir dir
)
138 for (uint i
= 0; i
< this->n
; i
++) {
139 if (this->data
[i
].tile
== tile
&& this->data
[i
].dir
== dir
) return true;
146 * Adds tile & dir into the set, checks for full set
147 * Sets the 'overflowed' flag if the set was full
149 * @param dir and dir to add
150 * @return true iff the item could be added (set wasn't full)
152 bool Add(TileIndex tile
, Tdir dir
)
154 if (this->IsFull()) {
156 Debug(misc
, 0, "SignalSegment too complex. Set {} is full (maximum {})", name
, items
);
157 return false; // set is full
160 this->data
[this->n
].tile
= tile
;
161 this->data
[this->n
].dir
= dir
;
168 * Reads the last added element into the set
169 * @param tile pointer where tile is written to
170 * @param dir pointer where dir is written to
171 * @return false iff the set was empty
173 bool Get(TileIndex
*tile
, Tdir
*dir
)
175 if (this->n
== 0) return false;
178 *tile
= this->data
[this->n
].tile
;
179 *dir
= this->data
[this->n
].dir
;
185 static SmallSet
<Trackdir
, SIG_TBU_SIZE
> _tbuset("_tbuset"); ///< set of signals that will be updated
186 static SmallSet
<DiagDirection
, SIG_TBD_SIZE
> _tbdset("_tbdset"); ///< set of open nodes in current signal block
187 static SmallSet
<DiagDirection
, SIG_GLOB_SIZE
> _globset("_globset"); ///< set of places to be updated in following runs
190 /** Check whether there is a train on rail, not in a depot */
191 static Vehicle
*TrainOnTileEnum(Vehicle
*v
, void *)
193 if (v
->type
!= VEH_TRAIN
|| Train::From(v
)->track
== TRACK_BIT_DEPOT
) return nullptr;
200 * Perform some operations before adding data into Todo set
201 * The new and reverse direction is removed from _globset, because we are sure
202 * it doesn't need to be checked again
203 * Also, remove reverse direction from _tbdset
204 * This is the 'core' part so the graph searching won't enter any tile twice
206 * @param t1 tile we are entering
207 * @param d1 direction (tile side) we are entering
208 * @param t2 tile we are leaving
209 * @param d2 direction (tile side) we are leaving
210 * @return false iff reverse direction was in Todo set
212 static inline bool CheckAddToTodoSet(TileIndex t1
, DiagDirection d1
, TileIndex t2
, DiagDirection d2
)
214 _globset
.Remove(t1
, d1
); // it can be in Global but not in Todo
215 _globset
.Remove(t2
, d2
); // remove in all cases
217 assert(!_tbdset
.IsIn(t1
, d1
)); // it really shouldn't be there already
219 return !_tbdset
.Remove(t2
, d2
);
224 * Perform some operations before adding data into Todo set
225 * The new and reverse direction is removed from Global set, because we are sure
226 * it doesn't need to be checked again
227 * Also, remove reverse direction from Todo set
228 * This is the 'core' part so the graph searching won't enter any tile twice
230 * @param t1 tile we are entering
231 * @param d1 direction (tile side) we are entering
232 * @param t2 tile we are leaving
233 * @param d2 direction (tile side) we are leaving
234 * @return false iff the Todo buffer would be overrun
236 static inline bool MaybeAddToTodoSet(TileIndex t1
, DiagDirection d1
, TileIndex t2
, DiagDirection d2
)
238 if (!CheckAddToTodoSet(t1
, d1
, t2
, d2
)) return true;
240 return _tbdset
.Add(t1
, d1
);
244 /** Current signal block state flags */
247 SF_TRAIN
= 1 << 0, ///< train found in segment
248 SF_EXIT
= 1 << 1, ///< exitsignal found
249 SF_EXIT2
= 1 << 2, ///< two or more exits found
250 SF_GREEN
= 1 << 3, ///< green exitsignal found
251 SF_GREEN2
= 1 << 4, ///< two or more green exits found
252 SF_FULL
= 1 << 5, ///< some of buffers was full, do not continue
253 SF_PBS
= 1 << 6, ///< pbs signal found
256 DECLARE_ENUM_AS_BIT_SET(SigFlags
)
260 * Search signal block
262 * @param owner owner whose signals we are updating
265 static SigFlags
ExploreSegment(Owner owner
)
267 SigFlags flags
= SF_NONE
;
269 TileIndex tile
= INVALID_TILE
; // Stop GCC from complaining about a possibly uninitialized variable (issue #8280).
270 DiagDirection enterdir
= INVALID_DIAGDIR
;
272 while (_tbdset
.Get(&tile
, &enterdir
)) { // tile and enterdir are initialized here, unless I'm mistaken.
273 TileIndex oldtile
= tile
; // tile we are leaving
274 DiagDirection exitdir
= enterdir
== INVALID_DIAGDIR
? INVALID_DIAGDIR
: ReverseDiagDir(enterdir
); // expected new exit direction (for straight line)
276 switch (GetTileType(tile
)) {
278 if (GetTileOwner(tile
) != owner
) continue; // do not propagate signals on others' tiles (remove for tracksharing)
280 if (IsRailDepot(tile
)) {
281 if (enterdir
== INVALID_DIAGDIR
) { // from 'inside' - train just entered or left the depot
282 if (!(flags
& SF_TRAIN
) && HasVehicleOnPos(tile
, nullptr, &TrainOnTileEnum
)) flags
|= SF_TRAIN
;
283 exitdir
= GetRailDepotDirection(tile
);
284 tile
+= TileOffsByDiagDir(exitdir
);
285 enterdir
= ReverseDiagDir(exitdir
);
287 } else if (enterdir
== GetRailDepotDirection(tile
)) { // entered a depot
288 if (!(flags
& SF_TRAIN
) && HasVehicleOnPos(tile
, nullptr, &TrainOnTileEnum
)) flags
|= SF_TRAIN
;
295 assert(IsValidDiagDirection(enterdir
));
296 TrackBits tracks
= GetTrackBits(tile
); // trackbits of tile
297 TrackBits tracks_masked
= (TrackBits
)(tracks
& _enterdir_to_trackbits
[enterdir
]); // only incidating trackbits
299 if (tracks
== TRACK_BIT_HORZ
|| tracks
== TRACK_BIT_VERT
) { // there is exactly one incidating track, no need to check
300 tracks
= tracks_masked
;
301 /* If no train detected yet, and there is not no train -> there is a train -> set the flag */
302 if (!(flags
& SF_TRAIN
) && EnsureNoTrainOnTrackBits(tile
, tracks
).Failed()) flags
|= SF_TRAIN
;
304 if (tracks_masked
== TRACK_BIT_NONE
) continue; // no incidating track
305 if (!(flags
& SF_TRAIN
) && HasVehicleOnPos(tile
, nullptr, &TrainOnTileEnum
)) flags
|= SF_TRAIN
;
308 if (HasSignals(tile
)) { // there is exactly one track - not zero, because there is exit from this tile
309 Track track
= TrackBitsToTrack(tracks_masked
); // mask TRACK_BIT_X and Y too
310 if (HasSignalOnTrack(tile
, track
)) { // now check whole track, not trackdir
311 SignalType sig
= GetSignalType(tile
, track
);
312 Trackdir trackdir
= (Trackdir
)FindFirstBit((tracks
* 0x101U
) & _enterdir_to_trackdirbits
[enterdir
]);
313 Trackdir reversedir
= ReverseTrackdir(trackdir
);
314 /* add (tile, reversetrackdir) to 'to-be-updated' set when there is
315 * ANY conventional signal in REVERSE direction
316 * (if it is a presignal EXIT and it changes, it will be added to 'to-be-done' set later) */
317 if (HasSignalOnTrackdir(tile
, reversedir
)) {
318 if (IsPbsSignal(sig
)) {
320 } else if (!_tbuset
.Add(tile
, reversedir
)) {
321 return flags
| SF_FULL
;
324 if (HasSignalOnTrackdir(tile
, trackdir
) && !IsOnewaySignal(tile
, track
)) flags
|= SF_PBS
;
326 /* if it is a presignal EXIT in OUR direction and we haven't found 2 green exits yes, do special check */
327 if (!(flags
& SF_GREEN2
) && IsPresignalExit(tile
, track
) && HasSignalOnTrackdir(tile
, trackdir
)) { // found presignal exit
328 if (flags
& SF_EXIT
) flags
|= SF_EXIT2
; // found two (or more) exits
329 flags
|= SF_EXIT
; // found at least one exit - allow for compiler optimizations
330 if (GetSignalStateByTrackdir(tile
, trackdir
) == SIGNAL_STATE_GREEN
) { // found green presignal exit
331 if (flags
& SF_GREEN
) flags
|= SF_GREEN2
;
340 for (DiagDirection dir
= DIAGDIR_BEGIN
; dir
< DIAGDIR_END
; dir
++) { // test all possible exit directions
341 if (dir
!= enterdir
&& (tracks
& _enterdir_to_trackbits
[dir
])) { // any track incidating?
342 TileIndex newtile
= tile
+ TileOffsByDiagDir(dir
); // new tile to check
343 DiagDirection newdir
= ReverseDiagDir(dir
); // direction we are entering from
344 if (!MaybeAddToTodoSet(newtile
, newdir
, tile
, dir
)) return flags
| SF_FULL
;
348 continue; // continue the while() loop
352 if (!HasStationRail(tile
)) continue;
353 if (GetTileOwner(tile
) != owner
) continue;
354 if (DiagDirToAxis(enterdir
) != GetRailStationAxis(tile
)) continue; // different axis
355 if (IsStationTileBlocked(tile
)) continue; // 'eye-candy' station tile
357 if (!(flags
& SF_TRAIN
) && HasVehicleOnPos(tile
, nullptr, &TrainOnTileEnum
)) flags
|= SF_TRAIN
;
358 tile
+= TileOffsByDiagDir(exitdir
);
362 if (!IsLevelCrossing(tile
)) continue;
363 if (GetTileOwner(tile
) != owner
) continue;
364 if (DiagDirToAxis(enterdir
) == GetCrossingRoadAxis(tile
)) continue; // different axis
366 if (!(flags
& SF_TRAIN
) && HasVehicleOnPos(tile
, nullptr, &TrainOnTileEnum
)) flags
|= SF_TRAIN
;
367 tile
+= TileOffsByDiagDir(exitdir
);
370 case MP_TUNNELBRIDGE
: {
371 if (GetTileOwner(tile
) != owner
) continue;
372 if (GetTunnelBridgeTransportType(tile
) != TRANSPORT_RAIL
) continue;
373 DiagDirection dir
= GetTunnelBridgeDirection(tile
);
375 if (enterdir
== INVALID_DIAGDIR
) { // incoming from the wormhole
376 if (!(flags
& SF_TRAIN
) && HasVehicleOnPos(tile
, nullptr, &TrainOnTileEnum
)) flags
|= SF_TRAIN
;
378 exitdir
= ReverseDiagDir(dir
);
379 tile
+= TileOffsByDiagDir(exitdir
); // just skip to next tile
380 } else { // NOT incoming from the wormhole!
381 if (ReverseDiagDir(enterdir
) != dir
) continue;
382 if (!(flags
& SF_TRAIN
) && HasVehicleOnPos(tile
, nullptr, &TrainOnTileEnum
)) flags
|= SF_TRAIN
;
383 tile
= GetOtherTunnelBridgeEnd(tile
); // just skip to exit tile
384 enterdir
= INVALID_DIAGDIR
;
385 exitdir
= INVALID_DIAGDIR
;
391 continue; // continue the while() loop
394 if (!MaybeAddToTodoSet(tile
, enterdir
, oldtile
, exitdir
)) return flags
| SF_FULL
;
402 * Update signals around segment in _tbuset
404 * @param flags info about segment
406 static void UpdateSignalsAroundSegment(SigFlags flags
)
408 TileIndex tile
= INVALID_TILE
; // Stop GCC from complaining about a possibly uninitialized variable (issue #8280).
409 Trackdir trackdir
= INVALID_TRACKDIR
;
411 while (_tbuset
.Get(&tile
, &trackdir
)) {
412 assert(HasSignalOnTrackdir(tile
, trackdir
));
414 SignalType sig
= GetSignalType(tile
, TrackdirToTrack(trackdir
));
415 SignalState newstate
= SIGNAL_STATE_GREEN
;
417 /* determine whether the new state is red */
418 if (flags
& SF_TRAIN
) {
419 /* train in the segment */
420 newstate
= SIGNAL_STATE_RED
;
422 /* is it a bidir combo? - then do not count its other signal direction as exit */
423 if (sig
== SIGTYPE_COMBO
&& HasSignalOnTrackdir(tile
, ReverseTrackdir(trackdir
))) {
424 /* at least one more exit */
425 if ((flags
& SF_EXIT2
) &&
427 (!(flags
& SF_GREEN
) ||
428 /* only one green exit, and it is this one - so all other exits are red */
429 (!(flags
& SF_GREEN2
) && GetSignalStateByTrackdir(tile
, ReverseTrackdir(trackdir
)) == SIGNAL_STATE_GREEN
))) {
430 newstate
= SIGNAL_STATE_RED
;
432 } else { // entry, at least one exit, no green exit
433 if (IsPresignalEntry(tile
, TrackdirToTrack(trackdir
)) && (flags
& SF_EXIT
) && !(flags
& SF_GREEN
)) newstate
= SIGNAL_STATE_RED
;
437 /* only when the state changes */
438 if (newstate
!= GetSignalStateByTrackdir(tile
, trackdir
)) {
439 if (IsPresignalExit(tile
, TrackdirToTrack(trackdir
))) {
440 /* for pre-signal exits, add block to the global set */
441 DiagDirection exitdir
= TrackdirToExitdir(ReverseTrackdir(trackdir
));
442 _globset
.Add(tile
, exitdir
); // do not check for full global set, first update all signals
444 SetSignalStateByTrackdir(tile
, trackdir
, newstate
);
445 MarkTileDirtyByTile(tile
);
452 /** Reset all sets after one set overflowed */
453 static inline void ResetSets()
462 * Updates blocks in _globset buffer
464 * @param owner company whose signals we are updating
465 * @return state of the first block from _globset
466 * @pre Company::IsValidID(owner)
468 static SigSegState
UpdateSignalsInBuffer(Owner owner
)
470 assert(Company::IsValidID(owner
));
472 bool first
= true; // first block?
473 SigSegState state
= SIGSEG_FREE
; // value to return
475 TileIndex tile
= INVALID_TILE
; // Stop GCC from complaining about a possibly uninitialized variable (issue #8280).
476 DiagDirection dir
= INVALID_DIAGDIR
;
478 while (_globset
.Get(&tile
, &dir
)) {
479 assert(_tbuset
.IsEmpty());
480 assert(_tbdset
.IsEmpty());
482 /* After updating signal, data stored are always MP_RAILWAY with signals.
483 * Other situations happen when data are from outside functions -
484 * modification of railbits (including both rail building and removal),
485 * train entering/leaving block, train leaving depot...
487 switch (GetTileType(tile
)) {
488 case MP_TUNNELBRIDGE
:
489 /* 'optimization assert' - do not try to update signals when it is not needed */
490 assert(GetTunnelBridgeTransportType(tile
) == TRANSPORT_RAIL
);
491 assert(dir
== INVALID_DIAGDIR
|| dir
== ReverseDiagDir(GetTunnelBridgeDirection(tile
)));
492 _tbdset
.Add(tile
, INVALID_DIAGDIR
); // we can safely start from wormhole centre
493 _tbdset
.Add(GetOtherTunnelBridgeEnd(tile
), INVALID_DIAGDIR
);
497 if (IsRailDepot(tile
)) {
498 /* 'optimization assert' do not try to update signals in other cases */
499 assert(dir
== INVALID_DIAGDIR
|| dir
== GetRailDepotDirection(tile
));
500 _tbdset
.Add(tile
, INVALID_DIAGDIR
); // start from depot inside
507 if ((TrackStatusToTrackBits(GetTileTrackStatus(tile
, TRANSPORT_RAIL
, 0)) & _enterdir_to_trackbits
[dir
]) != TRACK_BIT_NONE
) {
508 /* only add to set when there is some 'interesting' track */
509 _tbdset
.Add(tile
, dir
);
510 _tbdset
.Add(tile
+ TileOffsByDiagDir(dir
), ReverseDiagDir(dir
));
516 /* jump to next tile */
517 tile
= tile
+ TileOffsByDiagDir(dir
);
518 dir
= ReverseDiagDir(dir
);
519 if ((TrackStatusToTrackBits(GetTileTrackStatus(tile
, TRANSPORT_RAIL
, 0)) & _enterdir_to_trackbits
[dir
]) != TRACK_BIT_NONE
) {
520 _tbdset
.Add(tile
, dir
);
523 /* happens when removing a rail that wasn't connected at one or both sides */
524 continue; // continue the while() loop
527 assert(!_tbdset
.Overflowed()); // it really shouldn't overflow by these one or two items
528 assert(!_tbdset
.IsEmpty()); // it wouldn't hurt anyone, but shouldn't happen too
530 SigFlags flags
= ExploreSegment(owner
);
534 /* SIGSEG_FREE is set by default */
535 if (flags
& SF_PBS
) {
537 } else if ((flags
& SF_TRAIN
) || ((flags
& SF_EXIT
) && !(flags
& SF_GREEN
)) || (flags
& SF_FULL
)) {
542 /* do not do anything when some buffer was full */
543 if (flags
& SF_FULL
) {
544 ResetSets(); // free all sets
548 UpdateSignalsAroundSegment(flags
);
555 static Owner _last_owner
= INVALID_OWNER
; ///< last owner whose track was put into _globset
559 * Update signals in buffer
560 * Called from 'outside'
562 void UpdateSignalsInBuffer()
564 if (!_globset
.IsEmpty()) {
565 UpdateSignalsInBuffer(_last_owner
);
566 _last_owner
= INVALID_OWNER
; // invalidate
572 * Add track to signal update buffer
574 * @param tile tile where we start
575 * @param track track at which ends we will update signals
576 * @param owner owner whose signals we will update
578 void AddTrackToSignalBuffer(TileIndex tile
, Track track
, Owner owner
)
580 static const DiagDirection _search_dir_1
[] = {
581 DIAGDIR_NE
, DIAGDIR_SE
, DIAGDIR_NE
, DIAGDIR_SE
, DIAGDIR_SW
, DIAGDIR_SE
583 static const DiagDirection _search_dir_2
[] = {
584 DIAGDIR_SW
, DIAGDIR_NW
, DIAGDIR_NW
, DIAGDIR_SW
, DIAGDIR_NW
, DIAGDIR_NE
587 /* do not allow signal updates for two companies in one run */
588 assert(_globset
.IsEmpty() || owner
== _last_owner
);
592 _globset
.Add(tile
, _search_dir_1
[track
]);
593 _globset
.Add(tile
, _search_dir_2
[track
]);
595 if (_globset
.Items() >= SIG_GLOB_UPDATE
) {
596 /* too many items, force update */
597 UpdateSignalsInBuffer(_last_owner
);
598 _last_owner
= INVALID_OWNER
;
604 * Add side of tile to signal update buffer
606 * @param tile tile where we start
607 * @param side side of tile
608 * @param owner owner whose signals we will update
610 void AddSideToSignalBuffer(TileIndex tile
, DiagDirection side
, Owner owner
)
612 /* do not allow signal updates for two companies in one run */
613 assert(_globset
.IsEmpty() || owner
== _last_owner
);
617 _globset
.Add(tile
, side
);
619 if (_globset
.Items() >= SIG_GLOB_UPDATE
) {
620 /* too many items, force update */
621 UpdateSignalsInBuffer(_last_owner
);
622 _last_owner
= INVALID_OWNER
;
627 * Update signals, starting at one side of a tile
628 * Will check tile next to this at opposite side too
630 * @see UpdateSignalsInBuffer()
631 * @param tile tile where we start
632 * @param side side of tile
633 * @param owner owner whose signals we will update
634 * @return the state of the signal segment
636 SigSegState
UpdateSignalsOnSegment(TileIndex tile
, DiagDirection side
, Owner owner
)
638 assert(_globset
.IsEmpty());
639 _globset
.Add(tile
, side
);
641 return UpdateSignalsInBuffer(owner
);
646 * Update signals at segments that are at both ends of
647 * given (existent or non-existent) track
649 * @see UpdateSignalsInBuffer()
650 * @param tile tile where we start
651 * @param track track at which ends we will update signals
652 * @param owner owner whose signals we will update
654 void SetSignalsOnBothDir(TileIndex tile
, Track track
, Owner owner
)
656 assert(_globset
.IsEmpty());
658 AddTrackToSignalBuffer(tile
, track
, owner
);
659 UpdateSignalsInBuffer(owner
);