1

/* $Id$ */

     2

     3

/** @file npf.cpp */

     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.h"

    16

#include "station_map.h"

    17

#include "depot.h"

    18

#include "tunnel_map.h"

    19

#include "network/network.h"

    20

#include "water_map.h"

    21

#include "tunnelbridge_map.h"

    22

#include "functions.h"

    23

#include "vehicle_base.h"

    24

#include "settings_type.h"

    25

#include "tunnelbridge.h"

    26

    27

static AyStar _npf_aystar;

    28

    29

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

    30

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

    31

 */

    32

#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)

    33

static const uint _trackdir_length[TRACKDIR_END] = {

    34

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

    35

	0, 0,

    36

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH

    37

};

    38

    39

/**

    40

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

    41

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

    42

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

    43

 * prevent rounding.

    44

 */

    45

static uint NPFDistanceTrack(TileIndex t0, TileIndex t1)

    46

{

    47

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

    48

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

    49

    50

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

    51

	/* OPTIMISATION:

    52

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

    53

	 * Proof:

    54

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

    55

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

    56

    57

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

    58

	 * precision */

    59

	return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH;

    60

}

    61

    62

    63

#if 0

    64

static uint NTPHash(uint key1, uint key2)

    65

{

    66

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

    67

	return PATHFIND_HASH_TILE(key1);

    68

}

    69

#endif

    70

    71

/**

    72

 * Calculates a hash value for use in the NPF.

    73

 * @param key1 The TileIndex of the tile to hash

    74

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

    75

 *

    76

 * @todo Think of a better hash.

    77

 */

    78

static uint NPFHash(uint key1, uint key2)

    79

{

    80

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

    81

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

    82

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

    83

    84

	assert(IsValidTrackdir((Trackdir)key2));

    85

	assert(IsValidTile(key1));

    86

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

    87

}

    88

    89

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

    90

{

    91

	return 0;

    92

}

    93

    94

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

    95

 * for this we assume the station is a rectangle,

    96

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

    97

 */

    98

static TileIndex CalcClosestStationTile(StationID station, TileIndex tile)

    99

{

   100

	const Station* st = GetStation(station);

   101

   102

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

   103

	uint miny = TileY(st->train_tile);

   104

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

   105

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

   106

	uint x;

   107

	uint y;

   108

   109

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

   110

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

   111

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

   112

   113

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

   114

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

   115

   116

	/* return the tile of our target coordinates */

   117

	return TileXY(x, y);

   118

}

   119

   120

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

   121

 * takes into account the direction of approach.

   122

 */

   123

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

   124

{

   125

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

   126

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

   127

	TileIndex from = current->tile;

   128

	TileIndex to = fstd->dest_coords;

   129

	uint dist;

   130

   131

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

   132

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

   133

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

   134

   135

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

   136

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

   137

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

   138

	} else {

   139

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

   140

		dist = NPFDistanceTrack(from, to);

   141

	}

   142

   143

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

   144

   145

	if (dist < ftd->best_bird_dist) {

   146

		ftd->best_bird_dist = dist;

   147

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

   148

	}

   149

	return dist;

   150

}

   151

   152

   153

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

   154

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

   155

 * choice */

   156

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

   157

{

   158

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

   159

		Trackdir trackdir = (Trackdir)current->direction;

   160

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

   161

		 * direction we chose */

   162

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

   163

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

   164

	} else {

   165

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

   166

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

   167

	}

   168

}

   169

   170

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

   171

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

   172

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

   173

static uint NPFTunnelCost(AyStarNode* current)

   174

{

   175

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

   176

	TileIndex tile = current->tile;

   177

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

   178

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

   179

		 * facing the tunnel exit */

   180

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

   181

		/* @todo: Penalty for tunnels? */

   182

	} else {

   183

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

   184

		 * straight track */

   185

		return NPF_TILE_LENGTH;

   186

	}

   187

}

   188

   189

static inline uint NPFBridgeCost(AyStarNode *current)

   190

{

   191

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

   192

}

   193

   194

static uint NPFSlopeCost(AyStarNode* current)

   195

{

   196

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

   197

   198

	/* Get center of tiles */

   199

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

   200

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

   201

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

   202

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

   203

   204

	int dx4 = (x2 - x1) / 4;

   205

	int dy4 = (y2 - y1) / 4;

   206

   207

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

   208

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

   209

	 */

   210

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

   211

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

   212

   213

	if (z2 - z1 > 1) {

   214

		/* Slope up */

   215

		return _patches.npf_rail_slope_penalty;

   216

	}

   217

	return 0;

   218

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

   219

	 * could just substract that bonus from the penalty, because

   220

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

   221

}

   222

   223

/**

   224

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

   225

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

   226

 */

   227

static void NPFMarkTile(TileIndex tile)

   228

{

   229

#ifndef NO_DEBUG_MESSAGES

   230

	if (_debug_npf_level < 1 || _networking) return;

   231

	switch (GetTileType(tile)) {

   232

		case MP_RAILWAY:

   233

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

   234

			if (!IsTileDepotType(tile, TRANSPORT_RAIL)) {

   235

				SetRailGroundType(tile, RAIL_GROUND_BARREN);

   236

				MarkTileDirtyByTile(tile);

   237

			}

   238

			break;

   239

   240

		case MP_ROAD:

   241

			if (!IsTileDepotType(tile, TRANSPORT_ROAD)) {

   242

				SetRoadside(tile, ROADSIDE_BARREN);

   243

				MarkTileDirtyByTile(tile);

   244

			}

   245

			break;

   246

   247

		default:

   248

			break;

   249

	}

   250

#endif

   251

}

   252

   253

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

   254

{

   255

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

   256

	int32 cost = 0;

   257

	Trackdir trackdir = (Trackdir)current->direction;

   258

   259

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

   260

   261

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

   262

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

   263

   264

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

   265

		cost += _patches.npf_water_curve_penalty;

   266

   267

	/* @todo More penalties? */

   268

   269

	return cost;

   270

}

   271

   272

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

   273

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

   274

{

   275

	TileIndex tile = current->tile;

   276

	int32 cost = 0;

   277

   278

	/* Determine base length */

   279

	switch (GetTileType(tile)) {

   280

		case MP_TUNNELBRIDGE:

   281

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

   282

			break;

   283

   284

		case MP_ROAD:

   285

			cost = NPF_TILE_LENGTH;

   286

			/* Increase the cost for level crossings */

   287

			if (IsLevelCrossing(tile)) cost += _patches.npf_crossing_penalty;

   288

			break;

   289

   290

		case MP_STATION:

   291

			cost = NPF_TILE_LENGTH;

   292

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

   293

			if (IsDriveThroughStopTile(tile)) cost += _patches.npf_road_drive_through_penalty;

   294

			break;

   295

   296

		default:

   297

			break;

   298

	}

   299

   300

	/* Determine extra costs */

   301

   302

	/* Check for slope */

   303

	cost += NPFSlopeCost(current);

   304

   305

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

   306

	 * represented by non-diagonal tracks */

   307

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

   308

		cost += _patches.npf_road_curve_penalty;

   309

   310

	NPFMarkTile(tile);

   311

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

   312

	return cost;

   313

}

   314

   315

   316

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

   317

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

   318

{

   319

	TileIndex tile = current->tile;

   320

	Trackdir trackdir = (Trackdir)current->direction;

   321

	int32 cost = 0;

   322

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

   323

	OpenListNode new_node;

   324

   325

	/* Determine base length */

   326

	switch (GetTileType(tile)) {

   327

		case MP_TUNNELBRIDGE:

   328

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

   329

			break;

   330

   331

		case MP_RAILWAY:

   332

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

   333

			break;

   334

   335

		case MP_ROAD: /* Railway crossing */

   336

			cost = NPF_TILE_LENGTH;

   337

			break;

   338

   339

		case MP_STATION:

   340

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

   341

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

   342

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

   343

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

   344

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

   345

			 * will therefore not make a difference. */

   346

			cost = NPF_TILE_LENGTH + _patches.npf_rail_station_penalty;

   347

			break;

   348

   349

		default:

   350

			break;

   351

	}

   352

   353

	/* Determine extra costs */

   354

   355

	/* Check for signals */

   356

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

   357

		/* Ordinary track with signals */

   358

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

   359

			/* Signal facing us is red */

   360

			if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   361

				/* Penalize the first signal we

   362

				 * encounter, if it is red */

   363

   364

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

   365

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

   366

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

   367

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

   368

					cost += _patches.npf_rail_firstred_exit_penalty;

   369

				} else {

   370

					cost += _patches.npf_rail_firstred_penalty;

   371

				}

   372

			}

   373

			/* Record the state of this signal */

   374

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true);

   375

		} else {

   376

			/* Record the state of this signal */

   377

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false);

   378

		}

   379

		NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);

   380

	}

   381

   382

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

   383

	 * red */

   384

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

   385

	 * of course... */

   386

	new_node.path.node = *current;

   387

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

   388

		cost += _patches.npf_rail_lastred_penalty;

   389

   390

	/* Check for slope */

   391

	cost += NPFSlopeCost(current);

   392

   393

	/* Check for turns */

   394

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

   395

		cost += _patches.npf_rail_curve_penalty;

   396

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

   397

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

   398

   399

	/* Check for reverse in depot */

   400

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

   401

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

   402

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

   403

		 * that) */

   404

		cost += _patches.npf_rail_depot_reverse_penalty;

   405

	}

   406

   407

	/* Check for occupied track */

   408

	//TODO

   409

   410

	NPFMarkTile(tile);

   411

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

   412

	return cost;

   413

}

   414

   415

/* Will find any depot */

   416

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

   417

{

   418

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

   419

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

   420

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

   421

		AYSTAR_FOUND_END_NODE : AYSTAR_DONE;

   422

}

   423

   424

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

   425

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

   426

{

   427

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

   428

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

   429

	TileIndex tile = node->tile;

   430

   431

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

   432

	 * is correct */

   433

	if (

   434

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

   435

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

   436

	) {

   437

		return AYSTAR_FOUND_END_NODE;

   438

	} else {

   439

		return AYSTAR_DONE;

   440

	}

   441

}

   442

   443

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

   444

 * Will fill the contents of the NPFFoundTargetData using

   445

 * AyStarNode[NPF_TRACKDIR_CHOICE].

   446

 */

   447

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

   448

{

   449

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

   450

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

   451

	ftd->best_path_dist = current->g;

   452

	ftd->best_bird_dist = 0;

   453

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

   454

}

   455

   456

/**

   457

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

   458

 * @param owner    The owner of the vehicle.

   459

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

   460

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

   461

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

   462

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

   463

 *                 maybe moved to another file too.

   464

 */

   465

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

   466

{

   467

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

   468

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

   469

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

   470

			IsStandardRoadStopTile(tile) || /* Road station tile (but not drive-through stops) */

   471

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

   472

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

   473

	}

   474

   475

	switch (GetTileType(tile)) {

   476

		case MP_ROAD:

   477

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

   478

			if (IsLevelCrossing(tile) &&

   479

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

   480

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

   481

			}

   482

			break;

   483

   484

		case MP_TUNNELBRIDGE:

   485

			if (GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL) {

   486

				return IsTileOwner(tile, owner);

   487

			}

   488

			break;