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"

     9

    10

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

    11

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

    12

{

    13

	uint hash, val, offs;

    14

	TrackPathFinderLink *link, *new_link;

    15

	uint bits = 1 << dir;

    16

    17

	if (tpf->disable_tile_hash)

    18

		return true;

    19

    20

	hash = PATHFIND_HASH_TILE(tile);

    21

    22

	val = tpf->hash_head[hash];

    23

    24

	if (val == 0) {

    25

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

    26

		 * to indicate that a bit was set. */

    27

		tpf->hash_head[hash] = bits;

    28

		tpf->hash_tile[hash] = tile;

    29

		return true;

    30

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

    31

		/* single tile */

    32

    33

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

    34

			/* found another bit for the same tile,

    35

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

    36

			if (val & bits)

    37

				return false;

    38

    39

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

    40

			 * was set */

    41

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

    42

			return true;

    43

		} else {

    44

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

    45

    46

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

    47

			 * that a tile was already visisted. */

    48

			if (tpf->num_links_left == 0) {

    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

			return false;

    88

	}

    89

	tpf->num_links_left--;

    90

	new_link = tpf->new_link++;

    91

    92

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

    93

	 * link to the new one */

    94

	new_link->tile = tile;

    95

	new_link->flags = bits;

    96

	new_link->next = 0xFFFF;

    97

    98

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

    99

	return true;

   100

}

   101

   102

static const byte _bits_mask[4] = {

   103

	0x19,

   104

	0x16,

   105

	0x25,

   106

	0x2A,

   107

};

   108

   109

static const byte _tpf_new_direction[14] = {

   110

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

   111

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

   112

};

   113

   114

static const byte _tpf_prev_direction[14] = {

   115

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

   116

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

   117

};

   118

   119

   120

static const byte _otherdir_mask[4] = {

   121

	0x10,

   122

	0,

   123

	0x5,

   124

	0x2A,

   125

};

   126

   127

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

   128

{

   129

	uint bits;

   130

	int i;

   131

	RememberData rd;

   132

	int owner = -1;

   133

   134

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

   135

	if (tpf->tracktype == TRANSPORT_RAIL) {

   136

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

   137

			owner = GetTileOwner(tile);

   138

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

   139

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

   140

				owner = -1;

   141

		}

   142

	}

   143

   144

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

   145

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

   146

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

   147

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

   148

   149

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

   150

	if (tpf->tracktype == TRANSPORT_RAIL) {

   151

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

   152

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

   153

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

   154

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

   155

					return;

   156

	}

   157

   158

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

   159

		return;

   160

   161

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

   162

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

   163

	if (bits == 0)

   164

		return;

   165

   166

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

   167

   168

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

   169

		/* only one direction */

   170

		i = 0;

   171

		while (!(bits&1))

   172

			i++, bits>>=1;

   173

   174

		rd = tpf->rd;

   175

		goto continue_here;

   176

	}

   177

	/* several directions */

   178

	i=0;

   179

	do {

   180

		if (!(bits & 1)) continue;

   181

		rd = tpf->rd;

   182

   183

		// Change direction 4 times only

   184

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

   185

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

   186

				tpf->rd = rd;

   187

				return;

   188

			}

   189

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

   190

		}

   191

   192

continue_here:;

   193

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

   194

   195

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

   196

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

   197

		}

   198

   199

		tpf->rd = rd;

   200

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

   201

   202

}

   203

   204

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

   205

   206

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

   207

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

   208

 */

   209

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, int direction)

   210

{

   211

	FindLengthOfTunnelResult flotr;

   212

	int x,y;

   213

	byte z;

   214

   215

	flotr.length = 0;

   216

   217

	x = TileX(tile) * 16;

   218

	y = TileY(tile) * 16;

   219

   220

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

   221

   222

	for(;;) {

   223

		flotr.length++;

   224

   225

		x += _get_tunlen_inc[direction];

   226

		y += _get_tunlen_inc[direction+1];

   227

   228

		tile = TileVirtXY(x, y);

   229

   230

		if (IsTileType(tile, MP_TUNNELBRIDGE) &&

   231

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

   232

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

   233

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

   234

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

   235

					break;

   236

	}

   237

   238

	flotr.tile = tile;

   239

	return flotr;

   240

}

   241

   242

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

   243

   244

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

   245

{

   246

	FindLengthOfTunnelResult flotr;

   247

	TPFSetTileBit(tpf, tile, 14);

   248

	flotr = FindLengthOfTunnel(tile, direction);

   249

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

   250

	TPFSetTileBit(tpf, flotr.tile, 14);

   251

	return flotr.tile;

   252

}

   253

   254

const byte _ffb_64[128] = {

   255

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

   256

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

   257

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

   258

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

   259

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

   260

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

   261

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

   262

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

   263

   264

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

   265

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

   266

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

   267

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

   268

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

   269

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

   270

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

   271

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

   272

};

   273

   274

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

   275

{

   276

	uint bits;

   277

	int i;

   278

	RememberData rd;

   279

	TileIndex tile_org = tile;

   280

   281

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

   282

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

   283

			return;

   284

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   285

	}

   286

	tile += TileOffsByDir(direction);

   287

   288

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

   289

	if (tpf->tracktype == TRANSPORT_RAIL) {

   290

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

   291

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

   292

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

   293

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

   294

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

   295

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

   296

							return;

   297

	}

   298

   299

	tpf->rd.cur_length++;

   300

   301

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

   302

   303

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

   304

		bits &= _tpfmode1_and[direction];

   305

		bits = bits | (bits>>8);

   306

	}

   307

	bits &= 0xBF;

   308

   309

	if (bits != 0) {

   310

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

   311

			do {

   312

				i = FIND_FIRST_BIT(bits);

   313

				bits = KILL_FIRST_BIT(bits);

   314

   315

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

   316

				rd = tpf->rd;

   317

   318

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

   319

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

   320

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

   321

				}

   322

				tpf->rd = rd;

   323

			} while (bits != 0);

   324

		}

   325

	}

   326

   327

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

   328

	 * seems to go in 2 directions simultaneously */

   329

   330

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

   331

	 * stack space dramatically. */

   332

   333

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

   334

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

   335

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

   336

	if (tpf->hasbit_13)

   337

		return;

   338

   339

	tile = tile_org;

   340

	direction ^= 2;

   341

   342

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

   343

	bits |= (bits >> 8);

   344

   345

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

   346

		bits &= _bits_mask[direction];

   347

	}

   348

   349

	bits &= 0xBF;

   350

	if (bits == 0)

   351

		return;

   352

   353

	do {

   354

		i = FIND_FIRST_BIT(bits);

   355

		bits = KILL_FIRST_BIT(bits);

   356

   357

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

   358

		rd = tpf->rd;

   359

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

   360

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

   361

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

   362

		}

   363

		tpf->rd = rd;

   364

	} while (bits != 0);

   365

}

   366

   367

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

   368

{

   369

	TrackPathFinder tpf;

   370

   371

	assert(direction < 4);

   372

   373

	/* initialize path finder variables */

   374

	tpf.userdata = data;

   375

	tpf.enum_proc = enum_proc;

   376

	tpf.new_link = tpf.links;

   377

	tpf.num_links_left = lengthof(tpf.links);

   378

   379

	tpf.rd.cur_length = 0;

   380

	tpf.rd.depth = 0;

   381

	tpf.rd.pft_var6 = 0;

   382

   383

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

   384

   385

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

   386

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

   387

   388

   389

	tpf.tracktype = (byte)flags;

   390

   391

	if (HASBIT(flags, 11)) {

   392

		tpf.rd.pft_var6 = 0xFF;

   393

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

   394

		TPFMode2(&tpf, tile, direction);

   395

	} else {

   396

		/* clear the hash_heads */

   397

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

   398

		TPFMode1(&tpf, tile, direction);

   399

	}

   400

   401

	if (after_proc != NULL)

   402

		after_proc(&tpf);

   403

}

   404

   405

typedef struct {

   406

	TileIndex tile;

   407

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

   408

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

   409

	byte track;

   410

	byte depth;

   411

	byte state;

   412

	byte first_track;

   413

} StackedItem;

   414

   415

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

   416

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

   417

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

   418

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

   419

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

   420

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

   421

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

   422

};

   423

   424

typedef struct HashLink {

   425

	TileIndex tile;

   426

	uint16 typelength;

   427

	uint16 next;

   428

} HashLink;

   429

   430

typedef struct {

   431

	NTPEnumProc *enum_proc;

   432

	void *userdata;

   433

	TileIndex dest;

   434

   435

	byte tracktype;

   436

	uint maxlength;

   437

   438

	HashLink *new_link;

   439

	uint num_links_left;

   440

   441

	uint nstack;

   442

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

   443

   444

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

   445

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

   446

   447

	HashLink links[0x400]; // hash links

   448

   449

} NewTrackPathFinder;

   450

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

   451

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

   452

   453

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

   454

   455

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

   456

// move it down to the proper position

   457

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   458

{

   459

	StackedItem si;

   460

	int i = ++tpf->nstack;

   461

   462

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

   463

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

   464

		// swap the child item and the parent item.

   465

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

   466

		i>>=1;

   467

	}

   468

}

   469

   470

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

   471

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   472

{

   473

	StackedItem si;

   474

	int i = 1, j;

   475

	int n;

   476

   477

	assert(tpf->nstack > 0);

   478

	n = --tpf->nstack;

   479

   480

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

   481

   482

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

   483

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

   484

   485

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

   486

		// figure out which is smaller of the children.

   487

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

   488

			j++; // right item is smaller

   489

   490

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

   491

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

   492

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

   493

   494

		// swap parent with the child

   495

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

   496

		i = j;

   497

	}

   498

}

   499

   500

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

   501

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

   502

// otherwise return true.

   503

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

   504

{

   505

	uint hash,head;

   506

	HashLink *link, *new_link;

   507

   508

	assert(length < 16384-1);

   509

   510

	hash = PATHFIND_HASH_TILE(tile);