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

    59

public:

    60

	bool          m_stopped_on_first_two_way_signal;

    61

protected:

    62

    63

	static const int s_max_segment_cost = 10000;

    64

    65

	CYapfCostRailT()

    66

		: m_max_cost(0)

    67

		, m_stopped_on_first_two_way_signal(false)

    68

	{

    69

		// pre-compute look-ahead penalties into array

    70

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

    71

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

    72

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

    73

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

    74

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

    75

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

    76

	}

    77

    78

	/// to access inherited path finder

    79

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

    80

    81

public:

    82

	FORCEINLINE int SlopeCost(TileIndex tile, Trackdir td)

    83

	{

    84

		CPerfStart perf_cost(Yapf().m_perf_slope_cost);

    85

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

    86

		return Yapf().PfGetSettings().rail_slope_penalty;

    87

	}

    88

    89

	FORCEINLINE int CurveCost(Trackdir td1, Trackdir td2)

    90

	{

    91

		int cost = 0;

    92

		if (TrackFollower::Allow90degTurns()

    93

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

    94

			// 90-deg curve penalty

    95

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

    96

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

    97

			// 45-deg curve penalty

    98

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

    99

		}

   100

		return cost;

   101

	}

   102

   103

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

   104

	FORCEINLINE int OneTileCost(TileIndex& tile, Trackdir trackdir)

   105

	{

   106

		int cost = 0;

   107

		// set base cost

   108

		if (IsDiagonalTrackdir(trackdir)) {

   109

			cost += YAPF_TILE_LENGTH;

   110

			switch (GetTileType(tile)) {

   111

				case MP_STREET:

   112

					/* Increase the cost for level crossings */

   113

					if (IsLevelCrossing(tile))

   114

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

   115

					break;

   116

   117

				default:

   118

					break;

   119

			}

   120

		} else {

   121

			// non-diagonal trackdir

   122

			cost = YAPF_TILE_CORNER_LENGTH;

   123

		}

   124

		return cost;

   125

	}

   126

   127

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

   128

	{

   129

		int cost = 0;

   130

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

   131

		CPerfStart perf_cost(Yapf().m_perf_other_cost);

   132

		if (IsTileType(tile, MP_RAILWAY)) {

   133

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

   134

			bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);

   135

			if (has_signal_against && !has_signal_along) {

   136

				// one-way signal in opposite direction

   137

				n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

   138

			} else if (has_signal_along) {

   139

				SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);

   140

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

   141

				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;

   142

				if (sig_state != SIGNAL_STATE_RED) {

   143

					// green signal

   144

					n.flags_u.flags_s.m_last_signal_was_red = false;

   145

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

   146

					if (look_ahead_cost < 0) {

   147

						// add its negation to the cost

   148

						cost -= look_ahead_cost;

   149

					}

   150

				} else {

   151

					// we have a red signal in our direction

   152

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

   153

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

   154

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

   155

						n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

   156

						Yapf().m_stopped_on_first_two_way_signal = true;

   157

						return -1;

   158

					}

   159

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

   160

					n.m_last_red_signal_type = sig_type;

   161

					n.flags_u.flags_s.m_last_signal_was_red = true;

   162

   163

					// look-ahead signal penalty

   164

					if (look_ahead_cost > 0) {

   165

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

   166

						cost += look_ahead_cost;

   167

					}

   168

   169

					// special signal penalties

   170

					if (n.m_num_signals_passed == 0) {

   171

						switch (sig_type) {

   172

							case SIGTYPE_COMBO:

   173

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

   174

							case SIGTYPE_NORMAL:

   175

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

   176

						};

   177

					}

   178

				}

   179

				n.m_num_signals_passed++;

   180

				n.m_segment->m_last_signal_tile = tile;

   181

				n.m_segment->m_last_signal_td = trackdir;

   182

			}

   183

		}

   184

		return cost;

   185

	}

   186

   187

	FORCEINLINE int PlatformLengthPenalty(int platform_length)

   188

	{

   189

		int cost = 0;

   190

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

   191

		assert(v != NULL);

   192

		assert(v->type == VEH_TRAIN);

   193

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

   194

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

   195

		if (platform_length > needed_platform_length) {

   196

			// apply penalty for longer platform than needed

   197

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

   198

		} else if (needed_platform_length > platform_length) {

   199

			// apply penalty for shorter platform than needed

   200

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

   201

		}

   202

		return cost;

   203

	}

   204

   205

public:

   206

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

   207

   208

   209

   210

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

   211

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

   212

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

   213

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

   214

	{

   215

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

   216

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

   217

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

   218

   219

		CPerfStart perf_cost(Yapf().m_perf_cost);

   220

   221

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

   222

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

   223

   224

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

   225

		CachedData &segment = *n.m_segment;

   226

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

   227

   228

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

   229

   230

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

   231

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

   232

		 *    - curve cost (or zero for straight move)

   233

		 *  2. Tile cost:

   234

		 *    - base tile cost

   235

		 *      - YAPF_TILE_LENGTH for diagonal tiles

   236

		 *      - YAPF_TILE_CORNER_LENGTH for non-diagonal tiles

   237

		 *    - tile penalties

   238

		 *      - tile slope penalty (upward slopes)

   239

		 *      - red signal penalty

   240

		 *      - level crossing penalty

   241

		 *      - speed-limit penalty (bridges)

   242

		 *      - station platform penalty

   243

		 *      - penalty for reversing in the depot

   244

		 *      - etc.

   245

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

   246

		 *    - last red signal penalty

   247

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

   248

		 */

   249

		int transition_cost = 0;

   250

		int extra_cost = 0;

   251

   252

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

   253

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

   254

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

   255

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

   256

		 */

   257

		int segment_entry_cost = 0;

   258

		int segment_cost = 0;

   259

   260

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

   261

   262

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

   263

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

   264

   265

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

   266

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

   267

   268

		EndSegmentReasonBits end_segment_reason = ESRB_NONE;

   269

   270

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

   271

   272

		if (!has_parent) {

   273

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

   274

			assert(!is_cached_segment);

   275

			/* Skip the first transition cost calculation. */

   276

			goto no_entry_cost;

   277

		}

   278

   279

		for (;;) {

   280

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

   281

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

   282

   283

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

   284

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

   285

			if (segment_cost == 0) {

   286

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

   287

				segment_entry_cost = transition_cost;

   288

				transition_cost = 0;

   289

   290

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

   291

				if (is_cached_segment) {

   292

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

   293

					segment_cost = segment.m_cost;

   294

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

   295

					end_segment_reason = segment.m_end_segment_reason;

   296

					/* No further calculation needed. */

   297

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

   298

					break;

   299

				}

   300

			} else {

   301

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

   302

				segment_cost += transition_cost;

   303

			}

   304

   305

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

   306

   307

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

   308

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

   309

   310

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

   311

			segment_cost += YAPF_TILE_LENGTH * tf->m_tiles_skipped;

   312

   313

			/* Slope cost. */

   314

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

   315

   316

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

   317

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

   318

			end_segment_reason = segment.m_end_segment_reason;

   319

   320

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

   321

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

   322

				/* Penalty for reversing in a depot. */

   323

				assert(IsRailDepot(cur.tile));

   324

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

   325

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

   326

				end_segment_reason |= ESRB_DEPOT;

   327

   328

			} else if (tf->m_is_station) {

   329

				/* Station penalties. */

   330

				uint platform_length = tf->m_tiles_skipped + 1;

   331

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

   332

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

   333

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

   334

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

   335

				end_segment_reason |= ESRB_STATION;

   336

   337

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

   338

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

   339

				end_segment_reason |= ESRB_WAYPOINT;

   340

			}

   341

   342

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

   343

			 * it would cause desync in MP. */

   344

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

   345

			{

   346

				int min_speed = 0;

   347

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

   348

				if (max_speed < v->max_speed)

   349

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

   350

				if (min_speed > v->max_speed)

   351

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

   352

			}

   353

   354

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

   355

			 * searching for the nearest depot). */

   356

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

   357

				end_segment_reason |= ESRB_PATH_TOO_LONG;

   358

			}

   359

   360

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

   361

			tf = &tf_local;

   362

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

   363

   364

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

   365

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

   366

				end_segment_reason |= ESRB_DEAD_END;

   367

				break;

   368

			}

   369

   370

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

   371

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

   372

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

   373

				end_segment_reason |= ESRB_CHOICE_FOLLOWS;

   374

				break;

   375

			}

   376

   377

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

   378

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

   379

   380

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

   381

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

   382

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

   383

				end_segment_reason |= ESRB_RAIL_TYPE;

   384

				break;

   385

			}

   386

   387

			/* Avoid infinite looping. */

   388

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

   389

				end_segment_reason |= ESRB_INFINITE_LOOP;

   390

				break;

   391

			}

   392

   393

			if (segment_cost > s_max_segment_cost) {

   394

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

   395

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

   396

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

   397

					end_segment_reason |= ESRB_SEGMENT_TOO_LONG;

   398

					break;

   399

				}

   400

			}

   401

   402

			/* Any other reason bit set? */

   403

			if (end_segment_reason != ESRB_NONE) {

   404

				break;

   405

			}

   406

   407

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

   408

			prev = cur;

   409

			cur = next;

   410

   411

		} // for (;;)

   412

   413

		bool target_seen = false;

   414

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

   415

			/* Depot, station or waypoint. */

   416

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

   417

				/* Destination found. */

   418

				target_seen = true;

   419

			}

   420

		}

   421

   422

		/* Update the segment if needed. */

   423

		if (!is_cached_segment) {

   424

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

   425

			segment.m_cost = segment_cost;

   426

			segment.m_end_segment_reason = end_segment_reason & ESRB_CACHED_MASK;

   427

			assert(segment.m_end_segment_reason != ESRB_NONE);

   428

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

   429

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

   430

		}

   431

   432

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

   433

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

   434

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

   435

			return false;

   436

		}

   437

   438

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

   439

		if (target_seen) {

   440

			n.flags_u.flags_s.m_targed_seen = true;

   441

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

   442

			if (n.flags_u.flags_s.m_last_signal_was_red) {

   443

				if (n.m_last_red_signal_type == SIGTYPE_EXIT) {

   444

					// last signal was red pre-signal-exit

   445

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

   446

				} else {

   447

					// last signal was red, but not exit

   448

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

   449

				}

   450

			}

   451

   452

			/* Station platform-length penalty. */

   453

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

   454

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

   455

				assert(st != NULL);

   456

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

   457

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

   458

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

   459

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

   460

				extra_cost += PlatformLengthPenalty(platform_length);

   461

			}

   462

		}

   463

   464

		// total node cost

   465

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

   466

   467

		return true;

   468

	}

   469

   470

	FORCEINLINE bool CanUseGlobalCache(Node& n) const

   471

	{

   472

		return (n.m_parent != NULL)

   473

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

   474

	}

   475

   476

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

   477

	{

   478

		n.m_segment = &ci;

   479

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

   480

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

   481

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

   482

		}

   483

	}

   484

   485

};

   486

   487

   488

   489

#endif /* YAPF_COSTRAIL_HPP */