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

    11

#include "landscape.h"

    12

#include "pathfind.h"

    13

#include "rail_type.h"

    14

#include "debug.h"

    15

#include "tunnel_map.h"

    16

#include "settings_type.h"

    17

#include "depot.h"

    18

#include "tunnelbridge_map.h"

    19

#include "core/random_func.hpp"

    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

   162

	uint i = 0;

   163

	/* only one direction */

   164

	if (KillFirstBit(bits) == 0) {

   165

		i = FindFirstBit(bits);

   166

		rd = tpf->rd;

   167

		goto continue_here;

   168

	}

   169

	/* several directions */

   170

	do {

   171

		i = FindFirstBit(bits);

   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

   183

continue_here:

   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;

   191

	} while (ClrBit(bits, i) != 0);

   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

		GetTunnelBridgeDirection(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

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

   234

   235

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

   236

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

   237

 * gotos ;). */

   238

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

   239

{

   240

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

   241

	if (tpf->tracktype == TRANSPORT_RAIL) {

   242

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

   243

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

   244

   245

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

   246

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

   247

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

   248

	}

   249

   250

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

   251

	if (tpf->tracktype == TRANSPORT_ROAD) {

   252

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

   253

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

   254

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

   255

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

   256

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

   257

	}

   258

   259

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

   260

	 * and transport type match */

   261

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   262

		if (GetTunnelBridgeDirection(tile) != direction ||

   263

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

   264

			return;

   265

		}

   266

	}

   267

   268

	tpf->rd.cur_length++;

   269

   270

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

   271

   272

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

   273

		bits &= _tpfmode1_and[direction];

   274

		bits |= bits >> 8;

   275

	}

   276

	bits &= 0xBF;

   277

   278

	if (bits != 0) {

   279

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

   280

			do {

   281

				int i = FIND_FIRST_BIT(bits);

   282

				bits = KillFirstBit(bits);

   283

   284

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

   285

				RememberData rd = tpf->rd;

   286

   287

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

   288

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

   289

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

   290

				}

   291

				tpf->rd = rd;

   292

			} while (bits != 0);

   293

		}

   294

	}

   295

}

   296

   297

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

   298

{

   299

	TileIndex tile_org = tile;

   300

   301

	if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   302

		if (IsTunnel(tile)) {

   303

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

   304

				return;

   305

			}

   306

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

   307

			 * be headed outwards if our starting position was in a

   308

			 * tunnel and we're pathfinding backwards */

   309

			if (GetTunnelBridgeDirection(tile) == direction) {

   310

				tile = SkipToEndOfTunnel(tpf, tile, direction);

   311

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

   312

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

   313

				 * entrance :-) */

   314

				return;

   315

			}

   316

		} else {

   317

			TileIndex tile_end;

   318

			if (GetTunnelBridgeDirection(tile) != direction ||

   319

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

   320

				return;

   321

			}

   322

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

   323

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

   324

			TPFSetTileBit(tpf, tile, 14);

   325

			tile_end = GetOtherBridgeEnd(tile);

   326

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

   327

			tile = tile_end;

   328

			TPFSetTileBit(tpf, tile, 14);

   329

		}

   330

	}

   331

	tile += TileOffsByDiagDir(direction);

   332

   333

	TPFMode1_NormalCase(tpf, tile, tile_org, direction);

   334

   335

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

   336

	 * seems to go in 2 directions simultaneously */

   337

   338

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

   339

	 * stack space dramatically. */

   340

   341

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

   342

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

   343

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

   344

	if (tpf->hasbit_13)

   345

		return;

   346

   347

	direction = ReverseDiagDir(direction);

   348

	tile += TileOffsByDiagDir(direction);

   349

   350

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

   351

	bits |= (bits >> 8);

   352

   353

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

   354

		bits &= _bits_mask[direction];

   355

	}

   356

   357

	bits &= 0xBF;

   358

	if (bits == 0)

   359

		return;

   360

   361

	do {

   362

		uint i = FIND_FIRST_BIT(bits);

   363

		bits = KillFirstBit(bits);

   364

   365

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

   366

		RememberData rd = tpf->rd;

   367

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

   368

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

   369

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

   370

		}

   371

		tpf->rd = rd;

   372

	} while (bits != 0);

   373

}

   374

   375

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

   376

{

   377

	TrackPathFinder tpf;

   378

   379

	assert(direction < 4);

   380

   381

	/* initialize path finder variables */

   382

	tpf.userdata = data;

   383

	tpf.enum_proc = enum_proc;

   384

	tpf.new_link = tpf.links;

   385

	tpf.num_links_left = lengthof(tpf.links);

   386

   387

	tpf.rd.cur_length = 0;

   388

	tpf.rd.depth = 0;

   389

	tpf.rd.pft_var6 = 0;

   390

   391

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

   392

   393

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

   394

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

   395

   396

   397

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

   398

	tpf.sub_type = sub_type;

   399

   400

	if (HasBit(flags, 11)) {

   401

		tpf.rd.pft_var6 = 0xFF;

   402

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

   403

		TPFMode2(&tpf, tile, direction);

   404

	} else {

   405

		/* clear the hash_heads */

   406

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

   407

		TPFMode1(&tpf, tile, direction);

   408

	}

   409

   410

	if (after_proc != NULL)

   411

		after_proc(&tpf);

   412

}

   413

   414

struct StackedItem {

   415

	TileIndex tile;

   416

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

   417

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

   418

	TrackdirByte track;

   419

	byte depth;

   420

	byte state;

   421

	byte first_track;

   422

};

   423

   424

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

   425

{TRACKDIR_X_NE,    INVALID_TRACKDIR, TRACKDIR_X_SW,    INVALID_TRACKDIR,},

   426

{INVALID_TRACKDIR, TRACKDIR_Y_SE,    INVALID_TRACKDIR, TRACKDIR_Y_NW,},

   427

{INVALID_TRACKDIR, TRACKDIR_UPPER_E, TRACKDIR_UPPER_W, INVALID_TRACKDIR,},

   428

{TRACKDIR_LOWER_E, INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_LOWER_W,},

   429

{TRACKDIR_LEFT_N,  TRACKDIR_LEFT_S,  INVALID_TRACKDIR, INVALID_TRACKDIR,},

   430

{INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_RIGHT_S, TRACKDIR_RIGHT_N,},

   431

};

   432

   433

struct HashLink {

   434

	TileIndex tile;

   435

	uint16 typelength;

   436

	uint16 next;

   437

};

   438

   439

struct NewTrackPathFinder {

   440

	NTPEnumProc *enum_proc;

   441

	void *userdata;

   442

	TileIndex dest;

   443

   444

	TransportType tracktype;

   445

	RailTypes railtypes;

   446

	uint maxlength;

   447

   448

	HashLink *new_link;

   449

	uint num_links_left;

   450

   451

	uint nstack;

   452

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

   453

   454

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

   455

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

   456

   457

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

   458

   459

};

   460

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

   461

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

   462

   463

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

   464

   465

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

   466

 * move it down to the proper position */

   467

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   468

{

   469

	StackedItem si;

   470

	int i = ++tpf->nstack;

   471

   472

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

   473

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

   474

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

   475

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

   476

		i >>= 1;

   477

	}

   478

}

   479

   480

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

   481

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   482

{

   483

	StackedItem si;

   484

	int i = 1, j;

   485

	int n;

   486

   487

	assert(tpf->nstack > 0);

   488

	n = --tpf->nstack;

   489

   490

	if (n == 0) return; // heap is empty so nothing to do?

   491

   492

	/* copy the last item to index 0. we use it as base for heapify. */

   493

	ARR(1) = ARR(n + 1);

   494

   495

	while ((j = i * 2) <= n) {

   496

		/* figure out which is smaller of the children. */

   497

		if (j != n && ARR(j).priority > ARR(j + 1).priority)

   498

			j++; // right item is smaller