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);

   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

   257

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

   258

{

   259

	uint bits;

   260

	int i;

   261

	RememberData rd;

   262

	TileIndex tile_org = tile;

   263

   264

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   265

		if (IsTunnel(tile)) {

   266

			if (GetTunnelDirection(tile) != direction ||

   267

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

   268

				return;

   269

			}

   270

			tile = SkipToEndOfTunnel(tpf, tile, direction);

   271

		} else {

   272

			TileIndex tile_end;

   273

			if (GetBridgeRampDirection(tile) != direction ||

   274

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

   275

				return;

   276

			}

   277

			//fprintf(stderr, "%s: Planning over bridge\n", __func__);

   278

			// TODO doesn't work - WHAT doesn't work?

   279

			TPFSetTileBit(tpf, tile, 14);

   280

			tile_end = GetOtherBridgeEnd(tile);

   281

			tpf->rd.cur_length += DistanceManhattan(tile, tile_end);

   282

			tile = tile_end;

   283

			TPFSetTileBit(tpf, tile, 14);

   284

		}

   285

	}

   286

	tile += TileOffsByDiagDir(direction);

   287

   288

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

   289

	if (tpf->tracktype == TRANSPORT_RAIL) {

   290

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

   291

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

   292

   293

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

   294

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

   295

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

   296

	}

   297

   298

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

   299

	if (tpf->tracktype == TRANSPORT_ROAD) {

   300

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

   301

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

   302

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

   303

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

   304

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

   305

	}

   306

   307

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

   308

	 * and transport type match */

   309

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   310

		if (IsTunnel(tile)) {

   311

			if (GetTunnelDirection(tile) != direction ||

   312

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

   313

				return;

   314

			}

   315

		} else if (IsBridge(tile)) {

   316

			if (GetBridgeRampDirection(tile) != direction ||

   317

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

   318

				return;

   319

			}

   320

		}

   321

	}

   322

   323

	tpf->rd.cur_length++;

   324

   325

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

   326

   327

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

   328

		bits &= _tpfmode1_and[direction];

   329

		bits = bits | (bits >> 8);

   330

	}

   331

	bits &= 0xBF;

   332

   333

	if (bits != 0) {

   334

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

   335

			do {

   336

				i = FIND_FIRST_BIT(bits);

   337

				bits = KILL_FIRST_BIT(bits);

   338

   339

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

   340

				rd = tpf->rd;

   341

   342

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

   343

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

   344

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

   345

				}

   346

				tpf->rd = rd;

   347

			} while (bits != 0);

   348

		}

   349

	}

   350

   351

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

   352

	 * seems to go in 2 directions simultaneously */

   353

   354

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

   355

	 * stack space dramatically. */

   356

   357

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

   358

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

   359

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

   360

	if (tpf->hasbit_13)

   361

		return;

   362

   363

	direction = ReverseDiagDir(direction);

   364

	tile += TileOffsByDiagDir(direction);

   365

   366

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

   367

	bits |= (bits >> 8);

   368

   369

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

   370

		bits &= _bits_mask[direction];

   371

	}

   372

   373

	bits &= 0xBF;

   374

	if (bits == 0)

   375

		return;

   376

   377

	do {

   378

		i = FIND_FIRST_BIT(bits);

   379

		bits = KILL_FIRST_BIT(bits);

   380

   381

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

   382

		rd = tpf->rd;

   383

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

   384

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

   385

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

   386

		}

   387

		tpf->rd = rd;

   388

	} while (bits != 0);

   389

}

   390

   391

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

   392

{

   393

	TrackPathFinder tpf;

   394

   395

	assert(direction < 4);

   396

   397

	/* initialize path finder variables */

   398

	tpf.userdata = data;

   399

	tpf.enum_proc = enum_proc;

   400

	tpf.new_link = tpf.links;

   401

	tpf.num_links_left = lengthof(tpf.links);

   402

   403

	tpf.rd.cur_length = 0;

   404

	tpf.rd.depth = 0;

   405

	tpf.rd.pft_var6 = 0;

   406

   407

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

   408

   409

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

   410

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

   411

   412

   413

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

   414

   415

	if (HASBIT(flags, 11)) {

   416

		tpf.rd.pft_var6 = 0xFF;

   417

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

   418

		TPFMode2(&tpf, tile, direction);

   419

	} else {

   420

		/* clear the hash_heads */

   421

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

   422

		TPFMode1(&tpf, tile, direction);

   423

	}

   424

   425

	if (after_proc != NULL)

   426

		after_proc(&tpf);

   427

}

   428

   429

struct StackedItem {

   430

	TileIndex tile;

   431

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

   432

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

   433

	TrackdirByte track;

   434

	byte depth;

   435

	byte state;

   436

	byte first_track;

   437

};

   438

   439

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

   440

{TRACKDIR_X_NE,    INVALID_TRACKDIR, TRACKDIR_X_SW,    INVALID_TRACKDIR,},

   441

{INVALID_TRACKDIR, TRACKDIR_Y_SE,    INVALID_TRACKDIR, TRACKDIR_Y_NW,},

   442

{INVALID_TRACKDIR, TRACKDIR_UPPER_E, TRACKDIR_UPPER_W, INVALID_TRACKDIR,},

   443

{TRACKDIR_LOWER_E, INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_LOWER_W,},

   444

{TRACKDIR_LEFT_N,  TRACKDIR_LEFT_S,  INVALID_TRACKDIR, INVALID_TRACKDIR,},

   445

{INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_RIGHT_S, TRACKDIR_RIGHT_N,},

   446

};

   447

   448

struct HashLink {

   449

	TileIndex tile;

   450

	uint16 typelength;

   451

	uint16 next;

   452

};

   453

   454

struct NewTrackPathFinder {

   455

	NTPEnumProc *enum_proc;

   456

	void *userdata;

   457

	TileIndex dest;

   458

   459

	TransportType tracktype;

   460

	RailTypeMask railtypes;

   461

	uint maxlength;

   462

   463

	HashLink *new_link;

   464

	uint num_links_left;

   465

   466

	uint nstack;

   467

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

   468

   469

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

   470

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

   471

   472

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

   473

   474

};

   475

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

   476

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

   477

   478

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

   479

   480

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

   481

 * move it down to the proper position */

   482

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   483

{

   484

	StackedItem si;

   485

	int i = ++tpf->nstack;

   486

   487

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

   488

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

   489

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

   490

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

   491

		i >>= 1;

   492

	}

   493

}

   494

   495

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

   496

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   497

{

   498

	StackedItem si;

   499

	int i = 1, j;

   500

	int n;

   501