1

#include "stdafx.h"

     2

#include "ttd.h"

     3

#include "map.h"

     4

#include "pathfind.h"

     5

     6

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

     7

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

     8

{

     9

	uint hash, val, offs;

    10

	TrackPathFinderLink *link, *new_link;

    11

	uint bits = 1 << dir;

    12

    13

	if (tpf->disable_tile_hash)

    14

		return true;

    15

    16

	hash = PATHFIND_HASH_TILE(tile);

    17

    18

	val = tpf->hash_head[hash];

    19

    20

	if (val == 0) {

    21

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

    22

		 * to indicate that a bit was set. */

    23

		tpf->hash_head[hash] = bits;

    24

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

    25

		return true;

    26

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

    27

		/* single tile */

    28

    29

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

    30

			/* found another bit for the same tile,

    31

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

    32

			if (val & bits)

    33

				return false;

    34

    35

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

    36

			 * was set */

    37

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

    38

			return true;

    39

		} else {

    40

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

    41

    42

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

    43

			 * that a tile was already visisted. */

    44

			if (tpf->num_links_left == 0)

    45

				return false;

    46

			tpf->num_links_left--;

    47

			link = tpf->new_link++;

    48

    49

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

    50

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

    51

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

    52

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

    53

    54

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

    55

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

    56

    57

			link->next = 0xFFFF;

    58

		}

    59

	} else {

    60

		/* a linked list of many tiles,

    61

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

    62

		 * otherwise make a new link */

    63

    64

		offs = tpf->hash_tile[hash];

    65

		do {

    66

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    67

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

    68

				/* found the tile in the link list,

    69

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

    70

				 * bit was already set */

    71

				if (link->flags & bits)

    72

					return false;

    73

				link->flags |= bits;

    74

				return true;

    75

			}

    76

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

    77

	}

    78

    79

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

    80

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

    81

	if (tpf->num_links_left == 0)

    82

			return false;

    83

	tpf->num_links_left--;

    84

	new_link = tpf->new_link++;

    85

    86

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

    87

	 * link to the new one */

    88

	new_link->tile = (TileIndex)tile;

    89

	new_link->flags = bits;

    90

	new_link->next = 0xFFFF;

    91

    92

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

    93

	return true;

    94

}

    95

    96

static const byte _bits_mask[4] = {

    97

	0x19,

    98

	0x16,

    99

	0x25,

   100

	0x2A,

   101

};

   102

   103

static const byte _tpf_new_direction[14] = {

   104

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

   105

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

   106

};

   107

   108

static const byte _tpf_prev_direction[14] = {

   109

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

   110

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

   111

};

   112

   113

   114

static const byte _otherdir_mask[4] = {

   115

	0x10,

   116

	0,

   117

	0x5,

   118

	0x2A,

   119

};

   120

   121

#ifdef DEBUG_TILE_PUSH

   122

extern void dbg_push_tile(uint tile, int track);

   123

extern void dbg_pop_tile();

   124

#endif

   125

   126

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

   127

{

   128

	uint bits;

   129

	int i;

   130

	RememberData rd;

   132

   133

	if (tpf->tracktype == TRANSPORT_RAIL) {

   134

		owner = _map_owner[tile];

   135

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

   136

		if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xC0) == 0xC0)

   137

			owner = -1;

   138

	}

   139

   140

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

   141

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

   142

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

   143

	tile = TILE_MASK(tile + _tileoffs_by_dir[direction]);

   144

   145

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

   146

	if (tpf->tracktype == TRANSPORT_RAIL) {

   147

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

   148

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

   149

			if (owner != -1 && _map_owner[tile] != owner)

   150

				return;

   151

	}

   152

   153

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

   154

		return;

   155

   156

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

   157

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

   158

	if (bits == 0)

   159

		return;

   160

   161

	assert(GET_TILE_X(tile) != 255 && GET_TILE_Y(tile) != 255);

   162

   163

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

   164

		/* only one direction */

   165

		i = 0;

   166

		while (!(bits&1))

   167

			i++, bits>>=1;

   168

   169

		rd = tpf->rd;

   170

		goto continue_here;

   171

	}

   172

	/* several directions */

   173

	i=0;

   174

	do {

   175

		if (!(bits & 1)) continue;

   176

		rd = tpf->rd;

   177

   178

		// Change direction 4 times only

   179

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

   180

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

   181

				tpf->rd = rd;

   182

				return;

   183

			}

   184

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

   185

		}

   186

   187

continue_here:;

   188

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

   189

   190

#ifdef DEBUG_TILE_PUSH

   191

		dbg_push_tile(tile, tpf->the_dir);

   192

#endif

   193

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

   194

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

   195

		}

   196

#ifdef DEBUG_TILE_PUSH

   197

		dbg_pop_tile();

   198

#endif

   199

   200

		tpf->rd = rd;

   201

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

   202

   203

}

   204

   205

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

   206

   207

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

   208

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

   209

 */

   210

FindLengthOfTunnelResult FindLengthOfTunnel(uint tile, int direction)

   211

{

   212

	FindLengthOfTunnelResult flotr;

   213

	int x,y;

   214

	byte z;

   215

   216

	flotr.length = 0;

   217

   218

	x = GET_TILE_X(tile) * 16;

   219

	y = GET_TILE_Y(tile) * 16;

   220

   221

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

   222

   223

	for(;;) {

   224

		flotr.length++;

   225

   226

		x += _get_tunlen_inc[direction];

   227

		y += _get_tunlen_inc[direction+1];

   228

   229

		tile = TILE_FROM_XY(x,y);

   230

   231

		if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) &&

   232

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

   233

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

   234

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

   235

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

   236

					break;

   237

	}

   238

   239

	flotr.tile = tile;

   240

	return flotr;

   241

}

   242

   243

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

   244

   245

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

   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, uint tile, int direction)

   275

{

   276

	uint bits;

   277

	int i;

   278

	RememberData rd;

   279

	uint tile_org = tile;

   280

   281

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

   282

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

   283

			return;

   284

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   285

	}

   286

	tile += _tileoffs_by_dir[direction];

   287

   288

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

   289

	if (tpf->tracktype == TRANSPORT_RAIL) {

   290

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

   291

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

   292

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

   293

				if (_map_owner[tile_org] != _map_owner[tile])

   294

					return;

   295

	}

   296

   297

	tpf->rd.cur_length++;

   298

   299

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

   300

   301

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

   302

		bits &= _tpfmode1_and[direction];

   303

		bits = bits | (bits>>8);

   304

	}

   305

	bits &= 0xBF;

   306

   307

	if (bits != 0) {

   308

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

   309

			do {

   310

				i = FIND_FIRST_BIT(bits);

   311

				bits = KILL_FIRST_BIT(bits);

   312

   313

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

   314

				rd = tpf->rd;

   315

   316

#ifdef DEBUG_TILE_PUSH

   317

		dbg_push_tile(tile, tpf->the_dir);

   318

#endif

   319

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

   320

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

   321

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

   322

				}

   323

#ifdef DEBUG_TILE_PUSH

   324

		dbg_pop_tile();

   325

#endif

   326

				tpf->rd = rd;

   327

			} while (bits != 0);

   328

		}

   329

	}

   330

   331

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

   332

	 * seems to go in 2 directions simultaneously */

   333

   334

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

   335

	 * stack space dramatically. */

   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(uint 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;

   408

	byte track;

   409

	byte depth;

   410

	byte state;

   411

	byte first_track;

   412

} StackedItem;

   413

   414

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

   415

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

   416

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

   417

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

   418

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

   419

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

   420

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

   421

};

   422

   423

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

   424

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

   425

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

   426

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

   427

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

   428

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

   429

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

   430

};

   431

   432

typedef struct HashLink {

   433

	TileIndex tile;

   434

	uint16 typelength;

   435

	uint16 next;

   436

} HashLink;

   437

   438

typedef struct {

   439

	TPFEnumProc *enum_proc;

   440

	void *userdata;

   441

   442

	byte tracktype;

   443

	uint maxlength;

   444

   445

	HashLink *new_link;

   446

	uint num_links_left;

   447

   448

	int nstack;

   449

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

   450

   451

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

   452

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

   453

   454

	HashLink links[0x400]; // hash links

   455

   456

} NewTrackPathFinder;

   457

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

   458

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

   459

   460

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

   461

   462

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

   463

// move it down to the proper position

   464

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   465

{

   466

	StackedItem si;

   467

	int i = ++tpf->nstack;

   468

   469

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

   470

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

   471

		// swap the child item and the parent item.

   472

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

   473

		i>>=1;

   474

	}

   475

}

   476

   477

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

   478

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   479

{

   480

	StackedItem si;

   481

	int i = 1, j;

   482

	int n = --tpf->nstack;

   483

   484

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

   485

   486

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

   487

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

   488

   489

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

   490

		// figure out which is smaller of the children.

   491

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

   492

			j++; // right item is smaller

   493

   494

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

   495

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

   496

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

   497

   498

		// swap parent with the child

   499

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

   500

		i = j;

   501

	}

   502

}

   503

   504

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

   505

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

   506

// otherwise return true.

   507

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

   508

{

   509

	uint hash,head;

   510

	HashLink *link, *new_link;

   511

   512

	assert(length < 1024);

   513

   514

	hash = PATHFIND_HASH_TILE(tile);

   515

   516

	// never visited before?

   517

	if ((head=tpf->hash_head[hash]) == 0) {

   518

		tpf->hash_tile[hash] = tile;