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;

    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

    23

	static const int s_max_segment_cost = 10000;

    24

    25

	CYapfCostRailT() : m_max_cost(0)

    26

	{

    27

		// pre-compute look-ahead penalties into array

    28

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

    29

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

    30

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

    31

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

    32

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

    33

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

    34

	}

    35

    36

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

    37

    38

public:

    39

	FORCEINLINE int SlopeCost(TileIndex tile, Trackdir td)

    40

	{

    41

		CPerfStart perf_cost(Yapf().m_perf_slope_cost);

    42

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

    43

		return Yapf().PfGetSettings().rail_slope_penalty;

    44

	}

    45

    46

	FORCEINLINE int CurveCost(Trackdir td1, Trackdir td2)

    47

	{

    48

		int cost = 0;

    49

		if (TrackFollower::Allow90degTurns()

    50

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

    51

			// 90-deg curve penalty

    52

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

    53

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

    54

			// 45-deg curve penalty

    55

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

    56

		}

    57

		return cost;

    58

	}

    59

    60

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

    61

	FORCEINLINE int OneTileCost(TileIndex& tile, Trackdir trackdir)

    62

	{

    63

		int cost = 0;

    64

		// set base cost

    65

		if (IsDiagonalTrackdir(trackdir)) {

    66

			cost += YAPF_TILE_LENGTH;

    67

			switch (GetTileType(tile)) {

    68

				case MP_STREET:

    69

					/* Increase the cost for level crossings */

    70

					if (IsLevelCrossing(tile))

    71

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

    72

					break;

    73

    74

				case MP_STATION:

    75

					// penalty for passing station tiles

    76

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

    77

					break;

    78

    79

				default:

    80

					break;

    81

			}

    82

		} else {

    83

			// non-diagonal trackdir

    84

			cost = YAPF_TILE_CORNER_LENGTH;

    85

		}

    86

		return cost;

    87

	}

    88

    89

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

    90

	{

    91

		int cost = 0;

    92

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

    93

		CPerfStart perf_cost(Yapf().m_perf_other_cost);

    94

		if (IsTileType(tile, MP_RAILWAY)) {

    95

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

    96

			bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);

    97

			if (has_signal_against && !has_signal_along) {

    98

				// one-way signal in opposite direction

    99

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

   100

			} else if (has_signal_along) {

   101

				SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);

   102

				if (sig_state != SIGNAL_STATE_RED) {

   103

					// green signal

   104

					n.flags_u.flags_s.m_last_signal_was_red = false;

   105

				} else {

   106

					// we have a red signal in our direction

   107

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

   108

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

   109

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

   110

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

   111

						return -1;

   112

					}

   113

					SignalType sig_type = GetSignalType(tile);

   114

					n.m_last_red_signal_type = sig_type;

   115

					n.flags_u.flags_s.m_last_signal_was_red = true;

   116

   117

					// look-ahead signal penalty

   118

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

   119

						cost += m_sig_look_ahead_costs.Data()[n.m_num_signals_passed];

   120

					}

   121

   122

					// special signal penalties

   123

					if (n.m_num_signals_passed == 0) {

   124

						switch (sig_type) {

   125

							case SIGTYPE_COMBO:

   126

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

   127

							case SIGTYPE_NORMAL:

   128

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

   129

						};

   130

					}

   131

				}

   132

				n.m_num_signals_passed++;

   133

				n.m_segment->m_last_signal_tile = tile;

   134

				n.m_segment->m_last_signal_td = trackdir;

   135

			}

   136

		}

   137

		return cost;

   138

	}

   139

   140

public:

   141

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

   142

   143

	FORCEINLINE bool PfCalcCost(Node& n)

   144

	{

   145

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

   146

		CPerfStart perf_cost(Yapf().m_perf_cost);

   147

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

   148

		int first_tile_cost = 0;

   149

		int segment_cost = 0;

   150

		int extra_cost = 0;

   151

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

   152

   153

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

   154

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

   155

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

   156

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

   157

   158

		TileIndex tile = n.m_key.m_tile;

   159

		Trackdir trackdir = n.m_key.m_td;

   160

		TileType tile_type = GetTileType(tile);

   161

   162

		RailType rail_type = GetTileRailType(tile, trackdir);

   163

   164

		bool target_seen = false;

   165

   166

		while (true) {

   167

			segment_cost += Yapf().OneTileCost(tile, trackdir);

   168

			segment_cost += Yapf().CurveCost(prev_trackdir, trackdir);

   169

			segment_cost += Yapf().SlopeCost(tile, trackdir);

   170

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

   171

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

   172

				break;

   173

			}

   174

   175

			// finish if we have reached the destination

   176

			target_seen = Yapf().PfDetectDestination(n);

   177

			if (target_seen) {

   178

				break;

   179

			}

   180

   181

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

   182

			// when cached segments are used

   183

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

   184

				break;

   185

			}

   186

   187

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

   188

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

   189

				break;

   190

			}

   191

   192

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

   193

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

   194

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

   195

				// we can't continue?

   196

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

   197

				break;

   198

			}

   199

   200

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

   201

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

   202

				break;

   203

			}

   204

   205

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

   206

   207

			{

   208

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

   209

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

   210

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

   211

					break;

   212

   213

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

   214

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

   215

					return false;

   216

			}

   217

   218

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

   219

			{

   220

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

   221

				if (new_rail_type != rail_type) {

   222

					break;

   223

				}

   224

				rail_type = new_rail_type;

   225

			}

   226

   227

			// move to the next tile

   228

			prev_tile = tile;

   229

			prev_trackdir = trackdir;

   230

			prev_tile_type = tile_type;

   231

   232

			tile = F.m_new_tile;

   233

			trackdir = new_td;

   234

			tile_type = GetTileType(tile);

   235

   236

			// reversing in depot penalty

   237

			if (tile == prev_tile) {

   238

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

   239

				break;

   240

			}

   241

   242

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

   243

			segment_cost += YAPF_TILE_LENGTH * F.m_tunnel_tiles_skipped;

   244

   245

			// add min/max speed penalties

   246

			int min_speed = 0;

   247

			int max_speed = F.GetSpeedLimit(&min_speed);

   248

			if (max_speed < v->max_speed)

   249

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

   250

			if (min_speed > v->max_speed)

   251

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

   252

   253

			// finish if we already exceeded the maximum cost

   254

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

   255

				return false;

   256

			}

   257

   258

			if (first_tile_cost == 0) {

   259

				// we just have done first tile

   260

				first_tile_cost = segment_cost;

   261

				segment_cost = 0;

   262

   263

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

   264

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

   265

					// reuse the cached segment cost

   266

					break;

   267

				}

   268

			}

   269

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

   270

			n.SetLastTileTrackdir(tile, trackdir);

   271

   272

		} // while (true)

   273

   274

		if (first_tile_cost == 0) {

   275

			// we have just finished first tile

   276

			first_tile_cost = segment_cost;

   277

			segment_cost = 0;

   278

		}

   279

   280

		// do we have cached segment cost?

   281

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

   282

			// reuse the cached segment cost

   283

			segment_cost = n.m_segment->m_cost;

   284

		} else {

   285

			// save segment cost

   286

			n.m_segment->m_cost = segment_cost;

   287

   288

			// save end of segment back to the node

   289

			n.SetLastTileTrackdir(tile, trackdir);

   290

		}

   291

   292

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

   293

		if (target_seen) {

   294

			n.flags_u.flags_s.m_targed_seen = true;

   295

			if (n.flags_u.flags_s.m_last_signal_was_red) {

   296

				if (n.m_last_red_signal_type == SIGTYPE_EXIT) {

   297

					// last signal was red pre-signal-exit

   298

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

   299

				} else {

   300

					// last signal was red, but not exit

   301

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

   302

				}

   303

			}

   304

		}

   305

   306

		// total node cost

   307

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

   308

   309

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

   310

	}

   311

   312

	FORCEINLINE bool CanUseGlobalCache(Node& n) const

   313

	{

   314

		return (n.m_parent != NULL)

   315

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

   316

	}

   317

   318

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

   319

	{

   320

		n.m_segment = &ci;

   321

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

   322

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

   323

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

   324

		}

   325

	}

   326

   327

};

   328

   329

   330

   331

#endif /* YAPF_COSTRAIL_HPP */