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

	uint bits = 0;

   257

	int i;

   258

	RememberData rd;

   259

	TileIndex tile_org = tile;

   260

   261

	// check if the old tile can be left at 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 (IsRoadStopTile(tile) && GetRoadStopDir(tile) != direction) return;

   266

		// don't enter road depot from the back

   267

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

   268

	}

   269

   270

	if (IsTunnelTile(tile)) {

   271

		if (GetTunnelDirection(tile) != direction ||

   272

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

   273

			return;

   274

		}

   275

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   276

	}

   277

	tile += TileOffsByDiagDir(direction);

   278

   279

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

   280

	/* Inside this block we should not use 'return' to indicate 'no way' condition (at least for rail transport type) */

   281

	if (tpf->tracktype == TRANSPORT_ROAD || tpf->tracktype == TRANSPORT_RAIL) {

   282

		if (tpf->tracktype == TRANSPORT_RAIL) {

   283

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

   284

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

   285

   286

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

   287

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

   288

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

   289

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

   290

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

   291

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

   292

							if (GetTileOwner(tile_org) != GetTileOwner(tile)) goto no_way;

   293

   294

		} else if (tpf->tracktype == TRANSPORT_ROAD) {

   295

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

   296

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

   297

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

   298

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

   299

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

   300

		}

   301

   302

		if (IsTileType(tile, MP_TUNNELBRIDGE)) {

   303

			if (IsTunnel(tile)) {

   304

				/* tunnel hole can be entered only from one direction */

   305

				if (GetTunnelDirection(tile) != direction) goto no_way;

   306

			}

   307

		}

   308

		if (tpf->tracktype == TRANSPORT_RAIL) {

   309

			/* check for the rail type compatibility */

   310

			Trackdir td = DiagdirToDiagTrackdir(direction);

   311

			RailType type_org = GetTileRailType(tile_org, td);

   312

			RailType type = GetTileRailType(tile, td);

   313

			if (type != type_org) {

   314

				// they can be compatible only if one is normal and the other one is elrail

   315

				if (type_org == RAILTYPE_RAIL && type != RAILTYPE_ELECTRIC) goto no_way;

   316

				if (type == RAILTYPE_RAIL && type_org != RAILTYPE_ELECTRIC) goto no_way;

   317

			}

   318

		}

   319

	}

   320

   321

	/* the next line is skipped when the new tile can't be entered from tile_org */

   322

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

   323

no_way:

   324

   325

	tpf->rd.cur_length++;

   326

   327

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

   328

		bits &= _tpfmode1_and[direction];

   329

		bits = bits | (bits>>8);

   330

	}

   331

	bits &= 0xBF;

   332

   333

	if (bits != 0) {

   334

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

   335

			do {

   336

				i = FIND_FIRST_BIT(bits);

   337

				bits = KILL_FIRST_BIT(bits);

   338

   339

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

   340

				rd = tpf->rd;

   341

   342

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

   343

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

   344

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

   345

				}

   346

				tpf->rd = rd;

   347

			} while (bits != 0);

   348

		}

   349

	}

   350

   351

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

   352

	 * seems to go in 2 directions simultaneously */

   353

   354

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

   355

	 * stack space dramatically. */

   356

   357

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

   358

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

   359

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

   360

	if (tpf->hasbit_13)

   361

		return;

   362

   363

	tile = tile_org;

   364

	direction = ReverseDiagDir(direction);

   365

   366

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

   367

	bits |= (bits >> 8);

   368

   369

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

   370

		bits &= _bits_mask[direction];

   371

	}

   372

   373

	bits &= 0xBF;

   374

	if (bits == 0)

   375

		return;

   376

   377

	do {

   378

		i = FIND_FIRST_BIT(bits);

   379

		bits = KILL_FIRST_BIT(bits);

   380

   381

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

   382

		rd = tpf->rd;

   383

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

   384

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

   385

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

   386

		}

   387

		tpf->rd = rd;

   388

	} while (bits != 0);

   389

}

   390

   391

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

   392

{

   393

	TrackPathFinder tpf;

   394

   395

	assert(direction < 4);

   396

   397

	/* initialize path finder variables */

   398

	tpf.userdata = data;

   399

	tpf.enum_proc = enum_proc;

   400

	tpf.new_link = tpf.links;

   401

	tpf.num_links_left = lengthof(tpf.links);

   402

   403

	tpf.rd.cur_length = 0;

   404

	tpf.rd.depth = 0;

   405

	tpf.rd.pft_var6 = 0;

   406

   407

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

   408

   409

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

   410

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

   411

   412

   413

	tpf.tracktype = (byte)flags;

   414

   415

	if (HASBIT(flags, 11)) {

   416

		tpf.rd.pft_var6 = 0xFF;

   417

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

   418

		TPFMode2(&tpf, tile, direction);

   419

	} else {

   420

		/* clear the hash_heads */

   421

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

   422

		TPFMode1(&tpf, tile, direction);

   423

	}

   424

   425

	if (after_proc != NULL)

   426

		after_proc(&tpf);

   427

}

   428

   429

typedef struct {

   430

	TileIndex tile;

   431

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

   432

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

   433

	byte track;

   434

	byte depth;

   435

	byte state;

   436

	byte first_track;

   437

} StackedItem;

   438

   439

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

   440

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

   441

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

   442

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

   443

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

   444

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

   445

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

   446

};

   447

   448

typedef struct HashLink {

   449

	TileIndex tile;

   450

	uint16 typelength;

   451

	uint16 next;

   452

} HashLink;

   453

   454

typedef struct {

   455

	NTPEnumProc *enum_proc;

   456

	void *userdata;

   457

	TileIndex dest;

   458

   459

	TransportType tracktype;

   460

	RailTypeMask railtypes;

   461

	uint maxlength;

   462

   463

	HashLink *new_link;

   464

	uint num_links_left;

   465

   466

	uint nstack;

   467

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

   468

   469

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

   470

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

   471

   472

	HashLink links[0x400]; // hash links

   473

   474

} NewTrackPathFinder;

   475

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

   476

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

   477

   478

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

   479

   480

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

   481

// move it down to the proper position

   482

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   483

{

   484

	StackedItem si;

   485

	int i = ++tpf->nstack;

   486

   487

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

   488

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

   489

		// swap the child item and the parent item.

   490

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

   491

		i>>=1;

   492

	}

   493

}

   494

   495

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

   496

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   497

{

   498

	StackedItem si;

   499

	int i = 1, j;

   500

	int n;

   501

   502

	assert(tpf->nstack > 0);

   503

	n = --tpf->nstack;

   504

   505

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