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

    11

#include "landscape.h"

    12

#include "map.h"

    13

#include "tile.h"

    14

#include "pathfind.h"

    15

#include "rail.h"

    16

#include "debug.h"

    17

#include "tunnel_map.h"

    18

#include "variables.h"

    19

#include "depot.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 const byte _bits_mask[4] = {

   114

	0x19,

   115

	0x16,

   116

	0x25,

   117

	0x2A,

   118

};

   119

   120

static const DiagDirection _tpf_new_direction[14] = {

   121

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

   122

	INVALID_DIAGDIR, INVALID_DIAGDIR,

   123

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

   124

};

   125

   126

static const DiagDirection _tpf_prev_direction[14] = {

   127

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

   128

	INVALID_DIAGDIR, INVALID_DIAGDIR,

   129

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

   130

};

   131

   132

   133

static const byte _otherdir_mask[4] = {

   134

	0x10,

   135

	0,

   136

	0x5,

   137

	0x2A,

   138

};

   139

   140

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

   141

{

   142

	uint bits;

   143

	int i;

   144

	RememberData rd;

   145

   146

	assert(tpf->tracktype == TRANSPORT_WATER);

   147

   148

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

   149

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

   150

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

   151

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

   152

   153

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

   154

		return;

   155

   156

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

   157

	bits = (byte)((bits | (bits >> 8)) & _bits_mask[direction]);

   158

	if (bits == 0)

   159

		return;

   160

   161

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

   162

   163

	if ( (bits & (bits - 1)) == 0 ) {

   164

		/* only one direction */

   165

		i = 0;

   166

		while (!(bits & 1))

   167

			i++, bits >>= 1;

   168

   169

		rd = tpf->rd;

   170

		goto continue_here;

   171

	}

   172

	/* several directions */

   173

	i=0;

   174

	do {

   175

		if (!(bits & 1)) continue;

   176

		rd = tpf->rd;

   177

   178

		/* Change direction 4 times only */

   179

		if ((byte)i != tpf->rd.pft_var6) {

   180

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

   181

				tpf->rd = rd;

   182

				return;

   183

			}

   184

			tpf->rd.pft_var6 = (byte)i;

   185

		}

   186

   187

continue_here:;

   188

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

   189

   190

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

   191

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

   192

		}

   193

   194

		tpf->rd = rd;

   195

	} while (++i, bits >>= 1);

   196

   197

}

   198

   199

   200

/* Returns the end tile and the length of a tunnel. The length does not

   201

 * include the starting tile (entry), it does include the end tile (exit).

   202

 */

   203

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   204

{

   205

	TileIndexDiff delta = TileOffsByDiagDir(dir);

   206

	uint z = GetTileZ(tile);

   207

	FindLengthOfTunnelResult flotr;

   208

   209

	flotr.length = 0;

   210

   211

	dir = ReverseDiagDir(dir);

   212

	do {

   213

		flotr.length++;

   214

		tile += delta;

   215

	} while(

   216

		!IsTunnelTile(tile) ||

   217

		GetTunnelDirection(tile) != dir ||

   218

		GetTileZ(tile) != z

   219

	);

   220

   221

	flotr.tile = tile;

   222

	return flotr;

   223

}

   224

   225

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

   226

   227

static uint SkipToEndOfTunnel(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)

   228

{

   229

	FindLengthOfTunnelResult flotr;

   230

	TPFSetTileBit(tpf, tile, 14);

   231

	flotr = FindLengthOfTunnel(tile, direction);

   232

	tpf->rd.cur_length += flotr.length;

   233

	TPFSetTileBit(tpf, flotr.tile, 14);

   234

	return flotr.tile;

   235

}

   236

   237

const byte _ffb_64[128] = {

   238

 0,  0,  1,  0,  2,  0,  1,  0,

   239

 3,  0,  1,  0,  2,  0,  1,  0,

   240

 4,  0,  1,  0,  2,  0,  1,  0,

   241

 3,  0,  1,  0,  2,  0,  1,  0,

   242

 5,  0,  1,  0,  2,  0,  1,  0,

   243

 3,  0,  1,  0,  2,  0,  1,  0,

   244

 4,  0,  1,  0,  2,  0,  1,  0,

   245

 3,  0,  1,  0,  2,  0,  1,  0,

   246

   247

 0,  0,  0,  2,  0,  4,  4,  6,

   248

 0,  8,  8, 10,  8, 12, 12, 14,

   249

 0, 16, 16, 18, 16, 20, 20, 22,

   250

16, 24, 24, 26, 24, 28, 28, 30,

   251

 0, 32, 32, 34, 32, 36, 36, 38,

   252

32, 40, 40, 42, 40, 44, 44, 46,

   253

32, 48, 48, 50, 48, 52, 52, 54,

   254

48, 56, 56, 58, 56, 60, 60, 62,

   255

};

   256

   258

   264

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

   265

	if (tpf->tracktype == TRANSPORT_RAIL) {

   266

		/* don't enter train depot from the back */

   267

		if (IsTileDepotType(tile, TRANSPORT_RAIL) && GetRailDepotDirection(tile) == direction) return;

   268

   269

		if (IsTileType(tile_org, MP_RAILWAY) || IsTileType(tile_org, MP_STATION) || IsTileType(tile_org, MP_TUNNELBRIDGE))

   270

			if (IsTileType(tile, MP_RAILWAY) || IsTileType(tile, MP_STATION) || IsTileType(tile, MP_TUNNELBRIDGE))

   271

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

   272

	}

   273

   274

	/* check if the new tile can be entered from that direction */

   275

	if (tpf->tracktype == TRANSPORT_ROAD) {

   276

		/* road stops and depots now have a track (r4419)

   277

		 * don't enter road stop from the back */

   278

		if (IsStandardRoadStopTile(tile) && ReverseDiagDir(GetRoadStopDir(tile)) != direction) return;

   279

		/* don't enter road depot from the back */

   280

		if (IsTileDepotType(tile, TRANSPORT_ROAD) && ReverseDiagDir(GetRoadDepotDirection(tile)) != direction) return;

   281

	}

   282

   283

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

   284

	 * and transport type match */

   285

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   286

		if (IsTunnel(tile)) {

   287

			if (GetTunnelDirection(tile) != direction ||

   288

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

   289

				return;

   290

			}

   291

		} else if (IsBridge(tile)) {

   292

			if (GetBridgeRampDirection(tile) != direction ||

   293

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

   294

				return;

   295

			}

   296

		}

   297

	}

   298

   299

	tpf->rd.cur_length++;

   300

   302

   303

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

   304

		bits &= _tpfmode1_and[direction];

   305

		bits = bits | (bits >> 8);

   306

	}

   307

	bits &= 0xBF;

   308

   309

	if (bits != 0) {

   310

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

   311

			do {

   313

				bits = KILL_FIRST_BIT(bits);

   314

   315

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

   317

   318

				if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&

   319

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

   320

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

   321

				}

   322

				tpf->rd = rd;

   323

			} while (bits != 0);

   324

		}

   325

	}

   365

   366

	/* the next is only used when signals are checked.

   367

	 * seems to go in 2 directions simultaneously */

   368

   369

	/* if i can get rid of this, tail end recursion can be used to minimize

   370

	 * stack space dramatically. */

   371

   372

	/* If we are doing signal setting, we must reverse at evere tile, so we

   373

	 * iterate all the tracks in a signal block, even when a normal train would

   374

	 * not reach it (for example, when two lines merge */

   375

	if (tpf->hasbit_13)

   376

		return;

   377

   378

	direction = ReverseDiagDir(direction);

   379

	tile += TileOffsByDiagDir(direction);

   380

   382

	bits |= (bits >> 8);

   383

   384

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

   385

		bits &= _bits_mask[direction];

   386

	}

   387

   388

	bits &= 0xBF;

   389

	if (bits == 0)

   390

		return;

   391

   392

	do {

   394

		bits = KILL_FIRST_BIT(bits);

   395

   396

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

   398

		if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&

   399

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

   400

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

   401

		}

   402

		tpf->rd = rd;

   403

	} while (bits != 0);

   404

}

   405

   406

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

   407

{

   408

	TrackPathFinder tpf;

   409

   410

	assert(direction < 4);

   411

   412

	/* initialize path finder variables */

   413

	tpf.userdata = data;

   414

	tpf.enum_proc = enum_proc;

   415

	tpf.new_link = tpf.links;

   416

	tpf.num_links_left = lengthof(tpf.links);

   417

   418

	tpf.rd.cur_length = 0;

   419

	tpf.rd.depth = 0;

   420

	tpf.rd.pft_var6 = 0;

   421

   422

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

   423

   424

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

   425

	tpf.hasbit_13         = HASBIT(flags, 13);  // 0x2000

   426

   427

   428

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

   429

	tpf.sub_type = sub_type;

   430

   431

	if (HASBIT(flags, 11)) {

   432

		tpf.rd.pft_var6 = 0xFF;

   433

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

   434

		TPFMode2(&tpf, tile, direction);

   435

	} else {

   436

		/* clear the hash_heads */

   437

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

   438

		TPFMode1(&tpf, tile, direction);

   439

	}

   440

   441

	if (after_proc != NULL)

   442

		after_proc(&tpf);

   443

}

   444

   445

struct StackedItem {

   446

	TileIndex tile;

   447

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

   448

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

   449

	TrackdirByte track;

   450

	byte depth;

   451

	byte state;

   452

	byte first_track;

   453

};

   454

   455

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

   456

{TRACKDIR_X_NE,    INVALID_TRACKDIR, TRACKDIR_X_SW,    INVALID_TRACKDIR,},

   457

{INVALID_TRACKDIR, TRACKDIR_Y_SE,    INVALID_TRACKDIR, TRACKDIR_Y_NW,},

   458

{INVALID_TRACKDIR, TRACKDIR_UPPER_E, TRACKDIR_UPPER_W, INVALID_TRACKDIR,},

   459

{TRACKDIR_LOWER_E, INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_LOWER_W,},

   460

{TRACKDIR_LEFT_N,  TRACKDIR_LEFT_S,  INVALID_TRACKDIR, INVALID_TRACKDIR,},

   461

{INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_RIGHT_S, TRACKDIR_RIGHT_N,},

   462

};

   463

   464

struct HashLink {

   465

	TileIndex tile;

   466

	uint16 typelength;

   467

	uint16 next;

   468

};

   469

   470

struct NewTrackPathFinder {

   471

	NTPEnumProc *enum_proc;

   472

	void *userdata;

   473

	TileIndex dest;

   474

   475

	TransportType tracktype;

   476

	RailTypeMask railtypes;

   477

	uint maxlength;

   478

   479

	HashLink *new_link;

   480

	uint num_links_left;

   481

   482

	uint nstack;

   483

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

   484

   485

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

   486

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

   487

   488

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

   489

   490

};

   491

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

   492

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

   493

   494

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

   495

   496

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

   497

 * move it down to the proper position */

   498

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   499

{

   500

	StackedItem si;