1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "bridge_map.h"

     6

#include "station_map.h"

     7

#include "depot.h"

     8

#include "functions.h"

     9

#include "map.h"

    10

#include "tile.h"

    11

#include "pathfind.h"

    12

#include "rail.h"

    13

#include "debug.h"

    14

#include "tunnel_map.h"

    15

#include "variables.h"

    16

#include "depot.h"

    17

    18

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

    19

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

    20

{

    21

	uint hash, val, offs;

    22

	TrackPathFinderLink *link, *new_link;

    23

	uint bits = 1 << dir;

    24

    25

	if (tpf->disable_tile_hash)

    26

		return true;

    27

    28

	hash = PATHFIND_HASH_TILE(tile);

    29

    30

	val = tpf->hash_head[hash];

    31

    32

	if (val == 0) {

    33

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

    34

		 * to indicate that a bit was set. */

    35

		tpf->hash_head[hash] = bits;

    36

		tpf->hash_tile[hash] = tile;

    37

		return true;

    38

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

    39

		/* single tile */

    40

    41

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

    42

			/* found another bit for the same tile,

    43

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

    44

			if (val & bits)

    45

				return false;

    46

    47

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

    48

			 * was set */

    49

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

    50

			return true;

    51

		} else {

    52

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

    53

    54

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

    55

			 * that a tile was already visisted. */

    56

			if (tpf->num_links_left == 0) {

    57

				return false;

    58

			}

    59

			tpf->num_links_left--;

    60

			link = tpf->new_link++;

    61

    62

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

    63

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

    64

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

    65

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

    66

    67

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

    68

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

    69

    70

			link->next = 0xFFFF;

    71

		}

    72

	} else {

    73

		/* a linked list of many tiles,

    74

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

    75

		 * otherwise make a new link */

    76

    77

		offs = tpf->hash_tile[hash];

    78

		do {

    79

			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    80

			if (tile == link->tile) {

    81

				/* found the tile in the link list,

    82

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

    83

				 * bit was already set */

    84

				if (link->flags & bits)

    85

					return false;

    86

				link->flags |= bits;

    87

				return true;

    88

			}

    89

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

    90

	}

    91

    92

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

    93

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

    94

	if (tpf->num_links_left == 0) {

    95

			return false;

    96

	}

    97

	tpf->num_links_left--;

    98

	new_link = tpf->new_link++;

    99

   100

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

   101

	 * link to the new one */

   102

	new_link->tile = tile;

   103

	new_link->flags = bits;

   104

	new_link->next = 0xFFFF;

   105

   106

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

   107

	return true;

   108

}

   109

   110

static const byte _bits_mask[4] = {

   111

	0x19,

   112

	0x16,

   113

	0x25,

   114

	0x2A,

   115

};

   116

   117

static const byte _tpf_new_direction[14] = {

   118

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

   119

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

   120

};

   121

   122

static const byte _tpf_prev_direction[14] = {

   123

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

   124

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

   125

};

   126

   127

   128

static const byte _otherdir_mask[4] = {

   129

	0x10,

   130

	0,

   131

	0x5,

   132

	0x2A,

   133

};

   134

   135

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

   136

{

   137

	uint bits;

   138

	int i;

   139

	RememberData rd;

   140

   141

	assert(tpf->tracktype == TRANSPORT_WATER);

   142

   143

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

   144

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

   145

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

   146

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

   147

   148

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

   149

		return;

   150

   151

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

   152

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

   153

	if (bits == 0)

   154

		return;

   155

   156

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

   157

   158

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

   159

		/* only one direction */

   160

		i = 0;

   161

		while (!(bits&1))

   162

			i++, bits>>=1;

   163

   164

		rd = tpf->rd;

   165

		goto continue_here;

   166

	}

   167

	/* several directions */

   168

	i=0;

   169

	do {

   170

		if (!(bits & 1)) continue;

   171

		rd = tpf->rd;

   172

   173

		// Change direction 4 times only

   174

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

   175

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

   176

				tpf->rd = rd;

   177

				return;

   178

			}

   179

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

   180

		}

   181

   182

continue_here:;

   183

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

   184

   185

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

   186

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

   187

		}

   188

   189

		tpf->rd = rd;

   190

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

   191

   192

}

   193

   194

   195

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

   196

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

   197

 */

   198

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   199

{

   200

	TileIndexDiff delta = TileOffsByDir(dir);

   201

	uint z = GetTileZ(tile);

   202

	FindLengthOfTunnelResult flotr;

   203

   204

	flotr.length = 0;

   205

   206

	dir = ReverseDiagDir(dir);

   207

	do {

   208

		flotr.length++;

   209

		tile += delta;

   210

	} while(

   211

		!IsTunnelTile(tile) ||

   212

		GetTunnelDirection(tile) != dir ||

   213

		GetTileZ(tile) != z

   214

	);

   215

   216

	flotr.tile = tile;

   217

	return flotr;

   218

}

   219

   220

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

   221

   222

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

   223

{

   224

	FindLengthOfTunnelResult flotr;

   225

	TPFSetTileBit(tpf, tile, 14);

   226

	flotr = FindLengthOfTunnel(tile, direction);

   227

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

   228

	TPFSetTileBit(tpf, flotr.tile, 14);

   229

	return flotr.tile;

   230

}

   231

   232

const byte _ffb_64[128] = {

   233

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

   234

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

   235

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

   236

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

   237

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

   238

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

   239

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

   240

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

   241

   242

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

   243

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

   244

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

   245

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

   246

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

   247

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

   248

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

   249

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

   250

};

   251

   252

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

   253

{

   254

	uint bits;

   255

	int i;

   256

	RememberData rd;

   257

	TileIndex tile_org = tile;

   258

   259

	// check if the old tile can be left at that direction

   260

	if (tpf->tracktype == TRANSPORT_ROAD) {

   261

		// road stops and depots now have a track (r4419)

   262

		// don't enter road stop from the back

   263

		if (IsRoadStopTile(tile) && GetRoadStopDir(tile) != direction) return;

   264

		// don't enter road depot from the back

   265

		if (IsTileDepotType(tile, TRANSPORT_ROAD) && GetRoadDepotDirection(tile) != direction) return;

   266

	}

   267

   268

	if (IsTunnelTile(tile)) {

   269

		if (GetTunnelDirection(tile) != direction ||

   270

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

   271

			return;

   272

		}

   273

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   274

	}

   275

	tile += TileOffsByDir(direction);

   276

   277

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

   278

	if (tpf->tracktype == TRANSPORT_RAIL) {

   279

		// don't enter train depot from the back

   280

		if (IsTileDepotType(tile, TRANSPORT_RAIL) && GetRailDepotDirection(tile) == direction) return;

   281

   282

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

   283

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

   284

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

   285

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

   286

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

   287

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

   288

							return;

   289

	}

   290

   291

	// check if the new tile can be entered from that direction

   292

	if (tpf->tracktype == TRANSPORT_ROAD) {

   293

		// road stops and depots now have a track (r4419)

   294

		// don't enter road stop from the back

   295

		if (IsRoadStopTile(tile) && GetRoadStopDir(tile) == direction) return;

   296

		// don't enter road depot from the back

   297

		if (IsTileDepotType(tile, TRANSPORT_ROAD) && GetRoadDepotDirection(tile) == direction) return;

   298

	}

   299

   300

	tpf->rd.cur_length++;

   301

   302

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

   303

   304

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

   305

		bits &= _tpfmode1_and[direction];

   306

		bits = bits | (bits>>8);

   307

	}

   308

	bits &= 0xBF;

   309

   310

	if (bits != 0) {

   311

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

   312

			do {

   313

				i = FIND_FIRST_BIT(bits);

   314

				bits = KILL_FIRST_BIT(bits);

   315

   316

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

   317

				rd = tpf->rd;

   318

   319

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

   320

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

   321

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

   322

				}

   323

				tpf->rd = rd;

   324

			} while (bits != 0);

   325

		}

   326

	}

   327

   328

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

   329

	 * seems to go in 2 directions simultaneously */

   330

   331

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

   332

	 * stack space dramatically. */

   333

   334

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

   335

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

   336

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

   337

	if (tpf->hasbit_13)

   338

		return;

   339

   340

	tile = tile_org;

   341

	direction = ReverseDiagDir(direction);

   342

   343

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

   344

	bits |= (bits >> 8);

   345

   346

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

   347

		bits &= _bits_mask[direction];

   348

	}

   349

   350

	bits &= 0xBF;

   351

	if (bits == 0)

   352

		return;

   353

   354

	do {

   355

		i = FIND_FIRST_BIT(bits);

   356

		bits = KILL_FIRST_BIT(bits);

   357

   358

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

   359

		rd = tpf->rd;

   360

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

   361

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

   362

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

   363

		}

   364

		tpf->rd = rd;

   365

	} while (bits != 0);

   366

}

   367

   368

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

   369

{

   370

	TrackPathFinder tpf;

   371

   372

	assert(direction < 4);

   373

   374

	/* initialize path finder variables */

   375

	tpf.userdata = data;

   376

	tpf.enum_proc = enum_proc;

   377

	tpf.new_link = tpf.links;

   378

	tpf.num_links_left = lengthof(tpf.links);

   379

   380

	tpf.rd.cur_length = 0;

   381

	tpf.rd.depth = 0;

   382

	tpf.rd.pft_var6 = 0;

   383

   384

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

   385

   386

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

   387

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

   388

   389

   390

	tpf.tracktype = (byte)flags;

   391

   392

	if (HASBIT(flags, 11)) {

   393

		tpf.rd.pft_var6 = 0xFF;

   394

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

   395

		TPFMode2(&tpf, tile, direction);

   396

	} else {

   397

		/* clear the hash_heads */

   398

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

   399

		TPFMode1(&tpf, tile, direction);

   400

	}

   401

   402

	if (after_proc != NULL)

   403

		after_proc(&tpf);

   404

}

   405

   406

typedef struct {

   407

	TileIndex tile;

   408

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

   409

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

   410

	byte track;

   411

	byte depth;

   412

	byte state;

   413

	byte first_track;

   414

} StackedItem;

   415

   416

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

   417

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

   418

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

   419

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

   420

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

   421

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

   422

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

   423

};

   424

   425

typedef struct HashLink {

   426

	TileIndex tile;

   427

	uint16 typelength;

   428

	uint16 next;

   429

} HashLink;

   430

   431

typedef struct {

   432

	NTPEnumProc *enum_proc;

   433

	void *userdata;

   434

	TileIndex dest;

   435

   436

	TransportType tracktype;

   437

	RailTypeMask railtypes;

   438

	uint maxlength;

   439

   440

	HashLink *new_link;

   441

	uint num_links_left;

   442

   443

	uint nstack;

   444

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

   445

   446

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

   447

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

   448

   449

	HashLink links[0x400]; // hash links

   450

   451

} NewTrackPathFinder;

   452

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

   453

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

   454

   455

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

   456

   457

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

   458

// move it down to the proper position

   459

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   460

{

   461

	StackedItem si;

   462

	int i = ++tpf->nstack;

   463

   464

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

   465

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

   466

		// swap the child item and the parent item.

   467

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

   468

		i>>=1;

   469

	}

   470

}

   471

   472

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

   473

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   474

{

   475

	StackedItem si;

   476

	int i = 1, j;

   477

	int n;

   478

   479

	assert(tpf->nstack > 0);

   480

	n = --tpf->nstack;

   481

   482

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

   483

   484

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

   485

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

   486

   487

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

   488

		// figure out which is smaller of the children.

   489

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

   490

			j++; // right item is smaller

   491

   492

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

   493

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

   494

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

   495

   496

		// swap parent with the child

   497

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

   498

		i = j;

   499

	}

   500

}

   501

   502

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

   503

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

   504

// otherwise return true.

   505

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

   506

{

   507

	uint hash,head;

   508

	HashLink *link, *new_link;

   509