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

#if 0

    51

static uint NTPHash(uint key1, uint key2)

    52

{

    53

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

    54

	return PATHFIND_HASH_TILE(key1);

    55

}

    56

#endif

    57

    58

/**

    59

 * Calculates a hash value for use in the NPF.

    60

 * @param key1	The TileIndex of the tile to hash

    61

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

    62

 *

    63

 * @todo	Think of a better hash.

    64

 */

    65

static uint NPFHash(uint key1, uint key2)

    66

{

    67

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

    68

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

    69

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

    70

    71

	assert(IsValidTrackdir(key2));

    72

	assert(IsValidTile(key1));

    73

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

    74

}

    75

    76

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

    77

{

    78

	return 0;

    79

}

    80

    81

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

    82

 * for this we assume the station is a rectangle,

    83

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

    84

 */

    85

static TileIndex CalcClosestStationTile(StationID station, TileIndex tile)

    86

{

    87

	const Station* st = GetStation(station);

    88

    89

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

    90

	uint miny = TileY(st->train_tile);

    91

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

    92

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

    93

	uint x;

    94

	uint y;

    95

    96

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

    97

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

    98

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

    99

   100

	// same for y coordinate, see above comment

   101

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

   102

   103

	// return the tile of our target coordinates

   104

	return TileXY(x, y);

   105

}

   106

   107

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

   108

 * takes into account the direction of approach.

   109

 */

   110

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

   111

{

   112

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

   113

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

   114

	TileIndex from = current->tile;

   115

	TileIndex to = fstd->dest_coords;

   116

	uint dist;

   117

   118

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

   119

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

   120

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

   121

   122

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

   123

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

   124

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

   125

	else

   126

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

   127

		dist = NPFDistanceTrack(from, to);

   128

   129

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

   130

   131

	if (dist < ftd->best_bird_dist) {

   132

		ftd->best_bird_dist = dist;

   133

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

   134

	}

   135

	return dist;

   136

}

   137

   138

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

   139

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

   140

 * choice */

   141

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

   142

{

   143

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

   144

		Trackdir trackdir = (Trackdir)current->direction;

   145

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

   146

		 * direction we chose */

   147

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

   148

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

   149

	} else {

   150

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

   151

		 * decision */

   152

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

   153

	}

   154

   155

}

   156

   157

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

   158

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

   159

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

   160

static uint NPFTunnelCost(AyStarNode* current)

   161

{

   162

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

   163

	TileIndex tile = current->tile;

   164

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

   165

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

   166

		 * facing the tunnel exit */

   167

		FindLengthOfTunnelResult flotr;

   168

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

   169

		return flotr.length * NPF_TILE_LENGTH;

   170

		//TODO: Penalty for tunnels?

   171

	} else {

   172

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

   173

		 * straight track */

   174

		return NPF_TILE_LENGTH;

   175

	}

   176

}

   177

   178

static uint NPFSlopeCost(AyStarNode* current)

   179

{

   180

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

   181

	int x,y;

   182

	int8 z1,z2;

   183

   184

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

   185

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

   186

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

   187

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

   188

   189

	x = TileX(next) * TILE_SIZE;

   190

	y = TileY(next) * TILE_SIZE;

   191

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

   192

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

   193

   194

	if ((z2 - z1) > 1) {

   195

		/* Slope up */

   196

		return _patches.npf_rail_slope_penalty;

   197

	}

   198

	return 0;

   199

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

   200

	 * could just substract that bonus from the penalty, because

   201

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

   202

}

   203

   204

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

   205

static void NPFMarkTile(TileIndex tile)

   206

{

   207

#ifdef NO_DEBUG_MESSAGES

   208

	return;

   209

#else

   210

	if (_debug_npf_level >= 1)

   211

		switch(GetTileType(tile)) {

   212

			case MP_RAILWAY:

   213

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

   214

				 * ;-) */

   215

				if (!IsTileDepotType(tile, TRANSPORT_RAIL)) {

   216

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

   217

					MarkTileDirtyByTile(tile);

   218

				}

   219

				break;

   220

			case MP_STREET:

   221

				if (!IsTileDepotType(tile, TRANSPORT_ROAD)) {

   222

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

   223

					MarkTileDirtyByTile(tile);

   224

				}

   225

				break;

   226

			default:

   227

				break;

   228

		}

   229

#endif

   230

}

   231

   232

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

   233

{

   234

	//TileIndex tile = current->tile;

   235

	int32 cost = 0;

   236

	Trackdir trackdir = (Trackdir)current->direction;

   237

   238

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

   239

   240

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

   241

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

   242

   243

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

   244

		cost += _patches.npf_water_curve_penalty;

   245

   246

	/* TODO More penalties? */

   247

   248

	return cost;

   249

}

   250

   251

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

   252

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

   253

{

   254

	TileIndex tile = current->tile;

   255

	int32 cost = 0;

   256

   257

	/* Determine base length */

   258

	switch (GetTileType(tile)) {

   259

		case MP_TUNNELBRIDGE:

   260

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

   261

				cost = NPFTunnelCost(current);

   262

				break;

   263

			}

   264

			cost = NPF_TILE_LENGTH;

   265

			break;

   266

		case MP_STREET:

   267

			cost = NPF_TILE_LENGTH;

   268

			/* Increase the cost for level crossings */

   269

			if (IsLevelCrossing(tile))

   270

				cost += _patches.npf_crossing_penalty;

   271

			break;

   272

		default:

   273

			break;

   274

	}

   275

   276

	/* Determine extra costs */

   277

   278

	/* Check for slope */

   279

	cost += NPFSlopeCost(current);

   280

   281

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

   282

	 * represented by non-diagonal tracks */

   283

	if (!IsDiagonalTrackdir(current->direction))

   284

		cost += _patches.npf_road_curve_penalty;

   285

   286

	NPFMarkTile(tile);

   287

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

   288

	return cost;

   289

}

   290

   291

   292

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

   293

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

   294

{

   295

	TileIndex tile = current->tile;

   296

	Trackdir trackdir = (Trackdir)current->direction;

   297

	int32 cost = 0;

   298

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

   299

	OpenListNode new_node;

   300

   301

	/* Determine base length */

   302

	switch (GetTileType(tile)) {

   303

		case MP_TUNNELBRIDGE:

   304

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

   305

				cost = NPFTunnelCost(current);

   306

				break;

   307

			}

   308

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

   309

			 * then. We treat that as ordinary rail */

   310

		case MP_RAILWAY:

   311

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

   312

			break;

   313

		case MP_STREET: /* Railway crossing */

   314

			cost = NPF_TILE_LENGTH;

   315

			break;

   316

		case MP_STATION:

   317

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

   318

					* want to give station tiles that are not our destination

   319

					* this penalty. This would discourage trains to drive through

   320

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

   321

					* penalty, because every possible route will get this penalty

   322

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

   323

			* will therefore not make a difference. */

   324

			cost = NPF_TILE_LENGTH + _patches.npf_rail_station_penalty;

   325

			break;

   326

		default:

   327

			break;

   328

	}

   329

   330

	/* Determine extra costs */

   331

   332

	/* Check for signals */

   333

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

   334

		/* Ordinary track with signals */

   335

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

   336

			/* Signal facing us is red */

   337

			if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   338

				/* Penalize the first signal we

   339

				 * encounter, if it is red */

   340

   341

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

   342

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

   343

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

   344

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

   345

					cost += _patches.npf_rail_firstred_exit_penalty;

   346

				else

   347

					cost += _patches.npf_rail_firstred_penalty;

   348

			}

   349

			/* Record the state of this signal */

   350

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true);

   351

		} else {

   352

			/* Record the state of this signal */

   353

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false);

   354

		}

   355

		NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);

   356

	}

   357

   358

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

   359

	 * red */

   360

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

   361

	 * of course... */

   362

	new_node.path.node = *current;

   363

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

   364

		cost += _patches.npf_rail_lastred_penalty;

   365

   366

	/* Check for slope */

   367

	cost += NPFSlopeCost(current);

   368

   369

	/* Check for turns */

   370

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

   371

		cost += _patches.npf_rail_curve_penalty;

   372

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

   373

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

   374

   375

   376

	/* Check for reverse in depot */

   377

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

   378

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

   379

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

   380

		 * that) */

   381

		cost += _patches.npf_rail_depot_reverse_penalty;

   382

   383

	}

   384

   385

	/* Check for occupied track */

   386

	//TODO

   387

   388

	NPFMarkTile(tile);

   389

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

   390

	return cost;

   391

}

   392

   393

/* Will find any depot */

   394

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

   395

{

   396

	TileIndex tile = current->path.node.tile;

   397

   398

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

   399

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

   400

	if (IsTileDepotType(tile, as->user_data[NPF_TYPE]))

   401

		return AYSTAR_FOUND_END_NODE;

   402

	else

   403

		return AYSTAR_DONE;

   404

}

   405

   406

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

   407

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

   408

{

   409

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

   410

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

   411

	TileIndex tile = node->tile;

   412

   413

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

   414

	 * is correct */

   415

	if (

   416

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

   417

		(IsTileType(tile, MP_STATION) && _m[tile].m2 == fstd->station_index) /* the station */

   418

	) {

   419

		return AYSTAR_FOUND_END_NODE;

   420

	} else {

   421

		return AYSTAR_DONE;

   422

	}

   423

}

   424

   425

/* To be called when current contains the (shortest route to) the target node.

   426

 * Will fill the contents of the NPFFoundTargetData using

   427

 * AyStarNode[NPF_TRACKDIR_CHOICE].

   428

 */

   429

static void NPFSaveTargetData(AyStar* as, OpenListNode* current)

   430

{

   431

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

   432

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

   433

	ftd->best_path_dist = current->g;

   434

	ftd->best_bird_dist = 0;

   435

	ftd->node = current->path.node;

   436

}

   437

   438

/**

   439

 * Finds out if a given player's vehicles are allowed to enter a given tile.

   440

 * @param owner    The owner of the vehicle.

   441

 * @param tile     The tile that is about to be entered.

   442

 * @param enterdir The direction from which the vehicle wants to enter the tile.

   443

 * @return         true if the vehicle can enter the tile.

   444

 * @todo           This function should be used in other places than just NPF,

   445

 *                 maybe moved to another file too.

   446

 */

   447

static bool VehicleMayEnterTile(Owner owner, TileIndex tile, DiagDirection enterdir)

   448

{

   449

	if (

   450

		IsTileType(tile, MP_RAILWAY) /* Rail tile (also rail depot) */

   451

		|| IsTrainStationTile(tile) /* Rail station tile */

   452

		|| IsTileDepotType(tile, TRANSPORT_ROAD) /* Road depot tile */

   453

		|| IsRoadStationTile(tile) /* Road station tile */

   454

		|| IsTileDepotType(tile, TRANSPORT_WATER) /* Water depot tile */

   455

		)

   456

		return IsTileOwner(tile, owner); /* You need to own these tiles entirely to use them */

   457

   458

	switch (GetTileType(tile)) {

   459

		case MP_STREET:

   460

			/* rail-road crossing : are we looking at the railway part? */

   461

			if (IsLevelCrossing(tile) && GetCrossingTransportType(tile, TrackdirToTrack(DiagdirToDiagTrackdir(enterdir))) == TRANSPORT_RAIL)

   462

				return IsTileOwner(tile, owner); /* Railway needs owner check, while the street is public */

   463

			break;

   464

		case MP_TUNNELBRIDGE:

   465

#if 0

   466

/* OPTIMISATION: If we are on the middle of a bridge, we will not do the cpu

   467

 * intensive owner check, instead we will just assume that if the vehicle

   468

 * managed to get on the bridge, it is probably allowed to :-)

   469

 */

   470

			if ((_m[tile].m5 & 0xC6) == 0xC0 && GB(_m[tile].m5, 0, 1) == (enterdir & 0x1)) {

   471

				/* on the middle part of a railway bridge: find bridge ending */

   472

				while (IsTileType(tile, MP_TUNNELBRIDGE) && !((_m[tile].m5 & 0xC6) == 0x80)) {

   473

					tile += TileOffsByDir(GB(_m[tile].m5, 0, 1));

   474

				}

   475

			}

   476

			/* if we were on a railway middle part, we are now at a railway bridge ending */

   477

#endif

   478

			if (

   479

				(_m[tile].m5 & 0xFC) == 0 /* railway tunnel */

   480

				|| (_m[tile].m5 & 0xC6) == 0x80 /* railway bridge ending */

   481

				|| ((_m[tile].m5 & 0xF8) == 0xE0 && GB(_m[tile].m5, 0, 1) != (enterdir & 0x1)) /* railway under bridge */

   482

				)

   483

				return IsTileOwner(tile, owner);

   484

			break;

   485

		default:

   486

			break;

   487

	}

   488

   489

	return true; /* no need to check */

   490

}

   491

   492

/* Will just follow the results of GetTileTrackStatus concerning where we can

   493

 * go and where not. Uses AyStar.user_data[NPF_TYPE] as the transport type and

   494

 * an argument to GetTileTrackStatus. Will skip tunnels, meaning that the

   495