1 #include "stdafx.h"

     2 #include "ttd.h"

     3 #include "pathfind.h"

     4 

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

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

     7 {

     8 	uint hash, val, offs;

     9 	TrackPathFinderLink *link, *new_link;

    10 	uint bits = 1 << dir;

    11 

    12 	if (tpf->disable_tile_hash)

    13 		return true;

    14 

    15 	hash = PATHFIND_HASH_TILE(tile);

    16 

    17 	val = tpf->hash_head[hash];

    18 

    19 	if (val == 0) {

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

    21 		 * to indicate that a bit was set. */

    22 		tpf->hash_head[hash] = bits;

    23 		tpf->hash_tile[hash] = (TileIndex)tile;

    24 		return true;

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

    26 		/* single tile */

    27 

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

    29 			/* found another bit for the same tile,

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

    31 			if (val & bits)

    32 				return false;

    33 

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

    35 			 * was set */

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

    37 			return true;

    38 		} else {

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

    40 			

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

    42 			 * that a tile was already visisted. */

    43 			if (tpf->num_links_left == 0)

    44 				return false;

    45 			tpf->num_links_left--;

    46 			link = tpf->new_link++;

    47 

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

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

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

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

    52 

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

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

    55 

    56 			link->next = 0xFFFF;

    57 		}

    58 	} else {

    59 		/* a linked list of many tiles,

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

    61 		 * otherwise make a new link */

    62 		

    63 		offs = tpf->hash_tile[hash];

    64 		do {

    65 			link = PATHFIND_GET_LINK_PTR(tpf, offs);

    66 			if ( (TileIndex)tile == link->tile) {

    67 				/* found the tile in the link list,

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

    69 				 * bit was already set */

    70 				if (link->flags & bits)

    71 					return false;

    72 				link->flags |= bits;

    73 				return true;

    74 			}

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

    76 	}

    77 	

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

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

    80 	if (tpf->num_links_left == 0)

    81 			return false;

    82 	tpf->num_links_left--;

    83 	new_link = tpf->new_link++;

    84 

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

    86 	 * link to the new one */

    87 	new_link->tile = (TileIndex)tile;

    88 	new_link->flags = bits;

    89 	new_link->next = 0xFFFF;

    90 

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

    92 	return true;

    93 }

    94 

    95 static const byte _bits_mask[4] = {

    96 	0x19,

    97 	0x16,

    98 	0x25,

    99 	0x2A,

   100 };

   101 

   102 static const byte _tpf_new_direction[14] = {

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

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

   105 };

   106 

   107 static const byte _tpf_prev_direction[14] = {

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

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

   110 };

   111 

   112 

   113 static const byte _otherdir_mask[4] = {

   114 	0x10,

   115 	0,

   116 	0x5,

   117 	0x2A,

   118 };

   119 

   120 #ifdef DEBUG_TILE_PUSH

   121 extern void dbg_push_tile(uint tile, int track);

   122 extern void dbg_pop_tile();

   123 #endif

   124 

   125 void TPFMode2(TrackPathFinder *tpf, uint tile, int direction)

   126 {

   127 	uint bits;

   128 	int i;

   129 	RememberData rd;

   130 

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

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

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

   134 	tile = TILE_MASK(tile + _tileoffs_by_dir[direction]);

   135 

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

   137 		return;

   138 	

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

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

   141 	if (bits == 0)

   142 		return;

   143 

   144 	assert(GET_TILE_X(tile) != 255 && GET_TILE_Y(tile) != 255);

   145 

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

   147 		/* only one direction */

   148 		i = 0;

   149 		while (!(bits&1))

   150 			i++, bits>>=1;

   151 

   152 		rd = tpf->rd;

   153 		goto continue_here;

   154 	}

   155 	/* several directions */

   156 	i=0;

   157 	do {

   158 		if (!(bits & 1)) continue;

   159 		rd = tpf->rd;

   160 

   161 		// Change direction 4 times only

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

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

   164 				tpf->rd = rd;		

   165 				return;

   166 			}

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

   168 		}

   169 

   170 continue_here:;

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

   172 		

   173 #ifdef DEBUG_TILE_PUSH

   174 		dbg_push_tile(tile, tpf->the_dir);

   175 #endif

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

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

   178 		}

   179 #ifdef DEBUG_TILE_PUSH

   180 		dbg_pop_tile();

   181 #endif

   182 

   183 		tpf->rd = rd;

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

   185 

   186 }

   187 

   188 static const int8 _get_tunlen_inc[5] = { -16, 0, 16, 0, -16 };

   189 

   190 FindLengthOfTunnelResult FindLengthOfTunnel(uint tile, int direction, byte type)

   191 {

   192 	FindLengthOfTunnelResult flotr;

   193 	int x,y;

   194 	byte z;

   195 

   196 	flotr.length = 0;

   197 

   198 	x = GET_TILE_X(tile) * 16;

   199 	y = GET_TILE_Y(tile) * 16;

   200 

   201 	z = GetSlopeZ(x+8, y+8);

   202 

   203 	for(;;) {

   204 		flotr.length++;

   205 

   206 		x += _get_tunlen_inc[direction];

   207 		y += _get_tunlen_inc[direction+1];

   208 

   209 		tile = TILE_FROM_XY(x,y);

   210 

   211 		if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) &&

   212 				(_map5[tile] & 0xF0) == 0 &&

   213 				((_map5[tile]>>1)&6) == type &&

   214 				((_map5[tile] & 3)^2) == direction &&

   215 				GetSlopeZ(x+8, y+8) == z)

   216 					break;

   217 	}

   218 

   219 	flotr.tile = tile;

   220 	return flotr;

   221 }

   222 

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

   224 

   225 static uint SkipToEndOfTunnel(TrackPathFinder *tpf, uint tile, int direction) {

   226 	FindLengthOfTunnelResult flotr;

   227 	TPFSetTileBit(tpf, tile, 14);

   228 	flotr = FindLengthOfTunnel(tile, direction, tpf->tracktype);

   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 void TPFMode1(TrackPathFinder *tpf, uint tile, int direction)

   255 {

   256 	uint bits;

   257 	int i;

   258 	RememberData rd;

   259 	uint tile_org = tile;

   260 

   261 	if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0)==0) {

   262 		if ((_map5[tile] & 3) != direction || ((_map5[tile]>>1)&6) != tpf->tracktype)

   263 			return;

   264 		tile = SkipToEndOfTunnel(tpf, tile, direction);		

   265 	}

   266 	tile += _tileoffs_by_dir[direction];

   267 	tpf->rd.cur_length++;

   268 

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

   270 

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

   272 		bits &= _tpfmode1_and[direction];

   273 		bits = bits | (bits>>8);

   274 	}

   275 	bits &= 0xBF;

   276 

   277 	if (bits != 0) {

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

   279 			do {

   280 				i = FIND_FIRST_BIT(bits);

   281 				bits = KILL_FIRST_BIT(bits);

   282 

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

   284 				rd = tpf->rd;

   285 				

   286 #ifdef DEBUG_TILE_PUSH

   287 		dbg_push_tile(tile, tpf->the_dir);

   288 #endif

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

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

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

   292 				}

   293 #ifdef DEBUG_TILE_PUSH

   294 		dbg_pop_tile();

   295 #endif

   296 				tpf->rd = rd;

   297 			} while (bits != 0);

   298 		}

   299 	}

   300 

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

   302 	 * seems to go in 2 directions simultaneously */

   303 	 

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

   305 	 * stack space dramatically. */	

   306 	if (tpf->hasbit_13)

   307 		return;

   308 	

   309 	tile = tile_org;

   310 	direction ^= 2;

   311 

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

   313 	bits |= (bits >> 8);

   314 

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

   316 		bits &= _bits_mask[direction];

   317 	}

   318 

   319 	bits &= 0xBF;

   320 	if (bits == 0)

   321 		return;

   322 

   323 	do {

   324 		i = FIND_FIRST_BIT(bits);

   325 		bits = KILL_FIRST_BIT(bits);

   326 		

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

   328 		rd = tpf->rd;

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

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

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

   332 		}

   333 		tpf->rd = rd;

   334 	} while (bits != 0);

   335 }

   336 

   337 void FollowTrack(uint tile, uint16 flags, byte direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data)

   338 {

   339 	TrackPathFinder *tpf = alloca(sizeof(TrackPathFinder));

   340 

   341 	assert(direction < 4);

   342 

   343 	/* initialize path finder variables */	

   344 	tpf->userdata = data;

   345 	tpf->enum_proc = enum_proc;	

   346 	tpf->new_link = tpf->links;

   347 	tpf->num_links_left = 0x400;

   348 

   349 	tpf->rd.cur_length = 0;

   350 	tpf->rd.depth = 0;

   351 	tpf->rd.pft_var6 = 0;

   352 	

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

   354 

   355 	tpf->disable_tile_hash = HASBIT(flags, 12) != 0;     /* 0x1000 */

   356 	tpf->hasbit_13 = HASBIT(flags, 13) != 0;		 /* 0x2000 */

   357 

   358 

   359 	tpf->tracktype = (byte)flags;

   360 

   361 	if (HASBIT(flags, 11)) {	

   362 		tpf->rd.pft_var6 = 0xFF;

   363 		tpf->enum_proc(tile, data, 0, 0, 0);

   364 		TPFMode2(tpf, tile, direction);	

   365 	} else {

   366 		/* clear the hash_heads */

   367 		memset(tpf->hash_head, 0, sizeof(tpf->hash_head));

   368 		TPFMode1(tpf, tile, direction);

   369 	}

   370 

   371 	if (after_proc != NULL)

   372 		after_proc(tpf);	

   373 }

   374 

   375 typedef struct {

   376 	TileIndex tile;

   377 	uint16 cur_length;

   378 	byte track;

   379 	byte depth;

   380 	byte state;

   381 	byte first_track;

   382 } StackedItem;

   383 

   384 static const byte _new_dir[6][4] = {

   385 {0,0xff,2,0xff,},

   386 {0xff,1,0xff,3,},

   387 {0xff,0,3,0xff,},

   388 {1,0xff,0xff,2,},

   389 {3,2,0xff,0xff,},

   390 {0xff,0xff,1,0,},

   391 };

   392 

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

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

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

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

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

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

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

   400 };

   401 

   402 typedef struct HashLink {

   403 	TileIndex tile;

   404 	uint16 typelength;

   405 	uint16 next;

   406 } HashLink;

   407 

   408 typedef struct {

   409 	TPFEnumProc *enum_proc;

   410 	void *userdata;

   411 

   412 	byte tracktype;

   413 	uint maxlength;

   414 

   415 	HashLink *new_link;

   416 	uint num_links_left;

   417 

   418 	int nstack;

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

   420 

   421 	uint16 hash_head[0x400]; // hash heads. 0 means unused. 0xFFC0 = length, 0x3F = type

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

   423 

   424 	HashLink links[0x400]; // hash links

   425 

   426 } NewTrackPathFinder;

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

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

   429 

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

   431 

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

   433 // move it down to the proper position

   434 static void INLINE HeapifyUp(NewTrackPathFinder *tpf)

   435 {

   436 	StackedItem si;

   437 	int i = ++tpf->nstack;

   438 	

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

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

   441 		// swap the child item and the parent item. 

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

   443 		i>>=1;

   444 	}

   445 }

   446 

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

   448 static void INLINE HeapifyDown(NewTrackPathFinder *tpf)

   449 {

   450 	StackedItem si;

   451 	int i = 1, j;

   452 	int n = --tpf->nstack;

   453 

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

   455 

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

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

   458 

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

   460 		// figure out which is smaller of the children.

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

   462 			j++; // right item is smaller

   463 

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

   465 		if (ARR(i).cur_length <= ARR(j).cur_length)

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

   467 	

   468 		// swap parent with the child

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

   470 		i = j;

   471 	}

   472 }

   473 

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

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

   476 // otherwise return true.

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

   478 {

   479 	uint hash,head;

   480 	HashLink *link, *new_link;

   481 

   482 	assert(length < 1024);

   483 	

   484 	hash = PATHFIND_HASH_TILE(tile);

   485 

   486 	// never visited before?

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

   488 		tpf->hash_tile[hash] = tile;

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

   490 		return true;

   491 	}

   492 

   493 	if (head != 0xffff) {

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

   495 			

   496 			// longer length

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

   498 			

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

   500 			return true;

   501 		}

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

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

   504 		// that a tile was already visisted.

   505 		if (tpf->num_links_left == 0)

   506 			return false;

   507 		tpf->num_links_left--;

   508 		link = tpf->new_link++;

   509 

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

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

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

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

   514 

   515 		link->typelength = tpf->hash_head[hash];

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

   517 		link->next = 0xFFFF;

   518 	} else {

   519 		// a linked list of many tiles,

   520 		// find the one corresponding to the tile, if it exists.

   521 		// otherwise make a new link

   522 		

   523 		uint offs = tpf->hash_tile[hash];

   524 		do {

   525 			link = NTP_GET_LINK_PTR(tpf, offs);

   526 			if ( (TileIndex)tile == link->tile && (uint)(link->typelength & 0x3) == dir) {

   527 				if (length >= (uint)(link->typelength >> 2)) return false;

   528 				link->typelength = dir | (length << 2);

   529 				return true;

   530 			}

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

   532 	}

   533 	

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

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

   536 	if (tpf->num_links_left == 0)

   537 			return false;

   538 	tpf->num_links_left--;

   539 	new_link = tpf->new_link++;

   540 

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

   542 	 * link to the new one */

   543 	new_link->tile = (TileIndex)tile;

   544 	new_link->typelength = dir | (length << 2);

   545 	new_link->next = 0xFFFF;

   546 

   547 	link->next = NTP_GET_LINK_OFFS(tpf, new_link);

   548 	return true;

   549 }

   550 

   551 static bool NtpCheck(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)

   552 {

   553 	uint hash,head,offs;

   554 	HashLink *link;

   555 

   556 	hash = PATHFIND_HASH_TILE(tile);

   557 	head=tpf->hash_head[hash];

   558 	assert(head);

   559 

   560 	if (head != 0xffff) {

   561 		assert( tpf->hash_tile[hash] == tile && (head & 3) == dir);

   562 		assert( (head >> 2) <= length);

   563 		return length == (head >> 2);

   564 	}

   565 

   566 	// else it's a linked list of many tiles

   567 	offs = tpf->hash_tile[hash];

   568 	for(;;) {

   569 		link = NTP_GET_LINK_PTR(tpf, offs);

   570 		if ( (TileIndex)tile == link->tile && (uint)(link->typelength & 0x3) == dir) {

   571 			assert( (uint)(link->typelength >> 2) <= length);

   572 			return length == (uint)(link->typelength >> 2);

   573 		}

   574 		offs = link->next;

   575 		assert(offs != 0xffff);

   576 	}

   577 }

   578 

   579 

   580 // new more optimized pathfinder for trains...

   581 void NTPEnum(NewTrackPathFinder *tpf, uint tile, uint direction)

   582 {

   583 	uint bits, tile_org;

   584 	int i;

   585 	StackedItem si;

   586 	FindLengthOfTunnelResult flotr;

   587 

   588 	si.cur_length = 0;

   589 	si.depth = 0;

   590 	si.state = 0;

   591 

   592 restart:

   593 	if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0)==0) {

   594 		if ( (uint)(_map5[tile] & 3) != direction || ((_map5[tile]>>1)&6) != tpf->tracktype)

   595 				goto popnext;

   596 		flotr = FindLengthOfTunnel(tile, direction, tpf->tracktype);

   597 		si.cur_length += flotr.length;

   598 		tile = flotr.tile;

   599 	}

   600 

   601 	// remember the start tile so we know if we're in an inf loop.

   602 	tile_org = tile;

   603 

   604 	for(;;) {

   605 		tile += _tileoffs_by_dir[direction];

   606 		

   607 		// too long search length? bail out.

   608 		if (++si.cur_length >= tpf->maxlength)

   609 			goto popnext;

   610 

   611 		// not a regular rail tile?

   612 		if (!IS_TILETYPE(tile, MP_RAILWAY) || (bits = _map5[tile]) & 0xC0) {

   613 			bits = GetTileTrackStatus(tile, 0) & _tpfmode1_and[direction];

   614 			bits = (bits | (bits >> 8)) & 0x3F;

   615 			break;

   616 		}

   617 

   618 		// regular rail tile, determine the tracks that are actually reachable.

   619 		bits &= _bits_mask[direction];

   620 		if (bits == 0) goto popnext; // no tracks there? stop searching.

   621 		

   622 		// complex tile?, let the generic handler handle that..

   623 		if (KILL_FIRST_BIT(bits) != 0) break;

   624 

   625 		// don't bother calling the callback when we have regular tracks only.

   626 		// it's usually not needed anyway. that will speed up things.

   627 		direction = _new_dir[FIND_FIRST_BIT(bits)][direction];

   628 		assert(direction != 0xFF);

   629 		if (tile == tile_org) goto popnext; // detect infinite loop..

   630 	}

   631 

   632 	if (!bits) goto popnext;

   633 

   634 	// if only one reachable track, use tail recursion optimization.

   635 	if (KILL_FIRST_BIT(bits) == 0) {

   636 		i = _new_track[FIND_FIRST_BIT(bits)][direction];

   637 		// call the callback

   638 		if (tpf->enum_proc(tile, tpf->userdata, i, si.cur_length, &si.state))

   639 			goto popnext; // we should stop searching in this direction.

   640 

   641 		// we should continue searching. determine new direction.

   642 		direction = _tpf_new_direction[i];

   643 		goto restart; // use tail recursion optimization.

   644 	}

   645 

   646 	// too high recursion depth.. bail out..

   647 	if (si.depth >= _patches.pf_maxdepth)

   648 		goto popnext;

   649 	

   650 	si.depth++; // increase recursion depth.

   651 

   652 	// see if this tile was already visited..?

   653 	if (NtpVisit(tpf, tile, direction, si.cur_length)) {

   654 		// push all possible alternatives	

   655 		si.tile = tile;

   656 		do {

   657 			si.track = _new_track[FIND_FIRST_BIT(bits)][direction];

   658 			

   659 			// out of stack items, bail out?

   660 			if (tpf->nstack >= lengthof(tpf->stack))

   661 				break;

   662 			tpf->stack[tpf->nstack] = si;

   663 			HeapifyUp(tpf);

   664 		} while ((bits = KILL_FIRST_BIT(bits)) != 0);

   665 

   666 		// if this is the first recursion step, we need to fill the first_track member.

   667 		// so the code outside knows which path is better.

   668 		// also randomize the order in which we search through them.

   669 		if (si.depth == 1) {

   670 			uint32 r = Random();

   671 			assert(tpf->nstack == 2 || tpf->nstack == 3);			

   672 			if (r&1) swap_byte(&tpf->stack[0].track, &tpf->stack[1].track);	

   673 			if (tpf->nstack != 2) {

   674 				byte t = tpf->stack[2].track;

   675 				if (r&2) swap_byte(&tpf->stack[0].track, &t);	

   676 				if (r&4) swap_byte(&tpf->stack[1].track, &t);

   677 				tpf->stack[2].first_track = tpf->stack[2].track = t;

   678 			}

   679 			tpf->stack[0].first_track = tpf->stack[0].track;

   680 			tpf->stack[1].first_track = tpf->stack[1].track;

   681 		}

   682 	}

   683 

   684 popnext:

   685 	// where to continue.

   686 	do {

   687 		if (tpf->nstack == 0) return; // nothing left?

   688 		si = tpf->stack[0];

   689 		tile = si.tile;

   690 		HeapifyDown(tpf);

   691 	} while (

   692 		!NtpCheck(tpf, tile, _tpf_prev_direction[si.track], si.cur_length) || // already have better path to that tile?

   693 		tpf->enum_proc(tile, tpf->userdata, si.track, si.cur_length, &si.state)

   694 	);

   695 	

   696 	direction = _tpf_new_direction[si.track];

   697 	goto restart;

   698 }

   699 

   700 

   701 // new pathfinder for trains. better and faster.

   702 void NewTrainPathfind(uint tile, byte direction, TPFEnumProc *enum_proc, void *data, byte *cache)

   703 {

   704 	if (!_patches.new_pathfinding) {

   705 		FollowTrack(tile, 0x3000, direction, enum_proc, NULL, data);

   706 	} else {

   707 		NewTrackPathFinder *tpf;

   708 

   709 		tpf  = alloca(sizeof(NewTrackPathFinder));

   710 		tpf->userdata = data;

   711 		tpf->enum_proc = enum_proc;	

   712 		tpf->tracktype = 0;

   713 		tpf->maxlength = _patches.pf_maxlength;

   714 		tpf->nstack = 0;

   715 		tpf->new_link = tpf->links;

   716 		tpf->num_links_left = 0x400;

   717 		memset(tpf->hash_head, 0, sizeof(tpf->hash_head));

   718 

   719 		NTPEnum(tpf, tile, direction);

   720 	}

   721 }

   722