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

   199

   200

		// detect exit from bridge wormhole

   201

		Trackdir intermediate_trackdir = INVALID_TRACKDIR;

   202

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

   203

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

   204

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

   205

			if (skipped_tiles > 0) {

   206

				segment_cost += skipped_tiles * YAPF_TILE_LENGTH;

   207

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

   208

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

   209

			}

   210

		}

   211

   212

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

   213

   214

		while (true) {

   215

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

   216

			int curve_cost;

   217

			if (intermediate_trackdir == INVALID_TRACKDIR) {

   218

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

   219

			} else {

   220

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

   221

				intermediate_trackdir = INVALID_TRACKDIR;

   222

			}

   223

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

   224

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

   225

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

   226

			segment_cost += tile_cost + curve_cost + slope_cost + signal_cost;

   227

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

   228

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

   229

				break;

   230

			}

   231

   232

			// finish if we have reached the destination

   233

			if (target_seen) {

   234

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

   235

				break;

   236

			}

   237

   238

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

   239

			// when cached segments are used

   240

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

   241

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

   242

				break;

   243

			}

   244

   245

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

   246

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

   247

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

   248

				break;

   249

			}

   250

   251

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

   252

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

   253

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

   254

				// we can't continue?

   255

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

   256

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

   257

				break;

   258

			}

   259

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

   260

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

   261

   262

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

   263

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

   264

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

   265

				break;

   266

			}

   267

   268

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

   269

   270

			{

   271

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

   272

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

   273

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

   274

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

   275

					break;

   276

				}

   277

   278

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

   279

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

   280

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

   281

					return false;

   282

				}

   283

			}

   284

   285

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

   286

			{

   288

				if (new_rail_type != rail_type) {

   289

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

   290

					break;

   291

				}

   292

				rail_type = new_rail_type;

   293

			}

   294

   295

			// move to the next tile

   296

			prev_tile = tile;

   297

			prev_trackdir = trackdir;

   298

			prev_tile_type = tile_type;

   299

   300

			tile = F.m_new_tile;

   301

			trackdir = new_td;

   302

			tile_type = GetTileType(tile);

   303

   304

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

   305

   306

			// reversing in depot penalty

   307

			if (tile == prev_tile) {

   308

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

   309

				segment_cost += reverse_in_depot_cost;

   310

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

   311

				break;

   312

			}

   313

   314

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

   315

			segment_cost += YAPF_TILE_LENGTH * F.m_tiles_skipped;

   316

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

   317

   318

			// add penalty for skipped station tiles

   319

			if (F.m_is_station)

   320

			{

   321

				if (target_seen) {

   322

					// it is our destination station

   323

					uint platform_length = F.m_tiles_skipped + 1;

   324

					int platform_length_cost = PlatformLengthPenalty(platform_length);

   325

					segment_cost += platform_length_cost;

   326

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

   327

				} else {

   328

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

   329

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

   330

					segment_cost += station_cost;

   331

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

   332

				}

   333

			}

   334

   335

			// add min/max speed penalties

   336

			int min_speed = 0;

   337

			int max_speed = F.GetSpeedLimit(&min_speed);

   338

			if (max_speed < v->max_speed)

   339

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

   340

			if (min_speed > v->max_speed)

   341

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

   342

   343

			// finish if we already exceeded the maximum cost

   344

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

   345

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

   346

				return false;

   347

			}

   348

   349

			if (first_tile_cost == 0) {

   350

				// we just have done first tile

   351

				first_tile_cost = segment_cost;

   352

				segment_cost = 0;

   353

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

   354

   355

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

   356

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

   357

					// reuse the cached segment cost

   358

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

   359

					break;

   360

				}

   361

			}

   362

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

   363

			n.SetLastTileTrackdir(tile, trackdir);

   364

   365

		} // while (true)

   366

   367

		if (first_tile_cost == 0) {

   368

			// we have just finished first tile

   369

			first_tile_cost = segment_cost;

   370

			segment_cost = 0;

   371

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

   372

		}

   373

   374

		// do we have cached segment cost?

   375

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

   376

			// reuse the cached segment cost

   377

			segment_cost = n.m_segment->m_cost;

   378

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

   379

		} else {

   380

			// save segment cost

   381

			n.m_segment->m_cost = segment_cost;

   382

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

   383

   384

			// save end of segment back to the node

   385

			n.SetLastTileTrackdir(tile, trackdir);

   386

		}

   387

   388

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

   389

		if (target_seen) {

   390

			n.flags_u.flags_s.m_targed_seen = true;

   391

			if (n.flags_u.flags_s.m_last_signal_was_red) {

   392

				if (n.m_last_red_signal_type == SIGTYPE_EXIT) {

   393

					// last signal was red pre-signal-exit

   394

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

   395

				} else {

   396

					// last signal was red, but not exit

   397

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

   398

				}

   399

			}

   400

		}

   401

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

   402

   403

		// total node cost

   404

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

   405

		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);

   406

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

   407

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

   408

	}

   409

   410

	FORCEINLINE bool CanUseGlobalCache(Node& n) const

   411

	{

   412

		return (n.m_parent != NULL)

   413

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

   414

	}

   415

   416

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

   417

	{

   418

		n.m_segment = &ci;

   419

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

   420

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

   421

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

   422

		}

   423

	}

   424

   425

};

   426

   427

   428

   429

#endif /* YAPF_COSTRAIL_HPP */