1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "bridge_map.h"

     6

#include "debug.h"

     7

#include "functions.h"

     8

#include "npf.h"

     9

#include "aystar.h"

    10

#include "macros.h"

    11

#include "pathfind.h"

    12

#include "station.h"

    13

#include "station_map.h"

    14

#include "tile.h"

    15

#include "depot.h"

    16

#include "tunnel_map.h"

    18

    19

static AyStar _npf_aystar;

    20

    21

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

    22

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

    23

 */

    24

#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)

    25

static const uint _trackdir_length[TRACKDIR_END] = {

    26

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

    27

	0, 0,

    28

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH

    29

};

    30

    31

/**

    32

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

    33

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

    34

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

    35

 * prevent rounding.

    36

 */

    37

static uint NPFDistanceTrack(TileIndex t0, TileIndex t1)

    38

{

    39

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

    40

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

    41

    42

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

    43

	/* OPTIMISATION:

    44

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

    45

	 * Proof:

    46

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

    47

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

    48

    49

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

    50

	 * precision */

    51

	return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH;

    52

}

    53

    54

    55

#if 0

    56

static uint NTPHash(uint key1, uint key2)

    57

{

    58

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

    59

	return PATHFIND_HASH_TILE(key1);

    60

}

    61

#endif

    62

    63

/**

    64

 * Calculates a hash value for use in the NPF.

    65

 * @param key1	The TileIndex of the tile to hash

    66

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

    67

 *

    68

 * @todo	Think of a better hash.

    69

 */

    70

static uint NPFHash(uint key1, uint key2)

    71

{

    72

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

    73

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

    74

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

    75

    76

	assert(IsValidTrackdir(key2));

    77

	assert(IsValidTile(key1));

    78

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

    79

}

    80

    81

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

    82

{

    83

	return 0;

    84

}

    85

    86

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

    87

 * for this we assume the station is a rectangle,

    88

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

    89

 */

    90

static TileIndex CalcClosestStationTile(StationID station, TileIndex tile)

    91

{

    92

	const Station* st = GetStation(station);

    93

    94

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

    95

	uint miny = TileY(st->train_tile);

    96

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

    97

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

    98

	uint x;

    99

	uint y;

   100

   101

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

   102

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

   103

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

   104

   105

	// same for y coordinate, see above comment

   106

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

   107

   108

	// return the tile of our target coordinates

   109

	return TileXY(x, y);

   110

}

   111

   112

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

   113

 * takes into account the direction of approach.

   114

 */

   115

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

   116

{

   117

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

   118

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

   119

	TileIndex from = current->tile;

   120

	TileIndex to = fstd->dest_coords;

   121

	uint dist;

   122

   123

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

   124

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

   125

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

   126

   127

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

   128

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

   129

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

   130

	} else {

   131

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

   132

		dist = NPFDistanceTrack(from, to);

   133

	}

   134

   135

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

   136

   137

	if (dist < ftd->best_bird_dist) {

   138

		ftd->best_bird_dist = dist;

   139

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

   140

	}

   141

	return dist;

   142

}

   143

   144

   145

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

   146

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

   147

 * choice */

   148

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

   149

{

   150

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

   151

		Trackdir trackdir = (Trackdir)current->direction;

   152

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

   153

		 * direction we chose */

   154

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

   155

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

   156

	} else {

   157

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

   158

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

   159

	}

   160

}

   161

   162

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

   163

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

   164

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

   165

static uint NPFTunnelCost(AyStarNode* current)

   166

{

   167

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

   168

	TileIndex tile = current->tile;

   169

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

   170

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

   171

		 * facing the tunnel exit */

   172

		FindLengthOfTunnelResult flotr;

   173

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

   174

		return flotr.length * NPF_TILE_LENGTH;

   175

		//TODO: Penalty for tunnels?

   176

	} else {

   177

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

   178

		 * straight track */

   179

		return NPF_TILE_LENGTH;

   180

	}

   181

}

   182

   183

static uint NPFSlopeCost(AyStarNode* current)

   184

{

   185

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

   186

	int x,y;

   187

	int8 z1,z2;

   188

   189

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

   190

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

   191

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

   192

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

   193

   194

	x = TileX(next) * TILE_SIZE;

   195

	y = TileY(next) * TILE_SIZE;

   196

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

   197

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

   198

   199

	if (z2 - z1 > 1) {

   200

		/* Slope up */

   201

		return _patches.npf_rail_slope_penalty;

   202

	}

   203

	return 0;

   204

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

   205

	 * could just substract that bonus from the penalty, because

   206

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

   207

}

   208

   213

static void NPFMarkTile(TileIndex tile)

   214

{

   215

#ifdef NO_DEBUG_MESSAGES

   216

	return;

   217

#else

   219

	switch (GetTileType(tile)) {

   220

		case MP_RAILWAY:

   221

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

   222

			if (!IsTileDepotType(tile, TRANSPORT_RAIL)) {

   223

				SetRailGroundType(tile, RAIL_GROUND_BARREN);

   224

				MarkTileDirtyByTile(tile);

   225

			}

   226

			break;

   227

   228

		case MP_STREET:

   229

			if (!IsTileDepotType(tile, TRANSPORT_ROAD)) {

   230

				SetGroundType(tile, RGT_BARREN);

   231

				MarkTileDirtyByTile(tile);

   232

			}

   233

			break;

   234

   235

		default:

   236

			break;

   237

	}

   238

#endif

   239

}

   240

   241

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

   242

{

   243

	//TileIndex tile = current->tile;

   244

	int32 cost = 0;

   245

	Trackdir trackdir = (Trackdir)current->direction;

   246

   247

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

   248

   249

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

   250

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

   251

   252

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

   253

		cost += _patches.npf_water_curve_penalty;

   254

   255

	/* TODO More penalties? */

   256

   257

	return cost;

   258

}

   259

   260

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

   261

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

   262

{

   263

	TileIndex tile = current->tile;

   264

	int32 cost = 0;

   265

   266

	/* Determine base length */

   267

	switch (GetTileType(tile)) {

   268

		case MP_TUNNELBRIDGE:

   269

			if (IsTunnel(tile)) {

   270

				cost = NPFTunnelCost(current);

   271

			} else {

   272

				cost = NPF_TILE_LENGTH;

   273

			}

   274

			break;

   275

   276

		case MP_STREET:

   277

			cost = NPF_TILE_LENGTH;

   278

			/* Increase the cost for level crossings */

   279

			if (IsLevelCrossing(tile))

   280

				cost += _patches.npf_crossing_penalty;

   281

			break;

   282

   283

		default:

   284

			break;

   285

	}

   286

   287

	/* Determine extra costs */

   288

   289

	/* Check for slope */

   290

	cost += NPFSlopeCost(current);

   291

   292

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

   293

	 * represented by non-diagonal tracks */

   294

	if (!IsDiagonalTrackdir(current->direction))

   295

		cost += _patches.npf_road_curve_penalty;

   296

   297

	NPFMarkTile(tile);

   298

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

   299

	return cost;

   300

}

   301

   302

   303

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

   304

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

   305

{

   306

	TileIndex tile = current->tile;

   307

	Trackdir trackdir = (Trackdir)current->direction;

   308

	int32 cost = 0;

   309

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

   310

	OpenListNode new_node;

   311

   312

	/* Determine base length */

   313

	switch (GetTileType(tile)) {

   314

		case MP_TUNNELBRIDGE:

   315

			if (IsTunnel(tile)) {

   316

				cost = NPFTunnelCost(current);

   317

				break;

   318

			}

   319

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

   320

			 * then. We treat that as ordinary rail */

   321

   322

		case MP_RAILWAY:

   323

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

   324

			break;

   325

   326

		case MP_STREET: /* Railway crossing */

   327

			cost = NPF_TILE_LENGTH;

   328

			break;

   329

   330

		case MP_STATION:

   331

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

   332

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

   333

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

   334

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

   335

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

   336

			 * will therefore not make a difference. */

   337

			cost = NPF_TILE_LENGTH + _patches.npf_rail_station_penalty;

   338

			break;

   339

   340

		default:

   341

			break;

   342

	}

   343

   344

	/* Determine extra costs */

   345

   346

	/* Check for signals */

   347

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

   348

		/* Ordinary track with signals */

   349

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

   350

			/* Signal facing us is red */

   351

			if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   352

				/* Penalize the first signal we

   353

				 * encounter, if it is red */

   354

   355

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

   356

				SignalType sigtype = GetSignalType(tile);

   357

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

   358

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

   359

					cost += _patches.npf_rail_firstred_exit_penalty;

   360

				} else {

   361

					cost += _patches.npf_rail_firstred_penalty;

   362

				}

   363

			}

   364

			/* Record the state of this signal */

   365

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true);

   366

		} else {

   367

			/* Record the state of this signal */

   368

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false);

   369

		}

   370

		NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);

   371

	}

   372

   373

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

   374

	 * red */

   375

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

   376

	 * of course... */

   377

	new_node.path.node = *current;

   378

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

   379

		cost += _patches.npf_rail_lastred_penalty;

   380

   381

	/* Check for slope */

   382

	cost += NPFSlopeCost(current);

   383

   384

	/* Check for turns */

   385

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

   386

		cost += _patches.npf_rail_curve_penalty;

   387

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

   388

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

   389

   390

	/* Check for reverse in depot */

   391

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

   392

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

   393

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

   394

		 * that) */

   395

		cost += _patches.npf_rail_depot_reverse_penalty;

   396

	}

   397

   398

	/* Check for occupied track */

   399

	//TODO

   400

   401

	NPFMarkTile(tile);

   402

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

   403

	return cost;

   404

}

   405

   406

/* Will find any depot */

   407

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

   408

{

   409

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

   410

   411

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

   412

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

   413

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

   414

		return AYSTAR_FOUND_END_NODE;

   415

	} else {

   416

		return AYSTAR_DONE;

   417

	}

   418

}

   419

   420

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

   421

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

   422

{

   423

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

   424

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

   425

	TileIndex tile = node->tile;

   426

   427

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

   428

	 * is correct */

   429

	if (

   430

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

   431

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

   432

	) {

   433

		return AYSTAR_FOUND_END_NODE;

   434

	} else {

   435

		return AYSTAR_DONE;

   436

	}

   437

}

   438

   439

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

   440

 * Will fill the contents of the NPFFoundTargetData using

   441

 * AyStarNode[NPF_TRACKDIR_CHOICE].

   442

 */

   443

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

   444

{

   445

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

   446

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

   447

	ftd->best_path_dist = current->g;

   448

	ftd->best_bird_dist = 0;

   449

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

   450

}

   451

   452

/**

   453

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

   454

 * @param owner    The owner of the vehicle.

   455

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

   456

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

   457

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

   458

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

   459

 *                 maybe moved to another file too.

   460

 */

   461

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

   462

{

   463

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

   464

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

   465

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

   466

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

   467

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

   468

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

   469

	}

   470

   471

	switch (GetTileType(tile)) {

   472

		case MP_STREET:

   473

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

   474

			if (IsLevelCrossing(tile) &&

   475

					DiagDirToAxis(enterdir) != GetCrossingRoadAxis(tile)) {

   476

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

   477

			}

   478

			break;

   479

   480

		case MP_TUNNELBRIDGE:

   481

			if ((IsTunnel(tile) && GetTunnelTransportType(tile) == TRANSPORT_RAIL) ||

   482

					(IsBridge(tile) && (

   483

						(

   484

							IsBridgeRamp(tile) &&

   485

							GetBridgeTransportType(tile) == TRANSPORT_RAIL

   486

						) || (

   487

							IsBridgeMiddle(tile) &&

   488

							IsTransportUnderBridge(tile) &&

   489

							GetTransportTypeUnderBridge(tile) == TRANSPORT_RAIL &&

   490

							GetBridgeAxis(tile) != DiagDirToAxis(enterdir)

   491

						)