1

#include "stdafx.h"

     2

#include "ttd.h"

     3

#include "pathfind.h"

     4

     5

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

     6

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

     7

{

     8

	uint hash, val, offs;

     9

	TrackPathFinderLink *link, *new_link;

    10

	uint bits = 1 << dir;

    11

    12

	if (tpf->disable_tile_hash)

    13

		return true;

    14

    15

	hash = PATHFIND_HASH_TILE(tile);

    16

    17

	val = tpf->hash_head[hash];

    18

    19

	if (val == 0) {

    20

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

    21

		 * to indicate that a bit was set. */

    22

		tpf->hash_head[hash] = bits;

    23

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

    24

		return true;

    25

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

    26

		/* single tile */

    27

    28

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

    29

			/* found another bit for the same tile,

    30

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

    31

			if (val & bits)

    32

				return false;

    33

    34

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

    35

			 * was set */

    36

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

    37

			return true;

    38

		} else {

    39

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

    41

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

    42

			 * that a tile was already visisted. */

    43

			if (tpf->num_links_left == 0)

    44

				return false;

    45

			tpf->num_links_left--;

    46

			link = tpf->new_link++;

    47

    48

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

    49

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

    50

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

    51

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

    52

    53

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

    55

    56

			link->next = 0xFFFF;

    57

		}

    58

	} else {

    59

		/* a linked list of many tiles,

    60

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

    61

		 * otherwise make a new link */

    63

		offs = tpf->hash_tile[hash];

    64

		do {

    65

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    66

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

    67

				/* found the tile in the link list,

    68

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

    69

				 * bit was already set */

    70

				if (link->flags & bits)

    71

					return false;

    72

				link->flags |= bits;

    73

				return true;

    74

			}

    75

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

    76

	}

    78

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

    79

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

    80

	if (tpf->num_links_left == 0)

    81

			return false;

    82

	tpf->num_links_left--;

    83

	new_link = tpf->new_link++;

    84

    85

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

    86

	 * link to the new one */

    87

	new_link->tile = (TileIndex)tile;

    88

	new_link->flags = bits;

    89

	new_link->next = 0xFFFF;

    90

    91

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

    92

	return true;

    93

}

    94

    95

static const byte _bits_mask[4] = {

    96

	0x19,

    97

	0x16,

    98

	0x25,

    99

	0x2A,

   100

};

   101

   102

static const byte _tpf_new_direction[14] = {

   103

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

   104

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

   105

};

   106

   107

static const byte _tpf_prev_direction[14] = {

   108

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

   109

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

   110

};

   111

   112

   113

static const byte _otherdir_mask[4] = {

   114

	0x10,

   115

	0,

   116

	0x5,

   117

	0x2A,

   118

};

   119

   120

#ifdef DEBUG_TILE_PUSH

   121

extern void dbg_push_tile(uint tile, int track);

   122

extern void dbg_pop_tile();

   123

#endif

   124

   125

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

   126

{

   127

	uint bits;

   128

	int i;

   129

	RememberData rd;

   130

   131

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

   132

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

   134

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

   135

   136

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

   137

		return;

   139

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

   140

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

   141

	if (bits == 0)

   142

		return;

   143

   144

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

   145

   146

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

   147

		/* only one direction */

   148

		i = 0;

   149

		while (!(bits&1))

   150

			i++, bits>>=1;

   151

   152

		rd = tpf->rd;

   153

		goto continue_here;

   154

	}

   155

	/* several directions */

   156

	i=0;

   157

	do {

   158

		if (!(bits & 1)) continue;

   159

		rd = tpf->rd;

   160

   161

		// Change direction 4 times only

   162

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

   163

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

   165

				return;

   166

			}

   167

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

   168

		}

   169

   170

continue_here:;

   171

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

   173

#ifdef DEBUG_TILE_PUSH

   174

		dbg_push_tile(tile, tpf->the_dir);

   175

#endif

   176

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

   177

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

   178

		}

   179

#ifdef DEBUG_TILE_PUSH

   180

		dbg_pop_tile();

   181

#endif

   182

   183

		tpf->rd = rd;

   184

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

   185

   186

}

   187

   188

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

   189

   190

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

   191

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

   192

 */

   193

FindLengthOfTunnelResult FindLengthOfTunnel(uint tile, int direction)

   194

{

   195

	FindLengthOfTunnelResult flotr;

   196

	int x,y;

   197

	byte z;

   198

   199

	flotr.length = 0;

   200

   201

	x = GET_TILE_X(tile) * 16;

   202

	y = GET_TILE_Y(tile) * 16;

   203

   204

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

   205

   206

	for(;;) {

   207

		flotr.length++;

   208

   209

		x += _get_tunlen_inc[direction];

   210

		y += _get_tunlen_inc[direction+1];

   211

   212

		tile = TILE_FROM_XY(x,y);

   213

   214

		if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) &&

   215

				(_map5[tile] & 0xF0) == 0 &&

   216

				//((_map5[tile]>>2)&3) == type && // This is

   217

				//not necesary to check, right?

   218

				((_map5[tile] & 3)^2) == direction &&

   219

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

   220

					break;

   221

	}

   222

   223

	flotr.tile = tile;

   224

	return flotr;

   225

}

   226

   227

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

   228

   229

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

   230

	FindLengthOfTunnelResult flotr;

   231

	TPFSetTileBit(tpf, tile, 14);

   232

	flotr = FindLengthOfTunnel(tile, direction);

   233

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

   234

	TPFSetTileBit(tpf, flotr.tile, 14);

   235

	return flotr.tile;

   236

}

   237

   238

const byte _ffb_64[128] = {

   239

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

   240

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

   241

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

   242

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

   243

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

   244

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

   245

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

   246

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

   247

   248

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

   249

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

   250

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

   251

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

   252

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

   253

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

   254

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

   255

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

   256

};

   257

   258

void TPFMode1(TrackPathFinder *tpf, uint tile, int direction)

   259

{

   260

	uint bits;

   261

	int i;

   262

	RememberData rd;

   263

	uint tile_org = tile;

   264

   265

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

   266

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

   267

			return;

   269

	}

   270

	tile += _tileoffs_by_dir[direction];

   271

	tpf->rd.cur_length++;

   272

   273

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

   274

   275

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

   276

		bits &= _tpfmode1_and[direction];

   277

		bits = bits | (bits>>8);

   278

	}

   279

	bits &= 0xBF;

   280

   281

	if (bits != 0) {

   282

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

   283

			do {

   284

				i = FIND_FIRST_BIT(bits);

   285

				bits = KILL_FIRST_BIT(bits);

   286

   287

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

   288

				rd = tpf->rd;

   290

#ifdef DEBUG_TILE_PUSH

   291

		dbg_push_tile(tile, tpf->the_dir);

   292

#endif

   293

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

   294

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

   295

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

   296

				}

   297

#ifdef DEBUG_TILE_PUSH

   298

		dbg_pop_tile();

   299

#endif

   300

				tpf->rd = rd;

   301

			} while (bits != 0);

   302

		}

   303

	}

   304

   305

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

   306

	 * seems to go in 2 directions simultaneously */

   308

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

   310

	if (tpf->hasbit_13)

   311

		return;

   313

	tile = tile_org;

   314

	direction ^= 2;

   315

   316

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

   317

	bits |= (bits >> 8);

   318

   319

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

   320

		bits &= _bits_mask[direction];

   321

	}

   322

   323

	bits &= 0xBF;

   324

	if (bits == 0)

   325

		return;

   326

   327

	do {

   328

		i = FIND_FIRST_BIT(bits);

   329

		bits = KILL_FIRST_BIT(bits);

   331

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

   332

		rd = tpf->rd;

   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

		tpf->rd = rd;

   338

	} while (bits != 0);

   339

}

   340

   341

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

   342

{

   343

	TrackPathFinder *tpf = alloca(sizeof(TrackPathFinder));

   344

   345

	assert(direction < 4);

   346

   348

	tpf->userdata = data;

   350

	tpf->new_link = tpf->links;

   351

	tpf->num_links_left = 0x400;

   352

   353

	tpf->rd.cur_length = 0;

   354

	tpf->rd.depth = 0;

   355

	tpf->rd.pft_var6 = 0;

   357

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

   358

   359

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

   360

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

   361

   362

   363

	tpf->tracktype = (byte)flags;

   364

   366

		tpf->rd.pft_var6 = 0xFF;

   367

		tpf->enum_proc(tile, data, 0, 0, 0);

   369

	} else {

   370

		/* clear the hash_heads */

   371

		memset(tpf->hash_head, 0, sizeof(tpf->hash_head));

   372

		TPFMode1(tpf, tile, direction);

   373

	}

   374

   375

	if (after_proc != NULL)

   377

}

   378

   379

typedef struct {

   380

	TileIndex tile;

   381

	uint16 cur_length;

   382

	byte track;

   383

	byte depth;

   384

	byte state;

   385

	byte first_track;

   386

} StackedItem;

   387

   388

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

   389

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

   390

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

   391

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

   392

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

   393

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

   394

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

   395

};

   396

   397

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

   398

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

   399

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

   400

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

   401

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

   402

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

   403

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

   404

};

   405

   406

typedef struct HashLink {

   407

	TileIndex tile;

   408

	uint16 typelength;

   409

	uint16 next;

   410

} HashLink;

   411

   412

typedef struct {

   413

	TPFEnumProc *enum_proc;

   414

	void *userdata;

   415

   416

	byte tracktype;

   417

	uint maxlength;

   418

   419

	HashLink *new_link;

   420

	uint num_links_left;

   421

   422

	int nstack;

   423

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

   424

   425

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

   426

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

   427

   428

	HashLink links[0x400]; // hash links

   429

   430

} NewTrackPathFinder;

   431

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

   432

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

   433

   434

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

   435

   436

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

   437

// move it down to the proper position

   438

static void INLINE HeapifyUp(NewTrackPathFinder *tpf)

   439

{

   440

	StackedItem si;

   441

	int i = ++tpf->nstack;

   443

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

   444

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

   446

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

   447

		i>>=1;

   448

	}

   449

}

   450

   451

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

   452

static void INLINE HeapifyDown(NewTrackPathFinder *tpf)

   453

{

   454

	StackedItem si;

   455

	int i = 1, j;

   456

	int n = --tpf->nstack;

   457

   458

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

   459

   460

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

   461

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

   462

   463

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

   464

		// figure out which is smaller of the children.

   466

			j++; // right item is smaller

   467

   468

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

   469

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

   470

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

   472

		// swap parent with the child

   473

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

   474

		i = j;

   475

	}

   476

}

   477

   478

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

   479

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

   480

// otherwise return true.

   481

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

   482

{

   483

	uint hash,head;

   484

	HashLink *link, *new_link;

   485

   486

	assert(length < 1024);

   488

	hash = PATHFIND_HASH_TILE(tile);

   489

   490

	// never visited before?

   491

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

   492

		tpf->hash_tile[hash] = tile;

   493

		tpf->hash_head[hash] = dir | (length << 2);

   494

		return true;

   495

	}

   496

   497

	if (head != 0xffff) {

   498

		if ( (TileIndex)tile == tpf->hash_tile[hash] && (head & 0x3) == dir ) {

   500

			// longer length

   501

			if (length >= (head >> 2)) return false;

   503

			tpf->hash_head[hash] = dir | (length << 2);

   504

			return true;

   505

		}

   506

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

   507

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

   508

		// that a tile was already visisted.

   509

		if (tpf->num_links_left == 0)

   510

			return false;

   511

		tpf->num_links_left--;

   512

		link = tpf->new_link++;

   513

   514

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

   515

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

   516

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

   517

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

   518

   519

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

   521

		link->next = 0xFFFF;

   522

	} else {

   523

		// a linked list of many tiles,