1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "functions.h"

     6

#include "map.h"

     7

#include "tile.h"

     8

#include "pathfind.h"

     9

#include "rail.h"

    10

#include "debug.h"

    11

#include "variables.h"

    12

    13

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

    14

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

    15

{

    16

	uint hash, val, offs;

    17

	TrackPathFinderLink *link, *new_link;

    18

	uint bits = 1 << dir;

    19

    20

	if (tpf->disable_tile_hash)

    21

		return true;

    22

    23

	hash = PATHFIND_HASH_TILE(tile);

    24

    25

	val = tpf->hash_head[hash];

    26

    27

	if (val == 0) {

    28

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

    29

		 * to indicate that a bit was set. */

    30

		tpf->hash_head[hash] = bits;

    31

		tpf->hash_tile[hash] = tile;

    32

		return true;

    33

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

    34

		/* single tile */

    35

    36

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

    37

			/* found another bit for the same tile,

    38

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

    39

			if (val & bits)

    40

				return false;

    41

    42

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

    43

			 * was set */

    44

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

    45

			return true;

    46

		} else {

    47

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

    48

    49

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

    50

			 * that a tile was already visisted. */

    51

			if (tpf->num_links_left == 0) {

    52

				return false;

    53

			}

    54

			tpf->num_links_left--;

    55

			link = tpf->new_link++;

    56

    57

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

    58

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

    59

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

    60

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

    61

    62

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

    63

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

    64

    65

			link->next = 0xFFFF;

    66

		}

    67

	} else {

    68

		/* a linked list of many tiles,

    69

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

    70

		 * otherwise make a new link */

    71

    72

		offs = tpf->hash_tile[hash];

    73

		do {

    74

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    75

			if (tile == link->tile) {

    76

				/* found the tile in the link list,

    77

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

    78

				 * bit was already set */

    79

				if (link->flags & bits)

    80

					return false;

    81

				link->flags |= bits;

    82

				return true;

    83

			}

    84

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

    85

	}

    86

    87

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

    88

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

    89

	if (tpf->num_links_left == 0) {

    90

			return false;

    91

	}

    92

	tpf->num_links_left--;

    93

	new_link = tpf->new_link++;

    94

    95

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

    96

	 * link to the new one */

    97

	new_link->tile = tile;

    98

	new_link->flags = bits;

    99

	new_link->next = 0xFFFF;

   100

   101

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

   102

	return true;

   103

}

   104

   105

static const byte _bits_mask[4] = {

   106

	0x19,

   107

	0x16,

   108

	0x25,

   109

	0x2A,

   110

};

   111

   112

static const byte _tpf_new_direction[14] = {

   113

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

   114

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

   115

};

   116

   117

static const byte _tpf_prev_direction[14] = {

   118

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

   119

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

   120

};

   121

   122

   123

static const byte _otherdir_mask[4] = {

   124

	0x10,

   125

	0,

   126

	0x5,

   127

	0x2A,

   128

};

   129

   130

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

   131

{

   132

	uint bits;

   133

	int i;

   134

	RememberData rd;

   135

	int owner = -1;

   136

   137

	/* XXX: Mode 2 is currently only used for ships, why is this code here? */

   138

	if (tpf->tracktype == TRANSPORT_RAIL) {

   139

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

   140

			owner = GetTileOwner(tile);

   141

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

   142

			if (IsTileType(tile, MP_TUNNELBRIDGE) && (_m[tile].m5 & 0xC0) == 0xC0)

   143

				owner = -1;

   144

		}

   145

	}

   146

   147

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

   148

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

   149

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

   150

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

   151

   152

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

   153

	if (tpf->tracktype == TRANSPORT_RAIL) {

   154

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

   155

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

   156

			if (!IsTileType(tile, MP_TUNNELBRIDGE) || (_m[tile].m5 & 0xC0) != 0xC0)

   157

				if (owner != -1 && !IsTileOwner(tile, owner))

   158

					return;

   159

	}

   160

   161

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

   162

		return;

   163

   164

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

   165

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

   166

	if (bits == 0)

   167

		return;

   168

   169

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

   170

   171

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

   172

		/* only one direction */

   173

		i = 0;

   174

		while (!(bits&1))

   175

			i++, bits>>=1;

   176

   177

		rd = tpf->rd;

   178

		goto continue_here;

   179

	}

   180

	/* several directions */

   181

	i=0;

   182

	do {

   183

		if (!(bits & 1)) continue;

   184

		rd = tpf->rd;

   185

   186

		// Change direction 4 times only

   187

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

   188

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

   189

				tpf->rd = rd;

   190

				return;

   191

			}

   192

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

   193

		}

   194

   195

continue_here:;

   196

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

   197

   198

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

   199

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

   200

		}

   201

   202

		tpf->rd = rd;

   203

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

   204

   205

}

   206

   207

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

   208

   209

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

   210

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

   211

 */

   212

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, int direction)

   213

{

   214

	FindLengthOfTunnelResult flotr;

   215

	int x,y;

   216

	byte z;

   217

   218

	flotr.length = 0;

   219

   220

	x = TileX(tile) * 16;

   221

	y = TileY(tile) * 16;

   222

   223

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

   224

   225

	for(;;) {

   226

		flotr.length++;

   227

   228

		x += _get_tunlen_inc[direction];

   229

		y += _get_tunlen_inc[direction+1];

   230

   231

		tile = TileVirtXY(x, y);

   232

   233

		if (IsTileType(tile, MP_TUNNELBRIDGE) &&

   234

				(_m[tile].m5 & 0xF0) == 0 &&					// tunnel entrance/exit

   235

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

   236

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

   237

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

   238

					break;

   239

	}

   240

   241

	flotr.tile = tile;

   242

	return flotr;

   243

}

   244

   245

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

   246

   247

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

   248

{

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

   278

{

   279

	uint bits;

   280

	int i;

   281

	RememberData rd;

   282

	TileIndex tile_org = tile;

   283

   284

	if (IsTileType(tile, MP_TUNNELBRIDGE) && (_m[tile].m5 & 0xF0) == 0) {

   285

		if ((_m[tile].m5 & 3) != direction || ((_m[tile].m5>>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) || (_m[tile].m5 & 0xC0) != 0xC0)

   297

					if (!IsTileType(tile_org, MP_TUNNELBRIDGE) || (_m[tile_org].m5 & 0xC0) != 0xC0)

   298

						if (GetTileOwner(tile_org) != GetTileOwner(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

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

   322

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

   323

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

   324

				}

   325

				tpf->rd = rd;

   326

			} while (bits != 0);

   327

		}

   328

	}

   329

   330

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

   331

	 * seems to go in 2 directions simultaneously */

   332

   333

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

   334

	 * stack space dramatically. */

   335

   336

	/* If we are doing signal setting, we must reverse at evere tile, so we

   337

	 * iterate all the tracks in a signal block, even when a normal train would

   338

	 * not reach it (for example, when two lines merge */

   339

	if (tpf->hasbit_13)

   340

		return;

   341

   342

	tile = tile_org;

   343

	direction ^= 2;

   344

   345

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

   346

	bits |= (bits >> 8);

   347

   348

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

   349

		bits &= _bits_mask[direction];

   350

	}

   351

   352

	bits &= 0xBF;

   353

	if (bits == 0)

   354

		return;

   355

   356

	do {

   357

		i = FIND_FIRST_BIT(bits);

   358

		bits = KILL_FIRST_BIT(bits);

   359

   360

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

   361

		rd = tpf->rd;

   362

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

   363

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

   364

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

   365

		}

   366

		tpf->rd = rd;

   367

	} while (bits != 0);

   368

}

   369

   370

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

   371

{

   372

	TrackPathFinder tpf;

   373

   374

	assert(direction < 4);

   375

   376

	/* initialize path finder variables */

   377

	tpf.userdata = data;

   378

	tpf.enum_proc = enum_proc;

   379

	tpf.new_link = tpf.links;

   380

	tpf.num_links_left = lengthof(tpf.links);

   381

   382

	tpf.rd.cur_length = 0;

   383

	tpf.rd.depth = 0;

   384

	tpf.rd.pft_var6 = 0;

   385

   386

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

   387

   388

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

   389

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

   390

   391

   392

	tpf.tracktype = (byte)flags;

   393

   394

	if (HASBIT(flags, 11)) {

   395

		tpf.rd.pft_var6 = 0xFF;

   396

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

   397

		TPFMode2(&tpf, tile, direction);

   398

	} else {

   399

		/* clear the hash_heads */

   400

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

   401

		TPFMode1(&tpf, tile, direction);

   402

	}

   403

   404

	if (after_proc != NULL)

   405

		after_proc(&tpf);

   406

}

   407

   408

typedef struct {

   409

	TileIndex tile;

   410

	uint16 cur_length; // This is the current length to this tile.

   411

	uint16 priority; // This is the current length + estimated length to the goal.

   412

	byte track;

   413

	byte depth;

   414

	byte state;

   415

	byte first_track;

   416

} StackedItem;

   417

   418

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

   419

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

   420

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

   421

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

   422

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

   423

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

   424

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

   425

};

   426

   427

typedef struct HashLink {

   428

	TileIndex tile;

   429

	uint16 typelength;

   430

	uint16 next;

   431

} HashLink;

   432

   433

typedef struct {

   434

	NTPEnumProc *enum_proc;

   435

	void *userdata;

   436

	TileIndex dest;

   437

   438

	byte tracktype;

   439

	uint maxlength;

   440

   441

	HashLink *new_link;

   442

	uint num_links_left;

   443

   444

	uint nstack;

   445

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

   446

   447

	uint16 hash_head[0x400]; // hash heads. 0 means unused. 0xFFFC = length, 0x3 = dir

   448

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

   449

   450

	HashLink links[0x400]; // hash links

   451

   452

} NewTrackPathFinder;

   453

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

   454

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

   455

   456

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

   457

   458

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

   459

// move it down to the proper position

   460

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   461

{

   462

	StackedItem si;

   463

	int i = ++tpf->nstack;

   464

   465

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

   466

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

   467

		// swap the child item and the parent item.

   468

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

   469

		i>>=1;

   470

	}

   471

}

   472

   473

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

   474

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   475

{

   476

	StackedItem si;

   477

	int i = 1, j;

   478

	int n;

   479

   480

	assert(tpf->nstack > 0);

   481

	n = --tpf->nstack;

   482

   483

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

   484

   485

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

   486

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

   487

   488

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

   489

		// figure out which is smaller of the children.

   490

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

   491

			j++; // right item is smaller

   492

   493

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

   494

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

   495

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

   496

   497

		// swap parent with the child

   498

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

   499

		i = j;

   500

	}

   501

}

   502

   503

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

   504

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

   505

// otherwise return true.

   506

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

   507

{

   508

	uint hash,head;

   509

	HashLink *link, *new_link;

   510