1

#include "stdafx.h"

     2

#include "openttd.h"

     3

#include "map.h"

     4

#include "tile.h"

     5

#include "pathfind.h"

     6

     7

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

     8

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

     9

{

    10

	uint hash, val, offs;

    11

	TrackPathFinderLink *link, *new_link;

    12

	uint bits = 1 << dir;

    13

    14

	if (tpf->disable_tile_hash)

    15

		return true;

    16

    17

	hash = PATHFIND_HASH_TILE(tile);

    18

    19

	val = tpf->hash_head[hash];

    20

    21

	if (val == 0) {

    22

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

    23

		 * to indicate that a bit was set. */

    24

		tpf->hash_head[hash] = bits;

    25

		tpf->hash_tile[hash] = (TileIndex)tile;

    26

		return true;

    27

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

    28

		/* single tile */

    29

    30

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

    31

			/* found another bit for the same tile,

    32

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

    33

			if (val & bits)

    34

				return false;

    35

    36

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

    37

			 * was set */

    38

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

    39

			return true;

    40

		} else {

    41

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

    42

    43

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

    44

			 * that a tile was already visisted. */

    45

			if (tpf->num_links_left == 0)

    46

				return false;

    47

			tpf->num_links_left--;

    48

			link = tpf->new_link++;

    49

    50

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

    51

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

    52

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

    53

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

    54

    55

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

    56

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

    57

    58

			link->next = 0xFFFF;

    59

		}

    60

	} else {

    61

		/* a linked list of many tiles,

    62

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

    63

		 * otherwise make a new link */

    64

    65

		offs = tpf->hash_tile[hash];

    66

		do {

    67

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    68

			if ( (TileIndex)tile == link->tile) {

    69

				/* found the tile in the link list,

    70

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

    71

				 * bit was already set */

    72

				if (link->flags & bits)

    73

					return false;

    74

				link->flags |= bits;

    75

				return true;

    76

			}

    77

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

    78

	}

    79

    80

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

    81

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

    82

	if (tpf->num_links_left == 0)

    83

			return false;

    84

	tpf->num_links_left--;

    85

	new_link = tpf->new_link++;

    86

    87

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

    88

	 * link to the new one */

    89

	new_link->tile = (TileIndex)tile;

    90

	new_link->flags = bits;

    91

	new_link->next = 0xFFFF;

    92

    93

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

    94

	return true;

    95

}

    96

    97

static const byte _bits_mask[4] = {

    98

	0x19,

    99

	0x16,

   100

	0x25,

   101

	0x2A,

   102

};

   103

   104

static const byte _tpf_new_direction[14] = {

   105

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

   106

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

   107

};

   108

   109

static const byte _tpf_prev_direction[14] = {

   110

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

   111

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

   112

};

   113

   114

   115

static const byte _otherdir_mask[4] = {

   116

	0x10,

   117

	0,

   118

	0x5,

   119

	0x2A,

   120

};

   121

   122

#ifdef DEBUG_TILE_PUSH

   123

extern void dbg_push_tile(TileIndex tile, int track);

   124

extern void dbg_pop_tile();

   125

#endif

   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

	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) && (_map5[tile] & 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) || (_map5[tile] & 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

#ifdef DEBUG_TILE_PUSH

   195

		dbg_push_tile(tile, tpf->the_dir);

   196

#endif

   197

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

   198

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

   199

		}

   200

#ifdef DEBUG_TILE_PUSH

   201

		dbg_pop_tile();

   202

#endif

   203

   204

		tpf->rd = rd;

   205

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

   206

   207

}

   208

   209

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

   210

   211

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

   212

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

   213

 */

   214

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, int direction)

   215

{

   216

	FindLengthOfTunnelResult flotr;

   217

	int x,y;

   218

	byte z;

   219

   220

	flotr.length = 0;

   221

   222

	x = TileX(tile) * 16;

   223

	y = TileY(tile) * 16;

   224

   225

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

   226

   227

	for(;;) {

   228

		flotr.length++;

   229

   230

		x += _get_tunlen_inc[direction];

   231

		y += _get_tunlen_inc[direction+1];

   232

   234

   235

		if (IsTileType(tile, MP_TUNNELBRIDGE) &&

   236

				(_map5[tile] & 0xF0) == 0 &&					// tunnel entrance/exit

   237

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

   238

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

   239

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

   240

					break;

   241

	}

   242

   243

	flotr.tile = tile;

   244

	return flotr;

   245

}

   246

   247

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

   248

   249

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

   250

{

   251

	FindLengthOfTunnelResult flotr;

   252

	TPFSetTileBit(tpf, tile, 14);

   253

	flotr = FindLengthOfTunnel(tile, direction);

   254

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

   255

	TPFSetTileBit(tpf, flotr.tile, 14);

   256

	return flotr.tile;

   257

}

   258

   259

const byte _ffb_64[128] = {

   260

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

   261

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

   262

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

   263

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

   264

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

   265

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

   266

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

   267

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

   268

   269

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

   270

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

   271

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

   272

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

   273

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

   274

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

   275

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

   276

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

   277

};

   278

   279

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

   280

{

   281

	uint bits;

   282

	int i;

   283

	RememberData rd;

   284

	TileIndex tile_org = tile;

   285

   286

	if (IsTileType(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0) == 0) {

   287

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

   288

			return;

   289

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   290

	}

   291

	tile += TileOffsByDir(direction);

   292

   293

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

   294

	if (tpf->tracktype == TRANSPORT_RAIL) {

   295

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

   296

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

   297

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

   298

				if (!IsTileType(tile, MP_TUNNELBRIDGE) || (_map5[tile] & 0xC0) != 0xC0)

   299

					if (!IsTileType(tile_org, MP_TUNNELBRIDGE) || (_map5[tile_org] & 0xC0) != 0xC0)

   300

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

   301

							return;

   302

	}

   303

   304

	tpf->rd.cur_length++;

   305

   306

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

   307

   308

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

   309

		bits &= _tpfmode1_and[direction];

   310

		bits = bits | (bits>>8);

   311

	}

   312

	bits &= 0xBF;

   313

   314

	if (bits != 0) {

   315

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

   316

			do {

   317

				i = FIND_FIRST_BIT(bits);

   318

				bits = KILL_FIRST_BIT(bits);

   319

   320

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

   321

				rd = tpf->rd;

   322

   323

#ifdef DEBUG_TILE_PUSH

   324

		dbg_push_tile(tile, tpf->the_dir);

   325

#endif

   326

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

   327

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

   328

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

   329

				}

   330

#ifdef DEBUG_TILE_PUSH

   331

		dbg_pop_tile();

   332

#endif

   333

				tpf->rd = rd;

   334

			} while (bits != 0);

   335

		}

   336

	}

   337

   338

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

   339

	 * seems to go in 2 directions simultaneously */

   340

   341

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

   342

	 * stack space dramatically. */

   343

	if (tpf->hasbit_13)

   344

		return;

   345

   346

	tile = tile_org;

   347

	direction ^= 2;

   348

   349

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

   350

	bits |= (bits >> 8);

   351

   352

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

   353

		bits &= _bits_mask[direction];

   354

	}

   355

   356

	bits &= 0xBF;

   357

	if (bits == 0)

   358

		return;

   359

   360

	do {

   361

		i = FIND_FIRST_BIT(bits);

   362

		bits = KILL_FIRST_BIT(bits);

   363

   364

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

   365

		rd = tpf->rd;

   366

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

   367

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

   368

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

   369

		}

   370

		tpf->rd = rd;

   371

	} while (bits != 0);

   372

}

   373

   374

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

   375

{

   376

	TrackPathFinder tpf;

   377

   378

	assert(direction < 4);

   379

   380

	/* initialize path finder variables */

   381

	tpf.userdata = data;

   382

	tpf.enum_proc = enum_proc;

   383

	tpf.new_link = tpf.links;

   384

	tpf.num_links_left = lengthof(tpf.links);

   385

   386

	tpf.rd.cur_length = 0;

   387

	tpf.rd.depth = 0;

   388

	tpf.rd.pft_var6 = 0;

   389

   390

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

   391

   392

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

   393

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

   394

   395

   396

	tpf.tracktype = (byte)flags;

   397

   398

	if (HASBIT(flags, 11)) {

   399

		tpf.rd.pft_var6 = 0xFF;

   400

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

   401

		TPFMode2(&tpf, tile, direction);

   402

	} else {

   403

		/* clear the hash_heads */

   404

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

   405

		TPFMode1(&tpf, tile, direction);

   406

	}

   407

   408

	if (after_proc != NULL)

   409

		after_proc(&tpf);

   410

}

   411

   412

typedef struct {

   413

	TileIndex tile;

   414

	uint16 cur_length;

   415

	byte track;

   416

	byte depth;

   417

	byte state;

   418

	byte first_track;

   419

} StackedItem;

   420

   421

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

   422

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

   423

{0xff,1,0xff,3,},

   424

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

   425

{1,0xff,0xff,2,},

   426

{3,2,0xff,0xff,},

   427

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

   428

};

   429

   430

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

   431

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

   432

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

   433

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

   434

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

   435

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

   436

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

   437

};

   438

   439

typedef struct HashLink {

   440

	TileIndex tile;

   441

	uint16 typelength;

   442

	uint16 next;

   443

} HashLink;

   444

   445

typedef struct {

   446

	TPFEnumProc *enum_proc;

   447

	void *userdata;

   448

   449

	byte tracktype;

   450

	uint maxlength;

   451

   452

	HashLink *new_link;

   453

	uint num_links_left;

   454

   455

	uint nstack;

   456

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

   457

   458

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

   459

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

   460

   461

	HashLink links[0x400]; // hash links

   462

   463

} NewTrackPathFinder;

   464

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

   465

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

   466

   467

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

   468

   469

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

   470

// move it down to the proper position

   471

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   472

{

   473

	StackedItem si;

   474

	int i = ++tpf->nstack;

   475

   476

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

   477

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

   478

		// swap the child item and the parent item.

   479

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

   480

		i>>=1;

   481

	}

   482

}

   483

   484

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

   485

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   486

{

   487

	StackedItem si;

   488

	int i = 1, j;

   489

	int n;

   490

   491

	assert(tpf->nstack > 0);

   492

	n = --tpf->nstack;

   493

   494

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

   495

   496

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

   497

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

   498

   499

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

   500

		// figure out which is smaller of the children.

   501

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

   502

			j++; // right item is smaller

   503

   504

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

   505

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

   506

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

   507

   508

		// swap parent with the child

   509

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

   510

		i = j;

   511

	}

   512

}

   513

   514

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