1

/* $Id$ */

     2

     3

/** @file pathfind.cpp */

     4

     5

#include "stdafx.h"

     6

#include "openttd.h"

     7

#include "bridge_map.h"

     8

#include "station_map.h"

     9

#include "depot.h"

    10

#include "tile_cmd.h"

    11

#include "landscape.h"

    12

#include "pathfind.h"

    13

#include "rail_type.h"

    14

#include "debug.h"

    15

#include "tunnel_map.h"

    16

#include "settings_type.h"

    17

#include "depot.h"

    18

#include "tunnelbridge_map.h"

    19

#include "core/random_func.hpp"

    20

#include "core/alloc_func.hpp"

    21

#include "tunnelbridge.h"

    22

    23

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

    24

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

    25

{

    26

	uint hash, val, offs;

    27

	TrackPathFinderLink *link, *new_link;

    28

	uint bits = 1 << dir;

    29

    30

	if (tpf->disable_tile_hash)

    31

		return true;

    32

    33

	hash = PATHFIND_HASH_TILE(tile);

    34

    35

	val = tpf->hash_head[hash];

    36

    37

	if (val == 0) {

    38

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

    39

		 * to indicate that a bit was set. */

    40

		tpf->hash_head[hash] = bits;

    41

		tpf->hash_tile[hash] = tile;

    42

		return true;

    43

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

    44

		/* single tile */

    45

    46

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

    47

			/* found another bit for the same tile,

    48

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

    49

			if (val & bits)

    50

				return false;

    51

    52

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

    53

			 * was set */

    54

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

    55

			return true;

    56

		} else {

    57

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

    58

    59

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

    60

			 * that a tile was already visisted. */

    61

			if (tpf->num_links_left == 0) {

    62

				return false;

    63

			}

    64

			tpf->num_links_left--;

    65

			link = tpf->new_link++;

    66

    67

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

    68

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

    69

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

    70

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

    71

    72

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

    73

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

    74

    75

			link->next = 0xFFFF;

    76

		}

    77

	} else {

    78

		/* a linked list of many tiles,

    79

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

    80

		 * otherwise make a new link */

    81

    82

		offs = tpf->hash_tile[hash];

    83

		do {

    84

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    85

			if (tile == link->tile) {

    86

				/* found the tile in the link list,

    87

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

    88

				 * bit was already set */

    89

				if (link->flags & bits)

    90

					return false;

    91

				link->flags |= bits;

    92

				return true;

    93

			}

    94

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

    95

	}

    96

    97

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

    98

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

    99

	if (tpf->num_links_left == 0) {

   100

			return false;

   101

	}

   102

	tpf->num_links_left--;

   103

	new_link = tpf->new_link++;

   104

   105

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

   106

	 * link to the new one */

   107

	new_link->tile = tile;

   108

	new_link->flags = bits;

   109

	new_link->next = 0xFFFF;

   110

   111

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

   112

	return true;

   113

}

   114

   115

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

   116

{

   117

	RememberData rd;

   118

   119

	assert(tpf->tracktype == TRANSPORT_WATER);

   120

   121

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

   122

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

   123

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

   124

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

   125

   126

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

   127

		return;

   128

   129

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

   130

	if (bits == TRACK_BIT_NONE) return;

   131

   132

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

   133

   134

	bool only_one_track = true;

   135

	do {

   136

		Track track = RemoveFirstTrack(&bits);

   137

		if (bits != TRACK_BIT_NONE) only_one_track = false;

   138

		rd = tpf->rd;

   139

   140

		/* Change direction 4 times only */

   141

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

   142

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

   143

				tpf->rd = rd;

   144

				return;

   145

			}

   146

			tpf->rd.last_choosen_track = track;

   147

		}

   148

   149

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

   150

   151

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

   152

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

   153

		}

   154

   155

		tpf->rd = rd;

   156

	} while (bits != TRACK_BIT_NONE);

   157

   158

}

   159

   160

/**

   161

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

   162

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

   163

 * @param tile tile to check

   164

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

   165

 * @param tracktype type of transport

   166

 * @pre tile has trackbit at that diagdir

   167

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

   168

 */

   169

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

   170

{

   171

	if (tracktype == TRANSPORT_RAIL) {

   172

		/* depot from wrong side */

   173

		if (IsTileDepotType(tile, TRANSPORT_RAIL) && GetRailDepotDirection(tile) != side) return false;

   174

	} else if (tracktype == TRANSPORT_ROAD) {

   175

		/* depot from wrong side */

   176

		if (IsTileDepotType(tile, TRANSPORT_ROAD) && GetRoadDepotDirection(tile) != side) return false;

   177

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

   178

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

   179

	}

   180

   181

	return true;

   182

}

   183

   184

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

   185

{

   186

	const TileIndex tile_org = tile;

   187

   188

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   189

		/* wrong track type */

   190

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

   191

   192

		DiagDirection dir = GetTunnelBridgeDirection(tile);

   193

		/* entering tunnel / bridge? */

   194

		if (dir == direction) {

   195

			TileIndex endtile = GetOtherTunnelBridgeEnd(tile);

   196

   197

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

   198

   199

			TPFSetTileBit(tpf, tile, 14);

   200

			TPFSetTileBit(tpf, endtile, 14);

   201

   202

			tile = endtile;

   203

		} else {

   204

			/* leaving tunnel / bridge? */

   205

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

   206

		}

   207

	} else {

   208

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

   209

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

   210

	}

   211

   212

	tile += TileOffsByDiagDir(direction);

   213

   214

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

   215

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

   216

   217

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

   218

	 * and transport type match */

   219

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   220

		if (GetTunnelBridgeDirection(tile) != direction ||

   221

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

   222

			return;

   223

		}

   224

	}

   225

   226

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

   227

   228

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

   229

	if (tpf->tracktype == TRANSPORT_RAIL) {

   230

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

   231

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

   232

		}

   233

	}

   234

   235

	tpf->rd.cur_length++;

   236

   237

	trackdirbits &= DiagdirReachesTrackdirs(direction);

   238

	TrackBits bits = TrackdirBitsToTrackBits(trackdirbits);

   239

   240

	if (bits != TRACK_BIT_NONE) {

   241

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

   242

			do {

   243

				Track track = RemoveFirstTrack(&bits);

   244

   245

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

   246

				RememberData rd = tpf->rd;

   247

   248

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

   249

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

   250

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

   251

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

   252

				}

   253

				tpf->rd = rd;

   254

			} while (bits != TRACK_BIT_NONE);

   255

		}

   256

	}

   257

}

   258

   259

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

   260

{

   261

	assert(IsValidDiagDirection(direction));

   262

   263

	SmallStackSafeStackAlloc<TrackPathFinder, 1> tpf;

   264

   265

	/* initialize path finder variables */

   266

	tpf->userdata = data;

   267

	tpf->enum_proc = enum_proc;

   268

	tpf->new_link = tpf->links;

   269

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

   270

   271

	tpf->rd.cur_length = 0;

   272

	tpf->rd.depth = 0;

   273

	tpf->rd.last_choosen_track = INVALID_TRACK;

   274

   275

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

   276

   277

	tpf->tracktype = tt;

   278

	tpf->sub_type = sub_type;

   279

   280

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

   281

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

   282

		TPFModeShip(tpf, tile, direction);

   283

	} else {

   284

		/* clear the hash_heads */

   285

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

   286

		TPFModeNormal(tpf, tile, direction);

   287

	}

   288

   289

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

   290

}

   291

   292

struct StackedItem {

   293

	TileIndex tile;

   294

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

   295

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

   296

	TrackdirByte track;

   297

	byte depth;

   298

	byte state;

   299

	byte first_track;

   300

};

   301

   302

struct HashLink {

   303

	TileIndex tile;

   304

	uint16 typelength;

   305

	uint16 next;

   306

};

   307

   308

struct NewTrackPathFinder {

   309

	NTPEnumProc *enum_proc;

   310

	void *userdata;

   311

	TileIndex dest;

   312

   313

	TransportType tracktype;

   314

	RailTypes railtypes;

   315

	uint maxlength;

   316

   317

	HashLink *new_link;

   318

	uint num_links_left;

   319

   320

	uint nstack;

   321

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

   322

   323

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

   324

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

   325

   326

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

   327

   328

};

   329

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

   330

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

   331

   332

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

   333

   334

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

   335

 * move it down to the proper position */

   336

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   337

{

   338

	StackedItem si;

   339

	int i = ++tpf->nstack;

   340

   341

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

   342

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

   343

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

   344

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

   345

		i >>= 1;

   346

	}

   347

}

   348

   349

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

   350

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   351

{

   352

	StackedItem si;

   353

	int i = 1, j;

   354

	int n;

   355

   356

	assert(tpf->nstack > 0);

   357

	n = --tpf->nstack;

   358

   359

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

   360

   361

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

   362

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

   363

   364

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

   365

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

   366

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

   367

			j++; // right item is smaller

   368

   369

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

   370

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

   371

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

   372

   373

		/* swap parent with the child */

   374

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

   375

		i = j;

   376

	}

   377

}

   378

   379

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

   380

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

   381

 * otherwise return true. */

   382

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

   383

{

   384

	uint hash,head;

   385

	HashLink *link, *new_link;

   386

   387

	assert(length < 16384-1);

   388

   389

	hash = PATHFIND_HASH_TILE(tile);

   390

   391

	/* never visited before? */

   392

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

   393

		tpf->hash_tile[hash] = tile;

   394

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

   395

		return true;

   396

	}

   397

   398

	if (head != 0xffff) {

   399

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

   400

   401

			/* longer length */

   402

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

   403

   404

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

   405

			return true;

   406

		}

   407

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

   408

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

   409

		 * that a tile was already visisted. */

   410

		if (tpf->num_links_left == 0) {

   411

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

   412

			return false;

   413

		}

   414

   415

		tpf->num_links_left--;

   416

		link = tpf->new_link++;

   417

   418

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

   419

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

   420

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

   421

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

   422

   423

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

   424

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

   425

		link->next = 0xFFFF;

   426

	} else {

   427

		/* a linked list of many tiles,

   428

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

   429

		 * otherwise make a new link */

   430

   431

		uint offs = tpf->hash_tile[hash];

   432

		do {

   433

			link = NTP_GET_LINK_PTR(tpf, offs);

   434

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

   435

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

   436

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

   437

				return true;

   438

			}

   439

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

   440

	}

   441

   442

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

   443

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

   444

	if (tpf->num_links_left == 0) {

   445

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

   446

		return false;

   447

	}

   448

	tpf->num_links_left--;

   449

	new_link = tpf->new_link++;

   450

   451

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

   452

	 * link to the new one */

   453

	new_link->tile = tile;

   454

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

   455

	new_link->next = 0xFFFF;

   456

   457

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

   458

	return true;

   459

}

   460

   461

/**

   462

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

   463

 * length.

   464

 * @return true if the length is still the same

   465

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

   466

 *         previous call to NtpVisit().

   467

 */

   468

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

   469

{

   470

	uint hash,head,offs;

   471

	HashLink *link;

   472

   473

	hash = PATHFIND_HASH_TILE(tile);

   474

	head=tpf->hash_head[hash];

   475

	assert(head);

   476

   477

	if (head != 0xffff) {

   478

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

   479

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

   480

		return length == (head >> 2);

   481

	}

   482

   483

	/* else it's a linked list of many tiles */

   484

	offs = tpf->hash_tile[hash];

   485

	for (;;) {

   486

		link = NTP_GET_LINK_PTR(tpf, offs);

   487

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

   488

			assert((uint)(link->typelength >> 2) <= length);

   489

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

   490

		}

   491

		offs = link->next;

   492

		assert(offs != 0xffff);

   493

	}

   494

}

   495

   496