OpenTTD
signal.cpp
Go to the documentation of this file.
1 /* $Id: signal.cpp 27893 2017-08-13 18:38:42Z frosch $ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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  */
9 
12 #include "stdafx.h"
13 #include "debug.h"
14 #include "station_map.h"
15 #include "tunnelbridge_map.h"
16 #include "vehicle_func.h"
17 #include "viewport_func.h"
18 #include "train.h"
19 #include "company_base.h"
20 
21 #include "safeguards.h"
22 
23 
25 static const uint SIG_TBU_SIZE = 64;
26 static const uint SIG_TBD_SIZE = 256;
27 static const uint SIG_GLOB_SIZE = 128;
28 static const uint SIG_GLOB_UPDATE = 64;
29 
30 assert_compile(SIG_GLOB_UPDATE <= SIG_GLOB_SIZE);
31 
38 };
39 
46 };
47 
53 template <typename Tdir, uint items>
54 struct SmallSet {
55 private:
56  uint n; // actual number of units
57  bool overflowed; // did we try to overflow the set?
58  const char *name; // name, used for debugging purposes...
59 
61  struct SSdata {
62  TileIndex tile;
63  Tdir dir;
64  } data[items];
65 
66 public:
68  SmallSet(const char *name) : n(0), overflowed(false), name(name) { }
69 
71  void Reset()
72  {
73  this->n = 0;
74  this->overflowed = false;
75  }
76 
81  bool Overflowed()
82  {
83  return this->overflowed;
84  }
85 
90  bool IsEmpty()
91  {
92  return this->n == 0;
93  }
94 
99  bool IsFull()
100  {
101  return this->n == lengthof(data);
102  }
103 
108  uint Items()
109  {
110  return this->n;
111  }
112 
113 
120  bool Remove(TileIndex tile, Tdir dir)
121  {
122  for (uint i = 0; i < this->n; i++) {
123  if (this->data[i].tile == tile && this->data[i].dir == dir) {
124  this->data[i] = this->data[--this->n];
125  return true;
126  }
127  }
128 
129  return false;
130  }
131 
138  bool IsIn(TileIndex tile, Tdir dir)
139  {
140  for (uint i = 0; i < this->n; i++) {
141  if (this->data[i].tile == tile && this->data[i].dir == dir) return true;
142  }
143 
144  return false;
145  }
146 
154  bool Add(TileIndex tile, Tdir dir)
155  {
156  if (this->IsFull()) {
157  overflowed = true;
158  DEBUG(misc, 0, "SignalSegment too complex. Set %s is full (maximum %d)", name, items);
159  return false; // set is full
160  }
161 
162  this->data[this->n].tile = tile;
163  this->data[this->n].dir = dir;
164  this->n++;
165 
166  return true;
167  }
168 
175  bool Get(TileIndex *tile, Tdir *dir)
176  {
177  if (this->n == 0) return false;
178 
179  this->n--;
180  *tile = this->data[this->n].tile;
181  *dir = this->data[this->n].dir;
182 
183  return true;
184  }
185 };
186 
187 static SmallSet<Trackdir, SIG_TBU_SIZE> _tbuset("_tbuset");
190 
191 
193 static Vehicle *TrainOnTileEnum(Vehicle *v, void *)
194 {
195  if (v->type != VEH_TRAIN || Train::From(v)->track == TRACK_BIT_DEPOT) return NULL;
196 
197  return v;
198 }
199 
200 
215 {
216  _globset.Remove(t1, d1); // it can be in Global but not in Todo
217  _globset.Remove(t2, d2); // remove in all cases
218 
219  assert(!_tbdset.IsIn(t1, d1)); // it really shouldn't be there already
220 
221  if (_tbdset.Remove(t2, d2)) return false;
222 
223  return true;
224 }
225 
226 
241 {
242  if (!CheckAddToTodoSet(t1, d1, t2, d2)) return true;
243 
244  return _tbdset.Add(t1, d1);
245 }
246 
247 
249 enum SigFlags {
250  SF_NONE = 0,
251  SF_TRAIN = 1 << 0,
252  SF_EXIT = 1 << 1,
253  SF_EXIT2 = 1 << 2,
254  SF_GREEN = 1 << 3,
255  SF_GREEN2 = 1 << 4,
256  SF_FULL = 1 << 5,
257  SF_PBS = 1 << 6,
258 };
259 
261 
262 
263 
270 {
271  SigFlags flags = SF_NONE;
272 
273  TileIndex tile;
274  DiagDirection enterdir;
275 
276  while (_tbdset.Get(&tile, &enterdir)) {
277  TileIndex oldtile = tile; // tile we are leaving
278  DiagDirection exitdir = enterdir == INVALID_DIAGDIR ? INVALID_DIAGDIR : ReverseDiagDir(enterdir); // expected new exit direction (for straight line)
279 
280  switch (GetTileType(tile)) {
281  case MP_RAILWAY: {
282  if (GetTileOwner(tile) != owner) continue; // do not propagate signals on others' tiles (remove for tracksharing)
283 
284  if (IsRailDepot(tile)) {
285  if (enterdir == INVALID_DIAGDIR) { // from 'inside' - train just entered or left the depot
286  if (!(flags & SF_TRAIN) && HasVehicleOnPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
287  exitdir = GetRailDepotDirection(tile);
288  tile += TileOffsByDiagDir(exitdir);
289  enterdir = ReverseDiagDir(exitdir);
290  break;
291  } else if (enterdir == GetRailDepotDirection(tile)) { // entered a depot
292  if (!(flags & SF_TRAIN) && HasVehicleOnPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
293  continue;
294  } else {
295  continue;
296  }
297  }
298 
299  assert(IsValidDiagDirection(enterdir));
300  TrackBits tracks = GetTrackBits(tile); // trackbits of tile
301  TrackBits tracks_masked = (TrackBits)(tracks & _enterdir_to_trackbits[enterdir]); // only incidating trackbits
302 
303  if (tracks == TRACK_BIT_HORZ || tracks == TRACK_BIT_VERT) { // there is exactly one incidating track, no need to check
304  tracks = tracks_masked;
305  /* If no train detected yet, and there is not no train -> there is a train -> set the flag */
306  if (!(flags & SF_TRAIN) && EnsureNoTrainOnTrackBits(tile, tracks).Failed()) flags |= SF_TRAIN;
307  } else {
308  if (tracks_masked == TRACK_BIT_NONE) continue; // no incidating track
309  if (!(flags & SF_TRAIN) && HasVehicleOnPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
310  }
311 
312  if (HasSignals(tile)) { // there is exactly one track - not zero, because there is exit from this tile
313  Track track = TrackBitsToTrack(tracks_masked); // mask TRACK_BIT_X and Y too
314  if (HasSignalOnTrack(tile, track)) { // now check whole track, not trackdir
315  SignalType sig = GetSignalType(tile, track);
316  Trackdir trackdir = (Trackdir)FindFirstBit((tracks * 0x101) & _enterdir_to_trackdirbits[enterdir]);
317  Trackdir reversedir = ReverseTrackdir(trackdir);
318  /* add (tile, reversetrackdir) to 'to-be-updated' set when there is
319  * ANY conventional signal in REVERSE direction
320  * (if it is a presignal EXIT and it changes, it will be added to 'to-be-done' set later) */
321  if (HasSignalOnTrackdir(tile, reversedir)) {
322  if (IsPbsSignal(sig)) {
323  flags |= SF_PBS;
324  } else if (!_tbuset.Add(tile, reversedir)) {
325  return flags | SF_FULL;
326  }
327  }
328  if (HasSignalOnTrackdir(tile, trackdir) && !IsOnewaySignal(tile, track)) flags |= SF_PBS;
329 
330  /* if it is a presignal EXIT in OUR direction and we haven't found 2 green exits yes, do special check */
331  if (!(flags & SF_GREEN2) && IsPresignalExit(tile, track) && HasSignalOnTrackdir(tile, trackdir)) { // found presignal exit
332  if (flags & SF_EXIT) flags |= SF_EXIT2; // found two (or more) exits
333  flags |= SF_EXIT; // found at least one exit - allow for compiler optimizations
334  if (GetSignalStateByTrackdir(tile, trackdir) == SIGNAL_STATE_GREEN) { // found green presignal exit
335  if (flags & SF_GREEN) flags |= SF_GREEN2;
336  flags |= SF_GREEN;
337  }
338  }
339 
340  continue;
341  }
342  }
343 
344  for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) { // test all possible exit directions
345  if (dir != enterdir && (tracks & _enterdir_to_trackbits[dir])) { // any track incidating?
346  TileIndex newtile = tile + TileOffsByDiagDir(dir); // new tile to check
347  DiagDirection newdir = ReverseDiagDir(dir); // direction we are entering from
348  if (!MaybeAddToTodoSet(newtile, newdir, tile, dir)) return flags | SF_FULL;
349  }
350  }
351 
352  continue; // continue the while() loop
353  }
354 
355  case MP_STATION:
356  if (!HasStationRail(tile)) continue;
357  if (GetTileOwner(tile) != owner) continue;
358  if (DiagDirToAxis(enterdir) != GetRailStationAxis(tile)) continue; // different axis
359  if (IsStationTileBlocked(tile)) continue; // 'eye-candy' station tile
360 
361  if (!(flags & SF_TRAIN) && HasVehicleOnPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
362  tile += TileOffsByDiagDir(exitdir);
363  break;
364 
365  case MP_ROAD:
366  if (!IsLevelCrossing(tile)) continue;
367  if (GetTileOwner(tile) != owner) continue;
368  if (DiagDirToAxis(enterdir) == GetCrossingRoadAxis(tile)) continue; // different axis
369 
370  if (!(flags & SF_TRAIN) && HasVehicleOnPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
371  tile += TileOffsByDiagDir(exitdir);
372  break;
373 
374  case MP_TUNNELBRIDGE: {
375  if (GetTileOwner(tile) != owner) continue;
376  if (GetTunnelBridgeTransportType(tile) != TRANSPORT_RAIL) continue;
378 
379  if (enterdir == INVALID_DIAGDIR) { // incoming from the wormhole
380  if (!(flags & SF_TRAIN) && HasVehicleOnPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
381  enterdir = dir;
382  exitdir = ReverseDiagDir(dir);
383  tile += TileOffsByDiagDir(exitdir); // just skip to next tile
384  } else { // NOT incoming from the wormhole!
385  if (ReverseDiagDir(enterdir) != dir) continue;
386  if (!(flags & SF_TRAIN) && HasVehicleOnPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;
387  tile = GetOtherTunnelBridgeEnd(tile); // just skip to exit tile
388  enterdir = INVALID_DIAGDIR;
389  exitdir = INVALID_DIAGDIR;
390  }
391  }
392  break;
393 
394  default:
395  continue; // continue the while() loop
396  }
397 
398  if (!MaybeAddToTodoSet(tile, enterdir, oldtile, exitdir)) return flags | SF_FULL;
399  }
400 
401  return flags;
402 }
403 
404 
411 {
412  TileIndex tile;
413  Trackdir trackdir;
414 
415  while (_tbuset.Get(&tile, &trackdir)) {
416  assert(HasSignalOnTrackdir(tile, trackdir));
417 
418  SignalType sig = GetSignalType(tile, TrackdirToTrack(trackdir));
419  SignalState newstate = SIGNAL_STATE_GREEN;
420 
421  /* determine whether the new state is red */
422  if (flags & SF_TRAIN) {
423  /* train in the segment */
424  newstate = SIGNAL_STATE_RED;
425  } else {
426  /* is it a bidir combo? - then do not count its other signal direction as exit */
427  if (sig == SIGTYPE_COMBO && HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir))) {
428  /* at least one more exit */
429  if ((flags & SF_EXIT2) &&
430  /* no green exit */
431  (!(flags & SF_GREEN) ||
432  /* only one green exit, and it is this one - so all other exits are red */
433  (!(flags & SF_GREEN2) && GetSignalStateByTrackdir(tile, ReverseTrackdir(trackdir)) == SIGNAL_STATE_GREEN))) {
434  newstate = SIGNAL_STATE_RED;
435  }
436  } else { // entry, at least one exit, no green exit
437  if (IsPresignalEntry(tile, TrackdirToTrack(trackdir)) && (flags & SF_EXIT) && !(flags & SF_GREEN)) newstate = SIGNAL_STATE_RED;
438  }
439  }
440 
441  /* only when the state changes */
442  if (newstate != GetSignalStateByTrackdir(tile, trackdir)) {
443  if (IsPresignalExit(tile, TrackdirToTrack(trackdir))) {
444  /* for pre-signal exits, add block to the global set */
445  DiagDirection exitdir = TrackdirToExitdir(ReverseTrackdir(trackdir));
446  _globset.Add(tile, exitdir); // do not check for full global set, first update all signals
447  }
448  SetSignalStateByTrackdir(tile, trackdir, newstate);
449  MarkTileDirtyByTile(tile);
450  }
451  }
452 
453 }
454 
455 
457 static inline void ResetSets()
458 {
459  _tbuset.Reset();
460  _tbdset.Reset();
461  _globset.Reset();
462 }
463 
464 
473 {
474  assert(Company::IsValidID(owner));
475 
476  bool first = true; // first block?
477  SigSegState state = SIGSEG_FREE; // value to return
478 
479  TileIndex tile;
480  DiagDirection dir;
481 
482  while (_globset.Get(&tile, &dir)) {
483  assert(_tbuset.IsEmpty());
484  assert(_tbdset.IsEmpty());
485 
486  /* After updating signal, data stored are always MP_RAILWAY with signals.
487  * Other situations happen when data are from outside functions -
488  * modification of railbits (including both rail building and removal),
489  * train entering/leaving block, train leaving depot...
490  */
491  switch (GetTileType(tile)) {
492  case MP_TUNNELBRIDGE:
493  /* 'optimization assert' - do not try to update signals when it is not needed */
495  assert(dir == INVALID_DIAGDIR || dir == ReverseDiagDir(GetTunnelBridgeDirection(tile)));
496  _tbdset.Add(tile, INVALID_DIAGDIR); // we can safely start from wormhole centre
498  break;
499 
500  case MP_RAILWAY:
501  if (IsRailDepot(tile)) {
502  /* 'optimization assert' do not try to update signals in other cases */
503  assert(dir == INVALID_DIAGDIR || dir == GetRailDepotDirection(tile));
504  _tbdset.Add(tile, INVALID_DIAGDIR); // start from depot inside
505  break;
506  }
507  FALLTHROUGH;
508 
509  case MP_STATION:
510  case MP_ROAD:
512  /* only add to set when there is some 'interesting' track */
513  _tbdset.Add(tile, dir);
514  _tbdset.Add(tile + TileOffsByDiagDir(dir), ReverseDiagDir(dir));
515  break;
516  }
517  FALLTHROUGH;
518 
519  default:
520  /* jump to next tile */
521  tile = tile + TileOffsByDiagDir(dir);
522  dir = ReverseDiagDir(dir);
524  _tbdset.Add(tile, dir);
525  break;
526  }
527  /* happens when removing a rail that wasn't connected at one or both sides */
528  continue; // continue the while() loop
529  }
530 
531  assert(!_tbdset.Overflowed()); // it really shouldn't overflow by these one or two items
532  assert(!_tbdset.IsEmpty()); // it wouldn't hurt anyone, but shouldn't happen too
533 
534  SigFlags flags = ExploreSegment(owner);
535 
536  if (first) {
537  first = false;
538  /* SIGSEG_FREE is set by default */
539  if (flags & SF_PBS) {
540  state = SIGSEG_PBS;
541  } else if ((flags & SF_TRAIN) || ((flags & SF_EXIT) && !(flags & SF_GREEN)) || (flags & SF_FULL)) {
542  state = SIGSEG_FULL;
543  }
544  }
545 
546  /* do not do anything when some buffer was full */
547  if (flags & SF_FULL) {
548  ResetSets(); // free all sets
549  break;
550  }
551 
553  }
554 
555  return state;
556 }
557 
558 
560 
561 
567 {
568  if (!_globset.IsEmpty()) {
570  _last_owner = INVALID_OWNER; // invalidate
571  }
572 }
573 
574 
582 void AddTrackToSignalBuffer(TileIndex tile, Track track, Owner owner)
583 {
584  static const DiagDirection _search_dir_1[] = {
586  };
587  static const DiagDirection _search_dir_2[] = {
589  };
590 
591  /* do not allow signal updates for two companies in one run */
592  assert(_globset.IsEmpty() || owner == _last_owner);
593 
594  _last_owner = owner;
595 
596  _globset.Add(tile, _search_dir_1[track]);
597  _globset.Add(tile, _search_dir_2[track]);
598 
599  if (_globset.Items() >= SIG_GLOB_UPDATE) {
600  /* too many items, force update */
601  UpdateSignalsInBuffer(_last_owner);
602  _last_owner = INVALID_OWNER;
603  }
604 }
605 
606 
615 {
616  /* do not allow signal updates for two companies in one run */
617  assert(_globset.IsEmpty() || owner == _last_owner);
618 
619  _last_owner = owner;
620 
621  _globset.Add(tile, side);
622 
623  if (_globset.Items() >= SIG_GLOB_UPDATE) {
624  /* too many items, force update */
625  UpdateSignalsInBuffer(_last_owner);
626  _last_owner = INVALID_OWNER;
627  }
628 }
629 
641 {
642  assert(_globset.IsEmpty());
643  _globset.Add(tile, side);
644 
645  return UpdateSignalsInBuffer(owner);
646 }
647 
648 
658 void SetSignalsOnBothDir(TileIndex tile, Track track, Owner owner)
659 {
660  assert(_globset.IsEmpty());
661 
662  AddTrackToSignalBuffer(tile, track, owner);
663  UpdateSignalsInBuffer(owner);
664 }