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;

   134

   135

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

   136

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

   137

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

   138

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

   139

   144

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

   145

		return;

   146

   147

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

   148

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

   149

	if (bits == 0)

   150

		return;

   151

   152

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

   153

   154

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

   155

		/* only one direction */

   156

		i = 0;

   157

		while (!(bits&1))

   158

			i++, bits>>=1;

   159

   160

		rd = tpf->rd;

   161

		goto continue_here;

   162

	}

   163

	/* several directions */

   164

	i=0;

   165

	do {

   166

		if (!(bits & 1)) continue;

   167

		rd = tpf->rd;

   168

   169

		// Change direction 4 times only

   170

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

   171

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

   172

				tpf->rd = rd;

   173

				return;

   174

			}

   175

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

   176

		}

   177

   178

continue_here:;

   179

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

   180

   181

#ifdef DEBUG_TILE_PUSH

   182

		dbg_push_tile(tile, tpf->the_dir);

   183

#endif

   184

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

   185

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

   186

		}

   187

#ifdef DEBUG_TILE_PUSH

   188

		dbg_pop_tile();

   189

#endif

   190

   191

		tpf->rd = rd;

   192

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

   193

   194

}

   195

   196

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

   197

   198

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

   199

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

   200

 */

   201

FindLengthOfTunnelResult FindLengthOfTunnel(uint tile, int direction)

   202

{

   203

	FindLengthOfTunnelResult flotr;

   204

	int x,y;

   205

	byte z;

   206

   207

	flotr.length = 0;

   208

   209

	x = GET_TILE_X(tile) * 16;

   210

	y = GET_TILE_Y(tile) * 16;

   211

   212

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

   213

   214

	for(;;) {

   215

		flotr.length++;

   216

   217

		x += _get_tunlen_inc[direction];

   218

		y += _get_tunlen_inc[direction+1];

   219

   220

		tile = TILE_FROM_XY(x,y);

   221

   222

		if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) &&

   223

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

   224

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

   225

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

   226

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

   227

					break;

   228

	}

   229

   230

	flotr.tile = tile;

   231

	return flotr;

   232

}

   233

   234

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

   235

   236

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

   237

	FindLengthOfTunnelResult flotr;

   238

	TPFSetTileBit(tpf, tile, 14);

   239

	flotr = FindLengthOfTunnel(tile, direction);

   240

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

   241

	TPFSetTileBit(tpf, flotr.tile, 14);

   242

	return flotr.tile;

   243

}

   244

   245

const byte _ffb_64[128] = {

   246

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

   247

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

   248

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

   249

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

   250

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

   251

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

   252

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

   253

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

   254

   255

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

   256

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

   257

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

   258

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

   259

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

   260

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

   261

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

   262

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

   263

};

   264

   265

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

   266

{

   267

	uint bits;

   268

	int i;

   269

	RememberData rd;

   270

	uint tile_org = tile;

   271

   272

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

   273

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

   274

			return;

   275

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   276

	}

   277

	tile += _tileoffs_by_dir[direction];

   283

	tpf->rd.cur_length++;

   284

   285

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

   286

   287

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

   288

		bits &= _tpfmode1_and[direction];

   289

		bits = bits | (bits>>8);

   290

	}

   291

	bits &= 0xBF;

   292

   293

	if (bits != 0) {

   294

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

   295

			do {

   296

				i = FIND_FIRST_BIT(bits);

   297

				bits = KILL_FIRST_BIT(bits);

   298

   299

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

   300

				rd = tpf->rd;

   301

   302

#ifdef DEBUG_TILE_PUSH

   303

		dbg_push_tile(tile, tpf->the_dir);

   304

#endif

   305

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

   306

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

   307

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

   308

				}

   309

#ifdef DEBUG_TILE_PUSH

   310

		dbg_pop_tile();

   311

#endif

   312

				tpf->rd = rd;

   313

			} while (bits != 0);

   314

		}

   315

	}

   316

   317

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

   318

	 * seems to go in 2 directions simultaneously */

   319

   320

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

   321

	 * stack space dramatically. */

   322

	if (tpf->hasbit_13)

   323

		return;

   324

   325

	tile = tile_org;

   326

	direction ^= 2;

   327

   328

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

   329

	bits |= (bits >> 8);

   330

   331

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

   332

		bits &= _bits_mask[direction];

   333

	}

   334

   335

	bits &= 0xBF;

   336

	if (bits == 0)

   337

		return;

   338

   339

	do {

   340

		i = FIND_FIRST_BIT(bits);

   341

		bits = KILL_FIRST_BIT(bits);

   342

   343

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

   344

		rd = tpf->rd;

   345

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

   346

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

   347

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

   348

		}

   349

		tpf->rd = rd;

   350

	} while (bits != 0);

   351

}

   352

   353

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

   354

{

   355

	TrackPathFinder tpf;

   356

   357

	assert(direction < 4);

   358

   359

	/* initialize path finder variables */

   360

	tpf.userdata = data;

   361

	tpf.enum_proc = enum_proc;

   362

	tpf.new_link = tpf.links;

   363

	tpf.num_links_left = lengthof(tpf.links);

   364

   365

	tpf.rd.cur_length = 0;

   366

	tpf.rd.depth = 0;

   367

	tpf.rd.pft_var6 = 0;

   368

   369

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

   370

   371

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

   372

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

   373

   374

   375

	tpf.tracktype = (byte)flags;

   376

   377

	if (HASBIT(flags, 11)) {

   378

		tpf.rd.pft_var6 = 0xFF;

   379

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

   380

		TPFMode2(&tpf, tile, direction);

   381

	} else {

   382

		/* clear the hash_heads */

   383

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

   384

		TPFMode1(&tpf, tile, direction);

   385

	}

   386

   387

	if (after_proc != NULL)

   388

		after_proc(&tpf);

   389

}

   390

   391

typedef struct {

   392

	TileIndex tile;

   393

	uint16 cur_length;

   394

	byte track;

   395

	byte depth;

   396

	byte state;

   397

	byte first_track;

   398

} StackedItem;

   399

   400

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

   401

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

   402

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

   403

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

   404

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

   405

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

   406

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

   407

};

   408

   409

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

   410

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

   411

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

   412

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

   413

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

   414

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

   415

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

   416

};

   417

   418

typedef struct HashLink {

   419

	TileIndex tile;

   420

	uint16 typelength;

   421

	uint16 next;

   422

} HashLink;

   423

   424

typedef struct {

   425

	TPFEnumProc *enum_proc;

   426

	void *userdata;

   427

   428

	byte tracktype;

   429

	uint maxlength;

   430

   431

	HashLink *new_link;

   432

	uint num_links_left;

   433

   434

	int nstack;

   435

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

   436

   437

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

   438

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

   439

   440

	HashLink links[0x400]; // hash links

   441

   442

} NewTrackPathFinder;

   443

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

   444

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

   445

   446

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

   447

   448

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

   449

// move it down to the proper position

   450

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   451

{

   452

	StackedItem si;

   453

	int i = ++tpf->nstack;

   454

   455

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

   456

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

   457

		// swap the child item and the parent item.

   458

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

   459

		i>>=1;

   460

	}

   461

}

   462

   463

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

   464

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   465

{

   466

	StackedItem si;

   467

	int i = 1, j;

   468

	int n = --tpf->nstack;

   469

   470

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

   471

   472

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

   473

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

   474

   475

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

   476

		// figure out which is smaller of the children.

   477

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

   478

			j++; // right item is smaller

   479

   480

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

   481

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

   482

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

   483

   484

		// swap parent with the child

   485

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

   486

		i = j;

   487

	}

   488

}

   489

   490

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

   491

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

   492

// otherwise return true.

   493

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

   494

{

   495

	uint hash,head;

   496

	HashLink *link, *new_link;

   497

   498

	assert(length < 1024);

   499

   500

	hash = PATHFIND_HASH_TILE(tile);

   501

   502

	// never visited before?

   503

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

   504

		tpf->hash_tile[hash] = tile;

   505

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

   506

		return true;

   507

	}

   508

   509

	if (head != 0xffff) {

   510

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

   511

   512

			// longer length

   513

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

   514

   515

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

   516

			return true;

   517

		}

   518

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

   519

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