1

/* $Id$ */

     2

     3

/** @file yapf_costrail.hpp Cost determination for rails. */

     4

     5

#ifndef  YAPF_COSTRAIL_HPP

     6

#define  YAPF_COSTRAIL_HPP

     7

     8

#include "../pbs.h"

     9

    10

template <class Types>

    11

class CYapfCostRailT

    12

	: public CYapfCostBase

    13

	, public CostRailSettings

    14

{

    15

public:

    16

	typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)

    17

	typedef typename Types::TrackFollower TrackFollower;

    18

	typedef typename Types::NodeList::Titem Node; ///< this will be our node type

    19

	typedef typename Node::Key Key;               ///< key to hash tables

    20

	typedef typename Node::CachedData CachedData;

    21

    22

protected:

    23

    24

	/* Structure used inside PfCalcCost() to keep basic tile information. */

    25

	struct TILE {

    26

		TileIndex   tile;

    27

		Trackdir    td;

    28

		TileType    tile_type;

    29

		RailType    rail_type;

    30

    31

		TILE()

    32

		{

    33

			tile = INVALID_TILE;

    34

			td = INVALID_TRACKDIR;

    35

			tile_type = MP_VOID;

    36

			rail_type = INVALID_RAILTYPE;

    37

		}

    38

    39

		TILE(TileIndex tile, Trackdir td)

    40

		{

    41

			this->tile = tile;

    42

			this->td = td;

    43

			this->tile_type = GetTileType(tile);

    44

			this->rail_type = GetTileRailType(tile);

    45

		}

    46

    47

		TILE(const TILE &src)

    48

		{

    49

			tile = src.tile;

    50

			td = src.td;

    51

			tile_type = src.tile_type;

    52

			rail_type = src.rail_type;

    53

		}

    54

	};

    55

    56

protected:

    57

	int           m_max_cost;

    58

	CBlobT<int>   m_sig_look_ahead_costs;

    59

	bool          m_disable_cache;

    60

    61

public:

    62

	bool          m_stopped_on_first_two_way_signal;

    63

protected:

    64

    65

	static const int s_max_segment_cost = 10000;

    66

    67

	CYapfCostRailT()

    68

		: m_max_cost(0)

    69

		, m_disable_cache(false)

    70

		, m_stopped_on_first_two_way_signal(false)

    71

	{

    72

		// pre-compute look-ahead penalties into array

    73

		int p0 = Yapf().PfGetSettings().rail_look_ahead_signal_p0;

    74

		int p1 = Yapf().PfGetSettings().rail_look_ahead_signal_p1;

    75

		int p2 = Yapf().PfGetSettings().rail_look_ahead_signal_p2;

    76

		int *pen = m_sig_look_ahead_costs.GrowSizeNC(Yapf().PfGetSettings().rail_look_ahead_max_signals);

    77

		for (uint i = 0; i < Yapf().PfGetSettings().rail_look_ahead_max_signals; i++)

    78

			pen[i] = p0 + i * (p1 + i * p2);

    79

	}

    80

    81

	/// to access inherited path finder

    82

	Tpf& Yapf() {return *static_cast<Tpf*>(this);}

    83

    84

public:

    85

	FORCEINLINE int SlopeCost(TileIndex tile, Trackdir td)

    86

	{

    87

		CPerfStart perf_cost(Yapf().m_perf_slope_cost);

    88

		if (!stSlopeCost(tile, td)) return 0;

    89

		return Yapf().PfGetSettings().rail_slope_penalty;

    90

	}

    91

    92

	FORCEINLINE int CurveCost(Trackdir td1, Trackdir td2)

    93

	{

    94

		assert(IsValidTrackdir(td1));

    95

		assert(IsValidTrackdir(td2));

    96

		int cost = 0;

    97

		if (TrackFollower::Allow90degTurns()

    98

				&& ((TrackdirToTrackdirBits(td2) & (TrackdirBits)TrackdirCrossesTrackdirs(td1)) != 0)) {

    99

			// 90-deg curve penalty

   100

			cost += Yapf().PfGetSettings().rail_curve90_penalty;

   101

		} else if (td2 != NextTrackdir(td1)) {

   102

			// 45-deg curve penalty

   103

			cost += Yapf().PfGetSettings().rail_curve45_penalty;

   104

		}

   105

		return cost;

   106

	}

   107

   108

	FORCEINLINE int SwitchCost(TileIndex tile1, TileIndex tile2, DiagDirection exitdir)

   109

	{

   110

		if (IsTileType(tile1, MP_RAILWAY) && IsTileType(tile2, MP_RAILWAY)) {

   111

			bool t1 = KillFirstBit(GetTrackBits(tile1) & DiagdirReachesTracks(ReverseDiagDir(exitdir))) != TRACK_BIT_NONE;

   112

			bool t2 = KillFirstBit(GetTrackBits(tile2) & DiagdirReachesTracks(exitdir)) != TRACK_BIT_NONE;

   113

			if (t1 && t2) return Yapf().PfGetSettings().rail_doubleslip_penalty;

   114

		}

   115

		return 0;

   116

	}

   117

   118

	/** Return one tile cost (base cost + level crossing penalty). */

   119

	FORCEINLINE int OneTileCost(TileIndex& tile, Trackdir trackdir)

   120

	{

   121

		int cost = 0;

   122

		// set base cost

   123

		if (IsDiagonalTrackdir(trackdir)) {

   124

			cost += YAPF_TILE_LENGTH;

   125

			switch (GetTileType(tile)) {

   126

				case MP_ROAD:

   127

					/* Increase the cost for level crossings */

   128

					if (IsLevelCrossing(tile))

   129

						cost += Yapf().PfGetSettings().rail_crossing_penalty;

   130

					break;

   131

   132

				default:

   133

					break;

   134

			}

   135

		} else {

   136

			// non-diagonal trackdir

   137

			cost = YAPF_TILE_CORNER_LENGTH;

   138

		}

   139

		return cost;

   140

	}

   141

   142

	/** Check for a reserved station platform. */

   143

	FORCEINLINE bool IsAnyStationTileReserved(TileIndex tile, Trackdir trackdir, int skipped)

   144

	{

   145

		TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(trackdir)));

   146

		for (; skipped >= 0; skipped--, tile += diff) {

   147

			if (GetRailwayStationReservation(tile)) return true;

   148

		}

   149

		return false;

   150

	}

   151

   152

	/** The cost for reserved tiles, including skipped ones. */

   153

	FORCEINLINE int ReservationCost(Node& n, TileIndex tile, Trackdir trackdir, int skipped)

   154

	{

   155

		if (n.m_num_signals_passed >= m_sig_look_ahead_costs.Size() / 2) return 0;

   156

   157

		if (IsRailwayStationTile(tile) && IsAnyStationTileReserved(tile, trackdir, skipped)) {

   158

			return Yapf().PfGetSettings().rail_pbs_station_penalty * (skipped + 1);

   159

		} else if (TrackOverlapsTracks(GetReservedTrackbits(tile), TrackdirToTrack(trackdir))) {

   160

			int cost = Yapf().PfGetSettings().rail_pbs_cross_penalty;

   161

			if (!IsDiagonalTrackdir(trackdir)) cost = (cost * YAPF_TILE_CORNER_LENGTH) / YAPF_TILE_LENGTH;

   162

			return cost * (skipped + 1);

   163

		}

   164

		return 0;

   165

	}

   166

   167

	int SignalCost(Node& n, TileIndex tile, Trackdir trackdir)

   168

	{

   169

		int cost = 0;

   170

		// if there is one-way signal in the opposite direction, then it is not our way

   171

		CPerfStart perf_cost(Yapf().m_perf_other_cost);

   172

		if (IsTileType(tile, MP_RAILWAY)) {

   173

			bool has_signal_against = HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir));

   174

			bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);

   175

			if (has_signal_against && !has_signal_along && IsOnewaySignal(tile, TrackdirToTrack(trackdir))) {

   176

				// one-way signal in opposite direction

   177

				n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

   178

			} else {

   179

				if (has_signal_along) {

   180

					SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);

   181

					// cache the look-ahead polynomial constant only if we didn't pass more signals than the look-ahead limit is

   182

					int look_ahead_cost = (n.m_num_signals_passed < m_sig_look_ahead_costs.Size()) ? m_sig_look_ahead_costs.Data()[n.m_num_signals_passed] : 0;

   183

					if (sig_state != SIGNAL_STATE_RED) {

   184

						// green signal

   185

						n.flags_u.flags_s.m_last_signal_was_red = false;

   186

						// negative look-ahead red-signal penalties would cause problems later, so use them as positive penalties for green signal

   187

						if (look_ahead_cost < 0) {

   188

							// add its negation to the cost

   189

							cost -= look_ahead_cost;

   190

						}

   191

					} else {

   192

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

   193

						// we have a red signal in our direction

   194

						// was it first signal which is two-way?

   195

						if (!IsPbsSignal(sig_type) && Yapf().TreatFirstRedTwoWaySignalAsEOL() && n.flags_u.flags_s.m_choice_seen && has_signal_against && n.m_num_signals_passed == 0) {

   196

							// yes, the first signal is two-way red signal => DEAD END

   197

							n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

   198

							Yapf().m_stopped_on_first_two_way_signal = true;

   199

							return -1;

   200

						}

   201

						n.m_last_red_signal_type = sig_type;

   202

						n.flags_u.flags_s.m_last_signal_was_red = true;

   203

   204

						// look-ahead signal penalty

   205

						if (!IsPbsSignal(sig_type) && look_ahead_cost > 0) {

   206

							// add the look ahead penalty only if it is positive

   207

							cost += look_ahead_cost;

   208

						}

   209

   210

						// special signal penalties

   211

						if (n.m_num_signals_passed == 0) {

   212

							switch (sig_type) {

   213

								case SIGTYPE_COMBO:

   214

								case SIGTYPE_EXIT:   cost += Yapf().PfGetSettings().rail_firstred_exit_penalty; break; // first signal is red pre-signal-exit

   215

								case SIGTYPE_NORMAL:

   216

								case SIGTYPE_ENTRY:  cost += Yapf().PfGetSettings().rail_firstred_penalty; break;

   217

								default: break;

   218

							};

   219

						}

   220

					}

   221

   222

					n.m_num_signals_passed++;

   223

					n.m_segment->m_last_signal_tile = tile;

   224

					n.m_segment->m_last_signal_td = trackdir;

   225

				}

   226

   227

				if (has_signal_against && IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) {

   228

					cost += n.m_num_signals_passed < Yapf().PfGetSettings().rail_look_ahead_max_signals ? Yapf().PfGetSettings().rail_pbs_signal_back_penalty : 0;

   229

				}

   230

			}

   231

		}

   232

		return cost;

   233

	}

   234

   235

	FORCEINLINE int PlatformLengthPenalty(int platform_length)

   236

	{

   237

		int cost = 0;

   238

		const Vehicle *v = Yapf().GetVehicle();

   239

		assert(v != NULL);

   240

		assert(v->type == VEH_TRAIN);

   241

		assert(v->u.rail.cached_total_length != 0);

   242

		int needed_platform_length = (v->u.rail.cached_total_length + TILE_SIZE - 1) / TILE_SIZE;

   243

		if (platform_length > needed_platform_length) {

   244

			// apply penalty for longer platform than needed

   245

			cost += Yapf().PfGetSettings().rail_longer_platform_penalty;

   246

		} else if (needed_platform_length > platform_length) {

   247

			// apply penalty for shorter platform than needed

   248

			cost += Yapf().PfGetSettings().rail_shorter_platform_penalty;

   249

		}

   250

		return cost;

   251

	}

   252

   253

public:

   254

	FORCEINLINE void SetMaxCost(int max_cost) {m_max_cost = max_cost;}

   255

   256

   257

   258

	/** Called by YAPF to calculate the cost from the origin to the given node.

   259

	 *  Calculates only the cost of given node, adds it to the parent node cost

   260

	 *  and stores the result into Node::m_cost member */

   261

	FORCEINLINE bool PfCalcCost(Node &n, const TrackFollower *tf)

   262

	{

   263

		assert(!n.flags_u.flags_s.m_targed_seen);

   264

		assert(tf->m_new_tile == n.m_key.m_tile);

   265

		assert((TrackdirToTrackdirBits(n.m_key.m_td) & tf->m_new_td_bits) != TRACKDIR_BIT_NONE);

   266

   267

		CPerfStart perf_cost(Yapf().m_perf_cost);

   268

   269

		/* Does the node have some parent node? */

   270

		bool has_parent = (n.m_parent != NULL);

   271

   272

		/* Do we already have a cached segment? */

   273

		CachedData &segment = *n.m_segment;

   274

		bool is_cached_segment = (segment.m_cost >= 0);

   275

   276

		int parent_cost = has_parent ? n.m_parent->m_cost : 0;

   277

   278

		/* Each node cost contains 2 or 3 main components:

   279

		 *  1. Transition cost - cost of the move from previous node (tile):

   280

		 *    - curve cost (or zero for straight move)

   281

		 *  2. Tile cost:

   282

		 *    - base tile cost

   283

		 *      - YAPF_TILE_LENGTH for diagonal tiles

   284

		 *      - YAPF_TILE_CORNER_LENGTH for non-diagonal tiles

   285

		 *    - tile penalties

   286

		 *      - tile slope penalty (upward slopes)

   287

		 *      - red signal penalty

   288

		 *      - level crossing penalty

   289

		 *      - speed-limit penalty (bridges)

   290

		 *      - station platform penalty

   291

		 *      - penalty for reversing in the depot

   292

		 *      - etc.

   293

		 *  3. Extra cost (applies to the last node only)

   294

		 *    - last red signal penalty

   295

		 *    - penalty for too long or too short platform on the destination station

   296

		 */

   297

		int transition_cost = 0;

   298

		int extra_cost = 0;

   299

   300

		/* Segment: one or more tiles connected by contiguous tracks of the same type.

   301

		 * Each segment cost includes 'Tile cost' for all its tiles (including the first

   302

		 * and last), and the 'Transition cost' between its tiles. The first transition

   303

		 * cost of segment entry (move from the 'parent' node) is not included!

   304

		 */

   305

		int segment_entry_cost = 0;

   306

		int segment_cost = 0;

   307

   308

		const Vehicle *v = Yapf().GetVehicle();

   309

   310

		// start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment

   311

		TILE cur(n.m_key.m_tile, n.m_key.m_td);

   312

   313

		// the previous tile will be needed for transition cost calculations

   314

		TILE prev = !has_parent ? TILE() : TILE(n.m_parent->GetLastTile(), n.m_parent->GetLastTrackdir());

   315

   316

		EndSegmentReasonBits end_segment_reason = ESRB_NONE;

   317

   318

		TrackFollower tf_local(v, Yapf().GetCompatibleRailTypes(), &Yapf().m_perf_ts_cost);

   319

   320

		if (!has_parent) {

   321

			/* We will jump to the middle of the cost calculator assuming that segment cache is not used. */

   322

			assert(!is_cached_segment);

   323

			/* Skip the first transition cost calculation. */

   324

			goto no_entry_cost;

   325

		}

   326

   327

		for (;;) {

   328

			/* Transition cost (cost of the move from previous tile) */

   329

			transition_cost = Yapf().CurveCost(prev.td, cur.td);

   330

			transition_cost += Yapf().SwitchCost(prev.tile, cur.tile, TrackdirToExitdir(prev.td));

   331

   332

			/* First transition cost counts against segment entry cost, other transitions

   333

			 * inside segment will come to segment cost (and will be cached) */

   334

			if (segment_cost == 0) {

   335

				/* We just entered the loop. First transition cost goes to segment entry cost)*/

   336

				segment_entry_cost = transition_cost;

   337

				transition_cost = 0;

   338

   339

				/* It is the right time now to look if we can reuse the cached segment cost. */

   340

				if (is_cached_segment) {

   341

					/* Yes, we already know the segment cost. */

   342

					segment_cost = segment.m_cost;

   343

					/* We know also the reason why the segment ends. */

   344

					end_segment_reason = segment.m_end_segment_reason;

   345

					/* We will need also some information about the last signal (if it was red). */

   346

					if (segment.m_last_signal_tile != INVALID_TILE) {

   347

						assert(HasSignalOnTrackdir(segment.m_last_signal_tile, segment.m_last_signal_td));

   348

						SignalState sig_state = GetSignalStateByTrackdir(segment.m_last_signal_tile, segment.m_last_signal_td);

   349

						bool is_red = (sig_state == SIGNAL_STATE_RED);

   350

						n.flags_u.flags_s.m_last_signal_was_red = is_red;

   351

						if (is_red) {

   352

							n.m_last_red_signal_type = GetSignalType(segment.m_last_signal_tile, TrackdirToTrack(segment.m_last_signal_td));

   353

						}

   354

					}

   355

					/* No further calculation needed. */

   356

					cur = TILE(n.GetLastTile(), n.GetLastTrackdir());

   357

					break;

   358

				}

   359

			} else {

   360

				/* Other than first transition cost count as the regular segment cost. */

   361

				segment_cost += transition_cost;

   362

			}

   363

   364

no_entry_cost: // jump here at the beginning if the node has no parent (it is the first node)

   365

   366

			/* All other tile costs will be calculated here. */

   367

			segment_cost += Yapf().OneTileCost(cur.tile, cur.td);

   368

   369

			/* If we skipped some tunnel/bridge/station tiles, add their base cost */

   370

			segment_cost += YAPF_TILE_LENGTH * tf->m_tiles_skipped;

   371

   372

			/* Slope cost. */

   373

			segment_cost += Yapf().SlopeCost(cur.tile, cur.td);

   374

   375

			/* Reserved tiles. */

   376

			segment_cost += Yapf().ReservationCost(n, cur.tile, cur.td, tf->m_tiles_skipped);

   377

   378

			/* Signal cost (routine can modify segment data). */

   379

			segment_cost += Yapf().SignalCost(n, cur.tile, cur.td);

   380

			end_segment_reason = segment.m_end_segment_reason;

   381

   382

			/* Tests for 'potential target' reasons to close the segment. */

   383

			if (cur.tile == prev.tile) {

   384

				/* Penalty for reversing in a depot. */

   385

				assert(IsRailDepot(cur.tile));

   386

				segment_cost += Yapf().PfGetSettings().rail_depot_reverse_penalty;

   387

				/* We will end in this pass (depot is possible target) */

   388

				end_segment_reason |= ESRB_DEPOT;

   389

   390

			} else if (tf->m_is_station) {

   391

				/* Station penalties. */

   392

				uint platform_length = tf->m_tiles_skipped + 1;

   393

				/* We don't know yet if the station is our target or not. Act like

   394

				 * if it is pass-through station (not our destination). */

   395

				segment_cost += Yapf().PfGetSettings().rail_station_penalty * platform_length;

   396

				/* We will end in this pass (station is possible target) */

   397

				end_segment_reason |= ESRB_STATION;

   398

   399

			} else if (cur.tile_type == MP_RAILWAY && IsRailWaypoint(cur.tile)) {

   400

				/* Waypoint is also a good reason to finish. */

   401

				end_segment_reason |= ESRB_WAYPOINT;

   402

			} else if (TrackFollower::DoTrackMasking() && cur.tile_type == MP_RAILWAY) {

   403

				/* Searching for a safe tile? */

   404

				if (HasSignalOnTrackdir(cur.tile, cur.td) && !IsPbsSignal(GetSignalType(cur.tile, TrackdirToTrack(cur.td)))) {

   405

					end_segment_reason |= ESRB_SAFE_TILE;

   406

				}

   407

			}

   408

   409

			/* Apply min/max speed penalties only when inside the look-ahead radius. Otherwise

   410

			 * it would cause desync in MP. */

   411

			if (n.m_num_signals_passed < m_sig_look_ahead_costs.Size())

   412

			{

   413

				int min_speed = 0;

   414

				int max_speed = tf->GetSpeedLimit(&min_speed);

   415

				if (max_speed < v->max_speed)

   416

					extra_cost += YAPF_TILE_LENGTH * (v->max_speed - max_speed) * (4 + tf->m_tiles_skipped) / v->max_speed;

   417

				if (min_speed > v->max_speed)

   418

					extra_cost += YAPF_TILE_LENGTH * (min_speed - v->max_speed);

   419

			}

   420

   421

			/* Finish if we already exceeded the maximum path cost (i.e. when

   422

			 * searching for the nearest depot). */

   423

			if (m_max_cost > 0 && (parent_cost + segment_entry_cost + segment_cost) > m_max_cost) {

   424

				end_segment_reason |= ESRB_PATH_TOO_LONG;

   425

			}

   426

   427

			/* Move to the next tile/trackdir. */

   428

			tf = &tf_local;

   429

			tf_local.Init(v, Yapf().GetCompatibleRailTypes(), &Yapf().m_perf_ts_cost);

   430

   431

			if (!tf_local.Follow(cur.tile, cur.td)) {

   432

				assert(tf_local.m_err != TrackFollower::EC_NONE);

   433

				/* Can't move to the next tile (EOL?). */

   434

				if (tf_local.m_err == TrackFollower::EC_RAIL_TYPE) {

   435

					end_segment_reason |= ESRB_RAIL_TYPE;

   436

				} else {

   437

					end_segment_reason |= ESRB_DEAD_END;

   438

				}

   439

   440

				if (TrackFollower::DoTrackMasking() && !HasOnewaySignalBlockingTrackdir(cur.tile, cur.td)) {

   441

					end_segment_reason |= ESRB_SAFE_TILE;

   442

				}

   443

				break;

   444

			}

   445

   446

			/* Check if the next tile is not a choice. */

   447

			if (KillFirstBit(tf_local.m_new_td_bits) != TRACKDIR_BIT_NONE) {

   448

				/* More than one segment will follow. Close this one. */

   449

				end_segment_reason |= ESRB_CHOICE_FOLLOWS;

   450

				break;

   451

			}

   452

   453

			/* Gather the next tile/trackdir/tile_type/rail_type. */

   454

			TILE next(tf_local.m_new_tile, (Trackdir)FindFirstBit2x64(tf_local.m_new_td_bits));

   455

   456

			if (TrackFollower::DoTrackMasking() && HasPbsSignalOnTrackdir(next.tile, next.td)) {

   457

				/* Possible safe tile. */

   458

				end_segment_reason |= ESRB_SAFE_TILE;

   459

			}

   460

   461

			/* Check the next tile for the rail type. */

   462

			if (next.rail_type != cur.rail_type) {

   463

				/* Segment must consist from the same rail_type tiles. */

   464

				end_segment_reason |= ESRB_RAIL_TYPE;

   465

				break;

   466

			}

   467

   468

			/* Avoid infinite looping. */

   469

			if (next.tile == n.m_key.m_tile && next.td == n.m_key.m_td) {

   470

				end_segment_reason |= ESRB_INFINITE_LOOP;

   471

				break;

   472

			}

   473

   474

			if (segment_cost > s_max_segment_cost) {

   475

				/* Potentially in the infinite loop (or only very long segment?). We should

   476

				 * not force it to finish prematurely unless we are on a regular tile. */

   477

				if (IsTileType(tf->m_new_tile, MP_RAILWAY)) {

   478

					end_segment_reason |= ESRB_SEGMENT_TOO_LONG;

   479

					break;

   480

				}

   481

			}

   482

   483

			/* Any other reason bit set? */

   484

			if (end_segment_reason != ESRB_NONE) {

   485

				break;

   486

			}

   487

   488

			/* For the next loop set new prev and cur tile info. */

   489

			prev = cur;

   490

			cur = next;

   491

   492

		} // for (;;)

   493

   494

		bool target_seen = false;

   495

		if ((end_segment_reason & ESRB_POSSIBLE_TARGET) != ESRB_NONE) {

   496

			/* Depot, station or waypoint. */