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

static uint NTPHash(uint key1, uint key2)

    25

{

    26

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

    27

	return PATHFIND_HASH_TILE(key1);

    28

}

    29

    30

/**

    31

 * Calculates a hash value for use in the NPF.

    32

 * @param key1	The TileIndex of the tile to hash

    33

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

    34

 *

    35

 * @todo	Think of a better hash.

    36

 */

    37

static uint NPFHash(uint key1, uint key2)

    38

{

    39

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

    40

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

    41

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

    42

    43

	assert(IsValidTrackdir(key2));

    44

	assert(IsValidTile(key1));

    45

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

    46

}

    47

    48

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

    49

{

    50

	return 0;

    51

}

    52

    53

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

    54

 * for this we assume the station is a rectangle,

    55

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

    56

 */

    57

static TileIndex CalcClosestStationTile(StationID station, TileIndex tile)

    58

{

    59

	const Station* st = GetStation(station);

    60

    61

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

    62

	uint miny = TileY(st->train_tile);

    63

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

    64

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

    65

	uint x;

    66

	uint y;

    67

    68

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

    69

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

    70

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

    71

    72

	// same for y coordinate, see above comment

    73

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

    74

    75

	// return the tile of our target coordinates

    76

	return TileXY(x, y);

    77

};

    78

    79

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

    80

 * takes into account the direction of approach.

    81

 */

    82

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

    83

{

    84

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

    85

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

    86

	TileIndex from = current->tile;

    87

	TileIndex to = fstd->dest_coords;

    88

	uint dist;

    89

    90

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

    91

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

    92

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

    93

    94

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

    95

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

    96

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

    97

	else

    98

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

    99

		dist = DistanceTrack(from, to) * NPF_TILE_LENGTH;

   100

   101

	if (dist < ftd->best_bird_dist) {

   102

		ftd->best_bird_dist = dist;

   103

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

   104

	}

   105

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

   106

	return dist;

   107

}

   108

   109

   110

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

   111

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

   112

 * choice */

   113

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

   114

{

   115

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

   116

		Trackdir trackdir = (Trackdir)current->direction;

   117

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

   118

		 * direction we chose */

   119

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

   120

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

   121

	} else {

   122

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

   123

		 * decision */

   124

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

   125

	}

   126

   127

}

   128

   129

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

   130

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

   131

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

   132

static uint NPFTunnelCost(AyStarNode* current)

   133

{

   134

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

   135

	TileIndex tile = current->tile;

   136

	if ( (DiagDirection)(_map5[tile] & 3) == ReverseDiagdir(exitdir)) {

   137

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

   138

		 * facing the tunnel exit */

   139

		FindLengthOfTunnelResult flotr;

   140

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

   141

		return flotr.length * NPF_TILE_LENGTH;

   142

		//TODO: Penalty for tunnels?

   143

	} else {

   144

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

   145

		 * straight track */

   146

		return NPF_TILE_LENGTH;

   147

	}

   148

}

   149

   150

static uint NPFSlopeCost(AyStarNode* current)

   151

{

   152

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

   153

	int x,y;

   154

	int8 z1,z2;

   155

   156

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

   157

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

   158

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

   159

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

   160

   161

	x = TileX(next) * TILE_SIZE;

   162

	y = TileY(next) * TILE_SIZE;

   163

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

   164

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

   165

   166

	if ((z2 - z1) > 1) {

   167

		/* Slope up */

   168

		return _patches.npf_rail_slope_penalty;

   169

	}

   170

	return 0;

   171

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

   172

	 * could just substract that bonus from the penalty, because

   173

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

   174

}

   175

   176

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

   177

static void NPFMarkTile(TileIndex tile)

   178

{

   179

#ifdef NO_DEBUG_MESSAGES

   180

	return;

   181

#else

   182

	if (_debug_npf_level >= 1)

   183

		switch(GetTileType(tile)) {

   184

			case MP_RAILWAY:

   185

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

   186

				 * ;-) */

   187

				if (!IsTileDepotType(tile, TRANSPORT_RAIL)) {

   188

					_map2[tile] &= ~15; /* Clear bits 0-3 */

   189

					MarkTileDirtyByTile(tile);

   190

				}

   191

				break;

   192

			case MP_STREET:

   193

				if (!IsTileDepotType(tile, TRANSPORT_ROAD)) {

   194

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

   195

					MarkTileDirtyByTile(tile);

   196

				}

   197

				break;

   198

			default:

   199

				break;

   200

		}

   201

#endif

   202

}

   203

   204

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

   205

{

   206

	//TileIndex tile = current->tile;

   207

	int32 cost = 0;

   208

	Trackdir trackdir = (Trackdir)current->direction;

   209

   210

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

   211

   212

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

   213

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

   214

   215

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

   216

		cost += _patches.npf_water_curve_penalty;

   217

   218

	/* TODO More penalties? */

   219

   220

	return cost;

   221

}

   222

   223

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

   224

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

   225

{

   226

	TileIndex tile = current->tile;

   227

	int32 cost = 0;

   228

   229

	/* Determine base length */

   230

	switch (GetTileType(tile)) {

   231

		case MP_TUNNELBRIDGE:

   232

			if ((_map5[tile] & 0xF0)==0) {

   233

				cost = NPFTunnelCost(current);

   234

				break;

   235

			}

   236

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

   237

			 * then. We treat that as ordinary rail */

   238

		case MP_STREET:

   239

			cost = NPF_TILE_LENGTH;

   240

			break;

   241

		default:

   242

			break;

   243

	}

   244

   245

	/* Determine extra costs */

   246

   247

	/* Check for slope */

   248

	cost += NPFSlopeCost(current);

   249

   250

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

   251

	 * represented by non-diagonal tracks */

   252

	if (!IsDiagonalTrackdir(current->direction))

   253

		cost += _patches.npf_road_curve_penalty;

   254

   255

	NPFMarkTile(tile);

   256

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

   257

	return cost;

   258

}

   259

   260

   261

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

   262

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

   263

{

   264

	TileIndex tile = current->tile;

   265

	Trackdir trackdir = (Trackdir)current->direction;

   266

	int32 cost = 0;

   267

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

   268

	OpenListNode new_node;

   269

   270

	/* Determine base length */

   271

	switch (GetTileType(tile)) {

   272

		case MP_TUNNELBRIDGE:

   273

			if ((_map5[tile] & 0xF0)==0) {

   274

				cost = NPFTunnelCost(current);

   275

				break;

   276

			}

   277

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

   278

			 * then. We treat that as ordinary rail */

   279

		case MP_RAILWAY:

   280

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

   281

			break;

   282

		case MP_STREET: /* Railway crossing */

   283

			cost = NPF_TILE_LENGTH;

   284

			break;

   285

		case MP_STATION:

   286

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

   287

					* want to give station tiles that are not our destination

   288

					* this penalty. This would discourage trains to drive through

   289

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

   290

					* penalty, because every possible route will get this penalty

   291

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

   292

			* will therefore not make a difference. */

   293

			cost = NPF_TILE_LENGTH + _patches.npf_rail_station_penalty;

   294

			break;

   295

		default:

   296

			break;

   297

	}

   298

   299

	/* Determine extra costs */

   300

   301

	/* Check for signals */

   302

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

   303

		/* Ordinary track with signals */

   304

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

   305

			/* Signal facing us is red */

   306

			if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {

   307

				/* Penalize the first signal we

   308

				 * encounter, if it is red */

   309

   310

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

   311

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

   312

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

   313

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

   314

					cost += _patches.npf_rail_firstred_exit_penalty;

   315

				else

   316

					cost += _patches.npf_rail_firstred_penalty;

   317

			}

   318

			/* Record the state of this signal */

   319

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true);

   320

		} else {

   321

			/* Record the state of this signal */

   322

			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false);

   323

		}

   324

		NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);

   325

	}

   326

   327

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

   328

	 * red */

   329

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

   330

	 * of course... */

   331

	new_node.path.node = *current;

   332

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

   333

		cost += _patches.npf_rail_lastred_penalty;

   334

   335

	/* Check for slope */

   336

	cost += NPFSlopeCost(current);

   337

   338

	/* Check for turns */

   339

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

   340

		cost += _patches.npf_rail_curve_penalty;

   341

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

   342

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

   343

   344

	/* Check for reverse in depot */

   345

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

   346

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

   347

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

   348

		 * that) */

   349

		cost += _patches.npf_rail_depot_reverse_penalty;

   350

   351

	/* Check for occupied track */

   352

	//TODO

   353

   354

	NPFMarkTile(tile);

   355

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

   356

	return cost;

   357

}

   358

   359

/* Will find any depot */

   360

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

   361

{

   362

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

   363

   364

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

   365

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

   366

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

   367

		return AYSTAR_FOUND_END_NODE;

   368

	else

   369

		return AYSTAR_DONE;

   370

}

   371

   372

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

   373

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

   374

{

   375

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

   376

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

   377

	TileIndex tile = node->tile;

   378

   379

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

   380

	 * is correct */

   381

	if (

   382

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

   383

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

   384

	) {

   385

		return AYSTAR_FOUND_END_NODE;

   386

	} else {

   387

		return AYSTAR_DONE;

   388

	}

   389

}

   390

   391

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

   392

 * Will fill the contents of the NPFFoundTargetData using

   393

 * AyStarNode[NPF_TRACKDIR_CHOICE].

   394

 */

   395

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

   396

{

   397

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

   398

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

   399

	ftd->best_path_dist = current->g;

   400

	ftd->best_bird_dist = 0;

   401

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

   402

}

   403

   404

/**

   405

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

   406

 * @param owner    The owner of the vehicle.

   407

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

   408

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

   409

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

   410

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

   411

 *                 maybe moved to another file too.

   412

 */

   413

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

   414

{

   415

	if (

   416

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

   417

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

   418

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

   419

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

   420

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

   421

		)

   422

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

   423

   424

	switch (GetTileType(tile)) {

   425

		case MP_STREET:

   426

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

   427

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

   428

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

   429

			break;

   430

		case MP_TUNNELBRIDGE:

   431

#if 0

   432

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

   433

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

   434

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

   435

 */

   436

			if ((_map5[tile] & 0xC6) == 0xC0 && (unsigned)(_map5[tile] & 0x1) == (enterdir & 0x1)) {

   437

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

   438

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

   439

					tile += TileOffsByDir(_map5[tile] & 0x1);

   440

				}

   441

			}

   442

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

   443

#endif

   444

			if (

   445

				(_map5[tile] & 0xFC) == 0 /* railway tunnel */

   446

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

   447

				|| ((_map5[tile] & 0xF8) == 0xE0 && ((unsigned)_map5[tile] & 0x1) != (enterdir & 0x1)) /* railway under bridge */

   448

				)

   449

				return IsTileOwner(tile, owner);

   450

			break;

   451

		default:

   452

			break;

   453

	}

   454

   455

	return true; /* no need to check */

   456

}

   457

   458

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

   459

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

   460

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

   461

 * entry and exit are neighbours. Will fill

   462

 * AyStarNode.user_data[NPF_TRACKDIR_CHOICE] with an appropriate value, and

   463

 * copy AyStarNode.user_data[NPF_NODE_FLAGS] from the parent */

   464

static void NPFFollowTrack(AyStar* aystar, OpenListNode* current)

   465

{

   466

	Trackdir src_trackdir = (Trackdir)current->path.node.direction;

   467

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

   468

	DiagDirection src_exitdir = TrackdirToExitdir(src_trackdir);

   469

	FindLengthOfTunnelResult flotr;

   470

	TileIndex dst_tile;

   471

	int i;

   472

	TrackdirBits trackdirbits, ts;

   473

	TransportType type = aystar->user_data[NPF_TYPE];

   474

	/* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */

   475

	aystar->num_neighbours = 0;

   476

	DEBUG(npf, 4)("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile);

   477

   478

	/* Find dest tile */

   479

	if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (DiagDirection)(_map5[src_tile] & 3) == src_exitdir) {

   480

		/* This is a tunnel. We know this tunnel is our type,

   481

		 * otherwise we wouldn't have got here. It is also facing us,

   482

		 * so we should skip it's body */

   483

		flotr = FindLengthOfTunnel(src_tile, src_exitdir);

   484

		dst_tile = flotr.tile;

   485

	} else {

   486

		if (type != TRANSPORT_WATER && (IsRoadStationTile(src_tile) || IsTileDepotType(src_tile, type))){

   487

			/* This is a road station or a train or road depot. We can enter and exit

   488

			 * those from one side only. Trackdirs don't support that (yet), so we'll

   489

			 * do this here. */

   490

   491

			DiagDirection exitdir;

   492

			/* Find out the exit direction first */

   493

			if (IsRoadStationTile(src_tile))

   494

				exitdir = GetRoadStationDir(src_tile);

   495

			else /* Train or road depot. Direction is stored the same for both, in map5 */

   496

				exitdir = GetDepotDirection(src_tile, type);

   497

   498

			/* Let's see if were headed the right way into the depot, and reverse