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"

    15

    16

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

    17

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

    18

{

    19

	uint hash, val, offs;

    20

	TrackPathFinderLink *link, *new_link;

    21

	uint bits = 1 << dir;

    22

    23

	if (tpf->disable_tile_hash)

    24

		return true;

    25

    26

	hash = PATHFIND_HASH_TILE(tile);

    27

    28

	val = tpf->hash_head[hash];

    29

    30

	if (val == 0) {

    31

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

    32

		 * to indicate that a bit was set. */

    33

		tpf->hash_head[hash] = bits;

    34

		tpf->hash_tile[hash] = tile;

    35

		return true;

    36

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

    37

		/* single tile */

    38

    39

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

    40

			/* found another bit for the same tile,

    41

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

    42

			if (val & bits)

    43

				return false;

    44

    45

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

    46

			 * was set */

    47

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

    48

			return true;

    49

		} else {

    50

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

    51

    52

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

    53

			 * that a tile was already visisted. */

    54

			if (tpf->num_links_left == 0) {

    55

				return false;

    56

			}

    57

			tpf->num_links_left--;

    58

			link = tpf->new_link++;

    59

    60

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

    61

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

    62

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

    63

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

    64

    65

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

    66

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

    67

    68

			link->next = 0xFFFF;

    69

		}

    70

	} else {

    71

		/* a linked list of many tiles,

    72

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

    73

		 * otherwise make a new link */

    74

    75

		offs = tpf->hash_tile[hash];

    76

		do {

    77

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    78

			if (tile == link->tile) {

    79

				/* found the tile in the link list,

    80

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

    81

				 * bit was already set */

    82

				if (link->flags & bits)

    83

					return false;

    84

				link->flags |= bits;

    85

				return true;

    86

			}

    87

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

    88

	}

    89

    90

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

    91

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

    92

	if (tpf->num_links_left == 0) {

    93

			return false;

    94

	}

    95

	tpf->num_links_left--;

    96

	new_link = tpf->new_link++;

    97

    98

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

    99

	 * link to the new one */

   100

	new_link->tile = tile;

   101

	new_link->flags = bits;

   102

	new_link->next = 0xFFFF;

   103

   104

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

   105

	return true;

   106

}

   107

   108

static const byte _bits_mask[4] = {

   109

	0x19,

   110

	0x16,

   111

	0x25,

   112

	0x2A,

   113

};

   114

   115

static const byte _tpf_new_direction[14] = {

   116

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

   117

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

   118

};

   119

   120

static const byte _tpf_prev_direction[14] = {

   121

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

   122

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

   123

};

   124

   125

   126

static const byte _otherdir_mask[4] = {

   127

	0x10,

   128

	0,

   129

	0x5,

   130

	0x2A,

   131

};

   132

   133

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

   134

{

   135

	uint bits;

   136

	int i;

   137

	RememberData rd;

   138

   139

	assert(tpf->tracktype == TRANSPORT_WATER);

   140

   141

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

   142

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

   143

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

   144

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

   145

   146

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

   147

		return;

   148

   149

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

   150

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

   151

	if (bits == 0)

   152

		return;

   153

   154

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

   155

   156

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

   157

		/* only one direction */

   158

		i = 0;

   159

		while (!(bits&1))

   160

			i++, bits>>=1;

   161

   162

		rd = tpf->rd;

   163

		goto continue_here;

   164

	}

   165

	/* several directions */

   166

	i=0;

   167

	do {

   168

		if (!(bits & 1)) continue;

   169

		rd = tpf->rd;

   170

   171

		// Change direction 4 times only

   172

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

   173

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

   174

				tpf->rd = rd;

   175

				return;

   176

			}

   177

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

   178

		}

   179

   180

continue_here:;

   181

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

   182

   183

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

   184

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

   185

		}

   186

   187

		tpf->rd = rd;

   188

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

   189

   190

}

   191

   192

   193

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

   194

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

   195

 */

   196

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   197

{

   198

	TileIndexDiff delta = TileOffsByDir(dir);

   199

	uint z = GetTileZ(tile);

   200

	FindLengthOfTunnelResult flotr;

   201

   202

	flotr.length = 0;

   203

   204

	dir = ReverseDiagDir(dir);

   205

	do {

   206

		flotr.length++;

   207

		tile += delta;

   208

	} while(

   209

		!IsTunnelTile(tile) ||

   210

		GetTunnelDirection(tile) != dir ||

   211

		GetTileZ(tile) != z

   212

	);

   213

   214

	flotr.tile = tile;

   215

	return flotr;

   216

}

   217

   218

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

   219

   220

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

   221

{

   222

	FindLengthOfTunnelResult flotr;

   223

	TPFSetTileBit(tpf, tile, 14);

   224

	flotr = FindLengthOfTunnel(tile, direction);

   225

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

   226

	TPFSetTileBit(tpf, flotr.tile, 14);

   227

	return flotr.tile;

   228

}

   229

   230

const byte _ffb_64[128] = {

   231

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

   232

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

   233

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

   234

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

   235

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

   236

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

   237

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

   238

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

   239

   240

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

   241

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

   242

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

   243

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

   244

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

   245

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

   246

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

   247

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

   248

};

   249

   250

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

   251

{

   252

	uint bits;

   253

	int i;

   254

	RememberData rd;

   255

	TileIndex tile_org = tile;

   256

   257

	if (IsTunnelTile(tile)) {

   258

		if (GetTunnelDirection(tile) != direction ||

   259

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

   260

			return;

   261

		}

   262

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   263

	}

   264

	tile += TileOffsByDir(direction);

   265

   266

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

   267

	if (tpf->tracktype == TRANSPORT_RAIL) {

   271

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

   272

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

   273

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

   274

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

   275

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

   276

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

   277

							return;

   278

	}

   279

   280

	tpf->rd.cur_length++;

   281

   282

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

   283

   284

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

   285

		bits &= _tpfmode1_and[direction];

   286

		bits = bits | (bits>>8);

   287

	}

   288

	bits &= 0xBF;

   289

   290

	if (bits != 0) {

   291

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

   292

			do {

   293

				i = FIND_FIRST_BIT(bits);

   294

				bits = KILL_FIRST_BIT(bits);

   295

   296

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

   297

				rd = tpf->rd;

   298

   299

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

   300

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

   301

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

   302

				}

   303

				tpf->rd = rd;

   304

			} while (bits != 0);

   305

		}

   306

	}

   307

   308

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

   309

	 * seems to go in 2 directions simultaneously */

   310

   311

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

   312

	 * stack space dramatically. */

   313

   314

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

   315

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

   316

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

   317

	if (tpf->hasbit_13)

   318

		return;

   319

   320

	tile = tile_org;

   321

	direction = ReverseDiagDir(direction);

   322

   323

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

   324

	bits |= (bits >> 8);

   325

   326

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

   327

		bits &= _bits_mask[direction];

   328

	}

   329

   330

	bits &= 0xBF;

   331

	if (bits == 0)

   332

		return;

   333

   334

	do {

   335

		i = FIND_FIRST_BIT(bits);

   336

		bits = KILL_FIRST_BIT(bits);

   337

   338

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

   339

		rd = tpf->rd;

   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

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

   349

{

   350

	TrackPathFinder tpf;

   351

   352

	assert(direction < 4);

   353

   354

	/* initialize path finder variables */

   355

	tpf.userdata = data;

   356

	tpf.enum_proc = enum_proc;

   357

	tpf.new_link = tpf.links;

   358

	tpf.num_links_left = lengthof(tpf.links);

   359

   360

	tpf.rd.cur_length = 0;

   361

	tpf.rd.depth = 0;

   362

	tpf.rd.pft_var6 = 0;

   363

   364

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

   365

   366

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

   367

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

   368

   369

   370

	tpf.tracktype = (byte)flags;

   371

   372

	if (HASBIT(flags, 11)) {

   373

		tpf.rd.pft_var6 = 0xFF;

   374

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

   375

		TPFMode2(&tpf, tile, direction);

   376

	} else {

   377

		/* clear the hash_heads */

   378

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

   379

		TPFMode1(&tpf, tile, direction);

   380

	}

   381

   382

	if (after_proc != NULL)

   383

		after_proc(&tpf);

   384

}

   385

   386

typedef struct {

   387

	TileIndex tile;

   388

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

   389

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

   390

	byte track;

   391

	byte depth;

   392

	byte state;

   393

	byte first_track;

   394

} StackedItem;

   395

   396

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

   397

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

   398

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

   399

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

   400

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

   401

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

   402

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

   403

};

   404

   405

typedef struct HashLink {

   406

	TileIndex tile;

   407

	uint16 typelength;

   408

	uint16 next;

   409

} HashLink;

   410

   411

typedef struct {

   412

	NTPEnumProc *enum_proc;

   413

	void *userdata;

   414

	TileIndex dest;

   415

   416

	TransportType tracktype;

   417

	RailTypeMask railtypes;

   418

	uint maxlength;

   419

   420

	HashLink *new_link;

   421

	uint num_links_left;

   422

   423

	uint nstack;

   424

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

   425

   426

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

   427

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

   428

   429

	HashLink links[0x400]; // hash links

   430

   431

} NewTrackPathFinder;

   432

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

   433

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

   434

   435

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

   436

   437

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

   438

// move it down to the proper position

   439

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   440

{

   441

	StackedItem si;

   442

	int i = ++tpf->nstack;

   443

   444

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

   445

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

   446

		// swap the child item and the parent item.

   447

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

   448

		i>>=1;

   449

	}

   450

}

   451

   452

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

   453

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   454

{

   455

	StackedItem si;

   456

	int i = 1, j;

   457

	int n;

   458

   459

	assert(tpf->nstack > 0);

   460

	n = --tpf->nstack;

   461

   462

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

   463

   464

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

   465

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

   466

   467

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

   468

		// figure out which is smaller of the children.

   469

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

   470

			j++; // right item is smaller

   471

   472

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

   473

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

   474

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

   475

   476

		// swap parent with the child

   477

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

   478

		i = j;

   479

	}

   480

}

   481

   482

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

   483

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

   484

// otherwise return true.

   485

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

   486

{

   487

	uint hash,head;

   488

	HashLink *link, *new_link;

   489

   490

	assert(length < 16384-1);

   491

   492

	hash = PATHFIND_HASH_TILE(tile);

   493

   494

	// never visited before?

   495

	if ((head=tpf->hash_head[hash]) == 0) {

   496

		tpf->hash_tile[hash] = tile;

   497

		tpf->hash_head[hash] = dir | (length << 2);

   498

		return true;

   499

	}

   500

   501

	if (head != 0xffff) {

   502

		if (tile == tpf->hash_tile[hash] && (head & 0x3) == dir) {

   503

   504

			// longer length

   505

			if (length >= (head >> 2)) return false;

   506

   507

			tpf->hash_head[hash] = dir | (length << 2);

   508

			return true;

   509

		}

   510