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 */

    40

    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];

    54

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

    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 */

    62

    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

	}

    77

    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

   133

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

   134

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

   135

   136

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

   137

		return;

   138

   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) {

   164

				tpf->rd = rd;

   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;

   172

   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 &&					// tunnel entrance/exit

   216

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

   217

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

   218

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

   219

					break;

   220

	}

   221

   222

	flotr.tile = tile;

   223

	return flotr;

   224

}

   225

   226

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

   227

   228

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

   229

	FindLengthOfTunnelResult flotr;

   230

	TPFSetTileBit(tpf, tile, 14);

   231

	flotr = FindLengthOfTunnel(tile, direction);

   232

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

   233

	TPFSetTileBit(tpf, flotr.tile, 14);

   234

	return flotr.tile;

   235

}

   236

   237

const byte _ffb_64[128] = {

   238

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

   239

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

   240

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

   241

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

   242

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

   243

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

   244

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

   245

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

   246

   247

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

   248

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

   249

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

   250

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

   251

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

   252

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

   253

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

   254

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

   255

};

   256

   257

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

   258

{

   259

	uint bits;

   260

	int i;

   261

	RememberData rd;

   262

	uint tile_org = tile;

   263

   264

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

   265

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

   266

			return;

   267

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   268

	}

   269

	tile += _tileoffs_by_dir[direction];

   270

	tpf->rd.cur_length++;

   271

   272

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

   273

   274

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

   275

		bits &= _tpfmode1_and[direction];

   276

		bits = bits | (bits>>8);

   277

	}

   278

	bits &= 0xBF;

   279

   280

	if (bits != 0) {

   281

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

   282

			do {

   283

				i = FIND_FIRST_BIT(bits);

   284

				bits = KILL_FIRST_BIT(bits);

   285

   286

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

   287

				rd = tpf->rd;

   288

   289

#ifdef DEBUG_TILE_PUSH

   290

		dbg_push_tile(tile, tpf->the_dir);

   291

#endif

   292

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

   293

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

   294

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

   295

				}

   296

#ifdef DEBUG_TILE_PUSH

   297

		dbg_pop_tile();

   298

#endif

   299

				tpf->rd = rd;

   300

			} while (bits != 0);

   301

		}

   302

	}

   303

   304

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

   305

	 * seems to go in 2 directions simultaneously */

   306

   307

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

   308

	 * stack space dramatically. */

   309

	if (tpf->hasbit_13)

   310

		return;

   311

   312

	tile = tile_org;

   313

	direction ^= 2;

   314

   315

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

   316

	bits |= (bits >> 8);

   317

   318

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

   319

		bits &= _bits_mask[direction];

   320

	}

   321

   322

	bits &= 0xBF;

   323

	if (bits == 0)

   324

		return;

   325

   326

	do {

   327

		i = FIND_FIRST_BIT(bits);

   328

		bits = KILL_FIRST_BIT(bits);

   329

   330

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

   331

		rd = tpf->rd;

   332

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

   333

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

   334

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

   335

		}

   336

		tpf->rd = rd;

   337

	} while (bits != 0);

   338

}

   339

   340

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

   341

{

   343

   344

	assert(direction < 4);

   345

   346

	/* initialize path finder variables */

   351

   355

   357

   360

   361

   363

   364

	if (HASBIT(flags, 11)) {

   368

	} else {

   369

		/* clear the hash_heads */

   372

	}

   373

   374

	if (after_proc != NULL)

   376

}

   377

   378

typedef struct {

   379

	TileIndex tile;

   380

	uint16 cur_length;

   381

	byte track;

   382

	byte depth;

   383

	byte state;

   384

	byte first_track;

   385

} StackedItem;

   386

   387

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

   388

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

   389

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

   390

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

   391

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

   392

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

   393

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

   394

};

   395

   396

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

   397

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

   398

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

   399

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

   400

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

   401

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

   402

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

   403

};

   404

   405

typedef struct HashLink {

   406

	TileIndex tile;

   407

	uint16 typelength;

   408

	uint16 next;

   409

} HashLink;

   410

   411

typedef struct {

   412

	TPFEnumProc *enum_proc;

   413

	void *userdata;

   414

   415

	byte tracktype;

   416

	uint maxlength;

   417

   418

	HashLink *new_link;

   419

	uint num_links_left;

   420

   421

	int nstack;

   422

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

   423

   424

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

   425

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

   426

   427

	HashLink links[0x400]; // hash links

   428

   429

} NewTrackPathFinder;

   430

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

   431

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

   432

   433

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

   434

   435

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

   436

// move it down to the proper position

   437

static void INLINE HeapifyUp(NewTrackPathFinder *tpf)

   438

{

   439

	StackedItem si;

   440

	int i = ++tpf->nstack;

   441

   442

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

   443

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

   444

		// swap the child item and the parent item.

   445

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

   446

		i>>=1;

   447

	}

   448

}

   449

   450

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

   451

static void INLINE HeapifyDown(NewTrackPathFinder *tpf)

   452

{

   453

	StackedItem si;

   454

	int i = 1, j;

   455

	int n = --tpf->nstack;

   456

   457

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

   458

   459

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

   460

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

   461

   462

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

   463

		// figure out which is smaller of the children.

   464

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

   465

			j++; // right item is smaller

   466

   467

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

   468

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

   469

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

   470

   471

		// swap parent with the child

   472

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

   473

		i = j;

   474

	}

   475

}

   476

   477

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

   478

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

   479

// otherwise return true.

   480

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

   481

{

   482

	uint hash,head;

   483

	HashLink *link, *new_link;

   484

   485

	assert(length < 1024);

   486

   487

	hash = PATHFIND_HASH_TILE(tile);

   488

   489

	// never visited before?

   490

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

   491

		tpf->hash_tile[hash] = tile;

   492

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

   493

		return true;

   494

	}

   495

   496

	if (head != 0xffff) {

   497

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

   498

   499

			// longer length

   500

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

   501

   502

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

   503

			return true;

   504

		}

   505

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

   506

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

   507

		// that a tile was already visisted.

   508

		if (tpf->num_links_left == 0)

   509

			return false;

   510

		tpf->num_links_left--;

   511

		link = tpf->new_link++;

   512

   513

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

   514

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

   515

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

   516

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

   517

   518

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

   519

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

   520

		link->next = 0xFFFF;

   521

	} else {