1

/* $Id$ */

     2

     3

#ifndef  YAPF_COSTRAIL_HPP

     4

#define  YAPF_COSTRAIL_HPP

     5

     6

     7

template <class Types>

     8

class CYapfCostRailT

     9

	: public CYapfCostBase

    10

	, public CostRailSettings

    11

{

    12

public:

    13

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

    14

	typedef typename Types::TrackFollower TrackFollower;

    15

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

    16

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

    17

	typedef typename Node::CachedData CachedData;

    18

    19

protected:

    20

	int           m_max_cost;

    21

	CBlobT<int>   m_sig_look_ahead_costs;

    22

public:

    23

	bool          m_stopped_on_first_two_way_signal;

    24

protected:

    25

    26

	static const int s_max_segment_cost = 10000;

    27

    28

	CYapfCostRailT()

    29

		: m_max_cost(0)

    30

		, m_stopped_on_first_two_way_signal(false)

    31

	{

    32

		// pre-compute look-ahead penalties into array

    33

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

    34

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

    35

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

    36

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

    37

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

    38

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

    39

	}

    40

    41

	/// to access inherited path finder

    42

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

    43

    44

public:

    45

	FORCEINLINE int SlopeCost(TileIndex tile, Trackdir td)

    46

	{

    47

		CPerfStart perf_cost(Yapf().m_perf_slope_cost);

    48

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

    49

		return Yapf().PfGetSettings().rail_slope_penalty;

    50

	}

    51

    52

	FORCEINLINE int CurveCost(Trackdir td1, Trackdir td2)

    53

	{

    54

		int cost = 0;

    55

		if (TrackFollower::Allow90degTurns()

    56

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

    57

			// 90-deg curve penalty

    58

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

    59

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

    60

			// 45-deg curve penalty

    61

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

    62

		}

    63

		return cost;

    64

	}

    65

    66

	/** return one tile cost. If tile is a tunnel entry, it is moved to the end of tunnel */

    67

	FORCEINLINE int OneTileCost(TileIndex& tile, Trackdir trackdir)

    68

	{

    69

		int cost = 0;

    70

		// set base cost

    71

		if (IsDiagonalTrackdir(trackdir)) {

    72

			cost += YAPF_TILE_LENGTH;

    73

			switch (GetTileType(tile)) {

    74

				case MP_STREET:

    75

					/* Increase the cost for level crossings */

    76

					if (IsLevelCrossing(tile))

    77

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

    78

					break;

    79

    80

				case MP_STATION:

    81

					// penalty for passing station tiles

    82

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

    83

					break;

    84

    85

				default:

    86

					break;

    87

			}

    88

		} else {

    89

			// non-diagonal trackdir

    90

			cost = YAPF_TILE_CORNER_LENGTH;

    91

		}

    92

		return cost;

    93

	}

    94

    95

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

    96

	{

    97

		int cost = 0;

    98

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

    99

		CPerfStart perf_cost(Yapf().m_perf_other_cost);

   100

		if (IsTileType(tile, MP_RAILWAY)) {

   101

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

   102

			bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);

   103

			if (has_signal_against && !has_signal_along) {

   104

				// one-way signal in opposite direction

   105

				n.m_segment->flags_u.flags_s.m_end_of_line = true;

   106

			} else if (has_signal_along) {

   107

				SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);

   108

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

   109

				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;

   110

				if (sig_state != SIGNAL_STATE_RED) {

   111

					// green signal

   112

					n.flags_u.flags_s.m_last_signal_was_red = false;

   113

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

   114

					if (look_ahead_cost < 0) {

   115

						// add its negation to the cost

   116

						cost -= look_ahead_cost;

   117

					}

   118

				} else {

   119

					// we have a red signal in our direction

   120

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

   121

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

   122

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

   123

						n.m_segment->flags_u.flags_s.m_end_of_line = true;

   124

						Yapf().m_stopped_on_first_two_way_signal = true;

   125

						return -1;

   126

					}

   127

					SignalType sig_type = GetSignalType(tile);

   128

					n.m_last_red_signal_type = sig_type;

   129

					n.flags_u.flags_s.m_last_signal_was_red = true;

   130

   131

					// look-ahead signal penalty

   132

					if (look_ahead_cost > 0) {

   133

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

   134

						cost += look_ahead_cost;

   135

					}

   136

   137

					// special signal penalties

   138

					if (n.m_num_signals_passed == 0) {

   139

						switch (sig_type) {

   140

							case SIGTYPE_COMBO:

   141

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

   142

							case SIGTYPE_NORMAL:

   143

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

   144

						};

   145

					}

   146

				}

   147

				n.m_num_signals_passed++;

   148

				n.m_segment->m_last_signal_tile = tile;

   149

				n.m_segment->m_last_signal_td = trackdir;

   150

			}

   151

		}

   152

		return cost;

   153

	}

   154

   155

	FORCEINLINE int PlatformLengthPenalty(int platform_length)

   156

	{

   157

		int cost = 0;

   158

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

   159

		assert(v != NULL);

   160

		assert(v->type == VEH_Train);

   161

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

   162

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

   163

		if (platform_length > needed_platform_length) {

   164

			// apply penalty for longer platform than needed

   165

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

   166

		} else if (needed_platform_length > platform_length) {

   167

			// apply penalty for shorter platform than needed

   168

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

   169

		}

   170

		return cost;

   171

	}

   172

   173

public:

   174

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

   175

   176

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

   177

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

   178

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

   179

	FORCEINLINE bool PfCalcCost(Node& n)

   180

	{

   181

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

   182

		CPerfStart perf_cost(Yapf().m_perf_cost);

   183

		int parent_cost = (n.m_parent != NULL) ? n.m_parent->m_cost : 0;

   184

		int first_tile_cost = 0;

   185

		int segment_cost = 0;

   186

		int extra_cost = 0;

   187

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

   188

   189

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

   190

		TileIndex prev_tile      = (n.m_parent != NULL) ? n.m_parent->GetLastTile() : INVALID_TILE;

   191

		Trackdir  prev_trackdir  = (n.m_parent != NULL) ? n.m_parent->GetLastTrackdir() : INVALID_TRACKDIR;

   192

		TileType  prev_tile_type = (n.m_parent != NULL) ? GetTileType(n.m_parent->GetLastTile()) : MP_VOID;

   193

   194

		TileIndex tile = n.m_key.m_tile;

   195

		Trackdir trackdir = n.m_key.m_td;

   196

		TileType tile_type = GetTileType(tile);

   197

   198

		DEBUG(yapf, 3, "PfCalcCost(Node:tile=%04X td=%s; Parent:tile=%04X td=%s)", tile, GetTrackdirName(trackdir), prev_tile, GetTrackdirName(prev_trackdir));

   199

   200

		RailType rail_type = GetTileRailType(tile, trackdir);

   201

   202

		// detect exit from bridge wormhole

   203

		Trackdir intermediate_trackdir = INVALID_TRACKDIR;

   204

		if (IsBridgeTile(tile) && TrackdirToExitdir(ReverseTrackdir(trackdir)) == GetBridgeRampDirection(tile)) {

   205

			// we are jumping over bridge (possible now with custom bridge heads) we must add the cost of skipped tiles

   206

			int skipped_tiles = DistanceManhattan(prev_tile, tile) - 1;

   207

			if (skipped_tiles > 0) {

   208

				segment_cost += skipped_tiles * YAPF_TILE_LENGTH;

   209

				DEBUG(yapf, 6, "    Cost: skipped=%d", skipped_tiles * YAPF_TILE_LENGTH);

   210

				intermediate_trackdir = DiagdirToDiagTrackdir(ReverseDiagDir(GetBridgeRampDirection(tile)));

   211

			}

   212

		}

   213

   214

		bool target_seen = Yapf().PfDetectDestination(tile, trackdir);

   215

   216

		while (true) {

   217

			int tile_cost = Yapf().OneTileCost(tile, trackdir);

   218

			int curve_cost;

   219

			if (intermediate_trackdir == INVALID_TRACKDIR) {

   220

				curve_cost = Yapf().CurveCost(prev_trackdir, trackdir);

   221

			} else {

   222

				curve_cost = Yapf().CurveCost(prev_trackdir, intermediate_trackdir) + Yapf().CurveCost(intermediate_trackdir, trackdir);

   223

				intermediate_trackdir = INVALID_TRACKDIR;

   224

			}

   225

			int slope_cost = Yapf().SlopeCost(tile, trackdir);

   226

			int signal_cost = Yapf().SignalCost(n, tile, trackdir);

   227

			DEBUG(yapf, 6, "    Cost: tile=%d, curve=%d, slope=%d, signal=%d", tile_cost, curve_cost, slope_cost, signal_cost);

   228

			segment_cost += tile_cost + curve_cost + slope_cost + signal_cost;

   229

			if (n.m_segment->flags_u.flags_s.m_end_of_line) {

   230

				DEBUG(yapf, 4, "  end: EOL (signal)");

   231

				break;

   232

			}

   233

   234

			// finish if we have reached the destination

   235

			if (target_seen) {

   236

				DEBUG(yapf, 4, "  end: target_seen");

   237

				break;

   238

			}

   239

   240

			// finish on first station tile - segment should end here to avoid target skipping

   241

			// when cached segments are used

   242

			if (tile_type == MP_STATION && prev_tile_type != MP_STATION) {

   243

				DEBUG(yapf, 4, "  end: first station tile");

   244

				break;

   245

			}

   246

   247

			// finish also on waypoint - same workaround as for first station tile

   248

			if (tile_type == MP_RAILWAY && IsRailWaypoint(tile)) {

   249

				DEBUG(yapf, 4, "  end: waypoint");

   250

				break;

   251

			}

   252

   253

			// if there are no reachable trackdirs on the next tile, we have end of road

   254

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

   255

			if (!F.Follow(tile, trackdir)) {

   256

				// we can't continue?

   257

				// n.m_segment->flags_u.flags_s.m_end_of_line = true;

   258

				DEBUG(yapf, 4, "  end: can't foolow (dead end?)");

   259

				break;

   260

			}

   261

			if (F.m_is_bridge && F.m_tiles_skipped > 0) intermediate_trackdir = F.m_intermediate_trackdir;

   262

			DEBUG(yapf, 4, " next: tile=%04X td=%s", F.m_new_tile, GetTrackdirBitsName(F.m_new_td_bits).Data());

   263

   264

			// if there are more trackdirs available & reachable, we are at the end of segment

   265

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

   266

				DEBUG(yapf, 4, "  end: choice");

   267

				break;

   268

			}

   269

   270

			Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits);

   271

   272

			{

   273

				// end segment if train is about to enter simple loop with no junctions

   274

				// so next time it should stop on the next if

   275

				if (segment_cost > s_max_segment_cost && IsTileType(F.m_new_tile, MP_RAILWAY)) {

   276

					DEBUG(yapf, 4, "  end: loop fuse");

   277

					break;

   278

				}

   279

   280

				// stop if train is on simple loop with no junctions

   281

				if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) {

   282

					DEBUG(yapf, 4, "  end: loop detected");

   283

					return false;

   284

				}

   285

			}

   286

   287

			// if rail type changes, finish segment (cached segment can't contain more rail types)

   288

			{

   289

				RailType new_rail_type = GetTileRailType(F.m_new_tile, (Trackdir)FindFirstBit2x64(F.m_new_td_bits));

   290

				if (new_rail_type != rail_type) {

   291

					DEBUG(yapf, 4, "  end: rail type changes");

   292

					break;

   293

				}

   294

				rail_type = new_rail_type;

   295

			}

   296

   297

			// move to the next tile

   298

			prev_tile = tile;

   299

			prev_trackdir = trackdir;

   300

			prev_tile_type = tile_type;

   301

   302

			tile = F.m_new_tile;

   303

			trackdir = new_td;

   304

			tile_type = GetTileType(tile);

   305

   306

			target_seen = Yapf().PfDetectDestination(tile, trackdir);

   307

   308

			// reversing in depot penalty

   309

			if (tile == prev_tile) {

   310

				int reverse_in_depot_cost = Yapf().PfGetSettings().rail_depot_reverse_penalty;

   311

				segment_cost += reverse_in_depot_cost;

   312

				DEBUG(yapf, 4, "  end: reversing in depot (cost=%d)", reverse_in_depot_cost);

   313

				break;

   314

			}

   315

   316

			// if we skipped some tunnel tiles, add their cost

   317

			segment_cost += YAPF_TILE_LENGTH * F.m_tiles_skipped;

   318

			DEBUG(yapf, 6, "    Cost: wormhole=%d", YAPF_TILE_LENGTH * F.m_tiles_skipped);

   319

   320

			// add penalty for skipped station tiles

   321

			if (F.m_is_station)

   322

			{

   323

				if (target_seen) {

   324

					// it is our destination station

   325

					uint platform_length = F.m_tiles_skipped + 1;

   326

					int platform_length_cost = PlatformLengthPenalty(platform_length);

   327

					segment_cost += platform_length_cost;

   328

					DEBUG(yapf, 6, "    Cost: platform=%d", platform_length_cost);

   329

				} else {

   330

					// station is not our destination station, apply penalty for skipped platform tiles

   331

					int station_cost = Yapf().PfGetSettings().rail_station_penalty * F.m_tiles_skipped;

   332

					segment_cost += station_cost;

   333

					DEBUG(yapf, 6, "    Cost: station=%d", station_cost);

   334

				}

   335

			}

   336

   337

			// add min/max speed penalties

   338

			int min_speed = 0;

   339

			int max_speed = F.GetSpeedLimit(&min_speed);

   340

			if (max_speed < v->max_speed)

   341

				segment_cost += YAPF_TILE_LENGTH * (v->max_speed - max_speed) / v->max_speed;

   342

			if (min_speed > v->max_speed)

   343

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

   344

   345

			// finish if we already exceeded the maximum cost

   346

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

   347

				DEBUG(yapf, 4, "  abort: maximum cost reached");

   348

				return false;

   349

			}

   350

   351

			if (first_tile_cost == 0) {

   352

				// we just have done first tile

   353

				first_tile_cost = segment_cost;

   354

				segment_cost = 0;

   355

				DEBUG(yapf, 5, "    TotalCost: first_tile=%d", first_tile_cost);

   356

   357

				// look if we can reuse existing (cached) segment cost

   358

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

   359

					// reuse the cached segment cost

   360

					DEBUG(yapf, 4, "  end: reusing the cached segment cost");

   361

					break;

   362

				}

   363

			}

   364

			// segment cost was not filled yes, we have not cached it yet

   365

			n.SetLastTileTrackdir(tile, trackdir);

   366

   367

		} // while (true)

   368

   369

		if (first_tile_cost == 0) {

   370

			// we have just finished first tile

   371

			first_tile_cost = segment_cost;

   372

			segment_cost = 0;

   373

			DEBUG(yapf, 5, "    TotalCost: first_tile=%d", first_tile_cost);

   374

		}

   375

   376

		// do we have cached segment cost?

   377

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

   378

			// reuse the cached segment cost

   379

			segment_cost = n.m_segment->m_cost;

   380

			DEBUG(yapf, 5, "    TotalCost: cached_segment=%d", segment_cost);

   381

		} else {

   382

			// save segment cost

   383

			n.m_segment->m_cost = segment_cost;

   384

			DEBUG(yapf, 5, "    TotalCost: segment=%d", segment_cost);

   385

   386

			// save end of segment back to the node

   387

			n.SetLastTileTrackdir(tile, trackdir);

   388

		}

   389

   390

		// special costs for the case we have reached our target

   391

		if (target_seen) {

   392

			n.flags_u.flags_s.m_targed_seen = true;

   393

			if (n.flags_u.flags_s.m_last_signal_was_red) {

   394

				if (n.m_last_red_signal_type == SIGTYPE_EXIT) {

   395

					// last signal was red pre-signal-exit

   396

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

   397

				} else {

   398

					// last signal was red, but not exit

   399

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

   400

				}

   401

			}

   402

		}

   403

		DEBUG(yapf, 5, "    TotalCost: extra=%d", extra_cost);

   404

   405

		// total node cost

   406

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

   407

		DEBUG(yapf, 3, "  leaving: last_tile=%04X, last_td=%s, cost=%d", n.m_segment->m_last_tile, GetTrackdirName(n.m_segment->m_last_td), n.m_cost);

   408

		DEBUG(yapf, 3, " returning %s", n.m_segment->flags_u.flags_s.m_end_of_line ? "false" : "true");

   409

		return !n.m_segment->flags_u.flags_s.m_end_of_line;

   410

	}

   411

   412

	FORCEINLINE bool CanUseGlobalCache(Node& n) const

   413

	{

   414

		return (n.m_parent != NULL)

   415

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

   416

	}

   417

   418

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

   419

	{

   420

		n.m_segment = &ci;

   421

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

   422

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

   423

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

   424

		}

   425

	}

   426

   427

};

   428

   429

   430

   431

#endif /* YAPF_COSTRAIL_HPP */