1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "bridge_map.h"

     6

#include "functions.h"

     7

#include "map.h"

     8

#include "tile.h"

     9

#include "pathfind.h"

    10

#include "rail.h"

    11

#include "debug.h"

    12

#include "tunnel_map.h"

    13

#include "variables.h"

    14

    15

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

    16

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

    17

{

    18

	uint hash, val, offs;

    19

	TrackPathFinderLink *link, *new_link;

    20

	uint bits = 1 << dir;

    21

    22

	if (tpf->disable_tile_hash)

    23

		return true;

    24

    25

	hash = PATHFIND_HASH_TILE(tile);

    26

    27

	val = tpf->hash_head[hash];

    28

    29

	if (val == 0) {

    30

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

    31

		 * to indicate that a bit was set. */

    32

		tpf->hash_head[hash] = bits;

    33

		tpf->hash_tile[hash] = tile;

    34

		return true;

    35

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

    36

		/* single tile */

    37

    38

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

    39

			/* found another bit for the same tile,

    40

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

    41

			if (val & bits)

    42

				return false;

    43

    44

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

    45

			 * was set */

    46

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

    47

			return true;

    48

		} else {

    49

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

    50

    51

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

    52

			 * that a tile was already visisted. */

    53

			if (tpf->num_links_left == 0) {

    54

				return false;

    55

			}

    56

			tpf->num_links_left--;

    57

			link = tpf->new_link++;

    58

    59

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

    60

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

    61

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

    62

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

    63

    64

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

    65

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

    66

    67

			link->next = 0xFFFF;

    68

		}

    69

	} else {

    70

		/* a linked list of many tiles,

    71

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

    72

		 * otherwise make a new link */

    73

    74

		offs = tpf->hash_tile[hash];

    75

		do {

    76

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    77

			if (tile == link->tile) {

    78

				/* found the tile in the link list,

    79

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

    80

				 * bit was already set */

    81

				if (link->flags & bits)

    82

					return false;

    83

				link->flags |= bits;

    84

				return true;

    85

			}

    86

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

    87

	}

    88

    89

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

    90

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

    91

	if (tpf->num_links_left == 0) {

    92

			return false;

    93

	}

    94

	tpf->num_links_left--;

    95

	new_link = tpf->new_link++;

    96

    97

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

    98

	 * link to the new one */

    99

	new_link->tile = tile;

   100

	new_link->flags = bits;

   101

	new_link->next = 0xFFFF;

   102

   103

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

   104

	return true;

   105

}

   106

   107

static const byte _bits_mask[4] = {

   108

	0x19,

   109

	0x16,

   110

	0x25,

   111

	0x2A,

   112

};

   113

   114

static const byte _tpf_new_direction[14] = {

   115

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

   116

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

   117

};

   118

   119

static const byte _tpf_prev_direction[14] = {

   120

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

   121

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

   122

};

   123

   124

   125

static const byte _otherdir_mask[4] = {

   126

	0x10,

   127

	0,

   128

	0x5,

   129

	0x2A,

   130

};

   131

   132

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

   133

{

   134

	uint bits;

   135

	int i;

   136

	RememberData rd;

   137

	int owner = -1;

   138

   139

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

   140

	if (tpf->tracktype == TRANSPORT_RAIL) {

   141

		switch (GetTileType(tile)) {

   142

			case MP_TUNNELBRIDGE:

   143

				// bridge middle has no owner

   144

				if (IsBridge(tile) && IsBridgeMiddle(tile)) break;

   145

				/* FALLTHROUGH */

   146

   147

			case MP_RAILWAY:

   148

			case MP_STATION:

   149

				owner = GetTileOwner(tile);

   150

				break;

   151

   152

			default: break; // XXX can this occur?

   153

		}

   154

	}

   155

   156

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

   157

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

   158

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

   159

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

   160

   161

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

   162

	if (tpf->tracktype == TRANSPORT_RAIL) {

   163

		switch (GetTileType(tile)) {

   164

			case MP_TUNNELBRIDGE:

   165

				// bridge middle has no owner

   166

				if (IsBridge(tile) && IsBridgeMiddle(tile)) break;

   167

				/* FALLTHROUGH */

   168

   169

			case MP_RAILWAY:

   170

			case MP_STATION:

   171

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

   172

				break;

   173

   174

			default: break; // XXX can this occur?

   175

		}

   176

	}

   177

   178

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

   179

		return;

   180

   181

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

   182

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

   183

	if (bits == 0)

   184

		return;

   185

   186

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

   187

   188

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

   189

		/* only one direction */

   190

		i = 0;

   191

		while (!(bits&1))

   192

			i++, bits>>=1;

   193

   194

		rd = tpf->rd;

   195

		goto continue_here;

   196

	}

   197

	/* several directions */

   198

	i=0;

   199

	do {

   200

		if (!(bits & 1)) continue;

   201

		rd = tpf->rd;

   202

   203

		// Change direction 4 times only

   204

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

   205

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

   206

				tpf->rd = rd;

   207

				return;

   208

			}

   209

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

   210

		}

   211

   212

continue_here:;

   213

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

   214

   215

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

   216

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

   217

		}

   218

   219

		tpf->rd = rd;

   220

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

   221

   222

}

   223

   224

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

   225

   226

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

   227

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

   228

 */

   229

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection direction)

   230

{

   231

	FindLengthOfTunnelResult flotr;

   232

	int x,y;

   233

	byte z;

   234

   235

	flotr.length = 0;

   236

   237

	x = TileX(tile) * 16;

   238

	y = TileY(tile) * 16;

   239

   240

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

   241

   242

	for (;;) {

   243

		flotr.length++;

   244

   245

		x += _get_tunlen_inc[direction];

   246

		y += _get_tunlen_inc[direction+1];

   247

   248

		tile = TileVirtXY(x, y);

   249

   250

		if (IsTunnelTile(tile) &&

   251

				// GetTunnelTransportType(tile) == type &&  // rail/road-tunnel <-- This is not necesary to check, right?

   252

				ReverseDiagDir(GetTunnelDirection(tile)) == direction &&

   253

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

   254

			break;

   255

		}

   256

	}

   257

   258

	flotr.tile = tile;

   259

	return flotr;

   260

}

   261

   262

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

   263

   264

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

   265

{

   266

	FindLengthOfTunnelResult flotr;

   267

	TPFSetTileBit(tpf, tile, 14);

   268

	flotr = FindLengthOfTunnel(tile, direction);

   269

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

   270

	TPFSetTileBit(tpf, flotr.tile, 14);

   271

	return flotr.tile;

   272

}

   273

   274

const byte _ffb_64[128] = {

   275

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

   276

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

   277

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

   278

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

   279

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

   280

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

   281

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

   282

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

   283

   284

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

   285

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

   286

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

   287

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

   288

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

   289

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

   290

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

   291

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

   292

};

   293

   294

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

   295

{

   296

	uint bits;

   297

	int i;

   298

	RememberData rd;

   299

	TileIndex tile_org = tile;

   300

   301

	if (IsTunnelTile(tile)) {

   302

		if (GetTunnelDirection(tile) != direction ||

   303

				GetTunnelTransportType(tile) != tpf->tracktype) {

   304

			return;

   305

		}

   306

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   307

	}

   308

	tile += TileOffsByDir(direction);

   309

   310

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

   311

	if (tpf->tracktype == TRANSPORT_RAIL) {

   312

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

   313

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

   314

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

   315

				if (!IsBridgeTile(tile) || !IsBridgeMiddle(tile))

   316

					if (!IsBridgeTile(tile_org) || !IsBridgeMiddle(tile_org))

   317

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

   318

							return;

   319

	}

   320

   321

	tpf->rd.cur_length++;

   322

   323

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

   324

   325

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

   326

		bits &= _tpfmode1_and[direction];

   327

		bits = bits | (bits>>8);

   328

	}

   329

	bits &= 0xBF;

   330

   331

	if (bits != 0) {

   332

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

   333

			do {

   334

				i = FIND_FIRST_BIT(bits);

   335

				bits = KILL_FIRST_BIT(bits);

   336

   337

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

   338

				rd = tpf->rd;

   339

   340

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

   341

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

   342

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

   343

				}

   344

				tpf->rd = rd;

   345

			} while (bits != 0);

   346

		}

   347

	}

   348

   349

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

   350

	 * seems to go in 2 directions simultaneously */

   351

   352

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

   353

	 * stack space dramatically. */

   354

   355

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

   356

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

   357

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

   358

	if (tpf->hasbit_13)

   359

		return;

   360

   361

	tile = tile_org;

   362

	direction = ReverseDiagDir(direction);

   363

   364

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

   365

	bits |= (bits >> 8);

   366

   367

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

   368

		bits &= _bits_mask[direction];

   369

	}

   370

   371

	bits &= 0xBF;

   372

	if (bits == 0)

   373

		return;

   374

   375

	do {

   376

		i = FIND_FIRST_BIT(bits);

   377

		bits = KILL_FIRST_BIT(bits);

   378

   379

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

   380

		rd = tpf->rd;

   381

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

   382

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

   383

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

   384

		}

   385

		tpf->rd = rd;

   386

	} while (bits != 0);

   387

}

   388

   389

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

   390

{

   391

	TrackPathFinder tpf;

   392

   393

	assert(direction < 4);

   394

   395

	/* initialize path finder variables */

   396

	tpf.userdata = data;

   397

	tpf.enum_proc = enum_proc;

   398

	tpf.new_link = tpf.links;

   399

	tpf.num_links_left = lengthof(tpf.links);

   400

   401

	tpf.rd.cur_length = 0;

   402

	tpf.rd.depth = 0;

   403

	tpf.rd.pft_var6 = 0;

   404

   405

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

   406

   407

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

   408

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

   409

   410

   411

	tpf.tracktype = (byte)flags;

   412

   413

	if (HASBIT(flags, 11)) {

   414

		tpf.rd.pft_var6 = 0xFF;

   415

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

   416

		TPFMode2(&tpf, tile, direction);

   417

	} else {

   418

		/* clear the hash_heads */

   419

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

   420

		TPFMode1(&tpf, tile, direction);

   421

	}

   422

   423

	if (after_proc != NULL)

   424

		after_proc(&tpf);

   425

}

   426

   427

typedef struct {

   428

	TileIndex tile;

   429

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

   430

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

   431

	byte track;

   432

	byte depth;

   433

	byte state;

   434

	byte first_track;

   435

} StackedItem;

   436

   437

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

   438

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

   439

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

   440

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

   441

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

   442

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

   443

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

   444

};

   445

   446

typedef struct HashLink {

   447

	TileIndex tile;

   448

	uint16 typelength;

   449

	uint16 next;

   450

} HashLink;

   451

   452

typedef struct {

   453

	NTPEnumProc *enum_proc;

   454

	void *userdata;

   455

	TileIndex dest;

   456

   459

	uint maxlength;

   460

   461

	HashLink *new_link;

   462

	uint num_links_left;

   463

   464

	uint nstack;

   465

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

   466

   467

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

   468

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

   469

   470

	HashLink links[0x400]; // hash links

   471

   472

} NewTrackPathFinder;

   473

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

   474

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

   475

   476

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

   477

   478

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

   479

// move it down to the proper position

   480

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   481

{

   482

	StackedItem si;

   483

	int i = ++tpf->nstack;

   484

   485

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

   486

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

   487

		// swap the child item and the parent item.

   488

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

   489

		i>>=1;

   490

	}

   491

}

   492

   493

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

   494

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   495

{

   496

	StackedItem si;

   497

	int i = 1, j;

   498

	int n;

   499

   500

	assert(tpf->nstack > 0);

   501

	n = --tpf->nstack;

   502

   503

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

   504

   505

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

   506

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

   507

   508

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

   509