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

   225

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

   226

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

   227

 */

   228

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   229

{

   230

	TileIndexDiff delta = TileOffsByDir(dir);

   231

	uint z = GetTileZ(tile);

   232

	FindLengthOfTunnelResult flotr;

   233

   234

	flotr.length = 0;

   235

   236

	dir = ReverseDiagDir(dir);

   237

	do {

   238

		flotr.length++;

   239

		tile += delta;

   240

	} while(

   241

		!IsTunnelTile(tile) ||

   242

		GetTunnelDirection(tile) != dir ||

   243

		GetTileZ(tile) != z

   244

	);

   245

   246

	flotr.tile = tile;

   247

	return flotr;

   248

}

   249

   250

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

   251

   252

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

   253

{

   254

	FindLengthOfTunnelResult flotr;

   255

	TPFSetTileBit(tpf, tile, 14);

   256

	flotr = FindLengthOfTunnel(tile, direction);

   257

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

   258

	TPFSetTileBit(tpf, flotr.tile, 14);

   259

	return flotr.tile;

   260

}

   261

   262

const byte _ffb_64[128] = {

   263

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

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

   268

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

   269

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

   270

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

   271

   272

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

   273

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

   274

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

   275

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

   276

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

   277

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

   278

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

   279

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

   280

};

   281

   282

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

   283

{

   284

	uint bits;

   285

	int i;

   286

	RememberData rd;

   287

	TileIndex tile_org = tile;

   288

   289

	if (IsTunnelTile(tile)) {

   290

		if (GetTunnelDirection(tile) != direction ||

   291

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

   292

			return;

   293

		}

   294

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   295

	}

   296

	tile += TileOffsByDir(direction);

   297

   298

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

   299

	if (tpf->tracktype == TRANSPORT_RAIL) {

   300

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

   301

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

   302

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

   303

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

   304

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

   305

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

   306

							return;

   307

	}

   308

   309

	tpf->rd.cur_length++;

   310

   311

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

   312

   313

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

   314

		bits &= _tpfmode1_and[direction];

   315

		bits = bits | (bits>>8);

   316

	}

   317

	bits &= 0xBF;

   318

   319

	if (bits != 0) {

   320

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

   321

			do {

   322

				i = FIND_FIRST_BIT(bits);

   323

				bits = KILL_FIRST_BIT(bits);

   324

   325

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

   326

				rd = tpf->rd;

   327

   328

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

   329

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

   330

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

   331

				}

   332

				tpf->rd = rd;

   333

			} while (bits != 0);

   334

		}

   335

	}

   336

   337

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

   338

	 * seems to go in 2 directions simultaneously */

   339

   340

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

   341

	 * stack space dramatically. */

   342

   343

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

   344

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

   345

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

   346

	if (tpf->hasbit_13)

   347

		return;

   348

   349

	tile = tile_org;

   350

	direction = ReverseDiagDir(direction);

   351

   352

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

   353

	bits |= (bits >> 8);

   354

   355

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

   356

		bits &= _bits_mask[direction];

   357

	}

   358

   359

	bits &= 0xBF;

   360

	if (bits == 0)

   361

		return;

   362

   363

	do {

   364

		i = FIND_FIRST_BIT(bits);

   365

		bits = KILL_FIRST_BIT(bits);

   366

   367

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

   368

		rd = tpf->rd;

   369

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

   370

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

   371

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

   372

		}

   373

		tpf->rd = rd;

   374

	} while (bits != 0);

   375

}

   376

   377

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

   378

{

   379

	TrackPathFinder tpf;

   380

   381

	assert(direction < 4);

   382

   383

	/* initialize path finder variables */

   384

	tpf.userdata = data;

   385

	tpf.enum_proc = enum_proc;

   386

	tpf.new_link = tpf.links;

   387

	tpf.num_links_left = lengthof(tpf.links);

   388

   389

	tpf.rd.cur_length = 0;

   390

	tpf.rd.depth = 0;

   391

	tpf.rd.pft_var6 = 0;

   392

   393

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

   394

   395

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

   396

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

   397

   398

   399

	tpf.tracktype = (byte)flags;

   400

   401

	if (HASBIT(flags, 11)) {

   402

		tpf.rd.pft_var6 = 0xFF;

   403

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

   404

		TPFMode2(&tpf, tile, direction);

   405

	} else {

   406

		/* clear the hash_heads */

   407

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

   408

		TPFMode1(&tpf, tile, direction);

   409

	}

   410

   411

	if (after_proc != NULL)

   412

		after_proc(&tpf);

   413

}

   414

   415

typedef struct {

   416

	TileIndex tile;

   417

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

   418

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

   419

	byte track;

   420

	byte depth;

   421

	byte state;

   422

	byte first_track;

   423

} StackedItem;

   424

   425

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

   426

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

   427

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

   428

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

   429

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

   430

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

   431

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

   432

};

   433

   434

typedef struct HashLink {

   435

	TileIndex tile;

   436

	uint16 typelength;

   437

	uint16 next;

   438

} HashLink;

   439

   440

typedef struct {

   441

	NTPEnumProc *enum_proc;

   442

	void *userdata;

   443

	TileIndex dest;

   444

   445

	TransportType tracktype;

   446

	RailTypeMask railtypes;

   447

	uint maxlength;

   448

   449

	HashLink *new_link;

   450

	uint num_links_left;

   451

   452

	uint nstack;

   453

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

   454

   455

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

   456

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

   457

   458

	HashLink links[0x400]; // hash links

   459

   460

} NewTrackPathFinder;

   461

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

   462

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

   463

   464

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

   465

   466

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

   467

// move it down to the proper position

   468

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   469

{

   470

	StackedItem si;

   471

	int i = ++tpf->nstack;

   472

   473

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

   474

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

   475

		// swap the child item and the parent item.

   476

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

   477

		i>>=1;

   478

	}

   479

}

   480

   481

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

   482

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   483

{

   484

	StackedItem si;

   485

	int i = 1, j;

   486

	int n;

   487

   488

	assert(tpf->nstack > 0);

   489

	n = --tpf->nstack;

   490

   491

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

   492

   493

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

   494

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

   495

   496

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

   497

		// figure out which is smaller of the children.

   498

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

   499

			j++; // right item is smaller

   500

   501

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

   502

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

   503

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

   504

   505

		// swap parent with the child

   506

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

   507

		i = j;

   508

	}