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   = 128, ///< number of open blocks (block can be opened more times until detected)

    28

	SIG_GLOB_UPDATE =  64, ///< how many items need to be in _globset to force update

    29

};

    30

    31

/* need to typecast to compile with MorphOS */

    32

assert_compile((int)SIG_GLOB_UPDATE <= (int)SIG_GLOB_SIZE);

    33

    34

/** incidating trackbits with given enterdir */

    35

static const TrackBitsByte _enterdir_to_trackbits[DIAGDIR_END] = {

    36

	{TRACK_BIT_3WAY_NE},

    37

	{TRACK_BIT_3WAY_SE},

    38

	{TRACK_BIT_3WAY_SW},

    39

	{TRACK_BIT_3WAY_NW}

    40

};

    41

    42

/** incidating trackdirbits with given enterdir */

    43

static const TrackdirBitsShort _enterdir_to_trackdirbits[DIAGDIR_END] = {

    44

	{TRACKDIR_BIT_X_SW | TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_RIGHT_S},

    45

	{TRACKDIR_BIT_Y_NW | TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_RIGHT_N},

    46

	{TRACKDIR_BIT_X_NE | TRACKDIR_BIT_LOWER_E | TRACKDIR_BIT_LEFT_N},

    47

	{TRACKDIR_BIT_Y_SE | TRACKDIR_BIT_UPPER_E | TRACKDIR_BIT_LEFT_S}

    48

};

    49

    50

/**

    51

 * Set containing 'items' items of 'tile and Tdir'

    52

 * No tree structure is used because it would cause

    53

 * slowdowns in most usual cases

    54

 */

    55

template <typename Tdir, uint items>

    56

struct SmallSet {

    57

private:

    58

	uint n;           // actual number of units

    59

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

    60

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

    61

    62

	/** Element of set */

    63

	struct SSdata {

    64

		TileIndex tile;

    65

		Tdir dir;

    66

	} data[items];

    67

    68

public:

    69

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

    70

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

    71

    72

	/** Reset variables to default values */

    73

	void Reset()

    74

	{

    75

		this->n = 0;

    76

		this->overflowed = false;

    77

	}

    78

    79

	/**

    80

	 * Returns value of 'oveflowed'

    81

	 * @return did we try to overflow the set?

    82

	 */

    83

	bool Overflowed()

    84

	{

    85

		return this->overflowed;

    86

	}

    87

    88

	/**

    89

	 * Checks for empty set

    90

	 * @return is the set empty?

    91

	 */

    92

	bool IsEmpty()

    93

	{

    94

		return this->n == 0;

    95

	}

    96

    97

	/**

    98

	 * Checks for full set

    99

	 * @return is the set full?

   100

	 */

   101

	bool IsFull()

   102

	{

   103

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

   104

	}

   105

   106

	/**

   107

	 * Reads the number of items

   108

	 * @return current number of items

   109

	 */

   110

	uint Items()

   111

	{

   112

		return this->n;

   113

	}

   114

   115

   116

	/**

   117

	 * Tries to remove first instance of given tile and dir

   118

	 * @param tile tile

   119

	 * @param dir and dir to remove

   120

	 * @return element was found and removed

   121

	 */

   122

	bool Remove(TileIndex tile, Tdir dir)

   123

	{

   124

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

   125

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

   126

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

   127

				return true;

   128

			}

   129

		}

   130

   131

		return false;

   132

	}

   133

   134

	/**

   135

	 * Tries to find given tile and dir in the set

   136

	 * @param tile tile

   137

	 * @param dir and dir to find

   138

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

   139

	 */

   140

	bool IsIn(TileIndex tile, Tdir dir)

   141

	{

   142

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

   143

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

   144

		}

   145

   146

		return false;

   147

	}

   148

   149

	/**

   150

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

   151

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

   152

	 * @param tile tile

   153

	 * @param dir and dir to add

   154

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

   155

	 */

   156

	bool Add(TileIndex tile, Tdir dir)

   157

	{

   158

		if (this->IsFull()) {

   159

			overflowed = true;

   160

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

   161

			return false; // set is full

   162

		}

   163

   164

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

   165

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

   166

		this->n++;

   167

   168

		return true;

   169

	}

   170

   171

	/**

   172

	 * Reads the last added element into the set

   173

	 * @param tile pointer where tile is written to

   174

	 * @param dir pointer where dir is written to

   175

	 * @return false iff the set was empty

   176

	 */

   177

	bool Get(TileIndex *tile, Tdir *dir)

   178

	{

   179

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

   180

   181

		this->n--;

   182

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

   183

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

   184

   185

		return true;

   186

	}

   187

};

   188

   189

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

   190

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

   191

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

   192

   193

   194

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

   195

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

   196

{

   197

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

   198

   199

	return v;

   200

}

   201

   202

   203

/**

   204

 * Perform some operations before adding data into Todo set

   205

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

   206

 * it doesn't need to be checked again

   207

 * Also, remove reverse direction from _tbdset

   208

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

   209

 *

   210

 * @param t1 tile we are entering

   211

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

   212

 * @param t2 tile we are leaving

   213

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

   214

 * @return false iff reverse direction was in Todo set

   215

 */

   216

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

   217

{

   218

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

   219

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

   220

   221

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

   222

   223

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

   224

   225

	return true;

   226

}

   227

   228

   229

/**

   230

 * Perform some operations before adding data into Todo set

   231

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

   232

 * it doesn't need to be checked again

   233

 * Also, remove reverse direction from Todo set

   234

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

   235

 *

   236

 * @param t1 tile we are entering

   237

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

   238

 * @param t2 tile we are leaving

   239

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

   240

 * @return false iff the Todo buffer would be overrun

   241

 */

   242

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

   243

{

   244

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

   245

   246

	return _tbdset.Add(t1, d1);

   247

}

   248

   249

   250

/** Current signal block state flags */

   251

enum SigFlags {

   252

	SF_NONE   = 0,

   253

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

   254

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

   255

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

   256

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

   257

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

   258

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

   259

};

   260

   261

DECLARE_ENUM_AS_BIT_SET(SigFlags)

   262

   263

   264

/**

   265

 * Search signal block

   266

 *

   267

 * @param owner owner whose signals we are updating

   268

 * @return SigFlags

   269

 */

   270

static SigFlags ExploreSegment(Owner owner)

   271

{

   272

	SigFlags flags = SF_NONE;

   273

   274

	TileIndex tile;

   275

	DiagDirection enterdir;

   276

   277

	while (_tbdset.Get(&tile, &enterdir)) {

   278

		TileIndex oldtile = tile; // tile we are leaving

   279

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

   280

   281

		switch (GetTileType(tile)) {

   282

			case MP_RAILWAY: {

   283

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

   284

   285

				if (IsRailDepot(tile)) {

   286

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

   287

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

   288

						exitdir = GetRailDepotDirection(tile);

   289

						tile += TileOffsByDiagDir(exitdir);

   290

						enterdir = ReverseDiagDir(exitdir);

   291

						break;

   292

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

   293

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

   294

						continue;

   295

					} else {

   296

						continue;

   297

					}

   298

				}

   299

   300

				if (GetRailTileType(tile) == RAIL_TILE_WAYPOINT) {

   301

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

   302

					tile += TileOffsByDiagDir(exitdir);

   303

					/* enterdir and exitdir stay the same */

   304

					break;

   305

				}

   306

   307

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

   308

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

   309

   310

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

   311

					tracks = tracks_masked;

   312

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

   313

				} else {

   314

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

   315

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

   316

				}

   317

   318

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

   319

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

   320

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

   321

						SignalType sig = GetSignalType(tile, track);

   322

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

   323

						Trackdir reversedir = ReverseTrackdir(trackdir);

   324

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

   325

						 * ANY signal in REVERSE direction

   326

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

   327

						if (HasSignalOnTrackdir(tile, reversedir)) {

   328

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

   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) && (sig & SIGTYPE_EXIT) && 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

						continue;

   340

					}

   341

				}

   342

   343

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

   344

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

   345

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

   346

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

   347

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

   348

					}

   349

				}

   350

   351

				continue; // continue the while() loop

   352

				}

   353

   354

			case MP_STATION:

   355

				if (!IsRailwayStation(tile)) continue;

   356

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

   357

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

   358

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

   359

   360

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

   361

				tile += TileOffsByDiagDir(exitdir);

   362

				break;

   363

   364

			case MP_ROAD:

   365

				if (!IsLevelCrossing(tile)) continue;

   366

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

   367

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

   368

   369

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

   370

				tile += TileOffsByDiagDir(exitdir);

   371

				break;

   372

   373

			case MP_TUNNELBRIDGE: {

   374

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

   375

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

   376

				DiagDirection dir = GetTunnelBridgeDirection(tile);

   377

   378

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

   379

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

   380

					enterdir = dir;

   381

					exitdir = ReverseDiagDir(dir);

   382

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

   383

				} else { // NOT incoming from the wormhole!

   384

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

   385

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

   386

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

   387

					enterdir = INVALID_DIAGDIR;

   388

					exitdir = INVALID_DIAGDIR;

   389

				}

   390

				}

   391

				break;

   392

   393

			default:

   394

				continue; // continue the while() loop

   395

		}

   396

   397

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

   398

	}

   399

   400

	return flags;

   401

}

   402

   403

   404

/**

   405

 * Update signals around segment in _tbuset

   406

 *

   407

 * @param flags info about segment

   408

 */

   409

static void UpdateSignalsAroundSegment(SigFlags flags)

   410

{

   411

	TileIndex tile;

   412

	Trackdir trackdir;

   413

   414

	while (_tbuset.Get(&tile, &trackdir)) {

   415

		assert(HasSignalOnTrackdir(tile, trackdir));

   416

   417

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

   418

		SignalState newstate = SIGNAL_STATE_GREEN;

   419

   420

		/* determine whether the new state is red */

   421

		if (flags & SF_TRAIN) {

   422

			/* train in the segment */

   423

			newstate = SIGNAL_STATE_RED;

   424

		} else {

   425

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

   426

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

   427

				/* at least one more exit */

   428

				if (flags & SF_EXIT2 &&

   429

						/* no green exit */

   430

						(!(flags & SF_GREEN) ||

   431

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

   432

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

   433

					newstate = SIGNAL_STATE_RED;

   434

				}

   435

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

   436

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

   437

			}

   438

		}

   439

   440

		/* only when the state changes */

   441

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

   442

			if (sig & SIGTYPE_EXIT) {

   443

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

   444

				DiagDirection exitdir = TrackdirToExitdir(ReverseTrackdir(trackdir));

   445

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

   446

			}

   447

			SetSignalStateByTrackdir(tile, trackdir, newstate);

   448

			MarkTileDirtyByTile(tile);

   449

		}

   450

	}

   451

   452

}

   453

   454

   455

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

   456

static inline void ResetSets()

   457

{

   458

	_tbuset.Reset();

   459

	_tbdset.Reset();

   460

	_globset.Reset();

   461

}

   462

   463

   464

/**

   465

 * Updates blocks in _globset buffer

   466

 *

   467

 * @param owner player whose signals we are updating

   468

 * @return state of the first block from _globset

   469

 * @pre IsValidPlayer(owner)

   470

 */

   471

static SigSegState UpdateSignalsInBuffer(Owner owner)

   472

{

   473

	assert(IsValidPlayer(owner));

   474

   475

	bool first = true;  // first block?

   476

	SigSegState state = SIGSEG_FREE; // value to return

   477

   478

	TileIndex tile;

   479

	DiagDirection dir;

   480

   481

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

   482

		assert(_tbuset.IsEmpty());

   483

		assert(_tbdset.IsEmpty());

   484

   485

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

   486

		 * Other situations happen when data are from outside functions -

   487

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

   488

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

   489

		 */

   490

		switch (GetTileType(tile)) {

   491

			case MP_TUNNELBRIDGE:

   492

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

   493

				assert(GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL);

   494

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

   495

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

   496

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

   497

				break;

   498

   499

			case MP_RAILWAY:

   500

				if (IsRailDepot(tile)) {

   501

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

   502

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

   503

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

   504

					break;

   505

				}

   506

				/* FALLTHROUGH */

   507

			case MP_STATION:

   508

			case MP_ROAD:

   509

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

   510

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

   511

					_tbdset.Add(tile, dir);

   512

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

   513

					break;

   514

				}

   515

				/* FALLTHROUGH */

   516

			default:

   517

				/* jump to next tile */

   518

				tile = tile + TileOffsByDiagDir(dir);

   519

				dir = ReverseDiagDir(dir);

   520

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

   521

					_tbdset.Add(tile, dir);

   522

					break;

   523

				}

   524

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