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

		int cost = 0;

    94

		if (TrackFollower::Allow90degTurns()

    95

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

    96

			// 90-deg curve penalty

    97

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

    98

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

    99

			// 45-deg curve penalty

   100

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

   101

		}

   102

		return cost;

   103

	}

   104

   105

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

   106

	FORCEINLINE int OneTileCost(TileIndex& tile, Trackdir trackdir)

   107

	{

   108

		int cost = 0;

   109

		// set base cost

   110

		if (IsDiagonalTrackdir(trackdir)) {

   111

			cost += YAPF_TILE_LENGTH;

   112

			switch (GetTileType(tile)) {

   113

				case MP_STREET:

   114

					/* Increase the cost for level crossings */

   115

					if (IsLevelCrossing(tile))

   116

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

   117

					break;

   118

   119

				default:

   120

					break;

   121

			}

   122

		} else {

   123

			// non-diagonal trackdir

   124

			cost = YAPF_TILE_CORNER_LENGTH;

   125

		}

   126

		return cost;

   127

	}

   128

   129

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

   130

	{

   131

		int cost = 0;

   132

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

   133

		CPerfStart perf_cost(Yapf().m_perf_other_cost);

   134

		if (IsTileType(tile, MP_RAILWAY)) {

   135

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

   136

			bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);

   137

			if (has_signal_against && !has_signal_along) {

   138

				// one-way signal in opposite direction

   139

				n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

   140

			} else if (has_signal_along) {

   141

				SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);

   142

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

   143

				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;

   144

				if (sig_state != SIGNAL_STATE_RED) {

   145

					// green signal

   146

					n.flags_u.flags_s.m_last_signal_was_red = false;

   147

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

   148

					if (look_ahead_cost < 0) {

   149

						// add its negation to the cost

   150

						cost -= look_ahead_cost;

   151

					}

   152

				} else {

   153

					// we have a red signal in our direction

   154

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

   155

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

   156

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

   157

						n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

   158

						Yapf().m_stopped_on_first_two_way_signal = true;

   159

						return -1;

   160

					}

   161

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

   162

					n.m_last_red_signal_type = sig_type;

   163

					n.flags_u.flags_s.m_last_signal_was_red = true;

   164

   165

					// look-ahead signal penalty

   166

					if (look_ahead_cost > 0) {

   167

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

   168

						cost += look_ahead_cost;

   169

					}

   170

   171

					// special signal penalties

   172

					if (n.m_num_signals_passed == 0) {

   173

						switch (sig_type) {

   174

							case SIGTYPE_COMBO:

   175

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

   176

							case SIGTYPE_NORMAL:

   177

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

   178

						};

   179

					}

   180

				}

   181

				n.m_num_signals_passed++;

   182

				n.m_segment->m_last_signal_tile = tile;

   183

				n.m_segment->m_last_signal_td = trackdir;

   184

			}

   185

		}

   186

		return cost;

   187

	}

   188

   189

	FORCEINLINE int PlatformLengthPenalty(int platform_length)

   190

	{

   191

		int cost = 0;

   192

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

   193

		assert(v != NULL);

   194

		assert(v->type == VEH_TRAIN);

   195

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

   196

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

   197

		if (platform_length > needed_platform_length) {

   198

			// apply penalty for longer platform than needed

   199

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

   200

		} else if (needed_platform_length > platform_length) {

   201

			// apply penalty for shorter platform than needed

   202

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

   203

		}

   204

		return cost;

   205

	}

   206

   207

public:

   208

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

   209

   210

   211

   212

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

   213

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

   214

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

   215

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

   216

	{

   217

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

   218

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

   219

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

   220

   221

		CPerfStart perf_cost(Yapf().m_perf_cost);

   222

   223

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

   224

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

   225

   226

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

   227

		CachedData &segment = *n.m_segment;

   228

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

   229

   230

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

   231

   232

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

   233

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

   234

		 *    - curve cost (or zero for straight move)

   235

		 *  2. Tile cost:

   236

		 *    - base tile cost

   237

		 *      - YAPF_TILE_LENGTH for diagonal tiles

   238

		 *      - YAPF_TILE_CORNER_LENGTH for non-diagonal tiles

   239

		 *    - tile penalties

   240

		 *      - tile slope penalty (upward slopes)

   241

		 *      - red signal penalty

   242

		 *      - level crossing penalty

   243

		 *      - speed-limit penalty (bridges)

   244

		 *      - station platform penalty

   245

		 *      - penalty for reversing in the depot

   246

		 *      - etc.

   247

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

   248

		 *    - last red signal penalty

   249

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

   250

		 */

   251

		int transition_cost = 0;

   252

		int extra_cost = 0;

   253

   254

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

   255

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

   256

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

   257

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

   258

		 */

   259

		int segment_entry_cost = 0;

   260

		int segment_cost = 0;

   261

   262

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

   263

   264

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

   265

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

   266

   267

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

   268

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

   269

   270

		EndSegmentReasonBits end_segment_reason = ESRB_NONE;

   271

   272

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

   273

   274

		if (!has_parent) {

   275

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

   276

			assert(!is_cached_segment);

   277

			/* Skip the first transition cost calculation. */

   278

			goto no_entry_cost;

   279

		}

   280

   281

		for (;;) {

   282

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

   283

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

   284

   285

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

   286

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

   287

			if (segment_cost == 0) {

   288

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

   289

				segment_entry_cost = transition_cost;

   290

				transition_cost = 0;

   291

   292

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

   293

				if (is_cached_segment) {

   294

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

   295

					segment_cost = segment.m_cost;

   296

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

   297

					end_segment_reason = segment.m_end_segment_reason;

   308

					/* No further calculation needed. */

   309

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

   310

					break;

   311

				}

   312

			} else {

   313

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

   314

				segment_cost += transition_cost;

   315

			}

   316

   317

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

   318

   319

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

   320

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

   321

   322

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

   323

			segment_cost += YAPF_TILE_LENGTH * tf->m_tiles_skipped;

   324

   325

			/* Slope cost. */

   326

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

   327

   328

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

   329

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

   330

			end_segment_reason = segment.m_end_segment_reason;

   331

   332

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

   333

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

   334

				/* Penalty for reversing in a depot. */

   335

				assert(IsRailDepot(cur.tile));

   336

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

   337

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

   338

				end_segment_reason |= ESRB_DEPOT;

   339

   340

			} else if (tf->m_is_station) {

   341

				/* Station penalties. */

   342

				uint platform_length = tf->m_tiles_skipped + 1;

   343

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

   344

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

   345

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

   346

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

   347

				end_segment_reason |= ESRB_STATION;

   348

   349

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

   350

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

   351

				end_segment_reason |= ESRB_WAYPOINT;

   352

			}

   353

   354

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

   355

			 * it would cause desync in MP. */

   356

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

   357

			{

   358

				int min_speed = 0;

   359

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

   360

				if (max_speed < v->max_speed)

   361

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

   362

				if (min_speed > v->max_speed)

   363

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

   364

			}

   365

   366

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

   367

			 * searching for the nearest depot). */

   368

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

   369

				end_segment_reason |= ESRB_PATH_TOO_LONG;

   370

			}

   371

   372

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

   373

			tf = &tf_local;

   374

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

   375

   376

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

   377

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

   378

				end_segment_reason |= ESRB_DEAD_END;

   379

				break;

   380

			}

   381

   382

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

   383

			if (KillFirstBit2x64(tf_local.m_new_td_bits) != 0) {

   384

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

   385

				end_segment_reason |= ESRB_CHOICE_FOLLOWS;

   386

				break;

   387

			}

   388

   389

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

   390

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

   391

   392

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

   393

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

   394

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

   395

				end_segment_reason |= ESRB_RAIL_TYPE;

   396

				break;

   397

			}

   398

   399

			/* Avoid infinite looping. */

   400

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

   401

				end_segment_reason |= ESRB_INFINITE_LOOP;

   402

				break;

   403

			}

   404

   405

			if (segment_cost > s_max_segment_cost) {

   406

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

   407

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

   408

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

   409

					end_segment_reason |= ESRB_SEGMENT_TOO_LONG;

   410

					break;

   411

				}

   412

			}

   413

   414

			/* Any other reason bit set? */

   415

			if (end_segment_reason != ESRB_NONE) {

   416

				break;

   417

			}

   418

   419

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

   420

			prev = cur;

   421

			cur = next;

   422

   423

		} // for (;;)

   424

   425

		bool target_seen = false;

   426

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

   427

			/* Depot, station or waypoint. */

   428

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

   429

				/* Destination found. */

   430

				target_seen = true;

   431

			}

   432

		}

   433

   434

		/* Update the segment if needed. */

   435

		if (!is_cached_segment) {

   436

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

   437

			segment.m_cost = segment_cost;

   438

			segment.m_end_segment_reason = end_segment_reason & ESRB_CACHED_MASK;

   439

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

   440

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

   441

		}

   442

   443

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

   444

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

   445

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

   446

			return false;

   447

		}

   448

   449

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

   450

		if (target_seen) {

   451

			n.flags_u.flags_s.m_targed_seen = true;

   452

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

   453

			if (n.flags_u.flags_s.m_last_signal_was_red) {

   454

				if (n.m_last_red_signal_type == SIGTYPE_EXIT) {

   455

					// last signal was red pre-signal-exit

   456

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

   457

				} else {

   458

					// last signal was red, but not exit

   459

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

   460

				}

   461

			}

   462

   463

			/* Station platform-length penalty. */

   464

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

   465

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

   466

				assert(st != NULL);

   467

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

   468

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

   469

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

   470

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

   471

				extra_cost += PlatformLengthPenalty(platform_length);

   472

			}

   473

		}

   474

   475

		// total node cost

   476

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

   477

   478

		return true;

   479

	}

   480

   481

	FORCEINLINE bool CanUseGlobalCache(Node& n) const

   482

	{

   483

		return !m_disable_cache

   484

			&& (n.m_parent != NULL)

   485

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

   486

	}

   487

   488

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

   489

	{

   490

		n.m_segment = &ci;

   491

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

   492

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

   493

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

   494

		}

   495

	}

   496

   497

	void DisableCache(bool disable)

   498

	{

   499

		m_disable_cache = disable;

   500

	}

   501

};

   502