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;

   131

	int owner = -1;

   132

   133

	if (tpf->tracktype == TRANSPORT_RAIL) {

   134

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

   135

			owner = _map_owner[tile];

   136

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

   137

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

   138

				owner = -1;

   139

		}

   140

	}

   141

   142

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

   143

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

   144

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

   145

	tile = TILE_MASK(tile + TileOffsByDir(direction));

   146

   147

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

   148

	if (tpf->tracktype == TRANSPORT_RAIL) {

   149

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

   150

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

   151

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

   152

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

   153

					return;

   154

	}

   155

   156

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

   157

		return;

   158

   159

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

   160

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

   161

	if (bits == 0)

   162

		return;

   163

   164

	assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY());

   165

   166

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

   167

		/* only one direction */

   168

		i = 0;

   169

		while (!(bits&1))

   170

			i++, bits>>=1;

   171

   172

		rd = tpf->rd;

   173

		goto continue_here;

   174

	}

   175

	/* several directions */

   176

	i=0;

   177

	do {

   178

		if (!(bits & 1)) continue;

   179

		rd = tpf->rd;

   180

   181

		// Change direction 4 times only

   182

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

   183

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

   184

				tpf->rd = rd;

   185

				return;

   186

			}

   187

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

   188

		}

   189

   190

continue_here:;

   191

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

   192

   193

#ifdef DEBUG_TILE_PUSH

   194

		dbg_push_tile(tile, tpf->the_dir);

   195

#endif

   196

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

   197

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

   198

		}

   199

#ifdef DEBUG_TILE_PUSH

   200

		dbg_pop_tile();

   201

#endif

   202

   203

		tpf->rd = rd;

   204

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

   205

   206

}

   207

   208

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

   209

   210

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

   211

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

   212

 */

   213

FindLengthOfTunnelResult FindLengthOfTunnel(uint tile, int direction)

   214

{

   215

	FindLengthOfTunnelResult flotr;

   216

	int x,y;

   217

	byte z;

   218

   219

	flotr.length = 0;

   220

   221

	x = TileX(tile) * 16;

   222

	y = TileY(tile) * 16;

   223

   224

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

   225

   226

	for(;;) {

   227

		flotr.length++;

   228

   229

		x += _get_tunlen_inc[direction];

   230

		y += _get_tunlen_inc[direction+1];

   231

   232

		tile = TILE_FROM_XY(x,y);

   233

   234

		if (IsTileType(tile, MP_TUNNELBRIDGE) &&

   235

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

   236

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

   237

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

   238

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

   239

					break;

   240

	}

   241

   242

	flotr.tile = tile;

   243

	return flotr;

   244

}

   245

   246

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

   247

   248

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

   249

	FindLengthOfTunnelResult flotr;

   250

	TPFSetTileBit(tpf, tile, 14);

   251

	flotr = FindLengthOfTunnel(tile, direction);

   252

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

   253

	TPFSetTileBit(tpf, flotr.tile, 14);

   254

	return flotr.tile;

   255

}

   256

   257

const byte _ffb_64[128] = {

   258

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

   259

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

   260

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

   261

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

   262

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

   263

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

   264

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

   265

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

   266

   267

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

   268

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

   269

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

   270

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

   271

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

   272

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

   273

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

   274

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

   275

};

   276

   277

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

   278

{

   279

	uint bits;

   280

	int i;

   281

	RememberData rd;

   282

	uint tile_org = tile;

   283

   284

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

   285

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

   286

			return;

   287

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   288

	}

   289

	tile += TileOffsByDir(direction);

   290

   291

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

   292

	if (tpf->tracktype == TRANSPORT_RAIL) {

   293

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

   294

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

   295

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

   296

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

   297

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

   298

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

   299

							return;

   300

	}

   301

   302

	tpf->rd.cur_length++;

   303

   304

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

   305

   306

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

   307

		bits &= _tpfmode1_and[direction];

   308

		bits = bits | (bits>>8);

   309

	}

   310

	bits &= 0xBF;

   311

   312

	if (bits != 0) {

   313

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

   314

			do {

   315

				i = FIND_FIRST_BIT(bits);

   316

				bits = KILL_FIRST_BIT(bits);

   317

   318

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

   319

				rd = tpf->rd;

   320

   321

#ifdef DEBUG_TILE_PUSH

   322

		dbg_push_tile(tile, tpf->the_dir);

   323

#endif

   324

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

   325

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

   326

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

   327

				}

   328

#ifdef DEBUG_TILE_PUSH

   329

		dbg_pop_tile();

   330

#endif

   331

				tpf->rd = rd;

   332

			} while (bits != 0);

   333

		}

   334

	}

   335

   336

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

   337

	 * seems to go in 2 directions simultaneously */

   338

   339

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

   340

	 * stack space dramatically. */

   341

	if (tpf->hasbit_13)

   342

		return;

   343

   344

	tile = tile_org;

   345

	direction ^= 2;

   346

   347

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

   348

	bits |= (bits >> 8);

   349

   350

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

   351

		bits &= _bits_mask[direction];

   352

	}

   353

   354

	bits &= 0xBF;

   355

	if (bits == 0)

   356

		return;

   357

   358

	do {

   359

		i = FIND_FIRST_BIT(bits);

   360

		bits = KILL_FIRST_BIT(bits);

   361

   362

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

   363

		rd = tpf->rd;

   364

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

   365

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

   366

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

   367

		}

   368

		tpf->rd = rd;

   369

	} while (bits != 0);

   370

}

   371

   372

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

   373

{

   374

	TrackPathFinder tpf;

   375

   376

	assert(direction < 4);

   377

   378

	/* initialize path finder variables */

   379

	tpf.userdata = data;

   380

	tpf.enum_proc = enum_proc;

   381

	tpf.new_link = tpf.links;

   382

	tpf.num_links_left = lengthof(tpf.links);

   383

   384

	tpf.rd.cur_length = 0;

   385

	tpf.rd.depth = 0;

   386

	tpf.rd.pft_var6 = 0;

   387

   388

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

   389

   390

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

   391

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

   392

   393

   394

	tpf.tracktype = (byte)flags;

   395

   396

	if (HASBIT(flags, 11)) {

   397

		tpf.rd.pft_var6 = 0xFF;

   398

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

   399

		TPFMode2(&tpf, tile, direction);

   400

	} else {

   401

		/* clear the hash_heads */

   402

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

   403

		TPFMode1(&tpf, tile, direction);

   404

	}

   405

   406

	if (after_proc != NULL)

   407

		after_proc(&tpf);

   408

}

   409

   410

typedef struct {

   411

	TileIndex tile;

   412

	uint16 cur_length;

   413

	byte track;

   414

	byte depth;

   415

	byte state;

   416

	byte first_track;

   417

} StackedItem;

   418

   419

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

   420

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

   421

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

   422

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

   423

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

   424

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

   425

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

   426

};

   427

   428

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

   429

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

   430

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

   431

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

   432

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

   433

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

   434

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

   435

};

   436

   437

typedef struct HashLink {

   438

	TileIndex tile;

   439

	uint16 typelength;

   440

	uint16 next;

   441

} HashLink;

   442

   443

typedef struct {

   444

	TPFEnumProc *enum_proc;

   445

	void *userdata;

   446

   447

	byte tracktype;

   448

	uint maxlength;

   449

   450

	HashLink *new_link;

   451

	uint num_links_left;

   452

   453

	uint nstack;

   454

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

   455

   456

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

   457

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

   458

   459

	HashLink links[0x400]; // hash links

   460

   461

} NewTrackPathFinder;

   462

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

   463

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

   464

   465

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

   466

   467

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

   468

// move it down to the proper position

   469

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   470

{

   471

	StackedItem si;

   472

	int i = ++tpf->nstack;

   473

   474

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

   475

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

   476

		// swap the child item and the parent item.

   477

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

   478

		i>>=1;

   479

	}

   480

}

   481

   482

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

   483

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   484

{

   485

	StackedItem si;

   486

	int i = 1, j;

   487

	int n;

   488

   489

	assert(tpf->nstack > 0);

   490

	n = --tpf->nstack;

   491

   492

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

   493

   494

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

   495

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

   496

   497

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

   498

		// figure out which is smaller of the children.

   499

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

   500

			j++; // right item is smaller

   501

   502

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

   503

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

   504

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

   505

   506

		// swap parent with the child

   507

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

   508

		i = j;

   509

	}

   510

}

   511

   512

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

   513

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

   514

// otherwise return true.

   515

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

   516