1

/* $Id$ */

     2

     3

/** @file signal.cpp functions related to rail signals updating */

     4

     5

#include "stdafx.h"

     6

#include "openttd.h"

     7

#include "debug.h"

     8

#include "tile_cmd.h"

     9

#include "rail_map.h"

    10

#include "road_map.h"

    11

#include "station_map.h"

    12

#include "tunnelbridge_map.h"

    13

#include "vehicle_func.h"

    14

#include "train.h"

    15

#include "newgrf_station.h"

    16

#include "functions.h"

    17

#include "track_type.h"

    18

#include "track_func.h"

    19

#include "signal_func.h"

    20

#include "player_func.h"

    21

    22

    23

/** these are the maximums used for updating signal blocks */

    24

enum {

    25

	SIG_TBU_SIZE  =  64, ///< number of signals entering to block

    26

	SIG_TBD_SIZE  = 256, ///< number of intersections - open nodes in current block

    27

	SIG_GLOB_SIZE =  64, ///< number of open blocks (block can be opened more times until detected)

    28

};

    29

    30

/** incidating trackbits with given enterdir */

    31

static const TrackBitsByte _enterdir_to_trackbits[DIAGDIR_END] = {

    32

	{TRACK_BIT_3WAY_NE},

    33

	{TRACK_BIT_3WAY_SE},

    34

	{TRACK_BIT_3WAY_SW},

    35

	{TRACK_BIT_3WAY_NW}

    36

};

    37

    38

/** incidating trackdirbits with given enterdir */

    39

static const TrackdirBitsShort _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}

    44

};

    45

    46

/**

    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

    50

 */

    51

template <typename Tdir, uint items>

    52

struct SmallSet {

    53

private:

    54

	uint n;           // actual number of units

    55

	bool overflowed;  // did we try to oveflow the set?

    56

	const char *name; // name, used for debugging purposes...

    57

    58

	/** Element of set */

    59

	struct SSdata {

    60

		TileIndex tile;

    61

		Tdir dir;

    62

	} data[items];

    63

    64

public:

    65

	/** Constructor - just set default values and 'name' */

    66

	SmallSet(const char *name) : n(0), overflowed(false), name(name) { }

    67

    68

	/** Reset variables to default values */

    69

	void Reset()

    70

	{

    71

		this->n = 0;

    72

		this->overflowed = false;

    73

	}

    74

    75

	/**

    76

	 * Returns value of 'oveflowed'

    77

	 * @return did we try to overflow the set?

    78

	 */

    79

	bool Overflowed()

    80

	{

    81

		return this->overflowed;

    82

	}

    83

    84

	/**

    85

	 * Checks for empty set

    86

	 * @return is the set empty?

    87

	 */

    88

	bool IsEmpty()

    89

	{

    90

		return this->n == 0;

    91

	}

    92

    93

	/**

    94

	 * Checks for full set

    95

	 * @return is the set full?

    96

	 */

    97

	bool IsFull()

    98

	{

    99

		return this->n == lengthof(data);

   100

	}

   101

   102

	/**

   103

	 * Tries to remove first instance of given tile and dir

   104

	 * @param tile tile

   105

	 * @param dir and dir to remove

   106

	 * @return element was found and removed

   107

	 */

   108

	bool Remove(TileIndex tile, Tdir dir)

   109

	{

   110

		for (uint i = 0; i < this->n; i++) {

   111

			if (this->data[i].tile == tile && this->data[i].dir == dir) {

   112

				this->data[i] = this->data[--this->n];

   113

				return true;

   114

			}

   115

		}

   116

   117

		return false;

   118

	}

   119

   120

	/**

   121

	 * Tries to find given tile and dir in the set

   122

	 * @param tile tile

   123

	 * @param dir and dir to find

   124

	 * @return true iff the tile & dir elemnt was found

   125

	 */

   126

	bool IsIn(TileIndex tile, Tdir dir)

   127

	{

   128

		for (uint i = 0; i < this->n; i++) {

   129

			if (this->data[i].tile == tile && this->data[i].dir == dir) return true;

   130

		}

   131

   132

		return false;

   133

	}

   134

   135

	/**

   136

	 * Adds tile & dir into the set, checks for full set

   137

	 * Sets the 'overflowed' flag if the set was full

   138

	 * @param tile tile

   139

	 * @param dir and dir to add

   140

	 * @return true iff the item could be added (set wasn't full)

   141

	 */

   142

	bool Add(TileIndex tile, Tdir dir)

   143

	{

   144

		if (this->IsFull()) {

   145

			overflowed = true;

   146

			DEBUG(misc, 0, "SignalSegment too complex. Set %s is full (maximum %d)", name, items);

   147

			return false; // set is full

   148

		}

   149

   150

		this->data[this->n].tile = tile;

   151

		this->data[this->n].dir = dir;

   152

		this->n++;

   153

   154

		return true;

   155

	}

   156

   157

	/**

   158

	 * Reads the last added element into the set

   159

	 * @param tile pointer where tile is written to

   160

	 * @param dir pointer where dir is written to

   161

	 * @return false iff the set was empty

   162

	 */

   163

	bool Get(TileIndex *tile, Tdir *dir)

   164

	{

   165

		if (this->n == 0) return false;

   166

   167

		this->n--;

   168

		*tile = this->data[this->n].tile;

   169

		*dir = this->data[this->n].dir;

   170

   171

		return true;

   172

	}

   173

};

   174

   175

static SmallSet<Trackdir, SIG_TBU_SIZE> _tbuset("_tbuset");         ///< set of signals that will be updated

   176

static SmallSet<DiagDirection, SIG_TBD_SIZE> _tbdset("_tbdset");    ///< set of open nodes in current signal block

   177

static SmallSet<DiagDirection, SIG_GLOB_SIZE> _globset("_globset"); ///< set of places to be updated in following runs

   178

   179

   180

/** Check whether there is a train on rail, not in a depot */

   181

static void *TrainOnTileEnum(Vehicle *v, void *)

   182

{

   183

	if (v->type != VEH_TRAIN || v->u.rail.track == TRACK_BIT_DEPOT) return NULL;

   184

   185

	return v;

   186

}

   187

   188

   189

/**

   190

 * Perform some operations before adding data into Todo set

   191

 * The new and reverse direction is removed from _globset, because we are sure

   192

 * it doesn't need to be checked again

   193

 * Also, remove reverse direction from _tbdset

   194

 * This is the 'core' part so the graph seaching won't enter any tile twice

   195

 *

   196

 * @param t1 tile we are entering

   197

 * @param d1 direction (tile side) we are entering

   198

 * @param t2 tile we are leaving

   199

 * @param d2 direction (tile side) we are leaving

   200

 * @return false iff reverse direction was in Todo set

   201

 */

   202

static inline bool CheckAddToTodoSet(TileIndex t1, DiagDirection d1, TileIndex t2, DiagDirection d2)

   203

{

   204

	_globset.Remove(t1, d1); // it can be in Global but not in Todo

   205

	_globset.Remove(t2, d2); // remove in all cases

   206

   207

	assert(!_tbdset.IsIn(t1, d1)); // it really shouldn't be there already

   208

   209

	if (_tbdset.Remove(t2, d2)) return false;

   210

   211

	return true;

   212

}

   213

   214

   215

/**

   216

 * Perform some operations before adding data into Todo set

   217

 * The new and reverse direction is removed from Global set, because we are sure

   218

 * it doesn't need to be checked again

   219

 * Also, remove reverse direction from Todo set

   220

 * This is the 'core' part so the graph seaching won't enter any tile twice

   221

 *

   222

 * @param t1 tile we are entering

   223

 * @param d1 direction (tile side) we are entering

   224

 * @param t2 tile we are leaving

   225

 * @param d2 direction (tile side) we are leaving

   226

 * @return false iff the Todo buffer would be overrun

   227

 */

   228

static inline bool MaybeAddToTodoSet(TileIndex t1, DiagDirection d1, TileIndex t2, DiagDirection d2)

   229

{

   230

	if (!CheckAddToTodoSet(t1, d1, t2, d2)) return true;

   231

   232

	return _tbdset.Add(t1, d1);

   233

}

   234

   235

   236

/** Current signal block state flags */

   237

enum SigFlags {

   238

	SF_NONE   = 0,

   239

	SF_TRAIN  = 1 << 0, ///< train found in segment

   240

	SF_EXIT   = 1 << 1, ///< exitsignal found

   241

	SF_EXIT2  = 1 << 2, ///< two or more exits found

   242

	SF_GREEN  = 1 << 3, ///< green exitsignal found

   243

	SF_GREEN2 = 1 << 4, ///< two or more green exits found

   244

	SF_FULL   = 1 << 5, ///< some of buffers was full, do not continue

   245

};

   246

   247

DECLARE_ENUM_AS_BIT_SET(SigFlags)

   248

   249

   250

/**

   251

 * Search signal block

   252

 *

   253

 * @param owner owner whose signals we are updating

   254

 * @return SigFlags

   255

 */

   256

static SigFlags ExploreSegment(Owner owner)

   257

{

   258

	SigFlags flags = SF_NONE;

   259

   262

   264

		TileIndex oldtile = tile; // tile we are leaving

   265

		DiagDirection exitdir = enterdir == INVALID_DIAGDIR ? INVALID_DIAGDIR : ReverseDiagDir(enterdir); // expected new exit direction (for straight line)

   266

   267

		switch (GetTileType(tile)) {

   268

			case MP_RAILWAY: {

   269

				if (GetTileOwner(tile) != owner) continue; // do not propagate signals on others' tiles (remove for tracksharing)

   270

   271

				if (IsRailDepot(tile)) {

   272

					if (enterdir == INVALID_DIAGDIR) { // from 'inside' - train just entered or left the depot

   273

						if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;

   274

						exitdir = GetRailDepotDirection(tile);

   275

						tile += TileOffsByDiagDir(exitdir);

   276

						enterdir = ReverseDiagDir(exitdir);

   277

						break;

   278

					} else if (enterdir == GetRailDepotDirection(tile)) { // entered a depot

   279

						if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;

   280

						continue;

   281

					} else {

   282

						continue;

   283

					}

   284

				}

   285

   286

				if (GetRailTileType(tile) == RAIL_TILE_WAYPOINT) {

   287

					if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;

   288

					tile += TileOffsByDiagDir(exitdir);

   289

					/* enterdir and exitdir stay the same */

   290

					break;

   291

				}

   292

   293

				TrackBits tracks = GetTrackBits(tile); // trackbits of tile

   294

				TrackBits tracks_masked = (TrackBits)(tracks & _enterdir_to_trackbits[enterdir]); // only incidating trackbits

   295

   296

				if (tracks == TRACK_BIT_HORZ || tracks == TRACK_BIT_VERT) { // there is exactly one incidating track, no need to check

   297

					tracks = tracks_masked;

   298

					if (!(flags & SF_TRAIN) && VehicleFromPos(tile, &tracks, &EnsureNoTrainOnTrackProc)) flags |= SF_TRAIN;

   299

				} else {

   300

					if (tracks_masked == TRACK_BIT_NONE) continue; // no incidating track

   301

					if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;

   302

				}

   303

   304

				if (HasSignals(tile)) { // there is exactly one track - not zero, because there is exit from this tile

   305

					Track track = TrackBitsToTrack(tracks_masked); // mask TRACK_BIT_X and Y too

   306

					if (HasSignalOnTrack(tile, track)) { // now check whole track, not trackdir

   307

						SignalType sig = GetSignalType(tile, track);

   308

						Trackdir trackdir = (Trackdir)FindFirstBit((tracks * 0x101) & _enterdir_to_trackdirbits[enterdir]);

   309

						Trackdir reversedir = ReverseTrackdir(trackdir);

   310

						/* add (tile, reversetrackdir) to 'to-be-updated' set when there is

   311

						 * ANY signal in REVERSE direction

   312

						 * (if it is a presignal EXIT and it changes, it will be added to 'to-be-done' set later) */

   313

						if (HasSignalOnTrackdir(tile, reversedir)) {

   314

							if (!_tbuset.Add(tile, reversedir)) return flags | SF_FULL;

   315

						}

   316

						/* if it is a presignal EXIT in OUR direction and we haven't found 2 green exits yes, do special check */

   317

						if (!(flags & SF_GREEN2) && (sig & SIGTYPE_EXIT) && HasSignalOnTrackdir(tile, trackdir)) { // found presignal exit

   318

							if (flags & SF_EXIT) flags |= SF_EXIT2; // found two (or more) exits

   319

							flags |= SF_EXIT; // found at least one exit - allow for compiler optimizations

   320

							if (GetSignalStateByTrackdir(tile, trackdir) == SIGNAL_STATE_GREEN) { // found green presignal exit

   321

								if (flags & SF_GREEN) flags |= SF_GREEN2;

   322

								flags |= SF_GREEN;

   323

							}

   324

						}

   325

						continue;

   326

					}

   327

				}

   328

   329

				for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) { // test all possible exit directions

   330

					if (dir != enterdir && tracks & _enterdir_to_trackbits[dir]) { // any track incidating?

   331

						TileIndex newtile = tile + TileOffsByDiagDir(dir);  // new tile to check

   332

						DiagDirection newdir = ReverseDiagDir(dir); // direction we are entering from

   333

						if (!MaybeAddToTodoSet(newtile, newdir, tile, dir)) return flags | SF_FULL;

   334

					}

   335

				}

   336

   337

				continue; // continue the while() loop

   338

				}

   339

   340

			case MP_STATION:

   341

				if (!IsRailwayStation(tile)) continue;

   342

				if (GetTileOwner(tile) != owner) continue;

   343

				if (DiagDirToAxis(enterdir) != GetRailStationAxis(tile)) continue; // different axis

   344

				if (IsStationTileBlocked(tile)) continue; // 'eye-candy' station tile

   345

   346

				if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;

   347

				tile += TileOffsByDiagDir(exitdir);

   348

				break;

   349

   350

			case MP_ROAD:

   351

				if (!IsLevelCrossing(tile)) continue;

   352

				if (GetTileOwner(tile) != owner) continue;

   353

				if (DiagDirToAxis(enterdir) == GetCrossingRoadAxis(tile)) continue; // different axis

   354

   355

				if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;

   356

				tile += TileOffsByDiagDir(exitdir);

   357

				break;

   358

   359

			case MP_TUNNELBRIDGE: {

   360

				if (GetTileOwner(tile) != owner) continue;

   361

				if (GetTunnelBridgeTransportType(tile) != TRANSPORT_RAIL) continue;

   362

				DiagDirection dir = GetTunnelBridgeDirection(tile);

   363

   364

				if (enterdir == INVALID_DIAGDIR) { // incoming from the wormhole

   365

					if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;

   366

					enterdir = dir;

   367

					exitdir = ReverseDiagDir(dir);

   368

					tile += TileOffsByDiagDir(exitdir); // just skip to next tile

   369

				} else { // NOT incoming from the wormhole!

   370

					if (ReverseDiagDir(enterdir) != dir) continue;

   371

					if (!(flags & SF_TRAIN) && VehicleFromPos(tile, NULL, &TrainOnTileEnum)) flags |= SF_TRAIN;

   372

					tile = GetOtherTunnelBridgeEnd(tile); // just skip to exit tile

   373

					enterdir = INVALID_DIAGDIR;

   374

					exitdir = INVALID_DIAGDIR;

   375

				}

   376

				}

   377

				break;

   378

   379

			default:

   380

				continue; // continue the while() loop

   381

		}

   382

   383

		if (!MaybeAddToTodoSet(tile, enterdir, oldtile, exitdir)) return flags | SF_FULL;

   384

	}

   385

   386

	return flags;

   387

}

   388

   389

   390

/**

   391

 * Update signals around segment in _tbuset

   392

 *

   393

 * @param flags info about segment

   394

 */

   395

static void UpdateSignalsAroundSegment(SigFlags flags)

   396

{

   399

   401

		assert(HasSignalOnTrackdir(tile, trackdir));

   402

   403

		SignalType sig = GetSignalType(tile, TrackdirToTrack(trackdir));

   404

		SignalState newstate = SIGNAL_STATE_GREEN;

   405

   406

		/* determine whether the new state is red */

   407

		if (flags & SF_TRAIN) {

   408

			/* train in the segment */

   409

			newstate = SIGNAL_STATE_RED;

   410

		} else {

   411

 			/* is it a bidir combo? - then do not count its other signal direction as exit */

   412

			if (sig == SIGTYPE_COMBO && HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir))) {

   413

				/* at least one more exit */

   414

				if (flags & SF_EXIT2 &&

   415

 						/* no green exit */

   416

						(!(flags & SF_GREEN) ||

   417

						/* only one green exit, and it is this one - so all other exits are red */

   418

						(!(flags & SF_GREEN2) && GetSignalStateByTrackdir(tile, ReverseTrackdir(trackdir)) == SIGNAL_STATE_GREEN))) {

   419

					newstate = SIGNAL_STATE_RED;

   420

				}

   421

			} else { // entry, at least one exit, no green exit

   422

				if (sig & SIGTYPE_ENTRY && (flags & SF_EXIT && !(flags & SF_GREEN))) newstate = SIGNAL_STATE_RED;

   423

			}

   424

		}

   425

   426

		/* only when the state changes */

   427

		if (newstate != GetSignalStateByTrackdir(tile, trackdir)) {

   428

			if (sig & SIGTYPE_EXIT) {

   429

				/* for pre-signal exits, add block to the global set */

   430

				DiagDirection exitdir = TrackdirToExitdir(ReverseTrackdir(trackdir));

   431

				_globset.Add(tile, exitdir); // do not check for full global set, first update all signals

   432

			}

   433

			SetSignalStateByTrackdir(tile, trackdir, newstate);

   434

			MarkTileDirtyByTile(tile);

   435

		}

   436

	}

   437

   438

}

   439

   440

   441

/** Reset all sets after one set overflowed */

   442

static inline void ResetSets()

   443

{

   444

	_tbuset.Reset();

   445

	_tbdset.Reset();

   446

	_globset.Reset();

   447

}

   448

   449

   450

/**

   451

 * Updates blocks in _globset buffer

   452

 *

   454

 * @return false iff presignal entry would be green (needed for trains leaving depot)

   456

 */

   458

{

   461

	bool first = true;  // first block?

   462

	bool state = false; // value to return

   463

   464

	TileIndex tile;

   465

	DiagDirection dir;

   466

   467

	while (_globset.Get(&tile, &dir)) {

   468

		assert(_tbuset.IsEmpty());

   469

		assert(_tbdset.IsEmpty());

   470

   471

		/* After updating signal, data stored are always MP_RAILWAY with signals.

   472

		 * Other situations happen when data are from outside functions -

   473

		 * modification of railbits (including both rail building and removal),

   474

		 * train entering/leaving block, train leaving depot...

   475

		 */

   476

		switch (GetTileType(tile)) {

   477

			case MP_TUNNELBRIDGE:

   478

				/* 'optimization assert' - do not try to update signals when it is not needed */

   479

				assert(GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL);

   480

				assert(dir == INVALID_DIAGDIR || dir == ReverseDiagDir(GetTunnelBridgeDirection(tile)));

   481

				_tbdset.Add(tile, INVALID_DIAGDIR);  // we can safely start from wormhole centre

   482

				_tbdset.Add(GetOtherTunnelBridgeEnd(tile), INVALID_DIAGDIR);

   483

				break;

   484

   485

			case MP_RAILWAY:

   486

				if (IsRailDepot(tile)) {

   487

					/* 'optimization assert' do not try to update signals in other cases */

   488

					assert(dir == INVALID_DIAGDIR || dir == GetRailDepotDirection(tile));

   489

					_tbdset.Add(tile, INVALID_DIAGDIR); // start from depot inside

   490

					break;

   491

				}

   492

				/* FALLTHROUGH */

   493

			case MP_STATION:

   494

			case MP_ROAD:

   495

				if ((TrackBits)(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0) & _enterdir_to_trackbits[dir]) != TRACK_BIT_NONE) {

   496

 					/* only add to set when there is some 'interesting' track */

   497

					_tbdset.Add(tile, dir);

   498

					_tbdset.Add(tile + TileOffsByDiagDir(dir), ReverseDiagDir(dir));

   499

					break;

   500

				}

   501

				/* FALLTHROUGH */

   502

			default:

   503

				/* jump to next tile */

   504

				tile = tile + TileOffsByDiagDir(dir);

   505

				dir = ReverseDiagDir(dir);

   506

				if ((TrackBits)(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0) & _enterdir_to_trackbits[dir]) != TRACK_BIT_NONE) {

   507

					_tbdset.Add(tile, dir);

   508

					break;

   509

				}

   510

				/* happens when removing a rail that wasn't connected at one or both sides */

   511

				continue; // continue the while() loop

   512

		}

   513

   514

		assert(!_tbdset.Overflowed()); // it really shouldn't overflow by these one or two items

   515

		assert(!_tbdset.IsEmpty()); // it wouldn't hurt anyone, but shouldn't happen too

   516

   517

		SigFlags flags = ExploreSegment(owner);

   518

   519

		if (first) {

   520

			first = false;

   521

			state = (flags & SF_TRAIN) || (flags & SF_EXIT && !(flags & SF_GREEN)) || (flags & SF_FULL); // true iff train CAN'T leave the depot

   522

		}

   523

   524

		/* do not do anything when some buffer was full */

   525

		if (flags & SF_FULL) {

   526

			ResetSets(); // free all sets

   527

			break;