1

#include "stdafx.h"

     2

#include "openttd.h"

     3

#include "debug.h"

     4

#include "npf.h"

     5

#include "aystar.h"

     6

#include "macros.h"

     7

#include "pathfind.h"

     8

#include "station.h"

     9

#include "tile.h"

    10

#include "depot.h"

    11

    12

static AyStar _npf_aystar;

    13

    14

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

    15

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

    16

 */

    17

#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)

    18

static const uint _trackdir_length[TRACKDIR_END] = {

    19

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

    20

	0, 0,

    21

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH

    22

};

    23

    24

/**

    25

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

    26

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

    27

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

    28

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

    29

 */

    30

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

    31

{

    32

	byte exitdir = TrackdirToExitdir(trackdir);

    33

	TileIndex dst_tile;

    34

	uint32 ts;

    35

    36

	// tunnel entrance?

    37

	if (IsTileType(tile, MP_TUNNELBRIDGE) && (_m[tile].m5 & 0xF0)==0 && (_m[tile].m5 & 3) == exitdir)

    38

		return false;

    39

    40

	// depot

    41

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

    42

		return true;

    43

    44

	/* Calculate next tile */

    45

	dst_tile = tile + TileOffsByDir(exitdir);

    46

	// determine the track status on the next tile.

    47

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

    48

    49

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

    50

	if ( (ts & TRACKDIR_BIT_MASK) == 0)

    51

		return true;

    52

    53

	{

    54

		byte dst_type = GetTileRailType(dst_tile, exitdir);

    55

		if (!IsCompatibleRail(enginetype, dst_type))

    56

			return true;

    57

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

    58

			return true;

    59

    60

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

    61

			return true;

    62

    63

		/* Check for oneway signal against us */

    64

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

    65

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

    66

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

    67

				return true;

    68

		}

    69

    70

		return false;

    71

	}

    72

};

    73

    74

#if 0

    75

static uint NTPHash(uint key1, uint key2)

    76

{

    77

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

    78

	return PATHFIND_HASH_TILE(key1);

    79

}

    80

#endif

    81

    82

/**

    83

 * Calculates a hash value for use in the NPF.

    84

 * @param key1	The TileIndex of the tile to hash

    85

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

    86

 *

    87

 * @todo	Think of a better hash.

    88

 */

    89

static uint NPFHash(uint key1, uint key2)

    90

{

    91

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

    92

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

    93

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

    94

    95

	assert(IsValidTrackdir(key2));

    96

	assert(IsValidTile(key1));

    97

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

    98

}

    99

   100

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

   101

{

   102

	return 0;

   103

}

   104

   105

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

   106

 * for this we assume the station is a rectangle,

   107

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

   108

 */

   109

static TileIndex CalcClosestStationTile(StationID station, TileIndex tile)

   110

{

   111

	const Station* st = GetStation(station);

   112

   113

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

   114

	uint miny = TileY(st->train_tile);

   115

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

   116

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

   117

	uint x;

   118

	uint y;

   119

   120

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

   121

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

   122

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

   123

   124

	// same for y coordinate, see above comment

   125

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

   126

   127

	// return the tile of our target coordinates

   128

	return TileXY(x, y);

   129

};

   130

   131

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

   132

 * reserve the appropriate tracks, if needed. */

   133

void NPFReservePBSPath(AyStar *as)

   134

{

   135

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

   136

	bool eol_end = false;

   137

   138

	if (ftd->best_trackdir == 0xFF)

   139

		return;

   140

   141

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

   142

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

   143

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

   144

		eol_end = true;

   145

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

   146

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

   147

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

   148

	}

   149

   150

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

   151

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

   152

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

   153

	}

   154

   155

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

   156

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

   157

		 ((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

   158

		PathNode parent;

   159

		PathNode *curr;

   160

		PathNode *prev;

   161

		TileIndex start = INVALID_TILE;

   162

		byte trackdir = 0;

   163

   164

		parent.node = ftd->node;

   165

		parent.parent = &ftd->path;

   166

		curr = &parent;

   167

		prev = NULL;

   168

   169

		do {

   170

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

   171

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

   172

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

   173

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

   174

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

   175

				&& (start != INVALID_TILE)) {

   176

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

   177

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

   178

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

   179

					 * this point....

   180

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

   181

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

   182

					 */

   183

					PBSClearPath(start, trackdir);

   184

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

   185

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

   186

					return;

   187

				};

   188

   189

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

   190

   191

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

   192

				if (prev != NULL && start == INVALID_TILE) {

   193

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

   194

					start = prev->node.tile;

   195

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

   196

				}

   197

			}

   198

   199

			prev = curr;

   200

			curr = curr->parent;

   201

		} while (curr != NULL);

   202

	}

   203

   204

}

   205

   206

   207

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

   208

 * takes into account the direction of approach.

   209

 */

   210

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

   211

{

   212

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

   213

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

   214

	TileIndex from = current->tile;

   215

	TileIndex to = fstd->dest_coords;

   216

	uint dist;

   217

   218

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

   219

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

   220

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

   221

   222

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

   223

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

   224

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

   225

	else

   226

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

   227

		dist = DistanceTrack(from, to) * NPF_TILE_LENGTH;

   228

   229

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

   230

   231

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

   232

	   of the 'closest' tile */

   233

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

   234

	&&  (!NPFGetFlag(current , NPF_FLAG_SEEN_SIGNAL))

   235

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

   236

		return dist;

   237

   238

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

   239

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

   240

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

   241

) {

   242

		ftd->best_bird_dist = dist;

   243

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

   244

		ftd->path = parent->path;

   245

		ftd->node = *current;

   246

	}

   247

	return dist;

   248

}

   249

   250

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

   251

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

   252

 * choice */

   253

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

   254

{

   255

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

   256

		Trackdir trackdir = (Trackdir)current->direction;

   257

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

   258

		 * direction we chose */

   259

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

   260

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

   261

	} else {

   262

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

   263

		 * decision */

   264

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

   265

	}

   266

   267

}

   268

   269

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

   270

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

   271

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

   272

static uint NPFTunnelCost(AyStarNode* current)

   273

{

   274

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

   275

	TileIndex tile = current->tile;

   276

	if ( (DiagDirection)(_m[tile].m5 & 3) == ReverseDiagdir(exitdir)) {

   277

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

   278

		 * facing the tunnel exit */

   279

		FindLengthOfTunnelResult flotr;

   280

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

   281

		return flotr.length * NPF_TILE_LENGTH;

   282

		//TODO: Penalty for tunnels?

   283

	} else {

   284

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

   285

		 * straight track */

   286

		return NPF_TILE_LENGTH;

   287

	}

   288

}

   289

   290

static uint NPFSlopeCost(AyStarNode* current)

   291

{

   292

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

   293

	int x,y;

   294

	int8 z1,z2;

   295

   296

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

   297

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

   298

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

   299

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

   300

   301

	x = TileX(next) * TILE_SIZE;

   302

	y = TileY(next) * TILE_SIZE;

   303

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

   304

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

   305

   306

	if ((z2 - z1) > 1) {

   307

		/* Slope up */

   308

		return _patches.npf_rail_slope_penalty;

   309

	}

   310

	return 0;

   311

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

   312

	 * could just substract that bonus from the penalty, because

   313

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

   314

}

   315

   316

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

   317

static void NPFMarkTile(TileIndex tile)

   318

{

   319

#ifdef NO_DEBUG_MESSAGES

   320

	return;

   321

#else

   322

	if (_debug_npf_level >= 1)

   323

		switch(GetTileType(tile)) {

   324

			case MP_RAILWAY:

   325

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

   326

				 * ;-) */

   327

				if (!IsTileDepotType(tile, TRANSPORT_RAIL)) {

   328

					_m[tile].m2 &= ~15; /* Clear bits 0-3 */

   329

					MarkTileDirtyByTile(tile);

   330

				}

   331

				break;

   332

			case MP_STREET:

   333

				if (!IsTileDepotType(tile, TRANSPORT_ROAD)) {

   334

					_m[tile].m4 &= ~0x70; /* Clear bits 4-6 */

   335

					MarkTileDirtyByTile(tile);

   336

				}

   337

				break;

   338

			default:

   339

				break;

   340

		}

   341

#endif

   342

}

   343

   344

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

   345

{

   346

	//TileIndex tile = current->tile;

   347

	int32 cost = 0;

   348

	Trackdir trackdir = (Trackdir)current->direction;

   349

   350

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

   351

   352

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

   353

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

   354

   355

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

   356

		cost += _patches.npf_water_curve_penalty;

   357

   358

	/* TODO More penalties? */

   359

   360

	return cost;

   361

}

   362

   363

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

   364

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

   365

{

   366

	TileIndex tile = current->tile;

   367

	int32 cost = 0;

   368

   369

	/* Determine base length */

   370

	switch (GetTileType(tile)) {

   371

		case MP_TUNNELBRIDGE:

   372

			if ((_m[tile].m5 & 0xF0)==0) {

   373

				cost = NPFTunnelCost(current);

   374

				break;

   375

			}

   376

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

   377

			 * then. We treat that as ordinary road */

   378

		case MP_STREET:

   379

			cost = NPF_TILE_LENGTH;

   380

			/* Increase the cost for level crossings */

   381

			if ((_m[tile].m5 & 0xF0) == 0x10)

   382

				cost += _patches.npf_crossing_penalty;

   383

			break;

   384

		default:

   385

			break;

   386

	}

   387

   388

	/* Determine extra costs */

   389

   390

	/* Check for slope */

   391

	cost += NPFSlopeCost(current);

   392

   393

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

   394

	 * represented by non-diagonal tracks */

   395

	if (!IsDiagonalTrackdir(current->direction))

   396

		cost += _patches.npf_road_curve_penalty;

   397

   398

	NPFMarkTile(tile);

   399

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

   400

	return cost;

   401

}

   402

   403

   404

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

   405

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

   406

{

   407

	TileIndex tile = current->tile;

   408

	Trackdir trackdir = (Trackdir)current->direction;

   409

	int32 cost = 0;

   410

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

   411

	OpenListNode new_node;

   412

   413

	/* Determine base length */

   414

	switch (GetTileType(tile)) {

   415

		case MP_TUNNELBRIDGE:

   416

			if ((_m[tile].m5 & 0xF0)==0) {

   417

				cost = NPFTunnelCost(current);

   418

				break;

   419

			}

   420

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

   421

			 * then. We treat that as ordinary rail */

   422

		case MP_RAILWAY:

   423

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

   424

			break;

   425

		case MP_STREET: /* Railway crossing */

   426

			cost = NPF_TILE_LENGTH;

   427

			break;

   428

		case MP_STATION:

   429

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

   430

					* want to give station tiles that are not our destination

   431

					* this penalty. This would discourage trains to drive through

   432

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

   433

					* penalty, because every possible route will get this penalty

   434

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

   435

			* will therefore not make a difference. */

   436

			cost = NPF_TILE_LENGTH + _patches.npf_rail_station_penalty;

   437

			break;

   438

		default:

   439

			break;

   440

	}

   441

   442

	/* Determine extra costs */

   443

   444

	/* Check for reserved tracks (PBS) */

   445

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

   446

		NPFSetFlag(current, NPF_FLAG_PBS_BLOCKED, true);

   447

	};

   448

   449

	/* Check for signals */

   450

	if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir)) {

   451

		/* Ordinary track with signals */

   452

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

   453

			/* Signal facing us is red */

   454

			if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   455

				/* Penalize the first signal we

   456

				 * encounter, if it is red */

   457

   458

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

   459

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

   460

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

   461

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

   462

					cost += _patches.npf_rail_firstred_exit_penalty;

   463

				else

   464

					cost += _patches.npf_rail_firstred_penalty;

   465

   466

				/* for pbs runs, store the fact that the exit signal to the pbs block was red */

   467

				if (!(NPFGetFlag(current, NPF_FLAG_PBS_EXIT)) && !(NPFGetFlag(current, NPF_FLAG_PBS_RED)) && NPFGetFlag(current, NPF_FLAG_PBS_CHOICE))

   468

					NPFSetFlag(current, NPF_FLAG_PBS_RED, true);

   469

			}

   470

			/* Record the state of this signal */

   471

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true);

   472

		} else {

   473

			/* Record the state of this signal */

   474

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false);

   475

		}

   476

   477

		if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL) && NPFGetFlag(current, NPF_FLAG_PBS_BLOCKED)) {

   478

			/* penalise a path through the pbs block if it crosses reserved tracks */

   479

			cost += 1000;

   480

		}

   481

		if ((PBSIsPbsSignal(tile, trackdir)) && !NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   482

			/* we've encountered an exit signal to the pbs block */

   483

			NPFSetFlag(current, NPF_FLAG_PBS_EXIT, true);

   484

		}

   485

		NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);

   486

	}

   487

   488

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

   489

	 * red */

   490

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

   491

	 * of course... */

   492

	new_node.path.node = *current;

   493

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

   494

		cost += _patches.npf_rail_lastred_penalty;