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

				return false;

    49

			}

    50

			tpf->num_links_left--;

    51

			link = tpf->new_link++;

    52

    53

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

    54

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

    55

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

    56

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

    57

    58

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

    59

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

    60

    61

			link->next = 0xFFFF;

    62

		}

    63

	} else {

    64

		/* a linked list of many tiles,

    65

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

    66

		 * otherwise make a new link */

    67

    68

		offs = tpf->hash_tile[hash];

    69

		do {

    70

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    71

			if (tile == link->tile) {

    72

				/* found the tile in the link list,

    73

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

    74

				 * bit was already set */

    75

				if (link->flags & bits)

    76

					return false;

    77

				link->flags |= bits;

    78

				return true;

    79

			}

    80

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

    81

	}

    82

    83

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

    84

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

    85

	if (tpf->num_links_left == 0) {

    86

			return false;

    87

	}

    88

	tpf->num_links_left--;

    89

	new_link = tpf->new_link++;

    90

    91

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

    92

	 * link to the new one */

    93

	new_link->tile = tile;

    94

	new_link->flags = bits;

    95

	new_link->next = 0xFFFF;

    96

    97

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

    98

	return true;

    99

}

   100

   101

static const byte _bits_mask[4] = {

   102

	0x19,

   103

	0x16,

   104

	0x25,

   105

	0x2A,

   106

};

   107

   108

static const byte _tpf_new_direction[14] = {

   109

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

   110

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

   111

};

   112

   113

static const byte _tpf_prev_direction[14] = {

   114

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

   115

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

   116

};

   117

   118

   119

static const byte _otherdir_mask[4] = {

   120

	0x10,

   121

	0,

   122

	0x5,

   123

	0x2A,

   124

};

   125

   126

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

   127

{

   128

	uint bits;

   129

	int i;

   130

	RememberData rd;

   131

	int owner = -1;

   132

   133

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

   134

	if (tpf->tracktype == TRANSPORT_RAIL) {

   135

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

   136

			owner = GetTileOwner(tile);

   137

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

   138

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

   139

				owner = -1;

   140

		}

   141

	}

   142

   143

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

   144

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

   145

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

   146

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

   147

   148

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

   149

	if (tpf->tracktype == TRANSPORT_RAIL) {

   150

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

   151

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

   152

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

   153

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

   154

					return;

   155

	}

   156

   157

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

   158

		return;

   159

   160

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

   161

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

   162

	if (bits == 0)

   163

		return;

   164

   165

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

   166

   167

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

   168

		/* only one direction */

   169

		i = 0;

   170

		while (!(bits&1))

   171

			i++, bits>>=1;

   172

   173

		rd = tpf->rd;

   174

		goto continue_here;

   175

	}

   176

	/* several directions */

   177

	i=0;

   178

	do {

   179

		if (!(bits & 1)) continue;

   180

		rd = tpf->rd;

   181

   182

		// Change direction 4 times only

   183

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

   184

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

   185

				tpf->rd = rd;

   186

				return;

   187

			}

   188

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

   189

		}

   190

   191

continue_here:;

   192

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

   193

   194

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

   195

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

   196

		}

   197

   198

		tpf->rd = rd;

   199

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

   200

   201

}

   202

   203

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

   204

   205

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

   206

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

   207

 */

   208

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, int direction)

   209

{

   210

	FindLengthOfTunnelResult flotr;

   211

	int x,y;

   212

	byte z;

   213

   214

	flotr.length = 0;

   215

   216

	x = TileX(tile) * 16;

   217

	y = TileY(tile) * 16;

   218

   219

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

   220

   221

	for(;;) {

   222

		flotr.length++;

   223

   224

		x += _get_tunlen_inc[direction];

   225

		y += _get_tunlen_inc[direction+1];

   226

   227

		tile = TileVirtXY(x, y);

   228

   229

		if (IsTileType(tile, MP_TUNNELBRIDGE) &&

   230

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

   231

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

   232

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

   233

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

   234

					break;

   235

	}

   236

   237

	flotr.tile = tile;

   238

	return flotr;

   239

}

   240

   241

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

   242

   243

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

   244

{

   245

	FindLengthOfTunnelResult flotr;

   246

	TPFSetTileBit(tpf, tile, 14);

   247

	flotr = FindLengthOfTunnel(tile, direction);

   248

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

   249

	TPFSetTileBit(tpf, flotr.tile, 14);

   250

	return flotr.tile;

   251

}

   252

   253

const byte _ffb_64[128] = {

   254

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

   255

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

   256

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

   257

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

   258

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

   259

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

   260

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

   261

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

   262

   263

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

   264

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

   265

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

   266

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

   267

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

   268

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

   269

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

   270

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

   271

};

   272

   273

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

   274

{

   275

	uint bits;

   276

	int i;

   277

	RememberData rd;

   278

	TileIndex tile_org = tile;

   279

   280

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

   281

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

   282

			return;

   283

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   284

	}

   285

	tile += TileOffsByDir(direction);

   286

   287

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

   288

	if (tpf->tracktype == TRANSPORT_RAIL) {

   289

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

   290

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

   291

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

   292

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

   293

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

   294

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

   295

							return;

   296

	}

   297

   298

	tpf->rd.cur_length++;

   299

   300

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

   301

   302

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

   303

		bits &= _tpfmode1_and[direction];

   304

		bits = bits | (bits>>8);

   305

	}

   306

	bits &= 0xBF;

   307

   308

	if (bits != 0) {

   309

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

   310

			do {

   311

				i = FIND_FIRST_BIT(bits);

   312

				bits = KILL_FIRST_BIT(bits);

   313

   314

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

   315

				rd = tpf->rd;

   316

   317

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

   318

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

   319

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

   320

				}

   321

				tpf->rd = rd;

   322

			} while (bits != 0);

   323

		}

   324

	}

   325

   326

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

   327

	 * seems to go in 2 directions simultaneously */

   328

   329

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

   330

	 * stack space dramatically. */

   331

   332

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

   333

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

   334

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

   335

	if (tpf->hasbit_13)

   336

		return;

   337

   338

	tile = tile_org;

   339

	direction ^= 2;

   340

   341

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

   342

	bits |= (bits >> 8);

   343

   344

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

   345

		bits &= _bits_mask[direction];

   346

	}

   347

   348

	bits &= 0xBF;

   349

	if (bits == 0)

   350

		return;

   351

   352

	do {

   353

		i = FIND_FIRST_BIT(bits);

   354

		bits = KILL_FIRST_BIT(bits);

   355

   356

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

   357

		rd = tpf->rd;

   358

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

   359

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

   360

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

   361

		}

   362

		tpf->rd = rd;

   363

	} while (bits != 0);

   364

}

   365

   366

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

   367

{

   368

	TrackPathFinder tpf;

   369

   370

	assert(direction < 4);

   371

   372

	/* initialize path finder variables */

   373

	tpf.userdata = data;

   374

	tpf.enum_proc = enum_proc;

   375

	tpf.new_link = tpf.links;

   376

	tpf.num_links_left = lengthof(tpf.links);

   377

   378

	tpf.rd.cur_length = 0;

   379

	tpf.rd.depth = 0;

   380

	tpf.rd.pft_var6 = 0;

   381

   382

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

   383

   384

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

   385

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

   386

   387

   388

	tpf.tracktype = (byte)flags;

   389

   390

	if (HASBIT(flags, 11)) {

   391

		tpf.rd.pft_var6 = 0xFF;

   392

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

   393

		TPFMode2(&tpf, tile, direction);

   394

	} else {

   395

		/* clear the hash_heads */

   396

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

   397

		TPFMode1(&tpf, tile, direction);

   398

	}

   399

   400

	if (after_proc != NULL)

   401

		after_proc(&tpf);

   402

}

   403

   404

typedef struct {

   405

	TileIndex tile;

   406

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

   407

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

   408

	byte track;

   409

	byte depth;

   410

	byte state;

   411

	byte first_track;

   412

} StackedItem;

   413

   414

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

   415

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

   416

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

   417

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

   418

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

   419

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

   420

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

   421

};

   422

   423

typedef struct HashLink {

   424

	TileIndex tile;

   425

	uint16 typelength;

   426

	uint16 next;

   427

} HashLink;

   428

   429

typedef struct {

   430

	NTPEnumProc *enum_proc;

   431

	void *userdata;

   432

	TileIndex dest;

   433

   434

	byte tracktype;

   435

	uint maxlength;

   436

   437

	HashLink *new_link;

   438

	uint num_links_left;

   439

   440

	uint nstack;

   441

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

   442

   443

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

   444

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

   445

   446

	HashLink links[0x400]; // hash links

   447

   448

} NewTrackPathFinder;

   449

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

   450

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

   451

   452

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

   453

   454

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

   455

// move it down to the proper position

   456

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   457

{

   458

	StackedItem si;

   459

	int i = ++tpf->nstack;

   460

   461

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

   462

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

   463

		// swap the child item and the parent item.

   464

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

   465

		i>>=1;

   466

	}

   467

}

   468

   469

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

   470

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   471

{

   472

	StackedItem si;

   473

	int i = 1, j;

   474

	int n;

   475

   476

	assert(tpf->nstack > 0);

   477

	n = --tpf->nstack;

   478

   479

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

   480

   481

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

   482

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

   483

   484

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

   485

		// figure out which is smaller of the children.

   486

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

   487

			j++; // right item is smaller

   488

   489

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

   490

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

   491

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

   492

   493

		// swap parent with the child

   494

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

   495

		i = j;

   496

	}

   497

}

   498

   499

// mark a tile as visited and store the length of the path.

   500

// if we already had a better path to this tile, return false.

   501

// otherwise return true.

   502

static bool NtpVisit(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint length)

   503

{

   504

	uint hash,head;

   505

	HashLink *link, *new_link;

   506

   507

	assert(length < 16384-1);

   508

   509

	hash = PATHFIND_HASH_TILE(tile);

   510