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

   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[64] = {

   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

   248

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

   249

   250

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

   251

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

   252

 * gotos ;). */

   253

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

   254

{

   255

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

   256

	if (tpf->tracktype == TRANSPORT_RAIL) {

   257

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

   258

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

   259

   260

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

   261

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

   262

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

   263

	}

   264

   265

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

   266

	if (tpf->tracktype == TRANSPORT_ROAD) {

   267

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

   268

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

   269

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

   270

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

   271

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

   272

	}

   273

   274

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

   275

	 * and transport type match */

   276

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   277

		if (IsTunnel(tile)) {

   278

			if (GetTunnelDirection(tile) != direction ||

   279

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

   280

				return;

   281

			}

   282

		} else if (IsBridge(tile)) {

   283

			if (GetBridgeRampDirection(tile) != direction ||

   284

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

   285

				return;

   286

			}

   287

		}

   288

	}

   289

   290

	tpf->rd.cur_length++;

   291

   292

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

   293

   294

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

   295

		bits &= _tpfmode1_and[direction];

   296

		bits = bits | (bits >> 8);

   297

	}

   298

	bits &= 0xBF;

   299

   300

	if (bits != 0) {

   301

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

   302

			do {

   303

				int i = FIND_FIRST_BIT(bits);

   304

				bits = KillFirstBit(bits);

   305

   306

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

   307

				RememberData rd = tpf->rd;

   308

   309

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

   310

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

   311

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

   312

				}

   313

				tpf->rd = rd;

   314

			} while (bits != 0);

   315

		}

   316

	}

   317

}

   318

   319

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

   320

{

   321

	TileIndex tile_org = tile;

   322

   323

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   324

		if (IsTunnel(tile)) {

   325

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

   326

				return;

   327

			}

   328

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

   329

			 * be headed outwards if our starting position was in a

   330

			 * tunnel and we're pathfinding backwards */

   331

			if (GetTunnelDirection(tile) == direction) {

   332

				tile = SkipToEndOfTunnel(tpf, tile, direction);

   333

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

   334

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

   335

				 * entrance :-) */

   336

				return;

   337

			}

   338

		} else {

   339

			TileIndex tile_end;

   340

			if (GetBridgeRampDirection(tile) != direction ||

   341

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

   342

				return;

   343

			}

   344

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

   345

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

   346

			TPFSetTileBit(tpf, tile, 14);

   347

			tile_end = GetOtherBridgeEnd(tile);

   348

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

   349

			tile = tile_end;

   350

			TPFSetTileBit(tpf, tile, 14);

   351

		}

   352

	}

   353

	tile += TileOffsByDiagDir(direction);

   354

   355

	TPFMode1_NormalCase(tpf, tile, tile_org, direction);

   356

   357

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

   358

	 * seems to go in 2 directions simultaneously */

   359

   360

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

   361

	 * stack space dramatically. */

   362

   363

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

   364

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

   365

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

   366

	if (tpf->hasbit_13)

   367

		return;

   368

   369

	direction = ReverseDiagDir(direction);

   370

	tile += TileOffsByDiagDir(direction);

   371

   372

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

   373

	bits |= (bits >> 8);

   374

   375

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

   376

		bits &= _bits_mask[direction];

   377

	}

   378

   379

	bits &= 0xBF;

   380

	if (bits == 0)

   381

		return;

   382

   383

	do {

   384

		uint i = FIND_FIRST_BIT(bits);

   385

		bits = KillFirstBit(bits);

   386

   387

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

   388

		RememberData rd = tpf->rd;

   389

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

   390

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

   391

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

   392

		}

   393

		tpf->rd = rd;

   394

	} while (bits != 0);

   395

}

   396

   397

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

   398

{

   399

	TrackPathFinder tpf;

   400

   401

	assert(direction < 4);

   402

   403

	/* initialize path finder variables */

   404

	tpf.userdata = data;

   405

	tpf.enum_proc = enum_proc;

   406

	tpf.new_link = tpf.links;

   407

	tpf.num_links_left = lengthof(tpf.links);

   408

   409

	tpf.rd.cur_length = 0;

   410

	tpf.rd.depth = 0;

   411

	tpf.rd.pft_var6 = 0;

   412

   414

   417

   418

   419

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

   420

	tpf.sub_type = sub_type;

   421

   423

		tpf.rd.pft_var6 = 0xFF;

   424

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

   425

		TPFMode2(&tpf, tile, direction);

   426

	} else {

   427

		/* clear the hash_heads */

   428

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

   429

		TPFMode1(&tpf, tile, direction);

   430

	}

   431

   432

	if (after_proc != NULL)

   433

		after_proc(&tpf);

   434

}

   435

   436

struct StackedItem {

   437

	TileIndex tile;

   438

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

   439

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

   440

	TrackdirByte track;

   441

	byte depth;

   442

	byte state;

   443

	byte first_track;

   444

};

   445

   446

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

   447

{TRACKDIR_X_NE,    INVALID_TRACKDIR, TRACKDIR_X_SW,    INVALID_TRACKDIR,},

   448

{INVALID_TRACKDIR, TRACKDIR_Y_SE,    INVALID_TRACKDIR, TRACKDIR_Y_NW,},

   449

{INVALID_TRACKDIR, TRACKDIR_UPPER_E, TRACKDIR_UPPER_W, INVALID_TRACKDIR,},

   450

{TRACKDIR_LOWER_E, INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_LOWER_W,},

   451

{TRACKDIR_LEFT_N,  TRACKDIR_LEFT_S,  INVALID_TRACKDIR, INVALID_TRACKDIR,},

   452

{INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_RIGHT_S, TRACKDIR_RIGHT_N,},

   453

};

   454

   455

struct HashLink {

   456

	TileIndex tile;

   457

	uint16 typelength;

   458

	uint16 next;

   459

};

   460

   461

struct NewTrackPathFinder {

   462

	NTPEnumProc *enum_proc;

   463

	void *userdata;

   464

	TileIndex dest;

   465

   466

	TransportType tracktype;

   467

	RailTypeMask railtypes;

   468

	uint maxlength;

   469

   470

	HashLink *new_link;

   471

	uint num_links_left;

   472

   473

	uint nstack;

   474

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

   475

   476

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

   477

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

   478

   479

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

   480

   481

};

   482

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

   483

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

   484

   485

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

   486

   487

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

   488

 * move it down to the proper position */

   489

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   490

{

   491

	StackedItem si;

   492

	int i = ++tpf->nstack;

   493

   494

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

   495

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

   496

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

   497

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

   498

		i >>= 1;

   499

	}