1

/* $Id$ */

     2

     5

#include "stdafx.h"

     6

#include "openttd.h"

     7

#include "bridge_map.h"

     8

#include "debug.h"

     9

#include "functions.h"

    10

#include "npf.h"

    11

#include "aystar.h"

    12

#include "macros.h"

    13

#include "pathfind.h"

    14

#include "station.h"

    15

#include "station_map.h"

    16

#include "tile.h"

    17

#include "depot.h"

    18

#include "tunnel_map.h"

    19

#include "network/network.h"

    20

#include "water_map.h"

    21

    22

static AyStar _npf_aystar;

    23

    24

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

    25

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

    26

 */

    27

#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)

    28

static const uint _trackdir_length[TRACKDIR_END] = {

    29

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

    30

	0, 0,

    31

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH

    32

};

    33

    34

/**

    35

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

    36

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

    37

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

    38

 * prevent rounding.

    39

 */

    40

static uint NPFDistanceTrack(TileIndex t0, TileIndex t1)

    41

{

    42

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

    43

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

    44

    45

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

    46

	/* OPTIMISATION:

    47

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

    48

	 * Proof:

    49

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

    50

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

    51

    52

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

    53

	 * precision */

    54

	return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH;

    55

}

    56

    57

    58

#if 0

    59

static uint NTPHash(uint key1, uint key2)

    60

{

    61

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

    62

	return PATHFIND_HASH_TILE(key1);

    63

}

    64

#endif

    65

    66

/**

    67

 * Calculates a hash value for use in the NPF.

    68

 * @param key1 The TileIndex of the tile to hash

    69

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

    70

 *

    71

 * @todo Think of a better hash.

    72

 */

    73

static uint NPFHash(uint key1, uint key2)

    74

{

    75

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

    76

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

    77

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

    78

    79

	assert(IsValidTrackdir((Trackdir)key2));

    80

	assert(IsValidTile(key1));

    81

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

    82

}

    83

    84

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

    85

{

    86

	return 0;

    87

}

    88

    89

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

    90

 * for this we assume the station is a rectangle,

    91

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

    92

 */

    93

static TileIndex CalcClosestStationTile(StationID station, TileIndex tile)

    94

{

    95

	const Station* st = GetStation(station);

    96

    97

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

    98

	uint miny = TileY(st->train_tile);

    99

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

   100

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

   101

	uint x;

   102

	uint y;

   103

   106

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

   107

   109

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

   110

   112

	return TileXY(x, y);

   113

}

   114

   115

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

   116

 * takes into account the direction of approach.

   117

 */

   118

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

   119

{

   120

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

   121

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

   122

	TileIndex from = current->tile;

   123

	TileIndex to = fstd->dest_coords;

   124

	uint dist;

   125

   127

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

   128

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

   129

   130

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

   131

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

   132

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

   133

	} else {

   134

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

   135

		dist = NPFDistanceTrack(from, to);

   136

	}

   137

   138

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

   139

   140

	if (dist < ftd->best_bird_dist) {

   141

		ftd->best_bird_dist = dist;

   142

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

   143

	}

   144

	return dist;

   145

}

   146

   147

   148

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

   149

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

   150

 * choice */

   151

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

   152

{

   153

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

   154

		Trackdir trackdir = (Trackdir)current->direction;

   155

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

   156

		 * direction we chose */

   157

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

   158

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

   159

	} else {

   160

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

   161

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

   162

	}

   163

}

   164

   165

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

   166

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

   167

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

   168

static uint NPFTunnelCost(AyStarNode* current)

   169

{

   170

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

   171

	TileIndex tile = current->tile;

   172

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

   173

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

   174

		 * facing the tunnel exit */

   175

		FindLengthOfTunnelResult flotr;

   176

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

   177

		return flotr.length * NPF_TILE_LENGTH;

   179

	} else {

   180

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

   181

		 * straight track */

   182

		return NPF_TILE_LENGTH;

   183

	}

   184

}

   185

   186

static inline uint NPFBridgeCost(AyStarNode *current)

   187

{

   188

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

   189

}

   190

   191

static uint NPFSlopeCost(AyStarNode* current)

   192

{

   193

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

   194

	int x,y;

   195

	int8 z1,z2;

   196

   197

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

   198

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

   199

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

   200

	z1 = GetSlopeZ(x + TILE_SIZE / 2, y + TILE_SIZE / 2);

   201

   202

	x = TileX(next) * TILE_SIZE;

   203

	y = TileY(next) * TILE_SIZE;

   204

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

   205

	z2 = GetSlopeZ(x + TILE_SIZE / 2, y + TILE_SIZE / 2);

   206

   207

	if (z2 - z1 > 1) {

   208

		/* Slope up */

   209

		return _patches.npf_rail_slope_penalty;

   210

	}

   211

	return 0;

   212

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

   213

	 * could just substract that bonus from the penalty, because

   214

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

   215

}

   216

   217

/**

   218

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

   219

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

   220

 */

   221

static void NPFMarkTile(TileIndex tile)

   222

{

   223

#ifndef NO_DEBUG_MESSAGES

   224

	if (_debug_npf_level < 1 || _networking) return;

   225

	switch (GetTileType(tile)) {

   226

		case MP_RAILWAY:

   227

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

   228

			if (!IsTileDepotType(tile, TRANSPORT_RAIL)) {

   229

				SetRailGroundType(tile, RAIL_GROUND_BARREN);

   230

				MarkTileDirtyByTile(tile);

   231

			}

   232

			break;

   233

   234

		case MP_STREET:

   235

			if (!IsTileDepotType(tile, TRANSPORT_ROAD)) {

   236

				SetRoadside(tile, ROADSIDE_BARREN);

   237

				MarkTileDirtyByTile(tile);

   238

			}

   239

			break;

   240

   241

		default:

   242

			break;

   243

	}

   244

#endif

   245

}

   246

   247

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

   248

{

   250

	int32 cost = 0;

   251

	Trackdir trackdir = (Trackdir)current->direction;

   252

   254

   255

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

   257

   258

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

   259

		cost += _patches.npf_water_curve_penalty;

   260

   262

   263

	return cost;

   264

}

   265

   266

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

   267

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

   268

{

   269

	TileIndex tile = current->tile;

   270

	int32 cost = 0;

   271

   272

	/* Determine base length */

   273

	switch (GetTileType(tile)) {

   274

		case MP_TUNNELBRIDGE:

   275

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

   276

			break;

   277

   278

		case MP_STREET:

   279

			cost = NPF_TILE_LENGTH;

   280

			/* Increase the cost for level crossings */

   281

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

   282

			break;

   283

   284

		case MP_STATION:

   285

			cost = NPF_TILE_LENGTH;

   286

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

   287

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

   288

			break;

   289

   290

		default:

   291

			break;

   292

	}

   293

   294

	/* Determine extra costs */

   295

   296

	/* Check for slope */

   297

	cost += NPFSlopeCost(current);

   298

   299

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

   300

	 * represented by non-diagonal tracks */

   301

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

   302

		cost += _patches.npf_road_curve_penalty;

   303

   304

	NPFMarkTile(tile);

   305

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

   306

	return cost;

   307

}

   308

   309

   310

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

   311

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

   312

{

   313

	TileIndex tile = current->tile;

   314

	Trackdir trackdir = (Trackdir)current->direction;

   315

	int32 cost = 0;

   316

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

   317

	OpenListNode new_node;

   318

   319

	/* Determine base length */

   320

	switch (GetTileType(tile)) {

   321

		case MP_TUNNELBRIDGE:

   322

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

   323

			break;

   324

   325

		case MP_RAILWAY:

   326

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

   327

			break;

   328

   329

		case MP_STREET: /* Railway crossing */

   330

			cost = NPF_TILE_LENGTH;

   331

			break;

   332

   333

		case MP_STATION:

   334

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

   335

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

   336

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

   337

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

   338

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

   339

			 * will therefore not make a difference. */

   340

			cost = NPF_TILE_LENGTH + _patches.npf_rail_station_penalty;

   341

			break;

   342

   343

		default:

   344

			break;

   345

	}

   346

   347

	/* Determine extra costs */

   348

   349

	/* Check for signals */

   350

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

   351

		/* Ordinary track with signals */

   352

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

   353

			/* Signal facing us is red */

   354

			if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   355

				/* Penalize the first signal we

   356

				 * encounter, if it is red */

   357

   358

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

   359

				SignalType sigtype = GetSignalType(tile);

   360

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

   361

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

   362

					cost += _patches.npf_rail_firstred_exit_penalty;

   363

				} else {

   364

					cost += _patches.npf_rail_firstred_penalty;

   365

				}

   366

			}

   367

			/* Record the state of this signal */

   368

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true);

   369

		} else {

   370

			/* Record the state of this signal */

   371

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false);

   372

		}

   373

		NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);

   374

	}

   375

   376

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

   377

	 * red */

   378

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

   379

	 * of course... */

   380

	new_node.path.node = *current;

   381

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

   382

		cost += _patches.npf_rail_lastred_penalty;

   383

   384

	/* Check for slope */

   385

	cost += NPFSlopeCost(current);

   386

   387

	/* Check for turns */

   388

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

   389

		cost += _patches.npf_rail_curve_penalty;

   392

   393

	/* Check for reverse in depot */

   394

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

   395

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

   396

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

   397

		 * that) */

   398

		cost += _patches.npf_rail_depot_reverse_penalty;

   399

	}

   400

   401

	/* Check for occupied track */

   402

	//TODO

   403

   404

	NPFMarkTile(tile);

   405

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

   406

	return cost;

   407

}

   408

   409

/* Will find any depot */

   410

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

   411

{

   412

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

   413

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

   414

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

   415

		AYSTAR_FOUND_END_NODE : AYSTAR_DONE;

   416

}

   417

   418

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

   419

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

   420

{

   421

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

   422

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

   423

	TileIndex tile = node->tile;

   424

   425

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

   426

	 * is correct */

   427

	if (

   428

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

   429

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

   430

	) {

   431

		return AYSTAR_FOUND_END_NODE;

   432

	} else {

   433

		return AYSTAR_DONE;

   434

	}

   435

}

   436

   437

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

   438

 * Will fill the contents of the NPFFoundTargetData using

   439

 * AyStarNode[NPF_TRACKDIR_CHOICE].

   440

 */

   441

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

   442

{

   443

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

   444

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

   445

	ftd->best_path_dist = current->g;

   446

	ftd->best_bird_dist = 0;

   447

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

   448

}

   449

   450

/**

   451

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

   452

 * @param owner    The owner of the vehicle.

   453

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

   454

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

   455

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

   456

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

   457

 *                 maybe moved to another file too.

   458

 */

   459

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

   460

{

   461

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

   462

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

   463

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

   464

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

   465

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

   466

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

   467

	}

   468

   469

	switch (GetTileType(tile)) {

   470

		case MP_STREET:

   471

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

   472

			if (IsLevelCrossing(tile) &&

   473

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

   474

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

   475

			}

   476

			break;

   477

   478

		case MP_TUNNELBRIDGE:

   479

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

   480

					(IsBridge(tile) && GetBridgeTransportType(tile) == TRANSPORT_RAIL)) {

   481

				return IsTileOwner(tile, owner);

   482

			}

   483

			break;

   484

   485

		default:

   486

			break;

   487

	}

   488