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

    21

    22

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

    23

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

    24

{

    25

	uint hash, val, offs;

    26

	TrackPathFinderLink *link, *new_link;

    27

	uint bits = 1 << dir;

    28

    29

	if (tpf->disable_tile_hash)

    30

		return true;

    31

    32

	hash = PATHFIND_HASH_TILE(tile);

    33

    34

	val = tpf->hash_head[hash];

    35

    36

	if (val == 0) {

    37

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

    38

		 * to indicate that a bit was set. */

    39

		tpf->hash_head[hash] = bits;

    40

		tpf->hash_tile[hash] = tile;

    41

		return true;

    42

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

    43

		/* single tile */

    44

    45

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

    46

			/* found another bit for the same tile,

    47

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

    48

			if (val & bits)

    49

				return false;

    50

    51

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

    52

			 * was set */

    53

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

    54

			return true;

    55

		} else {

    56

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

    57

    58

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

    59

			 * that a tile was already visisted. */

    60

			if (tpf->num_links_left == 0) {

    61

				return false;

    62

			}

    63

			tpf->num_links_left--;

    64

			link = tpf->new_link++;

    65

    66

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

    67

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

    68

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

    69

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

    70

    71

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

    72

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

    73

    74

			link->next = 0xFFFF;

    75

		}

    76

	} else {

    77

		/* a linked list of many tiles,

    78

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

    79

		 * otherwise make a new link */

    80

    81

		offs = tpf->hash_tile[hash];

    82

		do {

    83

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    84

			if (tile == link->tile) {

    85

				/* found the tile in the link list,

    86

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

    87

				 * bit was already set */

    88

				if (link->flags & bits)

    89

					return false;

    90

				link->flags |= bits;

    91

				return true;

    92

			}

    93

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

    94

	}

    95

    96

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

    97

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

    98

	if (tpf->num_links_left == 0) {

    99

			return false;

   100

	}

   101

	tpf->num_links_left--;

   102

	new_link = tpf->new_link++;

   103

   104

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

   105

	 * link to the new one */

   106

	new_link->tile = tile;

   107

	new_link->flags = bits;

   108

	new_link->next = 0xFFFF;

   109

   110

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

   111

	return true;

   112

}

   113

   114

static const byte _bits_mask[4] = {

   115

	0x19,

   116

	0x16,

   117

	0x25,

   118

	0x2A,

   119

};

   120

   121

static const DiagDirection _tpf_new_direction[14] = {

   122

	DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SW, DIAGDIR_SE,

   123

	INVALID_DIAGDIR, INVALID_DIAGDIR,

   124

	DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE,

   125

};

   126

   127

static const DiagDirection _tpf_prev_direction[14] = {

   128

	DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SE, DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SW,

   129

	INVALID_DIAGDIR, INVALID_DIAGDIR,

   130

	DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE, DIAGDIR_NW,

   131

};

   132

   133

   134

static const byte _otherdir_mask[4] = {

   135

	0x10,

   136

	0,

   137

	0x5,

   138

	0x2A,

   139

};

   140

   141

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

   142

{

   143

	RememberData rd;

   144

   145

	assert(tpf->tracktype == TRANSPORT_WATER);

   146

   147

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

   148

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

   149

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

   150

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

   151

   152

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

   153

		return;

   154

   155

	TrackStatus ts = GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type);

   156

	TrackBits bits = (TrackBits)(TrackStatusToTrackBits(ts) & _bits_mask[direction]);

   157

	if (bits == TRACK_BIT_NONE) return;

   158

   159

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

   160

   161

	bool only_one_track = true;

   162

	do {

   163

		Track track = RemoveFirstTrack(&bits);

   164

		if (bits != TRACK_BIT_NONE) only_one_track = false;

   165

		rd = tpf->rd;

   166

   167

		/* Change direction 4 times only */

   168

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

   169

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

   170

				tpf->rd = rd;

   171

				return;

   172

			}

   173

			tpf->rd.last_choosen_track = track;

   174

		}

   175

   176

		tpf->the_dir = (Trackdir)(track + (HasBit(_otherdir_mask[direction], track) ? 8 : 0));

   177

   178

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

   179

			TPFMode2(tpf, tile, _tpf_new_direction[tpf->the_dir]);

   180

		}

   181

   182

		tpf->rd = rd;

   183

	} while (bits != TRACK_BIT_NONE);

   184

   185

}

   186

   187

/**

   188

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

   189

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

   190

 * @param tile tile to check

   191

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

   192

 * @param tracktype type of transport

   193

 * @pre tile has trackbit at that diagdir

   194

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

   195

 */

   196

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

   197

{

   198

	if (tracktype == TRANSPORT_RAIL) {

   199

		/* depot from wrong side */

   200

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

   201

	} else if (tracktype == TRANSPORT_ROAD) {

   202

		/* depot from wrong side */

   203

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

   204

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

   205

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

   206

	}

   207

   208

	return true;

   209

}

   210

   211

static const uint16 _tpfmode1_and[4] = { 0x1009, 0x16, 0x520, 0x2A00 };

   212

   213

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

   214

{

   215

	const TileIndex tile_org = tile;

   216

   217

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   218

		/* wrong track type */

   219

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

   220

   221

		DiagDirection dir = GetTunnelBridgeDirection(tile);

   222

		/* entering tunnel / bridge? */

   223

		if (dir == direction) {

   224

			TileIndex endtile = GetOtherTunnelBridgeEnd(tile);

   225

   226

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

   227

   228

			TPFSetTileBit(tpf, tile, 14);

   229

			TPFSetTileBit(tpf, endtile, 14);

   230

   231

			tile = endtile;

   232

		} else {

   233

			/* leaving tunnel / bridge? */

   234

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

   235

		}

   236

	} else {

   237

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

   238

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

   239

	}

   240

   241

	tile += TileOffsByDiagDir(direction);

   242

   243

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

   244

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

   245

   246

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

   247

	 * and transport type match */

   248

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   249

		if (GetTunnelBridgeDirection(tile) != direction ||

   250

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

   251

			return;

   252

		}

   253

	}

   254

   255

	uint32 bits = TrackStatusToTrackdirBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type));

   256

   257

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

   258

	if (tpf->tracktype == TRANSPORT_RAIL) {

   259

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

   260

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

   261

		}

   262

	}

   263

   264

	tpf->rd.cur_length++;

   265

   266

	if ((byte)bits != tpf->var2) {

   267

		bits &= _tpfmode1_and[direction];

   268

		bits |= bits >> 8;

   269

	}

   270

	bits &= 0xBF;

   271

   272

	if (bits != 0) {

   273

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

   274

			do {

   275

				int i = FIND_FIRST_BIT(bits);

   276

				bits = KillFirstBit(bits);

   277

   278

				tpf->the_dir = (Trackdir)((_otherdir_mask[direction] & (byte)(1 << i)) ? (i + 8) : i);

   279

				RememberData rd = tpf->rd;

   280

   281

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

   282

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

   283

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

   284

					TPFMode1(tpf, tile, _tpf_new_direction[tpf->the_dir]);

   285

				}

   286

				tpf->rd = rd;

   287

			} while (bits != 0);

   288

		}

   289

	}

   290

}

   291

   292

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

   293

{

   294

	TrackPathFinder tpf;

   295

   296

	assert(direction < 4);

   297

   298

	/* initialize path finder variables */

   299

	tpf.userdata = data;

   300

	tpf.enum_proc = enum_proc;

   301

	tpf.new_link = tpf.links;

   302

	tpf.num_links_left = lengthof(tpf.links);

   303

   304

	tpf.rd.cur_length = 0;

   305

	tpf.rd.depth = 0;

   306

	tpf.rd.last_choosen_track = INVALID_TRACK;

   307

   308

	tpf.var2 = HasBit(flags, 15) ? 0x43 : 0xFF; // 0x8000

   309

   310

	tpf.disable_tile_hash = HasBit(flags, 12);  // 0x1000

   311

   312

   313

	tpf.tracktype = (TransportType)(flags & 0xFF);

   314

	tpf.sub_type = sub_type;

   315

   316

	if (HasBit(flags, 11)) {

   317

		tpf.enum_proc(tile, data, INVALID_TRACKDIR, 0);

   318

		TPFMode2(&tpf, tile, direction);

   319

	} else {

   320

		/* clear the hash_heads */

   321

		memset(tpf.hash_head, 0, sizeof(tpf.hash_head));

   322

		TPFMode1(&tpf, tile, direction);

   323

	}

   324

   325

	if (after_proc != NULL)

   326

		after_proc(&tpf);

   327

}

   328

   329

struct StackedItem {

   330

	TileIndex tile;

   331

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

   332

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

   333

	TrackdirByte track;

   334

	byte depth;

   335

	byte state;

   336

	byte first_track;

   337

};

   338

   339

static const Trackdir _new_trackdir[6][4] = {

   340

{TRACKDIR_X_NE,    INVALID_TRACKDIR, TRACKDIR_X_SW,    INVALID_TRACKDIR,},

   341

{INVALID_TRACKDIR, TRACKDIR_Y_SE,    INVALID_TRACKDIR, TRACKDIR_Y_NW,},

   342

{INVALID_TRACKDIR, TRACKDIR_UPPER_E, TRACKDIR_UPPER_W, INVALID_TRACKDIR,},

   343

{TRACKDIR_LOWER_E, INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_LOWER_W,},

   344

{TRACKDIR_LEFT_N,  TRACKDIR_LEFT_S,  INVALID_TRACKDIR, INVALID_TRACKDIR,},

   345

{INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_RIGHT_S, TRACKDIR_RIGHT_N,},

   346

};

   347

   348

struct HashLink {

   349

	TileIndex tile;

   350

	uint16 typelength;

   351

	uint16 next;

   352

};

   353

   354

struct NewTrackPathFinder {

   355

	NTPEnumProc *enum_proc;

   356

	void *userdata;

   357

	TileIndex dest;

   358

   359

	TransportType tracktype;

   360

	RailTypes railtypes;

   361

	uint maxlength;

   362

   363

	HashLink *new_link;

   364

	uint num_links_left;

   365

   366

	uint nstack;

   367

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

   368

   369

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

   370

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

   371

   372

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

   373

   374

};

   375

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

   376

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

   377

   378

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

   379

   380

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

   381

 * move it down to the proper position */

   382

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   383

{

   384

	StackedItem si;

   385

	int i = ++tpf->nstack;

   386

   387

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

   388

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

   389

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

   390

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

   391

		i >>= 1;

   392

	}

   393

}

   394

   395

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

   396

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   397

{

   398

	StackedItem si;

   399

	int i = 1, j;

   400

	int n;

   401

   402

	assert(tpf->nstack > 0);

   403

	n = --tpf->nstack;

   404

   405

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

   406

   407

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

   408

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

   409

   410

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

   411

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

   412

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

   413

			j++; // right item is smaller

   414

   415

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

   416

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

   417

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

   418

   419

		/* swap parent with the child */

   420

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

   421

		i = j;

   422

	}

   423

}

   424

   425

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

   426

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

   427

 * otherwise return true. */

   428

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

   429

{

   430

	uint hash,head;

   431

	HashLink *link, *new_link;

   432

   433

	assert(length < 16384-1);

   434

   435

	hash = PATHFIND_HASH_TILE(tile);

   436

   437

	/* never visited before? */

   438

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

   439

		tpf->hash_tile[hash] = tile;

   440

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

   441

		return true;

   442

	}

   443

   444

	if (head != 0xffff) {

   445

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

   446

   447

			/* longer length */

   448

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

   449

   450

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

   451

			return true;

   452

		}

   453

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

   454

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

   455

		 * that a tile was already visisted. */

   456

		if (tpf->num_links_left == 0) {

   457

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

   458

			return false;

   459

		}

   460

   461

		tpf->num_links_left--;

   462

		link = tpf->new_link++;

   463

   464

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

   465

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

   466

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

   467

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

   468

   469

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

   470

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

   471

		link->next = 0xFFFF;

   472

	} else {

   473

		/* a linked list of many tiles,

   474

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

   475

		 * otherwise make a new link */

   476

   477

		uint offs = tpf->hash_tile[hash];

   478

		do {

   479

			link = NTP_GET_LINK_PTR(tpf, offs);

   480

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

   481

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

   482

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

   483

				return true;

   484

			}

   485

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

   486

	}

   487

   488

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

   489

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

   490

	if (tpf->num_links_left == 0) {

   491

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

   492

		return false;

   493

	}

   494

	tpf->num_links_left--;

   495

	new_link = tpf->new_link++;

   496

   497

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