1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "bridge_map.h"

     6

#include "station_map.h"

     7

#include "depot.h"

     8

#include "functions.h"

     9

#include "map.h"

    10

#include "tile.h"

    11

#include "pathfind.h"

    12

#include "rail.h"

    13

#include "debug.h"

    14

#include "tunnel_map.h"

    15

#include "variables.h"

    16

#include "depot.h"

    17

    18

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

    19

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

    20

{

    21

	uint hash, val, offs;

    22

	TrackPathFinderLink *link, *new_link;

    23

	uint bits = 1 << dir;

    24

    25

	if (tpf->disable_tile_hash)

    26

		return true;

    27

    28

	hash = PATHFIND_HASH_TILE(tile);

    29

    30

	val = tpf->hash_head[hash];

    31

    32

	if (val == 0) {

    33

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

    34

		 * to indicate that a bit was set. */

    35

		tpf->hash_head[hash] = bits;

    36

		tpf->hash_tile[hash] = tile;

    37

		return true;

    38

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

    39

		/* single tile */

    40

    41

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

    42

			/* found another bit for the same tile,

    43

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

    44

			if (val & bits)

    45

				return false;

    46

    47

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

    48

			 * was set */

    49

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

    50

			return true;

    51

		} else {

    52

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

    53

    54

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

    55

			 * that a tile was already visisted. */

    56

			if (tpf->num_links_left == 0) {

    57

				return false;

    58

			}

    59

			tpf->num_links_left--;

    60

			link = tpf->new_link++;

    61

    62

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

    63

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

    64

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

    65

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

    66

    67

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

    68

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

    69

    70

			link->next = 0xFFFF;

    71

		}

    72

	} else {

    73

		/* a linked list of many tiles,

    74

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

    75

		 * otherwise make a new link */

    76

    77

		offs = tpf->hash_tile[hash];

    78

		do {

    79

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    80

			if (tile == link->tile) {

    81

				/* found the tile in the link list,

    82

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

    83

				 * bit was already set */

    84

				if (link->flags & bits)

    85

					return false;

    86

				link->flags |= bits;

    87

				return true;

    88

			}

    89

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

    90

	}

    91

    92

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

    93

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

    94

	if (tpf->num_links_left == 0) {

    95

			return false;

    96

	}

    97

	tpf->num_links_left--;

    98

	new_link = tpf->new_link++;

    99

   100

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

   101

	 * link to the new one */

   102

	new_link->tile = tile;

   103

	new_link->flags = bits;

   104

	new_link->next = 0xFFFF;

   105

   106

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

   107

	return true;

   108

}

   109

   110

static const byte _bits_mask[4] = {

   111

	0x19,

   112

	0x16,

   113

	0x25,

   114

	0x2A,

   115

};

   116

   117

static const byte _tpf_new_direction[14] = {

   118

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

   119

	0, 0,

   120

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

   121

};

   122

   123

static const byte _tpf_prev_direction[14] = {

   124

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

   125

	0, 0,

   126

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

   127

};

   128

   129

   130

static const byte _otherdir_mask[4] = {

   131

	0x10,

   132

	0,

   133

	0x5,

   134

	0x2A,

   135

};

   136

   137

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

   138

{

   139

	uint bits;

   140

	int i;

   141

	RememberData rd;

   142

   143

	assert(tpf->tracktype == TRANSPORT_WATER);

   144

   145

	// This addition will sometimes overflow by a single tile.

   146

	// The use of TILE_MASK here makes sure that we still point at a valid

   147

	// tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail.

   148

	tile = TILE_MASK(tile + TileOffsByDiagDir(direction));

   149

   150

	if (++tpf->rd.cur_length > 50)

   151

		return;

   152

   153

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

   154

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

   155

	if (bits == 0)

   156

		return;

   157

   158

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

   159

   160

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

   161

		/* only one direction */

   162

		i = 0;

   163

		while (!(bits&1))

   164

			i++, bits>>=1;

   165

   166

		rd = tpf->rd;

   167

		goto continue_here;

   168

	}

   169

	/* several directions */

   170

	i=0;

   171

	do {

   172

		if (!(bits & 1)) continue;

   173

		rd = tpf->rd;

   174

   175

		// Change direction 4 times only

   176

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

   177

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

   178

				tpf->rd = rd;

   179

				return;

   180

			}

   181

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

   182

		}

   183

   184

continue_here:;

   185

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

   186

   187

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

   188

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

   189

		}

   190

   191

		tpf->rd = rd;

   192

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

   193

   194

}

   195

   196

   197

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

   198

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

   199

 */

   200

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   201

{

   202

	TileIndexDiff delta = TileOffsByDiagDir(dir);

   203

	uint z = GetTileZ(tile);

   204

	FindLengthOfTunnelResult flotr;

   205

   206

	flotr.length = 0;

   207

   208

	dir = ReverseDiagDir(dir);

   209

	do {

   210

		flotr.length++;

   211

		tile += delta;

   212

	} while(

   213

		!IsTunnelTile(tile) ||

   214

		GetTunnelDirection(tile) != dir ||

   215

		GetTileZ(tile) != z

   216

	);

   217

   218

	flotr.tile = tile;

   219

	return flotr;

   220

}

   221

   222

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

   223

   224

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

   225

{

   226

	FindLengthOfTunnelResult flotr;

   227

	TPFSetTileBit(tpf, tile, 14);

   228

	flotr = FindLengthOfTunnel(tile, direction);

   229

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

   230

	TPFSetTileBit(tpf, flotr.tile, 14);

   231

	return flotr.tile;

   232

}

   233

   234

const byte _ffb_64[128] = {

   235

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

   236

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

   237

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

   238

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

   239

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

   240

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

   241

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

   242

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

   243

   244

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

   245

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

   246

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

   247

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

   248

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

   249

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

   250

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

   251

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

   252

};

   253

   254

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

   255

   256

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

   257

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

   258

 * gotos ;). */

   259

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

   260

{

   261

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

   262

	if (tpf->tracktype == TRANSPORT_RAIL) {

   263

		// don't enter train depot from the back

   264

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

   265

   266

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

   267

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

   268

				/* Check if we are on a bridge (middle parts don't have an owner */

   269

				if (!IsBridgeTile(tile) || !IsBridgeMiddle(tile))

   270

					if (!IsBridgeTile(tile_org) || !IsBridgeMiddle(tile_org))

   271

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

   272

							return;

   273

	}

   274

   275

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

   276

	if (tpf->tracktype == TRANSPORT_ROAD) {

   277

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

   278

		// don't enter road stop from the back

   279

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

   280

		// don't enter road depot from the back

   281

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

   282

	}

   283

   284

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

   285

	 * and transport type match */

   286

	if (IsTileType(tile, MP_TUNNELBRIDGE) && IsTunnel(tile)) {

   287

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

   288

			return;

   289

		}

   290

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

   291

		 * be headed outwards if our starting position was in a

   292

		 * tunnel and we're pathfinding backwards */

   293

		if (GetTunnelDirection(tile) == direction) {

   294

			tile = SkipToEndOfTunnel(tpf, tile, direction);

   295

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

   296

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

   297

			 * entrance :-) */

   298

			return;

   299

		}

   300

	}

   301

}

   302

   303

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

   304

{

   305

	uint bits;

   306

	int i;

   307

	RememberData rd;

   308

	TileIndex tile_org = tile;

   309

   310

	// check if the old tile can be left at that direction

   311

	if (tpf->tracktype == TRANSPORT_ROAD) {

   312

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

   313

		// don't enter road stop from the back

   314

		if (IsRoadStopTile(tile) && GetRoadStopDir(tile) != direction) return;

   315

		// don't enter road depot from the back

   316

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

   317

	}

   318

   319

	if (IsTunnelTile(tile)) {

   320

		if (GetTunnelDirection(tile) != direction ||

   321

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

   322

			return;

   323

		}

   324

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   325

	}

   326

	tile += TileOffsByDiagDir(direction);

   327

   328

	tpf->rd.cur_length++;

   329

   330

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

   331

   332

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

   333

		bits &= _tpfmode1_and[direction];

   334

		bits = bits | (bits>>8);

   335

	}

   336

	bits &= 0xBF;

   337

   338

	if (bits != 0) {

   339

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

   340

			do {

   341

				i = FIND_FIRST_BIT(bits);

   342

				bits = KILL_FIRST_BIT(bits);

   343

   344

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

   345

				rd = tpf->rd;

   346

   347

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

   348

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

   349

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

   350

				}

   351

				tpf->rd = rd;

   352

			} while (bits != 0);

   353

		}

   354

	}

   355

   356

	TPFMode1_NormalCase(tpf, tile, tile_org, direction);

   357

   358

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

   359

	 * seems to go in 2 directions simultaneously */

   360

   361

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

   362

	 * stack space dramatically. */

   363

   364

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

   365

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

   366

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

   367

	if (tpf->hasbit_13)

   368

		return;

   369

   370

	direction = ReverseDiagDir(direction);

   371

	tile += TileOffsByDiagDir(direction);

   372

   373

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

   374

	bits |= (bits >> 8);

   375

   376

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

   377

		bits &= _bits_mask[direction];

   378

	}

   379

   380

	bits &= 0xBF;

   381

	if (bits == 0)

   382

		return;

   383

   384

	do {

   385

		i = FIND_FIRST_BIT(bits);

   386

		bits = KILL_FIRST_BIT(bits);

   387

   388

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

   389

		rd = tpf->rd;

   390

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

   391

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

   392

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

   393

		}

   394

		tpf->rd = rd;

   395

	} while (bits != 0);

   396

}

   397

   398

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

   399

{

   400

	TrackPathFinder tpf;

   401

   402

	assert(direction < 4);

   403

   404

	/* initialize path finder variables */

   405

	tpf.userdata = data;

   406

	tpf.enum_proc = enum_proc;

   407

	tpf.new_link = tpf.links;

   408

	tpf.num_links_left = lengthof(tpf.links);

   409

   410

	tpf.rd.cur_length = 0;

   411

	tpf.rd.depth = 0;

   412

	tpf.rd.pft_var6 = 0;

   413

   414

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

   415

   416

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

   417

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

   418

   419

   420

	tpf.tracktype = (byte)flags;

   421

   422

	if (HASBIT(flags, 11)) {

   423

		tpf.rd.pft_var6 = 0xFF;

   424

		tpf.enum_proc(tile, data, 0, 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

typedef struct {

   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

	byte track;

   441

	byte depth;

   442

	byte state;

   443

	byte first_track;

   444

} StackedItem;

   445

   446

static const byte _new_track[6][4] = {

   447

{0,    0xff, 8,    0xff,},

   448

{0xff, 1,    0xff, 9,},

   449

{0xff, 2,    10,   0xff,},

   450

{3,    0xff, 0xff, 11,},

   451

{12,   4,    0xff, 0xff,},

   452

{0xff, 0xff, 5,    13,},

   453

};

   454

   455

typedef struct HashLink {

   456

	TileIndex tile;

   457

	uint16 typelength;

   458

	uint16 next;

   459

} HashLink;

   460

   461

typedef struct {

   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

} NewTrackPathFinder;

   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

	}

   500

}

   501

   502

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

   503

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   504

{

   505

	StackedItem si;