1

/* $Id$ */

     2

     3

/** @file npf.cpp Implementation of the NPF pathfinder. */

     4

     5

#include "stdafx.h"

     6

#include "openttd.h"

     7

#include "npf.h"

     8

#include "bridge_map.h"

     9

#include "debug.h"

    10

#include "tile_cmd.h"

    11

#include "bridge.h"

    12

#include "landscape.h"

    13

#include "aystar.h"

    14

#include "pathfind.h"

    15

#include "station_base.h"

    16

#include "station_map.h"

    17

#include "depot_base.h"

    18

#include "depot_map.h"

    19

#include "tunnel_map.h"

    20

#include "network/network.h"

    21

#include "water_map.h"

    22

#include "tunnelbridge_map.h"

    23

#include "functions.h"

    24

#include "vehicle_base.h"

    25

#include "settings_type.h"

    26

#include "tunnelbridge.h"

    27

#include "pbs.h"

    28

    29

static AyStar _npf_aystar;

    30

    31

/* The cost of each trackdir. A diagonal piece is the full NPF_TILE_LENGTH,

    32

 * the shorter piece is sqrt(2)/2*NPF_TILE_LENGTH =~ 0.7071

    33

 */

    34

#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)

    35

static const uint _trackdir_length[TRACKDIR_END] = {

    36

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH,

    37

	0, 0,

    38

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH

    39

};

    40

    41

/**

    42

 * Calculates the minimum distance traveled to get from t0 to t1 when only

    43

 * using tracks (ie, only making 45 degree turns). Returns the distance in the

    44

 * NPF scale, ie the number of full tiles multiplied by NPF_TILE_LENGTH to

    45

 * prevent rounding.

    46

 */

    47

static uint NPFDistanceTrack(TileIndex t0, TileIndex t1)

    48

{

    49

	const uint dx = Delta(TileX(t0), TileX(t1));

    50

	const uint dy = Delta(TileY(t0), TileY(t1));

    51

    52

	const uint straightTracks = 2 * min(dx, dy); /* The number of straight (not full length) tracks */

    53

	/* OPTIMISATION:

    54

	 * Original: diagTracks = max(dx, dy) - min(dx,dy);

    55

	 * Proof:

    56

	 * (dx+dy) - straightTracks  == (min + max) - straightTracks = min + max - 2 * min = max - min */

    57

	const uint diagTracks = dx + dy - straightTracks; /* The number of diagonal (full tile length) tracks. */

    58

    59

	/* Don't factor out NPF_TILE_LENGTH below, this will round values and lose

    60

	 * precision */

    61

	return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH;

    62

}

    63

    64

    65

#if 0

    66

static uint NTPHash(uint key1, uint key2)

    67

{

    68

	/* This function uses the old hash, which is fixed on 10 bits (1024 buckets) */

    69

	return PATHFIND_HASH_TILE(key1);

    70

}

    71

#endif

    72

    73

/**

    74

 * Calculates a hash value for use in the NPF.

    75

 * @param key1 The TileIndex of the tile to hash

    76

 * @param key2 The Trackdir of the track on the tile.

    77

 *

    78

 * @todo Think of a better hash.

    79

 */

    80

static uint NPFHash(uint key1, uint key2)

    81

{

    82

	/* TODO: think of a better hash? */

    83

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

    84

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

    85

    86

	assert(IsValidTrackdir((Trackdir)key2));

    87

	assert(IsValidTile(key1));

    88

	return ((part1 << NPF_HASH_HALFBITS | part2) + (NPF_HASH_SIZE * key2 / TRACKDIR_END)) % NPF_HASH_SIZE;

    89

}

    90

    91

static int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent)

    92

{

    93

	return 0;

    94

}

    95

    96

/* Calcs the tile of given station that is closest to a given tile

    97

 * for this we assume the station is a rectangle,

    98

 * as defined by its top tile (st->train_tile) and its width/height (st->trainst_w, st->trainst_h)

    99

 */

   100

static TileIndex CalcClosestStationTile(StationID station, TileIndex tile)

   101

{

   102

	const Station* st = GetStation(station);

   103

   104

	uint minx = TileX(st->train_tile);  // topmost corner of station

   105

	uint miny = TileY(st->train_tile);

   106

	uint maxx = minx + st->trainst_w - 1; // lowermost corner of station

   107

	uint maxy = miny + st->trainst_h - 1;

   108

	uint x;

   109

	uint y;

   110

   111

	/* we are going the aim for the x coordinate of the closest corner

   112

	 * but if we are between those coordinates, we will aim for our own x coordinate */

   113

	x = Clamp(TileX(tile), minx, maxx);

   114

   115

	/* same for y coordinate, see above comment */

   116

	y = Clamp(TileY(tile), miny, maxy);

   117

   118

	/* return the tile of our target coordinates */

   119

	return TileXY(x, y);

   120

}

   121

   122

/* Calcs the heuristic to the target station or tile. For train stations, it

   123

 * takes into account the direction of approach.

   124

 */

   125

static int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent)

   126

{

   127

	NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target;

   128

	NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path;

   129

	TileIndex from = current->tile;

   130

	TileIndex to = fstd->dest_coords;

   131

	uint dist;

   132

   133

	/* for train-stations, we are going to aim for the closest station tile */

   134

	if (as->user_data[NPF_TYPE] == TRANSPORT_RAIL && fstd->station_index != INVALID_STATION)

   135

		to = CalcClosestStationTile(fstd->station_index, from);

   136

   137

	if (as->user_data[NPF_TYPE] == TRANSPORT_ROAD) {

   138

		/* Since roads only have diagonal pieces, we use manhattan distance here */

   139

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

   140

	} else {

   141

		/* Ships and trains can also go diagonal, so the minimum distance is shorter */

   142

		dist = NPFDistanceTrack(from, to);

   143

	}

   144

   145

	DEBUG(npf, 4, "Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist);

   146

   147

	if (dist < ftd->best_bird_dist) {

   148

		ftd->best_bird_dist = dist;

   149

		ftd->best_trackdir = (Trackdir)current->user_data[NPF_TRACKDIR_CHOICE];

   150

	}

   151

	return dist;

   152

}

   153

   154

   155

/* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to

   156

 * get here, either getting it from the current choice or from the parent's

   157

 * choice */

   158

static void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent)

   159

{

   160

	if (parent->path.parent == NULL) {

   161

		Trackdir trackdir = (Trackdir)current->direction;

   162

		/* This is a first order decision, so we'd better save the

   163

		 * direction we chose */

   164

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

   165

		DEBUG(npf, 6, "Saving trackdir: 0x%X", trackdir);

   166

	} else {

   167

		/* We've already made the decision, so just save our parent's decision */

   168

		current->user_data[NPF_TRACKDIR_CHOICE] = parent->path.node.user_data[NPF_TRACKDIR_CHOICE];

   169

	}

   170

}

   171

   172

/* Will return the cost of the tunnel. If it is an entry, it will return the

   173

 * cost of that tile. If the tile is an exit, it will return the tunnel length

   174

 * including the exit tile. Requires that this is a Tunnel tile */

   175

static uint NPFTunnelCost(AyStarNode* current)

   176

{

   177

	DiagDirection exitdir = TrackdirToExitdir((Trackdir)current->direction);

   178

	TileIndex tile = current->tile;

   179

	if (GetTunnelBridgeDirection(tile) == ReverseDiagDir(exitdir)) {

   180

		/* We just popped out if this tunnel, since were

   181

		 * facing the tunnel exit */

   182

		return NPF_TILE_LENGTH * (GetTunnelBridgeLength(current->tile, GetOtherTunnelEnd(current->tile)) + 1);

   183

		/* @todo: Penalty for tunnels? */

   184

	} else {

   185

		/* We are entering the tunnel, the enter tile is just a

   186

		 * straight track */

   187

		return NPF_TILE_LENGTH;

   188

	}

   189

}

   190

   191

static inline uint NPFBridgeCost(AyStarNode *current)

   192

{

   193

	return NPF_TILE_LENGTH * GetTunnelBridgeLength(current->tile, GetOtherBridgeEnd(current->tile));

   194

}

   195

   196

static uint NPFSlopeCost(AyStarNode* current)

   197

{

   198

	TileIndex next = current->tile + TileOffsByDiagDir(TrackdirToExitdir((Trackdir)current->direction));

   199

   200

	/* Get center of tiles */

   201

	int x1 = TileX(current->tile) * TILE_SIZE + TILE_SIZE / 2;

   202

	int y1 = TileY(current->tile) * TILE_SIZE + TILE_SIZE / 2;

   203

	int x2 = TileX(next) * TILE_SIZE + TILE_SIZE / 2;

   204

	int y2 = TileY(next) * TILE_SIZE + TILE_SIZE / 2;

   205

   206

	int dx4 = (x2 - x1) / 4;

   207

	int dy4 = (y2 - y1) / 4;

   208

   209

	/* Get the height on both sides of the tile edge.

   210

	 * Avoid testing the height on the tile-center. This will fail for halftile-foundations.

   211

	 */

   212

	int z1 = GetSlopeZ(x1 + dx4, y1 + dy4);

   213

	int z2 = GetSlopeZ(x2 - dx4, y2 - dy4);

   214

   215

	if (z2 - z1 > 1) {

   216

		/* Slope up */

   217

		return _settings_game.pf.npf.npf_rail_slope_penalty;

   218

	}

   219

	return 0;

   220

	/* Should we give a bonus for slope down? Probably not, we

   221

	 * could just substract that bonus from the penalty, because

   222

	 * there is only one level of steepness... */

   223

}

   224

   225

static uint NPFReservedTrackCost(AyStarNode *current)

   226

{

   227

	TileIndex tile = current->tile;

   228

	TrackBits track = TrackToTrackBits(TrackdirToTrack((Trackdir)current->direction));

   229

	TrackBits res = GetReservedTrackbits(tile);

   230

   231

	if (NPFGetFlag(current, NPF_FLAG_3RD_SIGNAL) || ((res & track) == TRACK_BIT_NONE && !TracksOverlap(res | track))) return 0;

   232

   233

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   234

		DiagDirection exitdir = TrackdirToExitdir((Trackdir)current->direction);

   235

		if (GetTunnelBridgeDirection(tile) == ReverseDiagDir(exitdir)) {

   236

			return  _settings_game.pf.npf.npf_rail_pbs_cross_penalty * (GetTunnelBridgeLength(tile, GetOtherTunnelBridgeEnd(tile)) + 1);

   237

		}

   238

	}

   239

	return  _settings_game.pf.npf.npf_rail_pbs_cross_penalty;

   240

}

   241

   242

/**

   243

 * Mark tiles by mowing the grass when npf debug level >= 1.

   244

 * Will not work for multiplayer games, since it can (will) cause desyncs.

   245

 */

   246

static void NPFMarkTile(TileIndex tile)

   247

{

   248

#ifndef NO_DEBUG_MESSAGES

   249

	if (_debug_npf_level < 1 || _networking) return;

   250

	switch (GetTileType(tile)) {

   251

		case MP_RAILWAY:

   252

			/* DEBUG: mark visited tiles by mowing the grass under them ;-) */

   253

			if (!IsRailDepot(tile)) {

   254

				SetRailGroundType(tile, RAIL_GROUND_BARREN);

   255

				MarkTileDirtyByTile(tile);

   256

			}

   257

			break;

   258

   259

		case MP_ROAD:

   260

			if (!IsRoadDepot(tile)) {

   261

				SetRoadside(tile, ROADSIDE_BARREN);

   262

				MarkTileDirtyByTile(tile);

   263

			}

   264

			break;

   265

   266

		default:

   267

			break;

   268

	}

   269

#endif

   270

}

   271

   272

static int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent)

   273

{

   274

	/* TileIndex tile = current->tile; */

   275

	int32 cost = 0;

   276

	Trackdir trackdir = (Trackdir)current->direction;

   277

   278

	cost = _trackdir_length[trackdir]; // Should be different for diagonal tracks

   279

   280

	if (IsBuoyTile(current->tile) && IsDiagonalTrackdir(trackdir))

   281

		cost += _settings_game.pf.npf.npf_buoy_penalty; // A small penalty for going over buoys

   282

   283

	if (current->direction != NextTrackdir((Trackdir)parent->path.node.direction))

   284

		cost += _settings_game.pf.npf.npf_water_curve_penalty;

   285

   286

	/* @todo More penalties? */

   287

   288

	return cost;

   289

}

   290

   291

/* Determine the cost of this node, for road tracks */

   292

static int32 NPFRoadPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent)

   293

{

   294

	TileIndex tile = current->tile;

   295

	int32 cost = 0;

   296

   297

	/* Determine base length */

   298

	switch (GetTileType(tile)) {

   299

		case MP_TUNNELBRIDGE:

   300

			cost = IsTunnel(tile) ? NPFTunnelCost(current) : NPFBridgeCost(current);

   301

			break;

   302

   303

		case MP_ROAD:

   304

			cost = NPF_TILE_LENGTH;

   305

			/* Increase the cost for level crossings */

   306

			if (IsLevelCrossing(tile)) cost += _settings_game.pf.npf.npf_crossing_penalty;

   307

			break;

   308

   309

		case MP_STATION:

   310

			cost = NPF_TILE_LENGTH;

   311

			/* Increase the cost for drive-through road stops */

   312

			if (IsDriveThroughStopTile(tile)) cost += _settings_game.pf.npf.npf_road_drive_through_penalty;

   313

			break;

   314

   315

		default:

   316

			break;

   317

	}

   318

   319

	/* Determine extra costs */

   320

   321

	/* Check for slope */

   322

	cost += NPFSlopeCost(current);

   323

   324

	/* Check for turns. Road vehicles only really drive diagonal, turns are

   325

	 * represented by non-diagonal tracks */

   326

	if (!IsDiagonalTrackdir((Trackdir)current->direction))

   327

		cost += _settings_game.pf.npf.npf_road_curve_penalty;

   328

   329

	NPFMarkTile(tile);

   330

	DEBUG(npf, 4, "Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost);

   331

	return cost;

   332

}

   333

   334

   335

/* Determine the cost of this node, for railway tracks */

   336

static int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent)

   337

{

   338

	TileIndex tile = current->tile;

   339

	Trackdir trackdir = (Trackdir)current->direction;

   340

	int32 cost = 0;

   341

	/* HACK: We create a OpenListNode manually, so we can call EndNodeCheck */

   342

	OpenListNode new_node;

   343

   344

	/* Determine base length */

   345

	switch (GetTileType(tile)) {

   346

		case MP_TUNNELBRIDGE:

   347

			cost = IsTunnel(tile) ? NPFTunnelCost(current) : NPFBridgeCost(current);

   348

			break;

   349

   350

		case MP_RAILWAY:

   351

			cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */

   352

			break;

   353

   354

		case MP_ROAD: /* Railway crossing */

   355

			cost = NPF_TILE_LENGTH;

   356

			break;

   357

   358

		case MP_STATION:

   359

			/* We give a station tile a penalty. Logically we would only want to give

   360

			 * station tiles that are not our destination this penalty. This would

   361

			 * discourage trains to drive through busy stations. But, we can just

   362

			 * give any station tile a penalty, because every possible route will get

   363

			 * this penalty exactly once, on its end tile (if it's a station) and it

   364

			 * will therefore not make a difference. */

   365

			cost = NPF_TILE_LENGTH + _settings_game.pf.npf.npf_rail_station_penalty;

   366

			break;

   367

   368

		default:

   369

			break;

   370

	}

   371

   372

	/* Determine extra costs */

   373

   374

	/* Check for signals */

   375

	if (IsTileType(tile, MP_RAILWAY)) {

   376

		if (HasSignalOnTrackdir(tile, trackdir)) {

   377

			/* Ordinary track with signals */

   378

			if (GetSignalStateByTrackdir(tile, trackdir) == SIGNAL_STATE_RED) {

   379

				/* Signal facing us is red */

   380

				if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   381

					/* Penalize the first signal we

   382

					 * encounter, if it is red */

   383

   384

					/* Is this a presignal exit or combo? */

   385

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

   386

					if (!IsPbsSignal(sigtype)) {

   387

						if (sigtype == SIGTYPE_EXIT || sigtype == SIGTYPE_COMBO) {

   388

							/* Penalise exit and combo signals differently (heavier) */

   389

							cost += _settings_game.pf.npf.npf_rail_firstred_exit_penalty;

   390

						} else {

   391

							cost += _settings_game.pf.npf.npf_rail_firstred_penalty;

   392

						}

   393

					}

   394

				}

   395

				/* Record the state of this signal */

   396

				NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true);

   397

			} else {

   398

				/* Record the state of this signal */

   399

				NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false);

   400

			}

   401

			if (NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   402

				if (NPFGetFlag(current, NPF_FLAG_2ND_SIGNAL)) {

   403

					NPFSetFlag(current, NPF_FLAG_3RD_SIGNAL, true);

   404

				} else {

   405

					NPFSetFlag(current, NPF_FLAG_2ND_SIGNAL, true);

   406

				}

   407

			} else {

   408

				NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);

   409

			}

   410

		}

   411

   412

		if (HasPbsSignalOnTrackdir(tile, ReverseTrackdir(trackdir)) && !NPFGetFlag(current, NPF_FLAG_3RD_SIGNAL)) {

   413

			cost += _settings_game.pf.npf.npf_rail_pbs_signal_back_penalty;

   414

		}

   415

	}

   416

   417

	/* Penalise the tile if it is a target tile and the last signal was

   418

	 * red */

   419

	/* HACK: We create a new_node here so we can call EndNodeCheck. Ugly as hell

   420

	 * of course... */

   421

	new_node.path.node = *current;

   422

	if (as->EndNodeCheck(as, &new_node) == AYSTAR_FOUND_END_NODE && NPFGetFlag(current, NPF_FLAG_LAST_SIGNAL_RED))

   423

		cost += _settings_game.pf.npf.npf_rail_lastred_penalty;

   424

   425

	/* Check for slope */

   426

	cost += NPFSlopeCost(current);

   427

   428

	/* Check for turns */

   429

	if (current->direction != NextTrackdir((Trackdir)parent->path.node.direction))

   430

		cost += _settings_game.pf.npf.npf_rail_curve_penalty;

   431

	/*TODO, with realistic acceleration, also the amount of straight track between

   432

	 *      curves should be taken into account, as this affects the speed limit. */

   433

   434

	/* Check for reverse in depot */

   435

	if (IsRailDepotTile(tile) && as->EndNodeCheck(as, &new_node) != AYSTAR_FOUND_END_NODE) {

   436

		/* Penalise any depot tile that is not the last tile in the path. This

   437

		 * _should_ penalise every occurence of reversing in a depot (and only

   438

		 * that) */

   439

		cost += _settings_game.pf.npf.npf_rail_depot_reverse_penalty;

   440

	}

   441

   442

	/* Check for occupied track */

   443

	cost += NPFReservedTrackCost(current);

   444

   445

	NPFMarkTile(tile);

   446

	DEBUG(npf, 4, "Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost);

   447

	return cost;

   448

}

   449

   450

/* Will find any depot */

   451

static int32 NPFFindDepot(AyStar* as, OpenListNode *current)

   452

{

   453

	/* It's not worth caching the result with NPF_FLAG_IS_TARGET here as below,

   454

	 * since checking the cache not that much faster than the actual check */

   455

	return IsDepotTypeTile(current->path.node.tile, (TransportType)as->user_data[NPF_TYPE]) ?

   456

		AYSTAR_FOUND_END_NODE : AYSTAR_DONE;

   457

}

   458

   459

/** Find any safe and free tile. */

   460

static int32 NPFFindSafeTile(AyStar *as, OpenListNode *current)

   461

{

   462

	const Vehicle *v = ((NPFFindStationOrTileData*)as->user_target)->v;

   463

   464

	return

   465

		IsSafeWaitingPosition(v, current->path.node.tile, (Trackdir)current->path.node.direction, true, _settings_game.pf.forbid_90_deg) &&

   466

		IsWaitingPositionFree(v, current->path.node.tile, (Trackdir)current->path.node.direction, _settings_game.pf.forbid_90_deg) ?

   467

			AYSTAR_FOUND_END_NODE : AYSTAR_DONE;

   468

}

   469

   470

/* Will find a station identified using the NPFFindStationOrTileData */

   471

static int32 NPFFindStationOrTile(AyStar* as, OpenListNode *current)

   472

{

   473

	NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target;

   474

	AyStarNode *node = &current->path.node;

   475

	TileIndex tile = node->tile;

   476

   477

	/* If GetNeighbours said we could get here, we assume the station type

   478

	 * is correct */

   479

	if (

   480

		(fstd->station_index == INVALID_STATION && tile == fstd->dest_coords) || /* We've found the tile, or */

   481

		(IsTileType(tile, MP_STATION) && GetStationIndex(tile) == fstd->station_index) /* the station */

   482

	) {

   483

		return AYSTAR_FOUND_END_NODE;

   484

	} else {

   485

		return AYSTAR_DONE;

   486

	}

   487

}

   488

   489