1

#include "stdafx.h"

     2

#include "openttd.h"

     3

#include "map.h"

     4

#include "tile.h"

     5

#include "pathfind.h"

     6

#include "rail.h"

     7

#include "debug.h"

     8

     9

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

    10

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

    11

{

    12

	uint hash, val, offs;

    13

	TrackPathFinderLink *link, *new_link;

    14

	uint bits = 1 << dir;

    15

    16

	if (tpf->disable_tile_hash)

    17

		return true;

    18

    19

	hash = PATHFIND_HASH_TILE(tile);

    20

    21

	val = tpf->hash_head[hash];

    22

    23

	if (val == 0) {

    24

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

    25

		 * to indicate that a bit was set. */

    26

		tpf->hash_head[hash] = bits;

    27

		tpf->hash_tile[hash] = tile;

    28

		return true;

    29

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

    30

		/* single tile */

    31

    32

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

    33

			/* found another bit for the same tile,

    34

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

    35

			if (val & bits)

    36

				return false;

    37

    38

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

    39

			 * was set */

    40

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

    41

			return true;

    42

		} else {

    43

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

    44

    45

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

    46

			 * that a tile was already visisted. */

    47

			if (tpf->num_links_left == 0) {

    48

				DEBUG(misc, 4) ("[NTP] no links left\n");

    49

				return false;

    50

			}

    51

			tpf->num_links_left--;

    52

			link = tpf->new_link++;

    53

    54

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

    55

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

    56

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

    57

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

    58

    59

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

    60

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

    61

    62

			link->next = 0xFFFF;

    63

		}

    64

	} else {

    65

		/* a linked list of many tiles,

    66

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

    67

		 * otherwise make a new link */

    68

    69

		offs = tpf->hash_tile[hash];

    70

		do {

    71

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    72

			if (tile == link->tile) {

    73

				/* found the tile in the link list,

    74

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

    75

				 * bit was already set */

    76

				if (link->flags & bits)

    77

					return false;

    78

				link->flags |= bits;

    79

				return true;

    80

			}

    81

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

    82

	}

    83

    84

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

    85

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

    86

	if (tpf->num_links_left == 0) {

    87

			DEBUG(misc, 4)("[NTP] no links left\n");

    88

			return false;

    89

	}

    90

	tpf->num_links_left--;

    91

	new_link = tpf->new_link++;

    92

    93

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

    94

	 * link to the new one */

    95

	new_link->tile = tile;

    96

	new_link->flags = bits;

    97

	new_link->next = 0xFFFF;

    98

    99

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

   100

	return true;

   101

}

   102

   103

static const byte _bits_mask[4] = {

   104

	0x19,

   105

	0x16,

   106

	0x25,

   107

	0x2A,

   108

};

   109

   110

static const byte _tpf_new_direction[14] = {

   111

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

   112

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

   113

};

   114

   115

static const byte _tpf_prev_direction[14] = {

   116

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

   117

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

   118

};

   119

   120

   121

static const byte _otherdir_mask[4] = {

   122

	0x10,

   123

	0,

   124

	0x5,

   125

	0x2A,

   126

};

   127

   128

#ifdef DEBUG_TILE_PUSH

   129

extern void dbg_push_tile(TileIndex tile, int track);

   130

extern void dbg_pop_tile();

   131

#endif

   132

   133

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

   134

{

   135

	uint bits;

   136

	int i;

   137

	RememberData rd;

   138

	int owner = -1;

   139

   140

	/* XXX: Mode 2 is currently only used for ships, why is this code here? */

   141

	if (tpf->tracktype == TRANSPORT_RAIL) {

   142

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

   143

			owner = GetTileOwner(tile);

   144

			/* Check if we are on the middle of a bridge (has no owner) */

   145

			if (IsTileType(tile, MP_TUNNELBRIDGE) && (_m[tile].m5 & 0xC0) == 0xC0)

   146

				owner = -1;

   147

		}

   148

	}

   149

   150

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

   151

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

   152

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

   153

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

   154

   155

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

   156

	if (tpf->tracktype == TRANSPORT_RAIL) {

   157

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

   158

			/* Check if we are on the middle of a bridge (has no owner) */

   159

			if (!IsTileType(tile, MP_TUNNELBRIDGE) || (_m[tile].m5 & 0xC0) != 0xC0)

   160

				if (owner != -1 && !IsTileOwner(tile, owner))

   161

					return;

   162

	}

   163

   164

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

   165

		return;

   166

   167

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

   168

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

   169

	if (bits == 0)

   170

		return;

   171

   172

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

   173

   174

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

   175

		/* only one direction */

   176

		i = 0;

   177

		while (!(bits&1))

   178

			i++, bits>>=1;

   179

   180

		rd = tpf->rd;

   181

		goto continue_here;

   182

	}

   183

	/* several directions */

   184

	i=0;

   185

	do {

   186

		if (!(bits & 1)) continue;

   187

		rd = tpf->rd;

   188

   189

		// Change direction 4 times only

   190

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

   191

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

   192

				tpf->rd = rd;

   193

				return;

   194

			}

   195

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

   196

		}

   197

   198

continue_here:;

   199

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

   200

   201

#ifdef DEBUG_TILE_PUSH

   202

		dbg_push_tile(tile, tpf->the_dir);

   203

#endif

   204

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

   205

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

   206

		}

   207

#ifdef DEBUG_TILE_PUSH

   208

		dbg_pop_tile();

   209

#endif

   210

   211

		tpf->rd = rd;

   212

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

   213

   214

}

   215

   216

static const int8 _get_tunlen_inc[5] = { -16, 0, 16, 0, -16 };

   217

   218

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

   219

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

   220

 */

   221

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, int direction)

   222

{

   223

	FindLengthOfTunnelResult flotr;

   224

	int x,y;

   225

	byte z;

   226

   227

	flotr.length = 0;

   228

   229

	x = TileX(tile) * 16;

   230

	y = TileY(tile) * 16;

   231

   232

	z = GetSlopeZ(x+8, y+8);

   233

   234

	for(;;) {

   235

		flotr.length++;

   236

   237

		x += _get_tunlen_inc[direction];

   238

		y += _get_tunlen_inc[direction+1];

   239

   240

		tile = TileVirtXY(x, y);

   241

   242

		if (IsTileType(tile, MP_TUNNELBRIDGE) &&

   243

				(_m[tile].m5 & 0xF0) == 0 &&					// tunnel entrance/exit

   244

				//((_m[tile].m5>>2)&3) == type &&		// rail/road-tunnel <-- This is not necesary to check, right?

   245

				((_m[tile].m5 & 3)^2) == direction &&	// entrance towards: 0 = NE, 1 = SE, 2 = SW, 3 = NW

   246

				GetSlopeZ(x+8, y+8) == z)

   247

					break;

   248

	}

   249

   250

	flotr.tile = tile;

   251

	return flotr;

   252

}

   253

   254

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

   255

   256

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

   257

{

   258

	FindLengthOfTunnelResult flotr;

   259

	TPFSetTileBit(tpf, tile, 14);

   260

	flotr = FindLengthOfTunnel(tile, direction);

   261

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

   262

	TPFSetTileBit(tpf, flotr.tile, 14);

   263

	return flotr.tile;

   264

}

   265

   266

const byte _ffb_64[128] = {

   267

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

   268

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

   269

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

   270

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

   271

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

   272

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

   273

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

   274

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

   275

   276

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

   277

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

   278

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

   279

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

   280

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

   281

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

   282

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

   283

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

   284

};

   285

   286

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

   287

{

   288

	uint bits;

   289

	int i;

   290

	RememberData rd;

   291

	TileIndex tile_org = tile;

   292

   293

	if (IsTileType(tile, MP_TUNNELBRIDGE) && (_m[tile].m5 & 0xF0) == 0) {

   294

		if ((_m[tile].m5 & 3) != direction || ((_m[tile].m5>>2)&3) != tpf->tracktype)

   295

			return;

   296

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   297

	}

   298

	tile += TileOffsByDir(direction);

   299

   300

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

   301

	if (tpf->tracktype == TRANSPORT_RAIL) {

   302

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

   303

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

   304

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

   305

				if (!IsTileType(tile, MP_TUNNELBRIDGE) || (_m[tile].m5 & 0xC0) != 0xC0)

   306

					if (!IsTileType(tile_org, MP_TUNNELBRIDGE) || (_m[tile_org].m5 & 0xC0) != 0xC0)

   307

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

   308

							return;

   309

	}

   310

   311

	tpf->rd.cur_length++;

   312

   313

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

   314

   315

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

   316

		bits &= _tpfmode1_and[direction];

   317

		bits = bits | (bits>>8);

   318

	}

   319

	bits &= 0xBF;

   320

   321

	if (bits != 0) {

   322

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

   323

			do {

   324

				i = FIND_FIRST_BIT(bits);

   325

				bits = KILL_FIRST_BIT(bits);

   326

   327

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

   328

				rd = tpf->rd;

   329

   330

#ifdef DEBUG_TILE_PUSH

   331

		dbg_push_tile(tile, tpf->the_dir);

   332

#endif

   333

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

   334

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

   335

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

   336

				}

   337

#ifdef DEBUG_TILE_PUSH

   338

		dbg_pop_tile();

   339

#endif

   340

				tpf->rd = rd;

   341

			} while (bits != 0);

   342

		}

   343

	}

   344

   345

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

   346

	 * seems to go in 2 directions simultaneously */

   347

   348

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

   349

	 * stack space dramatically. */

   350

   351

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

   352

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

   353

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

   354

	if (tpf->hasbit_13)

   355

		return;

   356

   357

	tile = tile_org;

   358

	direction ^= 2;

   359

   360

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

   361

	bits |= (bits >> 8);

   362

   363

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

   364

		bits &= _bits_mask[direction];

   365

	}

   366

   367

	bits &= 0xBF;

   368

	if (bits == 0)

   369

		return;

   370

   371

	do {

   372

		i = FIND_FIRST_BIT(bits);

   373

		bits = KILL_FIRST_BIT(bits);

   374

   375

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

   376

		rd = tpf->rd;

   377

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

   378

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

   379

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

   380

		}

   381

		tpf->rd = rd;

   382

	} while (bits != 0);

   383

}

   384

   385

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

   386

{

   387

	TrackPathFinder tpf;

   388

   389

	assert(direction < 4);

   390

   391

	/* initialize path finder variables */

   392

	tpf.userdata = data;

   393

	tpf.enum_proc = enum_proc;

   394

	tpf.new_link = tpf.links;

   395

	tpf.num_links_left = lengthof(tpf.links);

   396

   397

	tpf.rd.cur_length = 0;

   398

	tpf.rd.depth = 0;

   399

	tpf.rd.pft_var6 = 0;

   400

   401

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

   402

   403

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

   404

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

   405

   406

   407

	tpf.tracktype = (byte)flags;

   408

   409

	if (HASBIT(flags, 11)) {

   410

		tpf.rd.pft_var6 = 0xFF;

   411

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

   412

		TPFMode2(&tpf, tile, direction);

   413

	} else {

   414

		/* clear the hash_heads */

   415

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

   416

		TPFMode1(&tpf, tile, direction);

   417

	}

   418

   419

	if (after_proc != NULL)

   420

		after_proc(&tpf);

   421

}

   422

   423

typedef struct {

   424

	TileIndex tile;

   425

	uint16 cur_length;

   426

	byte track;

   427

	byte depth;

   428

	byte state;

   429

	byte first_track;

   430

} StackedItem;

   431

   432

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

   433

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

   434

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

   435

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

   436

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

   437

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

   438

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

   439

};

   440

   441

typedef struct HashLink {

   442

	TileIndex tile;

   443

	uint16 typelength;

   444

	uint16 next;

   445

} HashLink;

   446

   447

typedef struct {

   448

	TPFEnumProc *enum_proc;

   449

	void *userdata;

   450

   451

	byte tracktype;

   452

	uint maxlength;

   453

   454

	HashLink *new_link;

   455

	uint num_links_left;

   456

   457

	uint nstack;

   458

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

   459

   460

	uint16 hash_head[0x400]; // hash heads. 0 means unused. 0xFFC0 = length, 0x3F = type

   461

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

   462

   463

	HashLink links[0x400]; // hash links

   464

   465

} NewTrackPathFinder;

   466

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

   467

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

   468

   469

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

   470

   471

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

   472

// move it down to the proper position

   473

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   474

{

   475

	StackedItem si;

   476

	int i = ++tpf->nstack;

   477

   478

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

   479

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

   480

		// swap the child item and the parent item.

   481

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

   482

		i>>=1;

   483

	}

   484

}

   485

   486

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

   487

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   488

{

   489

	StackedItem si;

   490

	int i = 1, j;

   491

	int n;

   492

   493

	assert(tpf->nstack > 0);

   494

	n = --tpf->nstack;

   495

   496

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

   497

   498

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

   499

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

   500

   501

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

   502

		// figure out which is smaller of the children.

   503

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

   504

			j++; // right item is smaller

   505

   506

		assert(i <= n && j <= n);

   507

		if (ARR(i).cur_length <= ARR(j).cur_length)

   508

			break; // base elem smaller than smallest, done!

   509

   510

		// swap parent with the child

   511

		si = ARR(i); ARR(i) = ARR(j); ARR(j) = si;