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

	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, tpf->sub_type);

   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

   166

		rd = tpf->rd;

   167

		goto continue_here;

   168

	}

   169

	/* several directions */

   170

	do {

   172

		rd = tpf->rd;

   173

   174

		/* Change direction 4 times only */

   175

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

   176

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

   177

				tpf->rd = rd;

   178

				return;

   179

			}

   180

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

   181

		}

   182

   184

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

   185

   186

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

   187

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

   188

		}

   189

   190

		tpf->rd = rd;

   192

   193

}

   194

   195

   196

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

   197

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

   198

 */

   199

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   200

{

   201

	TileIndexDiff delta = TileOffsByDiagDir(dir);

   202

	uint z = GetTileZ(tile);

   203

	FindLengthOfTunnelResult flotr;

   204

   205

	flotr.length = 0;

   206

   207

	dir = ReverseDiagDir(dir);

   208

	do {

   209

		flotr.length++;

   210

		tile += delta;

   211

	} while(

   212

		!IsTunnelTile(tile) ||

   213

		GetTunnelDirection(tile) != dir ||

   214

		GetTileZ(tile) != z

   215

	);

   216

   217

	flotr.tile = tile;

   218

	return flotr;

   219

}

   220

   221

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

   222

   223

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

   224

{

   225

	FindLengthOfTunnelResult flotr;

   226

	TPFSetTileBit(tpf, tile, 14);

   227

	flotr = FindLengthOfTunnel(tile, direction);

   228

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

   229

	TPFSetTileBit(tpf, flotr.tile, 14);

   230

	return flotr.tile;

   231

}

   232

   233

const byte _ffb_64[64] = {

   234

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

   235

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

   236

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

   237

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

   238

 5,  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

};

   243

   244

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

   245

   246

/** Most code of the "Normal" case of TPF Mode 1; for signals special tricks

   247

 * have to be done, but those happen in TPFMode1; this is just to prevent

   248

 * gotos ;). */

   249

static inline void TPFMode1_NormalCase(TrackPathFinder* tpf, TileIndex tile, TileIndex tile_org, DiagDirection direction)

   250

{

   251

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

   252

	if (tpf->tracktype == TRANSPORT_RAIL) {

   253

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

   254

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

   255

   256

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

   257

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

   258

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

   259

	}

   260

   261

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

   262

	if (tpf->tracktype == TRANSPORT_ROAD) {

   263

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

   264

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

   265

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

   266

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

   267

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

   268

	}

   269

   270

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

   271

	 * and transport type match */

   272

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   273

		if (IsTunnel(tile)) {

   274

			if (GetTunnelDirection(tile) != direction ||

   275

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

   276

				return;

   277

			}

   278

		} else if (IsBridge(tile)) {

   279

			if (GetBridgeRampDirection(tile) != direction ||

   280

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

   281

				return;

   282

			}

   283

		}

   284

	}

   285

   286

	tpf->rd.cur_length++;

   287

   288

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

   289

   290

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

   291

		bits &= _tpfmode1_and[direction];

   293

	}

   294

	bits &= 0xBF;

   295

   296

	if (bits != 0) {

   297

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

   298

			do {

   299

				int i = FIND_FIRST_BIT(bits);

   300

				bits = KillFirstBit(bits);

   301

   302

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

   303

				RememberData rd = tpf->rd;

   304

   305

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

   306

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

   307

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

   308

				}

   309

				tpf->rd = rd;

   310

			} while (bits != 0);

   311

		}

   312

	}

   313

}

   314

   315

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

   316

{

   317

	TileIndex tile_org = tile;

   318

   319

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   320

		if (IsTunnel(tile)) {

   321

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

   322

				return;

   323

			}

   324

			/* Only skip through the tunnel if heading inwards. We can

   325

			 * be headed outwards if our starting position was in a

   326

			 * tunnel and we're pathfinding backwards */

   327

			if (GetTunnelDirection(tile) == direction) {

   328

				tile = SkipToEndOfTunnel(tpf, tile, direction);

   329

			} else if (GetTunnelDirection(tile) != ReverseDiagDir(direction)) {

   330

				/* We don't support moving through the sides of a tunnel

   331

				 * entrance :-) */

   332

				return;

   333

			}

   334

		} else {

   335

			TileIndex tile_end;

   336

			if (GetBridgeRampDirection(tile) != direction ||

   337

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

   338

				return;

   339

			}

   340

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

   341

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

   342

			TPFSetTileBit(tpf, tile, 14);

   343

			tile_end = GetOtherBridgeEnd(tile);

   344

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

   345

			tile = tile_end;

   346

			TPFSetTileBit(tpf, tile, 14);

   347

		}

   348

	}

   349

	tile += TileOffsByDiagDir(direction);

   350

   351

	TPFMode1_NormalCase(tpf, tile, tile_org, direction);

   352

   353

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

   354

	 * seems to go in 2 directions simultaneously */

   355

   356

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

   357

	 * stack space dramatically. */

   358

   359

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

   360

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

   361

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

   362

	if (tpf->hasbit_13)

   363

		return;

   364

   365

	direction = ReverseDiagDir(direction);

   366

	tile += TileOffsByDiagDir(direction);

   367

   368

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

   369

	bits |= (bits >> 8);

   370

   371

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

   372

		bits &= _bits_mask[direction];

   373

	}

   374

   375

	bits &= 0xBF;

   376

	if (bits == 0)

   377

		return;

   378

   379

	do {

   380

		uint i = FIND_FIRST_BIT(bits);

   381

		bits = KillFirstBit(bits);

   382

   383

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

   384

		RememberData rd = tpf->rd;

   385

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

   386

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

   387

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

   388

		}

   389

		tpf->rd = rd;

   390

	} while (bits != 0);

   391

}

   392

   393

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

   394

{

   395

	TrackPathFinder tpf;

   396

   397

	assert(direction < 4);

   398

   399

	/* initialize path finder variables */

   400

	tpf.userdata = data;

   401

	tpf.enum_proc = enum_proc;

   402

	tpf.new_link = tpf.links;

   403

	tpf.num_links_left = lengthof(tpf.links);

   404

   405

	tpf.rd.cur_length = 0;

   406

	tpf.rd.depth = 0;

   407

	tpf.rd.pft_var6 = 0;

   408

   409

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

   410

   411

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

   412

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

   413

   414

   415

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

   416

	tpf.sub_type = sub_type;

   417

   418

	if (HasBit(flags, 11)) {

   419

		tpf.rd.pft_var6 = 0xFF;

   420

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

   421

		TPFMode2(&tpf, tile, direction);

   422

	} else {

   423

		/* clear the hash_heads */

   424

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

   425

		TPFMode1(&tpf, tile, direction);

   426

	}

   427

   428

	if (after_proc != NULL)

   429

		after_proc(&tpf);

   430

}

   431

   432

struct StackedItem {

   433

	TileIndex tile;

   434

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

   435

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

   436

	TrackdirByte track;

   437

	byte depth;

   438

	byte state;

   439

	byte first_track;

   440

};

   441

   442

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

   443

{TRACKDIR_X_NE,    INVALID_TRACKDIR, TRACKDIR_X_SW,    INVALID_TRACKDIR,},

   444

{INVALID_TRACKDIR, TRACKDIR_Y_SE,    INVALID_TRACKDIR, TRACKDIR_Y_NW,},

   445

{INVALID_TRACKDIR, TRACKDIR_UPPER_E, TRACKDIR_UPPER_W, INVALID_TRACKDIR,},

   446

{TRACKDIR_LOWER_E, INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_LOWER_W,},

   447

{TRACKDIR_LEFT_N,  TRACKDIR_LEFT_S,  INVALID_TRACKDIR, INVALID_TRACKDIR,},

   448

{INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_RIGHT_S, TRACKDIR_RIGHT_N,},

   449

};

   450

   451

struct HashLink {

   452

	TileIndex tile;

   453

	uint16 typelength;

   454

	uint16 next;

   455

};

   456

   457

struct NewTrackPathFinder {

   458

	NTPEnumProc *enum_proc;

   459

	void *userdata;

   460

	TileIndex dest;

   461

   462

	TransportType tracktype;

   463

	RailTypeMask railtypes;

   464

	uint maxlength;

   465

   466

	HashLink *new_link;

   467

	uint num_links_left;

   468

   469

	uint nstack;

   470

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

   471

   472

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

   473

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

   474

   475

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

   476

   477

};

   478

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

   479

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

   480

   481

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

   482

   483

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

   484

 * move it down to the proper position */

   485

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   486

{

   487

	StackedItem si;

   488

	int i = ++tpf->nstack;

   489

   490

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

   491

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

   492

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

   493

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

   494

		i >>= 1;

   495

	}

   496

}

   497

   498

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

   499