1

/* $Id$ */

     2

     3

/** @file yapf_costrail.hpp */

     4

     5

#ifndef  YAPF_COSTRAIL_HPP

     6

#define  YAPF_COSTRAIL_HPP

     7

     8

     9

template <class Types>

    10

class CYapfCostRailT

    11

	: public CYapfCostBase

    12

	, public CostRailSettings

    13

{

    14

public:

    15

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

    16

	typedef typename Types::TrackFollower TrackFollower;

    17

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

    18

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

    19

	typedef typename Node::CachedData CachedData;

    20

    21

protected:

    22

    23

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

    24

	struct TILE {

    25

		TileIndex   tile;

    26

		Trackdir    td;

    27

		TileType    tile_type;

    28

		RailType    rail_type;

    29

    30

		TILE()

    31

		{

    32

			tile = INVALID_TILE;

    33

			td = INVALID_TRACKDIR;

    34

			tile_type = MP_VOID;

    35

			rail_type = INVALID_RAILTYPE;

    36

		}

    37

    38

		TILE(TileIndex tile, Trackdir td)

    39

		{

    40

			this->tile = tile;

    41

			this->td = td;

    42

			this->tile_type = GetTileType(tile);

    43

			this->rail_type = GetTileRailType(tile);

    44

		}

    45

    46

		TILE(const TILE &src)

    47

		{

    48

			tile = src.tile;

    49

			td = src.td;

    50

			tile_type = src.tile_type;

    51

			rail_type = src.rail_type;

    52

		}

    53

	};

    54

    55

protected:

    56

	int           m_max_cost;

    57

	CBlobT<int>   m_sig_look_ahead_costs;

    58

	bool          m_disable_cache;

    59

    60

public:

    61

	bool          m_stopped_on_first_two_way_signal;

    62

protected:

    63

    64

	static const int s_max_segment_cost = 10000;

    65

    66

	CYapfCostRailT()

    67

		: m_max_cost(0)

    68

		, m_disable_cache(false)

    69

		, m_stopped_on_first_two_way_signal(false)

    70

	{

    71

		// pre-compute look-ahead penalties into array

    72

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

    73

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

    74

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

    75

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

    76

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

    77

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

    78

	}

    79

    80

	/// to access inherited path finder

    81

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

    82

    83

public:

    84

	FORCEINLINE int SlopeCost(TileIndex tile, Trackdir td)

    85

	{

    86

		CPerfStart perf_cost(Yapf().m_perf_slope_cost);

    87

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

    88

		return Yapf().PfGetSettings().rail_slope_penalty;

    89

	}

    90

    91

	FORCEINLINE int CurveCost(Trackdir td1, Trackdir td2)

    92

	{

    93

		assert(IsValidTrackdir(td1));

    94

		assert(IsValidTrackdir(td2));

    95

		int cost = 0;

    96

		if (TrackFollower::Allow90degTurns()

    97

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

    98

			// 90-deg curve penalty

    99

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

   100

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

   101

			// 45-deg curve penalty

   102

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

   103

		}

   104

		return cost;

   105

	}

   106

   107

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

   108

	FORCEINLINE int OneTileCost(TileIndex& tile, Trackdir trackdir)

   109

	{

   110

		int cost = 0;

   111

		// set base cost

   112

		if (IsDiagonalTrackdir(trackdir)) {

   113

			cost += YAPF_TILE_LENGTH;

   114

			switch (GetTileType(tile)) {

   115

				case MP_ROAD:

   116

					/* Increase the cost for level crossings */

   117

					if (IsLevelCrossing(tile))

   118

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

   119

					break;

   120

   121

				default:

   122

					break;

   123

			}

   124

		} else {

   125

			// non-diagonal trackdir

   126

			cost = YAPF_TILE_CORNER_LENGTH;

   127

		}

   128

		return cost;

   129

	}

   130

   131

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

   132

	{

   133

		int cost = 0;

   134

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

   135

		CPerfStart perf_cost(Yapf().m_perf_other_cost);

   136

		if (IsTileType(tile, MP_RAILWAY)) {

   137

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

   138

			bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);

   139

			if (has_signal_against && !has_signal_along) {

   140

				// one-way signal in opposite direction

   141

				n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

   142

			} else if (has_signal_along) {

   143

				SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);

   144

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

   145

				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;

   146

				if (sig_state != SIGNAL_STATE_RED) {

   147

					// green signal

   148

					n.flags_u.flags_s.m_last_signal_was_red = false;

   149

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

   150

					if (look_ahead_cost < 0) {

   151

						// add its negation to the cost

   152

						cost -= look_ahead_cost;

   153

					}

   154

				} else {

   155

					// we have a red signal in our direction

   156

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

   157

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

   158

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

   159

						n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

   160

						Yapf().m_stopped_on_first_two_way_signal = true;

   161

						return -1;

   162

					}

   163

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

   164

					n.m_last_red_signal_type = sig_type;

   165

					n.flags_u.flags_s.m_last_signal_was_red = true;

   166

   167

					// look-ahead signal penalty

   168

					if (look_ahead_cost > 0) {

   169

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

   170

						cost += look_ahead_cost;

   171

					}

   172

   173

					// special signal penalties

   174

					if (n.m_num_signals_passed == 0) {

   175

						switch (sig_type) {

   176

							case SIGTYPE_COMBO:

   177

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

   178

							case SIGTYPE_NORMAL:

   179

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

   180

						};

   181

					}

   182

				}

   183

				n.m_num_signals_passed++;

   184

				n.m_segment->m_last_signal_tile = tile;

   185

				n.m_segment->m_last_signal_td = trackdir;

   186

			}

   187

		}

   188

		return cost;

   189

	}

   190

   191

	FORCEINLINE int PlatformLengthPenalty(int platform_length)

   192

	{

   193

		int cost = 0;

   194

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

   195

		assert(v != NULL);

   196

		assert(v->type == VEH_TRAIN);

   197

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

   198

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

   199

		if (platform_length > needed_platform_length) {

   200

			// apply penalty for longer platform than needed

   201

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

   202

		} else if (needed_platform_length > platform_length) {

   203

			// apply penalty for shorter platform than needed

   204

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

   205

		}

   206

		return cost;

   207

	}

   208

   209

public:

   210

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

   211

   212

   213

   214

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

   215

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

   216

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

   217

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

   218

	{

   219

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

   220

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

   221

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

   222

   223

		CPerfStart perf_cost(Yapf().m_perf_cost);

   224

   225

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

   226

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

   227

   228

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

   229

		CachedData &segment = *n.m_segment;

   230

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

   231

   232

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

   233

   234

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

   235

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

   236

		 *    - curve cost (or zero for straight move)

   237

		 *  2. Tile cost:

   238

		 *    - base tile cost

   239

		 *      - YAPF_TILE_LENGTH for diagonal tiles

   240

		 *      - YAPF_TILE_CORNER_LENGTH for non-diagonal tiles

   241

		 *    - tile penalties

   242

		 *      - tile slope penalty (upward slopes)

   243

		 *      - red signal penalty

   244

		 *      - level crossing penalty

   245

		 *      - speed-limit penalty (bridges)

   246

		 *      - station platform penalty

   247

		 *      - penalty for reversing in the depot

   248

		 *      - etc.

   249

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

   250

		 *    - last red signal penalty

   251

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

   252

		 */

   253

		int transition_cost = 0;

   254

		int extra_cost = 0;

   255

   256

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

   257

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

   258

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

   259

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

   260

		 */

   261

		int segment_entry_cost = 0;

   262

		int segment_cost = 0;

   263

   264

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

   265

   266

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

   267

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

   268

   269

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

   270

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

   271

   272

		EndSegmentReasonBits end_segment_reason = ESRB_NONE;

   273

   274

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

   275

   276

		if (!has_parent) {

   277

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

   278

			assert(!is_cached_segment);

   279

			/* Skip the first transition cost calculation. */

   280

			goto no_entry_cost;

   281

		}

   282

   283

		for (;;) {

   284

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

   285

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

   286

   287

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

   288

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

   289

			if (segment_cost == 0) {

   290

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

   291

				segment_entry_cost = transition_cost;

   292

				transition_cost = 0;

   293

   294

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

   295

				if (is_cached_segment) {

   296

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

   297

					segment_cost = segment.m_cost;

   298

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

   299

					end_segment_reason = segment.m_end_segment_reason;

   300

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

   301

					if (segment.m_last_signal_tile != INVALID_TILE) {

   302

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

   303

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

   304

						bool is_red = (sig_state == SIGNAL_STATE_RED);

   305

						n.flags_u.flags_s.m_last_signal_was_red = is_red;

   306

						if (is_red) {

   307

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

   308

						}

   309

					}

   310

					/* No further calculation needed. */

   311

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

   312

					break;

   313

				}

   314

			} else {

   315

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

   316

				segment_cost += transition_cost;

   317

			}

   318

   319

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

   320

   321

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

   322

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

   323

   324

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

   325

			segment_cost += YAPF_TILE_LENGTH * tf->m_tiles_skipped;

   326

   327

			/* Slope cost. */

   328

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

   329

   330

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

   331

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

   332

			end_segment_reason = segment.m_end_segment_reason;

   333

   334

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

   335

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

   336

				/* Penalty for reversing in a depot. */

   337

				assert(IsRailDepot(cur.tile));

   338

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

   339

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

   340

				end_segment_reason |= ESRB_DEPOT;

   341

   342

			} else if (tf->m_is_station) {

   343

				/* Station penalties. */

   344

				uint platform_length = tf->m_tiles_skipped + 1;

   345

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

   346

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

   347

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

   348

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

   349

				end_segment_reason |= ESRB_STATION;

   350

   351

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

   352

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

   353

				end_segment_reason |= ESRB_WAYPOINT;

   354

			}

   355

   356

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

   357

			 * it would cause desync in MP. */

   358

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

   359

			{

   360

				int min_speed = 0;

   361

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

   362

				if (max_speed < v->max_speed)

   363

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

   364

				if (min_speed > v->max_speed)

   365

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

   366

			}

   367

   368

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

   369

			 * searching for the nearest depot). */

   370

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

   371

				end_segment_reason |= ESRB_PATH_TOO_LONG;

   372

			}

   373

   374

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

   375

			tf = &tf_local;

   376

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

   377

   378

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

   379

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

   380

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

   381

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

   382

					end_segment_reason |= ESRB_RAIL_TYPE;

   383

				} else {

   384

					end_segment_reason |= ESRB_DEAD_END;

   385

				}

   386

				break;

   387

			}

   388

   389

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

   390

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

   391

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

   392

				end_segment_reason |= ESRB_CHOICE_FOLLOWS;

   393

				break;

   394

			}

   395

   396

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

   397

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

   398

   399

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

   400

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

   401

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

   402

				end_segment_reason |= ESRB_RAIL_TYPE;

   403

				break;

   404

			}

   405

   406

			/* Avoid infinite looping. */

   407

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

   408

				end_segment_reason |= ESRB_INFINITE_LOOP;

   409

				break;

   410

			}

   411

   412

			if (segment_cost > s_max_segment_cost) {

   413

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

   414

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

   415

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

   416

					end_segment_reason |= ESRB_SEGMENT_TOO_LONG;

   417

					break;

   418

				}

   419

			}

   420

   421

			/* Any other reason bit set? */

   422

			if (end_segment_reason != ESRB_NONE) {

   423

				break;

   424

			}

   425

   426

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

   427

			prev = cur;

   428

			cur = next;

   429

   430

		} // for (;;)

   431

   432

		bool target_seen = false;

   433

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

   434

			/* Depot, station or waypoint. */

   435

			if (Yapf().PfDetectDestination(cur.tile, cur.td)) {

   436

				/* Destination found. */

   437

				target_seen = true;

   438

			}

   439

		}

   440

   441

		/* Update the segment if needed. */

   442

		if (!is_cached_segment) {

   443

			/* Write back the segment information so it can be reused the next time. */

   444

			segment.m_cost = segment_cost;

   445

			segment.m_end_segment_reason = end_segment_reason & ESRB_CACHED_MASK;

   446

			/* Save end of segment back to the node. */

   447

			n.SetLastTileTrackdir(cur.tile, cur.td);

   448

		}

   449

   450

		/* Do we have an excuse why not to continue pathfinding in this direction? */

   451

		if (!target_seen && (end_segment_reason & ESRB_ABORT_PF_MASK) != ESRB_NONE) {

   452

			/* Reason to not continue. Stop this PF branch. */

   453

			return false;

   454

		}

   455

   456

		/* Special costs for the case we have reached our target. */

   457

		if (target_seen) {

   458

			n.flags_u.flags_s.m_targed_seen = true;

   459

			/* Last-red and last-red-exit penalties. */

   460

			if (n.flags_u.flags_s.m_last_signal_was_red) {

   461

				if (n.m_last_red_signal_type == SIGTYPE_EXIT) {

   462

					// last signal was red pre-signal-exit

   463

					extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty;

   464

				} else {

   465

					// last signal was red, but not exit

   466

					extra_cost += Yapf().PfGetSettings().rail_lastred_penalty;

   467

				}

   468

			}

   469

   470

			/* Station platform-length penalty. */

   471

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

   472

				Station *st = GetStationByTile(n.GetLastTile());

   473

				assert(st != NULL);

   474

				uint platform_length = st->GetPlatformLength(n.GetLastTile(), ReverseDiagDir(TrackdirToExitdir(n.GetLastTrackdir())));

   475

				/* Reduce the extra cost caused by passing-station penalty (each station receives it in the segment cost). */

   476

				extra_cost -= Yapf().PfGetSettings().rail_station_penalty * platform_length;

   477

				/* Add penalty for the inappropriate platform length. */

   478

				extra_cost += PlatformLengthPenalty(platform_length);

   479

			}

   480

		}

   481

   482

		// total node cost

   483

		n.m_cost = parent_cost + segment_entry_cost + segment_cost + extra_cost;

   484

   485

		return true;

   486

	}

   487

   488

	FORCEINLINE bool CanUseGlobalCache(Node& n) const

   489

	{

   490

		return !m_disable_cache

   491

			&& (n.m_parent != NULL)

   492

			&& (n.m_parent->m_num_signals_passed >= m_sig_look_ahead_costs.Size());

   493

	}

   494

   495

	FORCEINLINE void ConnectNodeToCachedData(Node& n, CachedData& ci)

   496

	{

   497

		n.m_segment = &ci;

   498

		if (n.m_segment->m_cost < 0) {

   499

			n.m_segment->m_last_tile = n.m_key.m_tile;

   500

			n.m_segment->m_last_td = n.m_key.m_td;

   501

		}