1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "debug.h"

     6

#include "functions.h"

     7

#include "npf.h"

     8

#include "aystar.h"

     9

#include "macros.h"

    10

#include "pathfind.h"

    11

#include "station.h"

    12

#include "tile.h"

    13

#include "depot.h"

    14

    15

static AyStar _npf_aystar;

    16

    17

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

    18

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

    19

 */

    20

#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)

    21

static const uint _trackdir_length[TRACKDIR_END] = {

    22

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

    23

	0, 0,

    24

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH

    25

};

    26

    27

/**

    28

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

    29

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

    30

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

    31

 * prevent rounding.

    32

 */

    33

static uint NPFDistanceTrack(TileIndex t0, TileIndex t1)

    34

{

    35

	const uint dx = abs(TileX(t0) - TileX(t1));

    36

	const uint dy = abs(TileY(t0) - TileY(t1));

    37

    38

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

    39

	/* OPTIMISATION:

    40

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

    41

	 * Proof:

    42

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

    43

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

    44

    45

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

    46

	 * precision */

    47

	return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH;

    48

}

    49

    50

/**

    51

 * Check if a rail track is the end of the line. Will also consider 1-way signals to be the end of a line.

    52

 * @param tile The tile on which the current track is.

    53

 * @param trackdir The (track)direction in which you want to look.

    54

 * @param enginetype The type of the engine for which we are checking this.

    55

 */

    56

static bool IsEndOfLine(TileIndex tile, Trackdir trackdir, RailType enginetype)

    57

{

    58

	byte exitdir = TrackdirToExitdir(trackdir);

    59

	TileIndex dst_tile;

    60

	uint32 ts;

    61

    62

	/* Can always go into a tunnel */

    63

	if (IsTileType(tile, MP_TUNNELBRIDGE) && GB(_m[tile].m5, 4, 4) == 0 &&

    64

			GB(_m[tile].m5, 0, 2) == exitdir) {

    65

		return false;

    66

	}

    67

    68

	/* Cannot go through the back of a depot */

    69

	if (IsTileDepotType(tile, TRANSPORT_RAIL) && (exitdir != GetDepotDirection(tile, TRANSPORT_RAIL)))

    70

		return true;

    71

    72

	/* Calculate next tile */

    73

	dst_tile = tile + TileOffsByDir(exitdir);

    74

	// determine the track status on the next tile.

    75

	ts = GetTileTrackStatus(dst_tile, TRANSPORT_RAIL) & TrackdirReachesTrackdirs(trackdir);

    76

    77

	// when none of the trackdir bits are set, we cant enter the new tile

    78

	if ( (ts & TRACKDIR_BIT_MASK) == 0)

    79

		return true;

    80

    81

	{

    82

		byte dst_type = GetTileRailType(dst_tile, exitdir);

    83

		if (!IsCompatibleRail(enginetype, dst_type))

    84

			return true;

    85

		if (GetTileOwner(tile) != GetTileOwner(dst_tile))

    86

			return true;

    87

    88

		/* Prevent us from entering a depot from behind */

    89

		if (IsTileDepotType(dst_tile, TRANSPORT_RAIL) && (exitdir != ReverseDiagdir(GetDepotDirection(dst_tile, TRANSPORT_RAIL))))

    90

			return true;

    91

    92

		/* Prevent us from falling off a slope into a tunnel exit */

    93

		if (IsTileType(dst_tile, MP_TUNNELBRIDGE) &&

    94

				GB(_m[dst_tile].m5, 4, 4) == 0 &&

    95

				(DiagDirection)GB(_m[dst_tile].m5, 0, 2) == ReverseDiagdir(exitdir)) {

    96

			return true;

    97

		}

    98

    99

		/* Check for oneway signal against us */

   100

		if (IsTileType(dst_tile, MP_RAILWAY) && GetRailTileType(dst_tile) == RAIL_TYPE_SIGNALS) {

   101

			if (HasSignalOnTrackdir(dst_tile, ReverseTrackdir(FindFirstBit2x64(ts))) && !HasSignalOnTrackdir(dst_tile, FindFirstBit2x64(ts)))

   102

				// if one way signal not pointing towards us, stop going in this direction.

   103

				return true;

   104

		}

   105

   106

		return false;

   107

	}

   108

}

   109

   110

#if 0

   111

static uint NTPHash(uint key1, uint key2)

   112

{

   113

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

   114

	return PATHFIND_HASH_TILE(key1);

   115

}

   116

#endif

   117

   118

/**

   119

 * Calculates a hash value for use in the NPF.

   120

 * @param key1	The TileIndex of the tile to hash

   121

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

   122

 *

   123

 * @todo	Think of a better hash.

   124

 */

   125

static uint NPFHash(uint key1, uint key2)

   126

{

   127

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

   128

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

   129

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

   130

   131

	assert(IsValidTrackdir(key2));

   132

	assert(IsValidTile(key1));

   133

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

   134

}

   135

   136

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

   137

{

   138

	return 0;

   139

}

   140

   141

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

   142

 * for this we assume the station is a rectangle,

   143

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

   144

 */

   145

static TileIndex CalcClosestStationTile(StationID station, TileIndex tile)

   146

{

   147

	const Station* st = GetStation(station);

   148

   149

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

   150

	uint miny = TileY(st->train_tile);

   151

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

   152

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

   153

	uint x;

   154

	uint y;

   155

   156

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

   157

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

   158

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

   159

   160

	// same for y coordinate, see above comment

   161

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

   162

   163

	// return the tile of our target coordinates

   164

	return TileXY(x, y);

   165

}

   166

   167

/* On PBS pathfinding runs, this is called before pathfinding ends (BeforeExit aystar callback), and will

   168

 * reserve the appropriate tracks, if needed. */

   169

static void NPFReservePBSPath(AyStar *as)

   170

{

   171

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

   172

	bool eol_end = false;

   173

   174

	if (ftd->best_trackdir == 0xFF)

   175

		return;

   176

   177

	if (!NPFGetFlag(&ftd->node, NPF_FLAG_PBS_EXIT) && IsEndOfLine(ftd->node.tile, ftd->node.direction, as->user_data[NPF_RAILTYPE]) && !NPFGetFlag(&ftd->node, NPF_FLAG_SEEN_SIGNAL)) {

   178

		/* The path ends in an end of line, we'll need to reserve a path.

   179

		 * We treat and end of line as a red exit signal */

   180

		eol_end = true;

   181

		NPFSetFlag(&ftd->node, NPF_FLAG_PBS_EXIT, true);

   182

		if (!NPFGetFlag(&ftd->node, NPF_FLAG_PBS_TARGET_SEEN))

   183

			NPFSetFlag(&ftd->node, NPF_FLAG_PBS_RED, true);

   184

	}

   185

   186

	if (!NPFGetFlag(&ftd->node, NPF_FLAG_PBS_CHOICE)) {

   187

		/* there have been no choices to make on our path, we dont care if our end signal is red */

   188

		NPFSetFlag(&ftd->node, NPF_FLAG_PBS_RED, false);

   189

	}

   190

   191

	if (NPFGetFlag(&ftd->node, NPF_FLAG_PBS_EXIT) && // we passed an exit signal

   192

		 !NPFGetFlag(&ftd->node, NPF_FLAG_PBS_BLOCKED) && // we didnt encounter reserver tracks

   193

		 ((as->user_data[NPF_PBS_MODE] != PBS_MODE_GREEN) || (!NPFGetFlag(&ftd->node, NPF_FLAG_PBS_RED))) ) { // our mode permits having a red exit signal, or the signal is green

   194

		PathNode parent;

   195

		PathNode *curr;

   196

		PathNode *prev;

   197

		TileIndex start = INVALID_TILE;

   198

		byte trackdir = 0;

   199

   200

		parent.node = ftd->node;

   201

		parent.parent = &ftd->path;

   202

		curr = &parent;

   203

		prev = NULL;

   204

   205

		do {

   206

			if (!NPFGetFlag(&curr->node, NPF_FLAG_PBS_EXIT) || eol_end) {

   207

				/* check for already reserved track on this path, if they clash with what we

   208

				   currently trying to reserve, we have a self-crossing path :-( */

   209

				if ((PBSTileUnavail(curr->node.tile) & (1 << curr->node.direction))

   210

				&& !(PBSTileReserved(curr->node.tile) & (1 << (curr->node.direction & 7)))

   211

				&& (start != INVALID_TILE)) {

   212

					/* It's actually quite bad if this happens, it means the pathfinder

   213

					 * found a path that is intersecting with itself, which is a very bad

   214

					 * thing in a pbs block. Also there is not much we can do about it at

   215

					 * this point....

   216

					 * BUT, you have to have a pretty fucked up junction layout for this to happen,

   217

					 * so we'll just stop this train, the user will eventually notice, so he can fix it.

   218

					 */

   219

					PBSClearPath(start, trackdir, curr->node.tile, curr->node.direction);

   220

					NPFSetFlag(&ftd->node, NPF_FLAG_PBS_BLOCKED, true);

   221

					DEBUG(pbs, 1) ("PBS: Self-crossing path!!!");

   222

					return;

   223

				};

   224

   225

				PBSReserveTrack(curr->node.tile, TrackdirToTrack(curr->node.direction) );

   226

   227

				/* we want to reserve the last tile (with the signal) on the path too

   228

				   also remember this tile, cause its the end of the path (where we exit the block) */

   229

				if (start == INVALID_TILE) {

   230

					if (prev != NULL) {

   231

						PBSReserveTrack(prev->node.tile, TrackdirToTrack(prev->node.direction) );

   232

						start = prev->node.tile;

   233

						trackdir = ReverseTrackdir(prev->node.direction);

   234

					} else {

   235

						start = curr->node.tile;

   236

						trackdir = curr->node.direction;

   237

					}

   238

				}

   239

			}

   240

   241

			prev = curr;

   242

			curr = curr->parent;

   243

		} while (curr != NULL);

   244

		// we remember the tile/track where this path leaves the pbs junction

   245

		ftd->node.tile = start;

   246

		ftd->node.direction = trackdir;

   247

	}

   248

}

   249

   250

   251

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

   252

 * takes into account the direction of approach.

   253

 */

   254

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

   255

{

   256

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

   257

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

   258

	TileIndex from = current->tile;

   259

	TileIndex to = fstd->dest_coords;

   260

	uint dist;

   261

   262

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

   263

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

   264

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

   265

   266

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

   267

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

   268

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

   269

	else

   270

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

   271

		dist = NPFDistanceTrack(from, to);

   272

   273

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

   274

   275

	/* for pbs runs, we ignore tiles inside the pbs block for the tracking

   276

	   of the 'closest' tile */

   277

	if ((as->user_data[NPF_PBS_MODE] != PBS_MODE_NONE)

   278

	&&  (!NPFGetFlag(current , NPF_FLAG_SEEN_SIGNAL))

   279

	&&  (!IsEndOfLine(current->tile, current->direction, as->user_data[NPF_RAILTYPE])))

   280

		return dist;

   281

   282

	if ((dist < ftd->best_bird_dist) ||

   283

		/* for pbs runs, prefer tiles that pass a green exit signal to the pbs blocks */

   284

		((as->user_data[NPF_PBS_MODE] != PBS_MODE_NONE) && !NPFGetFlag(current, NPF_FLAG_PBS_RED) && NPFGetFlag(&ftd->node, NPF_FLAG_PBS_RED))

   285

) {

   286

		ftd->best_bird_dist = dist;

   287

		ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE];

   288

		ftd->path = parent->path;

   289

		ftd->node = *current;

   290

	}

   291

	return dist;

   292

}

   293

   294

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

   295

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

   296

 * choice */

   297

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

   298

{

   299

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

   300

		Trackdir trackdir = (Trackdir)current->direction;

   301

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

   302

		 * direction we chose */

   303

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

   304

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

   305

	} else {

   306

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

   307

		 * decision */

   308

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

   309

	}

   310

   311

}

   312

   313

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

   314

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

   315

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

   316

static uint NPFTunnelCost(AyStarNode* current)

   317

{

   318

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

   319

	TileIndex tile = current->tile;

   320

	if ((DiagDirection)GB(_m[tile].m5, 0, 2) == ReverseDiagdir(exitdir)) {

   321

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

   322

		 * facing the tunnel exit */

   323

		FindLengthOfTunnelResult flotr;

   324

		flotr = FindLengthOfTunnel(tile, ReverseDiagdir(exitdir));

   325

		return flotr.length * NPF_TILE_LENGTH;

   326

		//TODO: Penalty for tunnels?

   327

	} else {

   328

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

   329

		 * straight track */

   330

		return NPF_TILE_LENGTH;

   331

	}

   332

}

   333

   334

static uint NPFSlopeCost(AyStarNode* current)

   335

{

   336

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

   337

	int x,y;

   338

	int8 z1,z2;

   339

   340

	x = TileX(current->tile) * TILE_SIZE;

   341

	y = TileY(current->tile) * TILE_SIZE;

   342

	/* get the height of the center of the current tile */

   343

	z1 = GetSlopeZ(x+TILE_HEIGHT, y+TILE_HEIGHT);

   344

   345

	x = TileX(next) * TILE_SIZE;

   346

	y = TileY(next) * TILE_SIZE;

   347

	/* get the height of the center of the next tile */

   348

	z2 = GetSlopeZ(x+TILE_HEIGHT, y+TILE_HEIGHT);

   349

   350

	if ((z2 - z1) > 1) {

   351

		/* Slope up */

   352

		return _patches.npf_rail_slope_penalty;

   353

	}

   354

	return 0;

   355

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

   356

	 * could just substract that bonus from the penalty, because

   357

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

   358

}

   359

   360

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

   361

static void NPFMarkTile(TileIndex tile)

   362

{

   363

#ifdef NO_DEBUG_MESSAGES

   364

	return;

   365

#else

   366

	if (_debug_npf_level >= 1)

   367

		switch(GetTileType(tile)) {

   368

			case MP_RAILWAY:

   369

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

   370

				 * ;-) */

   371

				if (!IsTileDepotType(tile, TRANSPORT_RAIL)) {

   372

					SB(_m[tile].m2, 0, 4, 0);

   373

					MarkTileDirtyByTile(tile);

   374

				}

   375

				break;

   376

			case MP_STREET:

   377

				if (!IsTileDepotType(tile, TRANSPORT_ROAD)) {

   378

					SB(_m[tile].m2, 4, 3, 0);

   379

					MarkTileDirtyByTile(tile);

   380

				}

   381

				break;

   382

			default:

   383

				break;

   384

		}

   385

#endif

   386

}

   387

   388

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

   389

{

   390

	//TileIndex tile = current->tile;

   391

	int32 cost = 0;

   392

	Trackdir trackdir = (Trackdir)current->direction;

   393

   394

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

   395

   396

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

   397

		cost += _patches.npf_buoy_penalty; /* A small penalty for going over buoys */

   398

   399

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

   400

		cost += _patches.npf_water_curve_penalty;

   401

   402

	/* TODO More penalties? */

   403

   404

	return cost;

   405

}

   406

   407

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

   408

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

   409

{

   410

	TileIndex tile = current->tile;

   411

	int32 cost = 0;

   412

   413

	/* Determine base length */

   414

	switch (GetTileType(tile)) {

   415

		case MP_TUNNELBRIDGE:

   416

			if (GB(_m[tile].m5, 4, 4) == 0) {

   417

				cost = NPFTunnelCost(current);

   418

				break;

   419

			}

   422

		case MP_STREET:

   423

			cost = NPF_TILE_LENGTH;

   424

			/* Increase the cost for level crossings */

   426

				cost += _patches.npf_crossing_penalty;

   427

			break;

   428

		default:

   429

			break;

   430

	}

   431

   432

	/* Determine extra costs */

   433

   434

	/* Check for slope */

   435

	cost += NPFSlopeCost(current);

   436

   437

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

   438

	 * represented by non-diagonal tracks */

   439

	if (!IsDiagonalTrackdir(current->direction))

   440

		cost += _patches.npf_road_curve_penalty;

   441

   442

	NPFMarkTile(tile);

   443

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

   444

	return cost;

   445

}

   446

   447

   448

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

   449

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

   450

{

   451

	TileIndex tile = current->tile;

   452

	Trackdir trackdir = (Trackdir)current->direction;

   453

	int32 cost = 0;

   454

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

   455

	OpenListNode new_node;

   456

   457

	/* Determine base length */

   458

	switch (GetTileType(tile)) {

   459

		case MP_TUNNELBRIDGE:

   460

			if (GB(_m[tile].m5, 4, 4) == 0) {

   461

				cost = NPFTunnelCost(current);

   462

				break;

   463

			}

   464

			/* Fall through if above if is false, it is a bridge

   465

			 * then. We treat that as ordinary rail */

   466

		case MP_RAILWAY:

   467

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

   468

			break;

   469

		case MP_STREET: /* Railway crossing */

   470

			cost = NPF_TILE_LENGTH;

   471

			break;

   472

		case MP_STATION:

   473

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

   474

					* want to give station tiles that are not our destination

   475

					* this penalty. This would discourage trains to drive through

   476

					* busy stations. But, we can just give any station tile a

   477

					* penalty, because every possible route will get this penalty

   478

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

   479

			* will therefore not make a difference. */

   480

			cost = NPF_TILE_LENGTH + _patches.npf_rail_station_penalty;

   481

			break;

   482

		default:

   483

			break;

   484

	}

   485

   486

	/* Determine extra costs */

   487

   488

	/* Check for reserved tracks (PBS) */

   489

	if ((as->user_data[NPF_PBS_MODE] != PBS_MODE_NONE) && !(NPFGetFlag(current, NPF_FLAG_PBS_EXIT)) && !(NPFGetFlag(current, NPF_FLAG_PBS_BLOCKED)) && (PBSTileUnavail(tile) & (1<<trackdir))) {

   490

		NPFSetFlag(current, NPF_FLAG_PBS_BLOCKED, true);

   491

	};

   492

   493

	/* Check for signals */

   494