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

    12

#include "tile.h"

    13

#include "pathfind.h"

    14

#include "rail.h"

    15

#include "debug.h"

    16

#include "tunnel_map.h"

    17

#include "variables.h"

    18

#include "depot.h"

    19

    20

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

    21

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

    22

{

    23

	uint hash, val, offs;

    24

	TrackPathFinderLink *link, *new_link;

    25

	uint bits = 1 << dir;

    26

    27

	if (tpf->disable_tile_hash)

    28

		return true;

    29

    30

	hash = PATHFIND_HASH_TILE(tile);

    31

    32

	val = tpf->hash_head[hash];

    33

    34

	if (val == 0) {

    35

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

    36

		 * to indicate that a bit was set. */

    37

		tpf->hash_head[hash] = bits;

    38

		tpf->hash_tile[hash] = tile;

    39

		return true;

    40

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

    41

		/* single tile */

    42

    43

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

    44

			/* found another bit for the same tile,

    45

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

    46

			if (val & bits)

    47

				return false;

    48

    49

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

    50

			 * was set */

    51

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

    52

			return true;

    53

		} else {

    54

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

    55

    56

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

    57

			 * that a tile was already visisted. */

    58

			if (tpf->num_links_left == 0) {

    59

				return false;

    60

			}

    61

			tpf->num_links_left--;

    62

			link = tpf->new_link++;

    63

    64

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

    65

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

    66

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

    67

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

    68

    69

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

    70

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

    71

    72

			link->next = 0xFFFF;

    73

		}

    74

	} else {

    75

		/* a linked list of many tiles,

    76

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

    77

		 * otherwise make a new link */

    78

    79

		offs = tpf->hash_tile[hash];

    80

		do {

    81

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    82

			if (tile == link->tile) {

    83

				/* found the tile in the link list,

    84

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

    85

				 * bit was already set */

    86

				if (link->flags & bits)

    87

					return false;

    88

				link->flags |= bits;

    89

				return true;

    90

			}

    91

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

    92

	}

    93

    94

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

    95

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

    96

	if (tpf->num_links_left == 0) {

    97

			return false;

    98

	}

    99

	tpf->num_links_left--;

   100

	new_link = tpf->new_link++;

   101

   102

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

   103

	 * link to the new one */

   104

	new_link->tile = tile;

   105

	new_link->flags = bits;

   106

	new_link->next = 0xFFFF;

   107

   108

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

   109

	return true;

   110

}

   111

   112

static const byte _bits_mask[4] = {

   113

	0x19,

   114

	0x16,

   115

	0x25,

   116

	0x2A,

   117

};

   118

   119

static const DiagDirection _tpf_new_direction[14] = {

   120

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

   121

	INVALID_DIAGDIR, INVALID_DIAGDIR,

   122

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

   123

};

   124

   125

static const DiagDirection _tpf_prev_direction[14] = {

   126

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

   127

	INVALID_DIAGDIR, INVALID_DIAGDIR,

   128

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

   129

};

   130

   131

   132

static const byte _otherdir_mask[4] = {

   133

	0x10,

   134

	0,

   135

	0x5,

   136

	0x2A,

   137

};

   138

   139

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

   140

{

   141

	uint bits;

   142

	int i;

   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

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

   156

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

   157

	if (bits == 0)

   158

		return;

   159

   160

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

   161

   162

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

   163

		/* only one direction */

   164

		i = 0;

   165

		while (!(bits & 1))

   166

			i++, bits >>= 1;

   167

   168

		rd = tpf->rd;

   169

		goto continue_here;

   170

	}

   171

	/* several directions */

   172

	i=0;

   173

	do {

   174

		if (!(bits & 1)) continue;

   175

		rd = tpf->rd;

   176

   177

		/* Change direction 4 times only */

   178

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

   179

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

   180

				tpf->rd = rd;

   181

				return;

   182

			}

   183

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

   184

		}

   185

   186

continue_here:;

   187

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

   188

   189

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

   190

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

   191

		}

   192

   193

		tpf->rd = rd;

   194

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

   195

   196

}

   197

   198

   199

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

   200

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

   201

 */

   202

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   203

{

   204

	TileIndexDiff delta = TileOffsByDiagDir(dir);

   205

	uint z = GetTileZ(tile);

   206

	FindLengthOfTunnelResult flotr;

   207

   208

	flotr.length = 0;

   209

   210

	dir = ReverseDiagDir(dir);

   211

	do {

   212

		flotr.length++;

   213

		tile += delta;

   214

	} while(

   215

		!IsTunnelTile(tile) ||

   216

		GetTunnelDirection(tile) != dir ||

   217

		GetTileZ(tile) != z

   218

	);

   219

   220

	flotr.tile = tile;

   221

	return flotr;

   222

}

   223

   224

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

   225

   226

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

   227

{

   228

	FindLengthOfTunnelResult flotr;

   229

	TPFSetTileBit(tpf, tile, 14);

   230

	flotr = FindLengthOfTunnel(tile, direction);

   231

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

   232

	TPFSetTileBit(tpf, flotr.tile, 14);

   233

	return flotr.tile;

   234

}

   235

   236

const byte _ffb_64[128] = {

   237

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

   238

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

   239

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

   240

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

   241

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

   242

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

   243

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

   244

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

   245

   246

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

   247

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

   248

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

   249

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

   250

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

   251

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

   252

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

   253

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

   254

};

   255

   256

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

   257

{

   258

	uint bits;

   259

	int i;

   260

	RememberData rd;

   261

	TileIndex tile_org = tile;

   262

   263

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   264

		if (IsTunnel(tile)) {

   265

			if (GetTunnelDirection(tile) != direction ||

   266

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

   267

				return;

   268

			}

   269

			tile = SkipToEndOfTunnel(tpf, tile, direction);

   270

		} else {

   271

			TileIndex tile_end;

   272

			if (GetBridgeRampDirection(tile) != direction ||

   273

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

   274

				return;

   275

			}

   276

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

   277

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

   278

			TPFSetTileBit(tpf, tile, 14);

   279

			tile_end = GetOtherBridgeEnd(tile);

   280

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

   281

			tile = tile_end;

   282

			TPFSetTileBit(tpf, tile, 14);

   283

		}

   284

	}

   285

	tile += TileOffsByDiagDir(direction);

   286

   287

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

   288

	if (tpf->tracktype == TRANSPORT_RAIL) {

   289

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

   290

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

   291

   292

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

   293

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

   294

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

   295

	}

   296

   297

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

   298

	if (tpf->tracktype == TRANSPORT_ROAD) {

   299

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

   300

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

   301

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

   302

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

   303

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

   304

	}

   305

   306

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

   307

	 * and transport type match */

   308

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   309

		if (IsTunnel(tile)) {

   310

			if (GetTunnelDirection(tile) != direction ||

   311

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

   312

				return;

   313

			}

   314

		} else if (IsBridge(tile)) {

   315

			if (GetBridgeRampDirection(tile) != direction ||

   316

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

   317

				return;

   318

			}

   319

		}

   320

	}

   321

   322

	tpf->rd.cur_length++;

   323

   324

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

   325

   326

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

   327

		bits &= _tpfmode1_and[direction];

   328

		bits = bits | (bits >> 8);

   329

	}

   330

	bits &= 0xBF;

   331

   332

	if (bits != 0) {

   333

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

   334

			do {

   335

				i = FIND_FIRST_BIT(bits);

   336

				bits = KILL_FIRST_BIT(bits);

   337

   338

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

   339

				rd = tpf->rd;

   340

   341

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

   342

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

   343

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

   344

				}

   345

				tpf->rd = rd;

   346

			} while (bits != 0);

   347

		}

   348

	}

   349

   350

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

   351

	 * seems to go in 2 directions simultaneously */

   352

   353

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

   354

	 * stack space dramatically. */

   355

   356

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

   357

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

   358

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

   359

	if (tpf->hasbit_13)

   360

		return;

   361

   362

	direction = ReverseDiagDir(direction);

   363

	tile += TileOffsByDiagDir(direction);

   364

   365

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

   366

	bits |= (bits >> 8);

   367

   368

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

   369

		bits &= _bits_mask[direction];

   370

	}

   371

   372

	bits &= 0xBF;

   373

	if (bits == 0)

   374

		return;

   375

   376

	do {

   377

		i = FIND_FIRST_BIT(bits);

   378

		bits = KILL_FIRST_BIT(bits);

   379

   380

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

   381

		rd = tpf->rd;

   382

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

   383

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

   384

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

   385

		}

   386

		tpf->rd = rd;

   387

	} while (bits != 0);

   388

}

   389

   390

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

   391

{

   392

	TrackPathFinder tpf;

   393

   394

	assert(direction < 4);

   395

   396

	/* initialize path finder variables */

   397

	tpf.userdata = data;

   398

	tpf.enum_proc = enum_proc;

   399

	tpf.new_link = tpf.links;

   400

	tpf.num_links_left = lengthof(tpf.links);

   401

   402

	tpf.rd.cur_length = 0;

   403

	tpf.rd.depth = 0;

   404

	tpf.rd.pft_var6 = 0;

   405

   406

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

   407

   408

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

   409

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

   410

   411

   412

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

   413

   414

	if (HASBIT(flags, 11)) {

   415

		tpf.rd.pft_var6 = 0xFF;

   416

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

   417

		TPFMode2(&tpf, tile, direction);

   418

	} else {

   419

		/* clear the hash_heads */

   420

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

   421

		TPFMode1(&tpf, tile, direction);

   422

	}

   423

   424

	if (after_proc != NULL)

   425

		after_proc(&tpf);

   426

}

   427

   428

struct StackedItem {

   429

	TileIndex tile;

   430

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

   431

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

   432

	TrackdirByte track;

   433

	byte depth;

   434

	byte state;

   435

	byte first_track;

   436

};

   437

   438

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

   439

{TRACKDIR_X_NE,    INVALID_TRACKDIR, TRACKDIR_X_SW,    INVALID_TRACKDIR,},

   440

{INVALID_TRACKDIR, TRACKDIR_Y_SE,    INVALID_TRACKDIR, TRACKDIR_Y_NW,},

   441

{INVALID_TRACKDIR, TRACKDIR_UPPER_E, TRACKDIR_UPPER_W, INVALID_TRACKDIR,},

   442

{TRACKDIR_LOWER_E, INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_LOWER_W,},

   443

{TRACKDIR_LEFT_N,  TRACKDIR_LEFT_S,  INVALID_TRACKDIR, INVALID_TRACKDIR,},

   444

{INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_RIGHT_S, TRACKDIR_RIGHT_N,},

   445

};

   446

   447

struct HashLink {

   448

	TileIndex tile;

   449

	uint16 typelength;

   450

	uint16 next;

   451

};

   452

   453

struct NewTrackPathFinder {

   454

	NTPEnumProc *enum_proc;

   455

	void *userdata;

   456

	TileIndex dest;

   457

   458

	TransportType tracktype;

   459

	RailTypeMask railtypes;

   460

	uint maxlength;

   461

   462

	HashLink *new_link;

   463

	uint num_links_left;

   464

   465

	uint nstack;

   466

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

   467

   468

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

   469

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

   470

   471

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

   472

   473

};

   474

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

   475

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

   476

   477

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

   478

   479

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

   480

 * move it down to the proper position */

   481

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   482

{

   483

	StackedItem si;

   484

	int i = ++tpf->nstack;

   485

   486

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

   487

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

   488

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

   489

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

   490

		i >>= 1;

   491

	}

   492

}

   493

   494

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

   495

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   496

{

   497

	StackedItem si;

   498

	int i = 1, j;

   499

	int n;

   500

   501

	assert(tpf->nstack > 0);