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, uint 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

				GB(_m[tile].m5, 4, 4) == 0 &&               // tunnel entrance/exit

   235

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

   236

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

   237

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

   238

			break;

   239

		}

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

   249

{

   250

	FindLengthOfTunnelResult flotr;

   251

	TPFSetTileBit(tpf, tile, 14);

   252

	flotr = FindLengthOfTunnel(tile, direction);

   253

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

   254

	TPFSetTileBit(tpf, flotr.tile, 14);

   255

	return flotr.tile;

   256

}

   257

   258

const byte _ffb_64[128] = {

   259

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

   260

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

   261

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

   262

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

   263

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

   264

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

   265

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

   266

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

   267

   268

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

   269

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

   270

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

   271

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

   272

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

   273

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

   274

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

   275

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

   276

};

   277

   278

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

   279

{

   280

	uint bits;

   281

	int i;

   282

	RememberData rd;

   283

	TileIndex tile_org = tile;

   284

   285

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

   286

		if (GB(_m[tile].m5, 0, 2) != direction ||

   287

				GB(_m[tile].m5, 2, 2) != tpf->tracktype) {

   288

			return;

   289

		}

   290

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   291

	}

   292

	tile += TileOffsByDir(direction);

   293

   294

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

   295

	if (tpf->tracktype == TRANSPORT_RAIL) {

   296

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

   297

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

   298

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

   299

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

   300

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

   301

						if (GetTileOwner(tile_org) != GetTileOwner(tile))

   302

							return;

   303

	}

   304

   305

	tpf->rd.cur_length++;

   306

   307

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

   308

   309

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

   310

		bits &= _tpfmode1_and[direction];

   311

		bits = bits | (bits>>8);

   312

	}

   313

	bits &= 0xBF;

   314

   315

	if (bits != 0) {

   316

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

   317

			do {

   318

				i = FIND_FIRST_BIT(bits);

   319

				bits = KILL_FIRST_BIT(bits);

   320

   321

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

   322

				rd = tpf->rd;

   323

   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

				tpf->rd = rd;

   329

			} while (bits != 0);

   330

		}

   331

	}

   332

   333

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

   334

	 * seems to go in 2 directions simultaneously */

   335

   336

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

   337

	 * stack space dramatically. */

   338

   339

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

   340

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

   341

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

   342

	if (tpf->hasbit_13)

   343

		return;

   344

   345

	tile = tile_org;

   346

	direction ^= 2;

   347

   348

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

   349

	bits |= (bits >> 8);

   350

   351

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

   352

		bits &= _bits_mask[direction];

   353

	}

   354

   355

	bits &= 0xBF;

   356

	if (bits == 0)

   357

		return;

   358

   359

	do {

   360

		i = FIND_FIRST_BIT(bits);

   361

		bits = KILL_FIRST_BIT(bits);

   362

   363

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

   364

		rd = tpf->rd;

   365

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

   366

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

   367

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

   368

		}

   369

		tpf->rd = rd;

   370

	} while (bits != 0);

   371

}

   372

   373

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

   374

{

   375

	TrackPathFinder tpf;

   376

   377

	assert(direction < 4);

   378

   379

	/* initialize path finder variables */

   380

	tpf.userdata = data;

   381

	tpf.enum_proc = enum_proc;

   382

	tpf.new_link = tpf.links;

   383

	tpf.num_links_left = lengthof(tpf.links);

   384

   385

	tpf.rd.cur_length = 0;

   386

	tpf.rd.depth = 0;

   387

	tpf.rd.pft_var6 = 0;

   388

   389

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

   390

   391

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

   392

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

   393

   394

   395

	tpf.tracktype = (byte)flags;

   396

   397

	if (HASBIT(flags, 11)) {

   398

		tpf.rd.pft_var6 = 0xFF;

   399

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

   400

		TPFMode2(&tpf, tile, direction);

   401

	} else {

   402

		/* clear the hash_heads */

   403

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

   404

		TPFMode1(&tpf, tile, direction);

   405

	}

   406

   407

	if (after_proc != NULL)

   408

		after_proc(&tpf);

   409

}

   410

   411

typedef struct {

   412

	TileIndex tile;

   413

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

   414

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

   415

	byte track;

   416

	byte depth;

   417

	byte state;

   418

	byte first_track;

   419

} StackedItem;

   420

   421

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

   422

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

   423

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

   424

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

   425

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

   426

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

   427

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

   428

};

   429

   430

typedef struct HashLink {

   431

	TileIndex tile;

   432

	uint16 typelength;

   433

	uint16 next;

   434

} HashLink;

   435

   436

typedef struct {

   437

	NTPEnumProc *enum_proc;

   438

	void *userdata;

   439

	TileIndex dest;

   440

   441

	byte tracktype;

   442

	uint maxlength;

   443

   444

	HashLink *new_link;

   445

	uint num_links_left;

   446

   447

	uint nstack;

   448

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

   449

   450

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

   451

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

   452

   453

	HashLink links[0x400]; // hash links

   454

   455

} NewTrackPathFinder;

   456

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

   457

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

   458

   459

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

   460

   461

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

   462

// move it down to the proper position

   463

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   464

{

   465

	StackedItem si;

   466

	int i = ++tpf->nstack;

   467

   468

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

   469

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

   470

		// swap the child item and the parent item.

   471

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

   472

		i>>=1;

   473

	}

   474

}

   475

   476

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

   477

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   478

{

   479

	StackedItem si;

   480

	int i = 1, j;

   481

	int n;

   482

   483

	assert(tpf->nstack > 0);

   484

	n = --tpf->nstack;

   485

   486

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

   487

   488

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

   489

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

   490

   491

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

   492

		// figure out which is smaller of the children.

   493

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

   494

			j++; // right item is smaller

   495

   496

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

   497

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

   498

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

   499

   500

		// swap parent with the child

   501

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

   502

		i = j;

   503

	}

   504

}

   505

   506

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

   507

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

   508

// otherwise return true.

   509

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