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,

   119

	0, 0,

   120

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

   121

};

   122

   123

static const byte _tpf_prev_direction[14] = {

   124

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

   125

	0, 0,

   126

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

   127

};

   128

   129

   130

static const byte _otherdir_mask[4] = {

   131

	0x10,

   132

	0,

   133

	0x5,

   134

	0x2A,

   135

};

   136

   137

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

   138

{

   139

	uint bits;

   140

	int i;

   141

	RememberData rd;

   142

   143

	assert(tpf->tracktype == TRANSPORT_WATER);

   144

   145

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

   146

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

   147

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

   148

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

   149

   150

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

   151

		return;

   152

   153

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

   154

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

   155

	if (bits == 0)

   156

		return;

   157

   158

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

   159

   160

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

   161

		/* only one direction */

   162

		i = 0;

   163

		while (!(bits&1))

   164

			i++, bits>>=1;

   165

   166

		rd = tpf->rd;

   167

		goto continue_here;

   168

	}

   169

	/* several directions */

   170

	i=0;

   171

	do {

   172

		if (!(bits & 1)) continue;

   173

		rd = tpf->rd;

   174

   175

		// Change direction 4 times only

   176

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

   177

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

   178

				tpf->rd = rd;

   179

				return;

   180

			}

   181

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

   182

		}

   183

   184

continue_here:;

   185

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

   186

   187

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

   188

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

   189

		}

   190

   191

		tpf->rd = rd;

   192

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

   193

   194

}

   195

   196

   197

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

   198

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

   199

 */

   200

FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)

   201

{

   202

	TileIndexDiff delta = TileOffsByDiagDir(dir);

   203

	uint z = GetTileZ(tile);

   204

	FindLengthOfTunnelResult flotr;

   205

   206

	flotr.length = 0;

   207

   208

	dir = ReverseDiagDir(dir);

   209

	do {

   210

		flotr.length++;

   211

		tile += delta;

   212

	} while(

   213

		!IsTunnelTile(tile) ||

   214

		GetTunnelDirection(tile) != dir ||

   215

		GetTileZ(tile) != z

   216

	);

   217

   218

	flotr.tile = tile;

   219

	return flotr;

   220

}

   221

   222

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

   223

   224

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

   225

{

   226

	FindLengthOfTunnelResult flotr;

   227

	TPFSetTileBit(tpf, tile, 14);

   228

	flotr = FindLengthOfTunnel(tile, direction);

   229

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

   230

	TPFSetTileBit(tpf, flotr.tile, 14);

   231

	return flotr.tile;

   232

}

   233

   234

const byte _ffb_64[128] = {

   235

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

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

   240

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

   241

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

   242

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

   243

   244

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

   245

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

   246

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

   247

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

   248

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

   249

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

   250

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

   251

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

   252

};

   253

   254

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

   255

{

   256

	uint bits;

   257

	int i;

   258

	RememberData rd;

   259

	TileIndex tile_org = tile;

   260

   261

	if (IsTileType(tile, MP_TUNNEL)) {

   262

		if (GetTunnelDirection(tile) != direction ||

   263

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

   264

			return;

   265

		}

   266

		tile = SkipToEndOfTunnel(tpf, tile, direction);

   267

	}

   268

   269

	if (IsTileType(tile, MP_STREET_BRIDGE) || IsTileType(tile, MP_RAILWAY_BRIDGE)) {

   270

		TileIndex tile_end;

   271

		if (GetBridgeRampDirection(tile) != direction ||

   272

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

   273

			return;

   274

		}

   275

		//fprintf(stderr, "%s: Planning over bridge\n", __func__);

   276

		// TODO doesn't work - WHAT doesn't work?

   277

		TPFSetTileBit(tpf, tile, 14);

   278

		tile_end = GetOtherBridgeEnd(tile);

   279

		tpf->rd.cur_length += DistanceManhattan(tile, tile_end);

   280

		tile = tile_end;

   281

		TPFSetTileBit(tpf, tile, 14);

   282

	}

   283

	tile += TileOffsByDiagDir(direction);

   284

   285

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

   286

	if (tpf->tracktype == TRANSPORT_RAIL) {

   287

		// don't enter train depot from the back

   288

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

   289

   290

		if (IsTileType(tile_org, MP_RAILWAY) || IsTileType(tile_org, MP_STATION) || IsTileType(tile_org, MP_TUNNEL) || IsTileType(tile_org, MP_RAILWAY_BRIDGE))

   291

			if (IsTileType(tile, MP_RAILWAY) || IsTileType(tile, MP_STATION) || IsTileType(tile, MP_TUNNEL) || IsTileType(tile, MP_RAILWAY_BRIDGE))

   292

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

   293

	}

   294

   295

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

   296

	if (tpf->tracktype == TRANSPORT_ROAD) {

   297

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

   298

		// don't enter road stop from the back

   299

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

   300

		// don't enter road depot from the back

   301

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

   302

	}

   303

   304

	tpf->rd.cur_length++;

   305

   306

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

   307

   308

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

   309

		bits &= _tpfmode1_and[direction];

   310

		bits = bits | (bits>>8);

   311

	}

   312

	bits &= 0xBF;

   313

   314

	if (bits != 0) {

   315

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

   316

			do {

   317

				i = FIND_FIRST_BIT(bits);

   318

				bits = KILL_FIRST_BIT(bits);

   319

   320

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

   321

				rd = tpf->rd;

   322

   323

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

   324

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

   325

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

   326

				}

   327

				tpf->rd = rd;

   328

			} while (bits != 0);

   329

		}

   330

	}

   331

   332

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

   333

	 * seems to go in 2 directions simultaneously */

   334

   335

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

   336

	 * stack space dramatically. */

   337

   338

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

   339

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

   340

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

   341

	if (tpf->hasbit_13)

   342

		return;

   343

   344

	tile = tile_org;

   345

	direction = ReverseDiagDir(direction);

   346

   347

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

   348

	bits |= (bits >> 8);

   349

   350

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

   351

		bits &= _bits_mask[direction];

   352

	}

   353

   354

	bits &= 0xBF;

   355

	if (bits == 0)

   356

		return;

   357

   358

	do {

   359

		i = FIND_FIRST_BIT(bits);

   360

		bits = KILL_FIRST_BIT(bits);

   361

   362

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

   363

		rd = tpf->rd;

   364

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

   365

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

   366

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

   367

		}

   368

		tpf->rd = rd;

   369

	} while (bits != 0);

   370

}

   371

   372

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

   373

{

   374

	TrackPathFinder tpf;

   375

   376

	assert(direction < 4);

   377

   378

	/* initialize path finder variables */

   379

	tpf.userdata = data;

   380

	tpf.enum_proc = enum_proc;

   381

	tpf.new_link = tpf.links;

   382

	tpf.num_links_left = lengthof(tpf.links);

   383

   384

	tpf.rd.cur_length = 0;

   385

	tpf.rd.depth = 0;

   386

	tpf.rd.pft_var6 = 0;

   387

   388

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

   389

   390

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

   391

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

   392

   393

   394

	tpf.tracktype = (byte)flags;

   395

   396

	if (HASBIT(flags, 11)) {

   397

		tpf.rd.pft_var6 = 0xFF;

   398

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

   399

		TPFMode2(&tpf, tile, direction);

   400

	} else {

   401

		/* clear the hash_heads */

   402

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

   403

		TPFMode1(&tpf, tile, direction);

   404

	}

   405

   406

	if (after_proc != NULL)

   407

		after_proc(&tpf);

   408

}

   409

   410

typedef struct {

   411

	TileIndex tile;

   412

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

   413

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

   414

	byte track;

   415

	byte depth;

   416

	byte state;

   417

	byte first_track;

   418

} StackedItem;

   419

   420

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

   421

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

   422

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

   423

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

   424

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

   425

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

   426

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

   427

};

   428

   429

typedef struct HashLink {

   430

	TileIndex tile;

   431

	uint16 typelength;

   432

	uint16 next;

   433

} HashLink;

   434

   435

typedef struct {

   436

	NTPEnumProc *enum_proc;

   437

	void *userdata;

   438

	TileIndex dest;

   439

   440

	TransportType tracktype;

   441

	RailTypeMask railtypes;

   442

	uint maxlength;

   443

   444

	HashLink *new_link;

   445

	uint num_links_left;

   446

   447

	uint nstack;

   448

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

   449

   450

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

   451

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

   452

   453

	HashLink links[0x400]; // hash links

   454

   455

} NewTrackPathFinder;

   456

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

   457

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

   458

   459

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

   460

   461

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

   462

// move it down to the proper position

   463

static inline void HeapifyUp(NewTrackPathFinder *tpf)

   464

{

   465

	StackedItem si;

   466

	int i = ++tpf->nstack;

   467

   468

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

   469

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

   470

		// swap the child item and the parent item.

   471

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

   472

		i>>=1;

   473

	}

   474

}

   475

   476

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

   477

static inline void HeapifyDown(NewTrackPathFinder *tpf)

   478

{

   479

	StackedItem si;

   480

	int i = 1, j;

   481

	int n;

   482

   483

	assert(tpf->nstack > 0);

   484

	n = --tpf->nstack;

   485

   486

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

   487

   488

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

   489

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

   490

   491

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

   492

		// figure out which is smaller of the children.

   493

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

   494

			j++; // right item is smaller

   495

   496

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

   497

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

   498

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

   499

   500

		// swap parent with the child

   501

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

   502

		i = j;

   503

	}

   504

}

   505

   506

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