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

   138

	assert(tpf->tracktype == TRANSPORT_WATER);

   139

   140

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

   141

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

   142

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

   143

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

   144

   145

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

   146

		return;

   147

   148

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

   149

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

   150

	if (bits == 0)

   151

		return;

   152

   153

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

   154

   155

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

   156

		/* only one direction */

   157

		i = 0;

   158

		while (!(bits&1))

   159

			i++, bits>>=1;

   160

   161

		rd = tpf->rd;

   162

		goto continue_here;

   163

	}

   164

	/* several directions */

   165

	i=0;

   166

	do {

   167

		if (!(bits & 1)) continue;

   168

		rd = tpf->rd;

   169

   170

		// Change direction 4 times only

   171

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

   172

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

   173

				tpf->rd = rd;

   174

				return;

   175

			}

   176

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

   177

		}

   178

   179

continue_here:;

   180

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

   181

   182

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

   183

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

   184

		}

   185

   186

		tpf->rd = rd;

   187

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

   188

   189

}

   190

   191

   192

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

   193

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

   194

 */

   195

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   196

{

   197

	TileIndexDiff delta = TileOffsByDir(dir);

   198

	uint z = GetTileZ(tile);

   199

	FindLengthOfTunnelResult flotr;

   200

   201

	flotr.length = 0;

   202

   203

	dir = ReverseDiagDir(dir);

   204

	do {

   205

		flotr.length++;

   206

		tile += delta;

   207

	} while(

   208

		!IsTunnelTile(tile) ||

   209

		GetTunnelDirection(tile) != dir ||

   210

		GetTileZ(tile) != z

   211

	);

   212

   213

	flotr.tile = tile;

   214

	return flotr;

   215

}

   216

   217

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

   218

   219

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

   220

{

   221

	FindLengthOfTunnelResult flotr;

   222

	TPFSetTileBit(tpf, tile, 14);

   223

	flotr = FindLengthOfTunnel(tile, direction);

   224

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

   225

	TPFSetTileBit(tpf, flotr.tile, 14);

   226

	return flotr.tile;

   227

}

   228

   229

const byte _ffb_64[128] = {

   230

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

   231

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

   232

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

   233

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

   234

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

   235

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

   236

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

   237

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

   238

   239

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

   240

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

   241

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

   242

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

   243

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

   244

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

   245

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

   246

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

   247

};

   248

   249

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

   250

{

   251

	uint bits;

   252

	int i;

   253

	RememberData rd;

   254

	TileIndex tile_org = tile;

   255

   256

	if (IsTunnelTile(tile)) {

   257

		if (GetTunnelDirection(tile) != direction ||

   258

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

   259

			return;

   260

		}

   261

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   262

	}

   263

	tile += TileOffsByDir(direction);

   264

   265

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

   266

	if (tpf->tracktype == TRANSPORT_RAIL) {

   267

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

   268

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

   269

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

   270

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

   271

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

   272

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

   273

							return;

   274

	}

   275

   276

	tpf->rd.cur_length++;

   277

   278

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

   279

   280

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

   281

		bits &= _tpfmode1_and[direction];

   282

		bits = bits | (bits>>8);

   283

	}

   284

	bits &= 0xBF;

   285

   286

	if (bits != 0) {

   287

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

   288

			do {

   289

				i = FIND_FIRST_BIT(bits);

   290

				bits = KILL_FIRST_BIT(bits);

   291

   292

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

   293

				rd = tpf->rd;

   294

   295

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

   296

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

   297

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

   298

				}

   299

				tpf->rd = rd;

   300

			} while (bits != 0);

   301

		}

   302

	}

   303

   304

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

   305

	 * seems to go in 2 directions simultaneously */

   306

   307

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

   308

	 * stack space dramatically. */

   309

   310

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

   311

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

   312

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

   313

	if (tpf->hasbit_13)

   314

		return;

   315

   316

	tile = tile_org;

   317

	direction = ReverseDiagDir(direction);

   318

   319

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

   320

	bits |= (bits >> 8);

   321

   322

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

   323

		bits &= _bits_mask[direction];

   324

	}

   325

   326

	bits &= 0xBF;

   327

	if (bits == 0)

   328

		return;

   329

   330

	do {

   331

		i = FIND_FIRST_BIT(bits);

   332

		bits = KILL_FIRST_BIT(bits);

   333

   334

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

   335

		rd = tpf->rd;

   336

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

   337

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

   338

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

   339

		}

   340

		tpf->rd = rd;

   341

	} while (bits != 0);

   342

}

   343

   344

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

   345

{

   346

	TrackPathFinder tpf;

   347

   348

	assert(direction < 4);

   349

   350

	/* initialize path finder variables */

   351

	tpf.userdata = data;

   352

	tpf.enum_proc = enum_proc;

   353

	tpf.new_link = tpf.links;

   354

	tpf.num_links_left = lengthof(tpf.links);

   355

   356

	tpf.rd.cur_length = 0;

   357

	tpf.rd.depth = 0;

   358

	tpf.rd.pft_var6 = 0;

   359

   360

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

   361

   362

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

   363

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

   364

   365

   366

	tpf.tracktype = (byte)flags;

   367

   368

	if (HASBIT(flags, 11)) {

   369

		tpf.rd.pft_var6 = 0xFF;

   370

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

   371

		TPFMode2(&tpf, tile, direction);

   372

	} else {

   373

		/* clear the hash_heads */

   374

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

   375

		TPFMode1(&tpf, tile, direction);

   376

	}

   377

   378

	if (after_proc != NULL)

   379

		after_proc(&tpf);

   380

}

   381

   382

typedef struct {

   383

	TileIndex tile;

   384

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

   385

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

   386

	byte track;

   387

	byte depth;

   388

	byte state;

   389

	byte first_track;

   390

} StackedItem;

   391

   392

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

   393

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

   394

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

   395

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

   396

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

   397

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

   398

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

   399

};

   400

   401

typedef struct HashLink {

   402

	TileIndex tile;

   403

	uint16 typelength;

   404

	uint16 next;

   405

} HashLink;

   406

   407

typedef struct {

   408

	NTPEnumProc *enum_proc;

   409

	void *userdata;

   410

	TileIndex dest;

   411

   412

	TransportType tracktype;

   413

	RailTypeMask railtypes;

   414

	uint maxlength;

   415

   416

	HashLink *new_link;

   417

	uint num_links_left;

   418

   419

	uint nstack;

   420

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

   421

   422

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

   423

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

   424

   425

	HashLink links[0x400]; // hash links

   426

   427

} NewTrackPathFinder;

   428

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

   429

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

   430

   431

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

   432

   433

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

   434

// move it down to the proper position

   435

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   436

{

   437

	StackedItem si;

   438

	int i = ++tpf->nstack;

   439

   440

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

   441

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

   442

		// swap the child item and the parent item.

   443

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

   444

		i>>=1;

   445

	}

   446

}

   447

   448

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

   449

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   450

{

   451

	StackedItem si;

   452

	int i = 1, j;

   453

	int n;

   454

   455

	assert(tpf->nstack > 0);

   456

	n = --tpf->nstack;

   457

   458

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

   459

   460

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

   461

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

   462

   463

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

   464

		// figure out which is smaller of the children.

   465

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

   466

			j++; // right item is smaller

   467

   468

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

   469

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

   470

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

   471

   472

		// swap parent with the child

   473

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

   474

		i = j;

   475

	}

   476

}

   477

   478

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

   479

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

   480

// otherwise return true.

   481

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

   482

{

   483

	uint hash,head;

   484

	HashLink *link, *new_link;

   485

   486

	assert(length < 16384-1);

   487

   488

	hash = PATHFIND_HASH_TILE(tile);

   489

   490

	// never visited before?

   491

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

   492

		tpf->hash_tile[hash] = tile;

   493

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

   494

		return true;

   495

	}

   496

   497

	if (head != 0xffff) {

   498

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

   499

   500

			// longer length

   501

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

   502

   503

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

   504

			return true;

   505

		}

   506

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

   507

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

   508

		// that a tile was already visisted.

   509

		if (tpf->num_links_left == 0) {

   510

			DEBUG(ntp, 1) ("[NTP] no links left");