1

/* $Id$ */

     2

     3

/** @file pathfind.cpp Implementation of the oldest supported pathfinder. */

     4

     5

#include "stdafx.h"

     6

#include "openttd.h"

     7

#include "bridge_map.h"

     8

#include "station_map.h"

     9

#include "tile_cmd.h"

    10

#include "landscape.h"

    11

#include "pathfind.h"

    12

#include "rail_type.h"

    13

#include "debug.h"

    14

#include "tunnel_map.h"

    15

#include "settings_type.h"

    16

#include "tunnelbridge_map.h"

    17

#include "core/random_func.hpp"

    18

#include "core/alloc_type.hpp"

    19

#include "tunnelbridge.h"

    20

    21

/* remember which tiles we have already visited so we don't visit them again. */

    22

static bool TPFSetTileBit(TrackPathFinder *tpf, TileIndex tile, int dir)

    23

{

    24

	uint hash, val, offs;

    25

	TrackPathFinderLink *link, *new_link;

    26

	uint bits = 1 << dir;

    27

    28

	if (tpf->disable_tile_hash)

    29

		return true;

    30

    31

	hash = PATHFIND_HASH_TILE(tile);

    32

    33

	val = tpf->hash_head[hash];

    34

    35

	if (val == 0) {

    36

		/* unused hash entry, set the appropriate bit in it and return true

    37

		 * to indicate that a bit was set. */

    38

		tpf->hash_head[hash] = bits;

    39

		tpf->hash_tile[hash] = tile;

    40

		return true;

    41

	} else if (!(val & 0x8000)) {

    42

		/* single tile */

    43

    44

		if (tile == tpf->hash_tile[hash]) {

    45

			/* found another bit for the same tile,

    46

			 * check if this bit is already set, if so, return false */

    47

			if (val & bits)

    48

				return false;

    49

    50

			/* otherwise set the bit and return true to indicate that the bit

    51

			 * was set */

    52

			tpf->hash_head[hash] = val | bits;

    53

			return true;

    54

		} else {

    55

			/* two tiles with the same hash, need to make a link */

    56

    57

			/* allocate a link. if out of links, handle this by returning

    58

			 * that a tile was already visisted. */

    59

			if (tpf->num_links_left == 0) {

    60

				return false;

    61

			}

    62

			tpf->num_links_left--;

    63

			link = tpf->new_link++;

    64

    65

			/* move the data that was previously in the hash_??? variables

    66

			 * to the link struct, and let the hash variables point to the link */

    67

			link->tile = tpf->hash_tile[hash];

    68

			tpf->hash_tile[hash] = PATHFIND_GET_LINK_OFFS(tpf, link);

    69

    70

			link->flags = tpf->hash_head[hash];

    71

			tpf->hash_head[hash] = 0xFFFF; // multi link

    72

    73

			link->next = 0xFFFF;

    74

		}

    75

	} else {

    76

		/* a linked list of many tiles,

    77

		 * find the one corresponding to the tile, if it exists.

    78

		 * otherwise make a new link */

    79

    80

		offs = tpf->hash_tile[hash];

    81

		do {

    82

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    83

			if (tile == link->tile) {

    84

				/* found the tile in the link list,

    85

				 * check if the bit was alrady set, if so return false to indicate that the

    86

				 * bit was already set */

    87

				if (link->flags & bits)

    88

					return false;

    89

				link->flags |= bits;

    90

				return true;

    91

			}

    92

		} while ((offs=link->next) != 0xFFFF);

    93

	}

    94

    95

	/* get here if we need to add a new link to link,

    96

	 * first, allocate a new link, in the same way as before */

    97

	if (tpf->num_links_left == 0) {

    98

			return false;

    99

	}

   100

	tpf->num_links_left--;

   101

	new_link = tpf->new_link++;

   102

   103

	/* then fill the link with the new info, and establish a ptr from the old

   104

	 * link to the new one */

   105

	new_link->tile = tile;

   106

	new_link->flags = bits;

   107

	new_link->next = 0xFFFF;

   108

   109

	link->next = PATHFIND_GET_LINK_OFFS(tpf, new_link);

   110

	return true;

   111

}

   112

   113

static void TPFModeShip(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)

   114

{

   115

	assert(tpf->tracktype == TRANSPORT_WATER);

   116

   117

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   118

		/* wrong track type */

   119

		if (GetTunnelBridgeTransportType(tile) != tpf->tracktype) return;

   120

   121

		DiagDirection dir = GetTunnelBridgeDirection(tile);

   122

		/* entering tunnel / bridge? */

   123

		if (dir == direction) {

   124

			TileIndex endtile = GetOtherTunnelBridgeEnd(tile);

   125

   126

			tpf->rd.cur_length += GetTunnelBridgeLength(tile, endtile) + 1;

   127

   128

			TPFSetTileBit(tpf, tile, 14);

   129

			TPFSetTileBit(tpf, endtile, 14);

   130

   131

			tile = endtile;

   132

		} else {

   133

			/* leaving tunnel / bridge? */

   134

			if (ReverseDiagDir(dir) != direction) return;

   135

		}

   136

	}

   137

   138

	/* This addition will sometimes overflow by a single tile.

   139

	 * The use of TILE_MASK here makes sure that we still point at a valid

   140

	 * tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail. */

   141

	tile = TILE_MASK(tile + TileOffsByDiagDir(direction));

   142

   143

	if (++tpf->rd.cur_length > 50)

   144

		return;

   145

   146

	TrackBits bits = TrackStatusToTrackBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type)) & DiagdirReachesTracks(direction);

   147

	if (bits == TRACK_BIT_NONE) return;

   148

   149

	assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY());

   150

   151

	bool only_one_track = true;

   152

	do {

   153

		Track track = RemoveFirstTrack(&bits);

   154

		if (bits != TRACK_BIT_NONE) only_one_track = false;

   155

		RememberData rd = tpf->rd;

   156

   157

		/* Change direction 4 times only */

   158

		if (!only_one_track && track != tpf->rd.last_choosen_track) {

   159

			if (++tpf->rd.depth > 4) {

   160

				tpf->rd = rd;

   161

				return;

   162

			}

   163

			tpf->rd.last_choosen_track = track;

   164

		}

   165

   166

		tpf->the_dir = TrackEnterdirToTrackdir(track, direction);

   167

   168

		if (!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length)) {

   169

			TPFModeShip(tpf, tile, TrackdirToExitdir(tpf->the_dir));

   170

		}

   171

   172

		tpf->rd = rd;

   173

	} while (bits != TRACK_BIT_NONE);

   174

   175

}

   176

   177

/**

   178

 * Checks if any vehicle can enter/leave tile in given diagdir

   179

 * Checks only for rail/road depots and road non-drivethrough stations

   180

 * @param tile tile to check

   181

 * @param side side of tile we are trying to leave/enter

   182

 * @param tracktype type of transport

   183

 * @pre tile has trackbit at that diagdir

   184

 * @return true iff vehicle can enter/leve the tile in given side

   185

 */

   186

static inline bool CanAccessTileInDir(TileIndex tile, DiagDirection side, TransportType tracktype)

   187

{

   188

	if (tracktype == TRANSPORT_RAIL) {

   189

		/* depot from wrong side */

   190

		if (IsRailDepotTile(tile) && GetRailDepotDirection(tile) != side) return false;

   191

	} else if (tracktype == TRANSPORT_ROAD) {

   192

		/* depot from wrong side */

   193

		if (IsRoadDepotTile(tile) && GetRoadDepotDirection(tile) != side) return false;

   194

		/* non-driverthrough road station from wrong side */

   195

		if (IsStandardRoadStopTile(tile) && GetRoadStopDir(tile) != side) return false;

   196

	}

   197

   198

	return true;

   199

}

   200

   201

static void TPFModeNormal(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)

   202

{

   203

	const TileIndex tile_org = tile;

   204

   205

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   206

		/* wrong track type */

   207

		if (GetTunnelBridgeTransportType(tile) != tpf->tracktype) return;

   208

   209

		DiagDirection dir = GetTunnelBridgeDirection(tile);

   210

		/* entering tunnel / bridge? */

   211

		if (dir == direction) {

   212

			TileIndex endtile = GetOtherTunnelBridgeEnd(tile);

   213

   214

			tpf->rd.cur_length += GetTunnelBridgeLength(tile, endtile) + 1;

   215

   216

			TPFSetTileBit(tpf, tile, 14);

   217

			TPFSetTileBit(tpf, endtile, 14);

   218

   219

			tile = endtile;

   220

		} else {

   221

			/* leaving tunnel / bridge? */

   222

			if (ReverseDiagDir(dir) != direction) return;

   223

		}

   224

	} else {

   225

		/* can we leave tile in this dir? */

   226

		if (!CanAccessTileInDir(tile, direction, tpf->tracktype)) return;

   227

	}

   228

   229

	tile += TileOffsByDiagDir(direction);

   230

   231

	/* can we enter tile in this dir? */

   232

	if (!CanAccessTileInDir(tile, ReverseDiagDir(direction), tpf->tracktype)) return;

   233

   234

	/* Check if the new tile is a tunnel or bridge head and that the direction

   235

	 * and transport type match */

   236

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   237

		if (GetTunnelBridgeDirection(tile) != direction ||

   238

				GetTunnelBridgeTransportType(tile) != tpf->tracktype) {

   239

			return;

   240

		}

   241

	}

   242

   243

	TrackdirBits trackdirbits = TrackStatusToTrackdirBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type));

   244

   245

	/* Check in case of rail if the owner is the same */

   246

	if (tpf->tracktype == TRANSPORT_RAIL) {

   247

		if (trackdirbits != TRACKDIR_BIT_NONE && TrackStatusToTrackdirBits(GetTileTrackStatus(tile_org, TRANSPORT_RAIL, 0)) != TRACKDIR_BIT_NONE) {

   248

			if (GetTileOwner(tile_org) != GetTileOwner(tile)) return;

   249

		}

   250

	}

   251

   252

	tpf->rd.cur_length++;

   253

   254

	trackdirbits &= DiagdirReachesTrackdirs(direction);

   255

	TrackBits bits = TrackdirBitsToTrackBits(trackdirbits);

   256

   257

	if (bits != TRACK_BIT_NONE) {

   258

		if (!tpf->disable_tile_hash || (tpf->rd.cur_length <= 64 && (KillFirstBit(bits) == 0 || ++tpf->rd.depth <= 7))) {

   259

			do {

   260

				Track track = RemoveFirstTrack(&bits);

   261

   262

				tpf->the_dir = TrackEnterdirToTrackdir(track, direction);

   263

				RememberData rd = tpf->rd;

   264

   265

				/* make sure we are not leaving from invalid side */

   266

				if (TPFSetTileBit(tpf, tile, tpf->the_dir) && CanAccessTileInDir(tile, TrackdirToExitdir(tpf->the_dir), tpf->tracktype) &&

   267

						!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length) ) {

   268

					TPFModeNormal(tpf, tile, TrackdirToExitdir(tpf->the_dir));

   269

				}

   270

				tpf->rd = rd;

   271

			} while (bits != TRACK_BIT_NONE);

   272

		}

   273

	}

   274

}

   275

   276

void FollowTrack(TileIndex tile, PathfindFlags flags, TransportType tt, uint sub_type, DiagDirection direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data)

   277

{

   278

	assert(IsValidDiagDirection(direction));

   279

   280

	SmallStackSafeStackAlloc<TrackPathFinder, 1> tpf;

   281

   282

	/* initialize path finder variables */

   283

	tpf->userdata = data;

   284

	tpf->enum_proc = enum_proc;

   285

	tpf->new_link = tpf->links;

   286

	tpf->num_links_left = lengthof(tpf->links);

   287

   288

	tpf->rd.cur_length = 0;

   289

	tpf->rd.depth = 0;

   290

	tpf->rd.last_choosen_track = INVALID_TRACK;

   291

   292

	tpf->disable_tile_hash = (flags & PATHFIND_FLAGS_DISABLE_TILE_HASH) != 0;

   293

   294

	tpf->tracktype = tt;

   295

	tpf->sub_type = sub_type;

   296

   297

	if ((flags & PATHFIND_FLAGS_SHIP_MODE) != 0) {

   298

		tpf->enum_proc(tile, data, INVALID_TRACKDIR, 0);

   299

		TPFModeShip(tpf, tile, direction);

   300

	} else {

   301

		/* clear the hash_heads */

   302

		memset(tpf->hash_head, 0, sizeof(tpf->hash_head));

   303

		TPFModeNormal(tpf, tile, direction);

   304

	}

   305

   306

	if (after_proc != NULL) after_proc(tpf);

   307

}

   308

   309

struct StackedItem {

   310

	TileIndex tile;

   311

	uint16 cur_length; ///< This is the current length to this tile.

   312

	uint16 priority;   ///< This is the current length + estimated length to the goal.

   313

	TrackdirByte track;

   314

	byte depth;

   315

	byte state;

   316

	byte first_track;

   317

};

   318

   319

struct HashLink {

   320

	TileIndex tile;

   321

	uint16 typelength;

   322

	uint16 next;

   323

};

   324

   325

struct NewTrackPathFinder {

   326

	NTPEnumProc *enum_proc;

   327

	void *userdata;

   328

	TileIndex dest;

   329

   330

	TransportType tracktype;

   331

	RailTypes railtypes;

   332

	uint maxlength;

   333

   334

	HashLink *new_link;

   335

	uint num_links_left;

   336

   337

	uint nstack;

   338

	StackedItem stack[256];     ///< priority queue of stacked items

   339

   340

	uint16 hash_head[0x400];    ///< hash heads. 0 means unused. 0xFFFC = length, 0x3 = dir

   341

	TileIndex hash_tile[0x400]; ///< tiles. or links.

   342

   343

	HashLink links[0x400];      ///< hash links

   344

   345

};

   346

#define NTP_GET_LINK_OFFS(tpf, link) ((byte*)(link) - (byte*)tpf->links)

   347

#define NTP_GET_LINK_PTR(tpf, link_offs) (HashLink*)((byte*)tpf->links + (link_offs))

   348

   349

#define ARR(i) tpf->stack[(i)-1]

   350

   351

/** called after a new element was added in the queue at the last index.

   352

 * move it down to the proper position */

   353

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   354

{

   355

	StackedItem si;

   356

	int i = ++tpf->nstack;

   357

   358

	while (i != 1 && ARR(i).priority < ARR(i>>1).priority) {

   359

		/* the child element is larger than the parent item.

   360

		 * swap the child item and the parent item. */

   361

		si = ARR(i); ARR(i) = ARR(i >> 1); ARR(i >> 1) = si;

   362

		i >>= 1;

   363

	}

   364

}

   365

   366

/** called after the element 0 was eaten. fill it with a new element */

   367

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   368

{

   369

	StackedItem si;

   370

	int i = 1, j;

   371

	int n;

   372

   373

	assert(tpf->nstack > 0);

   374

	n = --tpf->nstack;

   375

   376

	if (n == 0) return; // heap is empty so nothing to do?

   377

   378

	/* copy the last item to index 0. we use it as base for heapify. */

   379

	ARR(1) = ARR(n + 1);

   380

   381

	while ((j = i * 2) <= n) {

   382

		/* figure out which is smaller of the children. */

   383

		if (j != n && ARR(j).priority > ARR(j + 1).priority)

   384

			j++; // right item is smaller

   385

   386

		assert(i <= n && j <= n);

   387

		if (ARR(i).priority <= ARR(j).priority)

   388

			break; // base elem smaller than smallest, done!

   389

   390

		/* swap parent with the child */

   391

		si = ARR(i); ARR(i) = ARR(j); ARR(j) = si;

   392

		i = j;

   393

	}

   394

}

   395

   396

/** mark a tile as visited and store the length of the path.

   397

 * if we already had a better path to this tile, return false.

   398

 * otherwise return true. */

   399

static bool NtpVisit(NewTrackPathFinder* tpf, TileIndex tile, DiagDirection dir, uint length)

   400

{

   401

	uint hash,head;

   402

	HashLink *link, *new_link;

   403

   404

	assert(length < 16384-1);

   405

   406

	hash = PATHFIND_HASH_TILE(tile);

   407

   408

	/* never visited before? */

   409

	if ((head=tpf->hash_head[hash]) == 0) {

   410

		tpf->hash_tile[hash] = tile;

   411

		tpf->hash_head[hash] = dir | (length << 2);

   412

		return true;

   413

	}

   414

   415

	if (head != 0xffff) {

   416

		if (tile == tpf->hash_tile[hash] && (head & 0x3) == (uint)dir) {

   417

   418

			/* longer length */

   419

			if (length >= (head >> 2)) return false;

   420

   421

			tpf->hash_head[hash] = dir | (length << 2);

   422

			return true;

   423

		}

   424

		/* two tiles with the same hash, need to make a link

   425

		 * allocate a link. if out of links, handle this by returning

   426

		 * that a tile was already visisted. */

   427

		if (tpf->num_links_left == 0) {

   428

			DEBUG(ntp, 1, "No links left");

   429

			return false;

   430

		}

   431

   432

		tpf->num_links_left--;

   433

		link = tpf->new_link++;

   434

   435

		/* move the data that was previously in the hash_??? variables

   436

		 * to the link struct, and let the hash variables point to the link */

   437

		link->tile = tpf->hash_tile[hash];

   438

		tpf->hash_tile[hash] = NTP_GET_LINK_OFFS(tpf, link);

   439

   440

		link->typelength = tpf->hash_head[hash];

   441

		tpf->hash_head[hash] = 0xFFFF; // multi link

   442

		link->next = 0xFFFF;

   443

	} else {

   444

		/* a linked list of many tiles,

   445

		 * find the one corresponding to the tile, if it exists.

   446

		 * otherwise make a new link */

   447

   448

		uint offs = tpf->hash_tile[hash];

   449

		do {

   450

			link = NTP_GET_LINK_PTR(tpf, offs);

   451

			if (tile == link->tile && (link->typelength & 0x3U) == (uint)dir) {

   452

				if (length >= (uint)(link->typelength >> 2)) return false;

   453

				link->typelength = dir | (length << 2);

   454

				return true;

   455

			}

   456

		} while ((offs = link->next) != 0xFFFF);

   457

	}

   458

   459

	/* get here if we need to add a new link to link,

   460

	 * first, allocate a new link, in the same way as before */

   461

	if (tpf->num_links_left == 0) {

   462

		DEBUG(ntp, 1, "No links left");

   463

		return false;

   464

	}

   465

	tpf->num_links_left--;

   466

	new_link = tpf->new_link++;

   467

   468

	/* then fill the link with the new info, and establish a ptr from the old

   469

	 * link to the new one */

   470

	new_link->tile = tile;

   471

	new_link->typelength = dir | (length << 2);

   472

	new_link->next = 0xFFFF;

   473

   474

	link->next = NTP_GET_LINK_OFFS(tpf, new_link);

   475

	return true;

   476

}

   477

   478

/**

   479

 * Checks if the shortest path to the given tile/dir so far is still the given

   480

 * length.

   481

 * @return true if the length is still the same

   482

 * @pre    The given tile/dir combination should be present in the hash, by a

   483

 *         previous call to NtpVisit().

   484

 */

   485

static bool NtpCheck(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint length)

   486

{

   487

	uint hash,head,offs;

   488

	HashLink *link;

   489

   490

	hash = PATHFIND_HASH_TILE(tile);

   491

	head=tpf->hash_head[hash];

   492

	assert(head);

   493

   494

	if (head != 0xffff) {

   495

		assert( tpf->hash_tile[hash] == tile && (head & 3) == dir);

   496

		assert( (head >> 2) <= length);