truelight@0: #include "stdafx.h"
truelight@0: #include "ttd.h"
truelight@0: #include "pathfind.h"
truelight@0: 
truelight@0: // remember which tiles we have already visited so we don't visit them again.
truelight@0: static bool TPFSetTileBit(TrackPathFinder *tpf, uint tile, int dir)
truelight@0: {
truelight@0: 	uint hash, val, offs;
truelight@0: 	TrackPathFinderLink *link, *new_link;
truelight@0: 	uint bits = 1 << dir;
truelight@0: 
truelight@0: 	if (tpf->disable_tile_hash)
truelight@0: 		return true;
truelight@0: 
truelight@0: 	hash = PATHFIND_HASH_TILE(tile);
truelight@0: 
truelight@0: 	val = tpf->hash_head[hash];
truelight@0: 
truelight@0: 	if (val == 0) {
truelight@0: 		/* unused hash entry, set the appropriate bit in it and return true
truelight@0: 		 * to indicate that a bit was set. */
truelight@0: 		tpf->hash_head[hash] = bits;
truelight@0: 		tpf->hash_tile[hash] = (TileIndex)tile;
truelight@0: 		return true;
truelight@0: 	} else if (!(val & 0x8000)) {
truelight@0: 		/* single tile */
truelight@0: 
truelight@0: 		if ( (TileIndex)tile == tpf->hash_tile[hash] ) {
truelight@0: 			/* found another bit for the same tile,
truelight@0: 			 * check if this bit is already set, if so, return false */
truelight@0: 			if (val & bits)
truelight@0: 				return false;
truelight@0: 
truelight@0: 			/* otherwise set the bit and return true to indicate that the bit
truelight@0: 			 * was set */
truelight@0: 			tpf->hash_head[hash] = val | bits;
truelight@0: 			return true;
truelight@0: 		} else {
truelight@0: 			/* two tiles with the same hash, need to make a link */
truelight@193: 
truelight@0: 			/* allocate a link. if out of links, handle this by returning
truelight@0: 			 * that a tile was already visisted. */
truelight@0: 			if (tpf->num_links_left == 0)
truelight@0: 				return false;
truelight@0: 			tpf->num_links_left--;
truelight@0: 			link = tpf->new_link++;
truelight@0: 
truelight@0: 			/* move the data that was previously in the hash_??? variables
truelight@0: 			 * to the link struct, and let the hash variables point to the link */
truelight@0: 			link->tile = tpf->hash_tile[hash];
truelight@0: 			tpf->hash_tile[hash] = PATHFIND_GET_LINK_OFFS(tpf, link);
truelight@0: 
truelight@0: 			link->flags = tpf->hash_head[hash];
truelight@193: 			tpf->hash_head[hash] = 0xFFFF; /* multi link */
truelight@0: 
truelight@0: 			link->next = 0xFFFF;
truelight@0: 		}
truelight@0: 	} else {
truelight@0: 		/* a linked list of many tiles,
truelight@0: 		 * find the one corresponding to the tile, if it exists.
truelight@0: 		 * otherwise make a new link */
truelight@193: 
truelight@0: 		offs = tpf->hash_tile[hash];
truelight@0: 		do {
truelight@0: 			link = PATHFIND_GET_LINK_PTR(tpf, offs);
truelight@0: 			if ( (TileIndex)tile == link->tile) {
truelight@0: 				/* found the tile in the link list,
truelight@0: 				 * check if the bit was alrady set, if so return false to indicate that the
truelight@0: 				 * bit was already set */
truelight@0: 				if (link->flags & bits)
truelight@0: 					return false;
truelight@0: 				link->flags |= bits;
truelight@0: 				return true;
truelight@0: 			}
truelight@0: 		} while ((offs=link->next) != 0xFFFF);
truelight@0: 	}
truelight@193: 
truelight@0: 	/* get here if we need to add a new link to link,
truelight@0: 	 * first, allocate a new link, in the same way as before */
truelight@0: 	if (tpf->num_links_left == 0)
truelight@0: 			return false;
truelight@0: 	tpf->num_links_left--;
truelight@0: 	new_link = tpf->new_link++;
truelight@0: 
truelight@0: 	/* then fill the link with the new info, and establish a ptr from the old
truelight@0: 	 * link to the new one */
truelight@0: 	new_link->tile = (TileIndex)tile;
truelight@0: 	new_link->flags = bits;
truelight@0: 	new_link->next = 0xFFFF;
truelight@0: 
truelight@0: 	link->next = PATHFIND_GET_LINK_OFFS(tpf, new_link);
truelight@0: 	return true;
truelight@0: }
truelight@0: 
truelight@0: static const byte _bits_mask[4] = {
truelight@0: 	0x19,
truelight@0: 	0x16,
truelight@0: 	0x25,
truelight@0: 	0x2A,
truelight@0: };
truelight@0: 
truelight@0: static const byte _tpf_new_direction[14] = {
truelight@0: 	0,1,0,1,2,1, 0,0,
truelight@0: 	2,3,3,2,3,0,
truelight@0: };
truelight@0: 
truelight@0: static const byte _tpf_prev_direction[14] = {
truelight@0: 	0,1,1,0,1,2, 0,0,
truelight@0: 	2,3,2,3,0,3,
truelight@0: };
truelight@0: 
truelight@0: 
truelight@0: static const byte _otherdir_mask[4] = {
truelight@0: 	0x10,
truelight@0: 	0,
truelight@0: 	0x5,
truelight@0: 	0x2A,
truelight@0: };
truelight@0: 
truelight@0: #ifdef DEBUG_TILE_PUSH
truelight@0: extern void dbg_push_tile(uint tile, int track);
truelight@0: extern void dbg_pop_tile();
truelight@0: #endif
truelight@0: 
truelight@0: void TPFMode2(TrackPathFinder *tpf, uint tile, int direction)
truelight@0: {
truelight@0: 	uint bits;
truelight@0: 	int i;
truelight@0: 	RememberData rd;
truelight@0: 
truelight@0: 	// This addition will sometimes overflow by a single tile.
truelight@0: 	// The use of TILE_MASK here makes sure that we still point at a valid
truelight@193: 	// tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail.
truelight@0: 	tile = TILE_MASK(tile + _tileoffs_by_dir[direction]);
truelight@0: 
truelight@0: 	if (++tpf->rd.cur_length > 50)
truelight@0: 		return;
truelight@193: 
truelight@0: 	bits = GetTileTrackStatus(tile, tpf->tracktype);
truelight@0: 	bits = (byte)((bits | (bits >> 8)) & _bits_mask[direction]);
truelight@0: 	if (bits == 0)
truelight@0: 		return;
truelight@0: 
truelight@0: 	assert(GET_TILE_X(tile) != 255 && GET_TILE_Y(tile) != 255);
truelight@0: 
truelight@0: 	if ( (bits & (bits - 1)) == 0 ) {
truelight@0: 		/* only one direction */
truelight@0: 		i = 0;
truelight@0: 		while (!(bits&1))
truelight@0: 			i++, bits>>=1;
truelight@0: 
truelight@0: 		rd = tpf->rd;
truelight@0: 		goto continue_here;
truelight@0: 	}
truelight@0: 	/* several directions */
truelight@0: 	i=0;
truelight@0: 	do {
truelight@0: 		if (!(bits & 1)) continue;
truelight@0: 		rd = tpf->rd;
truelight@0: 
truelight@0: 		// Change direction 4 times only
truelight@0: 		if ((byte)i != tpf->rd.pft_var6) {
truelight@0: 			if(++tpf->rd.depth > 4) {
truelight@193: 				tpf->rd = rd;
truelight@0: 				return;
truelight@0: 			}
truelight@0: 			tpf->rd.pft_var6 = (byte)i;
truelight@0: 		}
truelight@0: 
truelight@0: continue_here:;
truelight@0: 		tpf->the_dir = HASBIT(_otherdir_mask[direction],i) ? (i+8) : i;
truelight@193: 
truelight@0: #ifdef DEBUG_TILE_PUSH
truelight@0: 		dbg_push_tile(tile, tpf->the_dir);
truelight@0: #endif
truelight@0: 		if (!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, NULL)) {
truelight@0: 			TPFMode2(tpf, tile, _tpf_new_direction[tpf->the_dir]);
truelight@0: 		}
truelight@0: #ifdef DEBUG_TILE_PUSH
truelight@0: 		dbg_pop_tile();
truelight@0: #endif
truelight@0: 
truelight@0: 		tpf->rd = rd;
truelight@0: 	} while (++i, bits>>=1);
truelight@0: 
truelight@0: }
truelight@0: 
truelight@0: static const int8 _get_tunlen_inc[5] = { -16, 0, 16, 0, -16 };
truelight@0: 
darkvater@22: /* Returns the end tile and the length of a tunnel. The length does not
darkvater@22:  * include the starting tile (entry), it does include the end tile (exit).
darkvater@22:  */
truelight@159: FindLengthOfTunnelResult FindLengthOfTunnel(uint tile, int direction)
truelight@0: {
truelight@0: 	FindLengthOfTunnelResult flotr;
truelight@0: 	int x,y;
truelight@0: 	byte z;
truelight@0: 
truelight@0: 	flotr.length = 0;
truelight@0: 
truelight@0: 	x = GET_TILE_X(tile) * 16;
truelight@0: 	y = GET_TILE_Y(tile) * 16;
truelight@0: 
truelight@0: 	z = GetSlopeZ(x+8, y+8);
truelight@0: 
truelight@0: 	for(;;) {
truelight@0: 		flotr.length++;
truelight@0: 
truelight@0: 		x += _get_tunlen_inc[direction];
truelight@0: 		y += _get_tunlen_inc[direction+1];
truelight@0: 
truelight@0: 		tile = TILE_FROM_XY(x,y);
truelight@0: 
truelight@0: 		if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) &&
darkvater@241: 				(_map5[tile] & 0xF0) == 0 &&					// tunnel entrance/exit
darkvater@241: 				//((_map5[tile]>>2)&3) == type &&		// rail/road-tunnel <-- This is not necesary to check, right?
darkvater@241: 				((_map5[tile] & 3)^2) == direction &&	// entrance towards: 0 = NE, 1 = SE, 2 = SW, 3 = NW
truelight@0: 				GetSlopeZ(x+8, y+8) == z)
truelight@0: 					break;
truelight@0: 	}
truelight@0: 
truelight@0: 	flotr.tile = tile;
truelight@0: 	return flotr;
truelight@0: }
truelight@0: 
truelight@0: static const uint16 _tpfmode1_and[4] = { 0x1009, 0x16, 0x520, 0x2A00 };
truelight@0: 
truelight@0: static uint SkipToEndOfTunnel(TrackPathFinder *tpf, uint tile, int direction) {
truelight@0: 	FindLengthOfTunnelResult flotr;
truelight@0: 	TPFSetTileBit(tpf, tile, 14);
truelight@159: 	flotr = FindLengthOfTunnel(tile, direction);
truelight@0: 	tpf->rd.cur_length += flotr.length;
truelight@0: 	TPFSetTileBit(tpf, flotr.tile, 14);
truelight@0: 	return flotr.tile;
truelight@0: }
truelight@0: 
truelight@0: const byte _ffb_64[128] = {
truelight@0: 0,0,1,0,2,0,1,0,
truelight@0: 3,0,1,0,2,0,1,0,
truelight@0: 4,0,1,0,2,0,1,0,
truelight@0: 3,0,1,0,2,0,1,0,
truelight@0: 5,0,1,0,2,0,1,0,
truelight@0: 3,0,1,0,2,0,1,0,
truelight@0: 4,0,1,0,2,0,1,0,
truelight@0: 3,0,1,0,2,0,1,0,
truelight@0: 
truelight@0: 0,0,0,2,0,4,4,6,
truelight@0: 0,8,8,10,8,12,12,14,
truelight@0: 0,16,16,18,16,20,20,22,
truelight@0: 16,24,24,26,24,28,28,30,
truelight@0: 0,32,32,34,32,36,36,38,
truelight@0: 32,40,40,42,40,44,44,46,
truelight@0: 32,48,48,50,48,52,52,54,
truelight@0: 48,56,56,58,56,60,60,62,
truelight@0: };
truelight@0: 
truelight@0: void TPFMode1(TrackPathFinder *tpf, uint tile, int direction)
truelight@0: {
truelight@0: 	uint bits;
truelight@0: 	int i;
truelight@0: 	RememberData rd;
truelight@0: 	uint tile_org = tile;
truelight@0: 
truelight@0: 	if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0)==0) {
darkvater@241: 		if ((_map5[tile] & 3) != direction || ((_map5[tile]>>2)&3) != tpf->tracktype)
truelight@0: 			return;
truelight@193: 		tile = SkipToEndOfTunnel(tpf, tile, direction);
truelight@0: 	}
truelight@0: 	tile += _tileoffs_by_dir[direction];
truelight@0: 	tpf->rd.cur_length++;
truelight@0: 
truelight@0: 	bits = GetTileTrackStatus(tile, tpf->tracktype);
truelight@0: 
truelight@0: 	if ((byte)bits != tpf->var2) {
truelight@0: 		bits &= _tpfmode1_and[direction];
truelight@0: 		bits = bits | (bits>>8);
truelight@0: 	}
truelight@0: 	bits &= 0xBF;
truelight@0: 
truelight@0: 	if (bits != 0) {
truelight@0: 		if (!tpf->disable_tile_hash || (tpf->rd.cur_length <= 64 && (KILL_FIRST_BIT(bits) == 0 || ++tpf->rd.depth <= 7))) {
truelight@0: 			do {
truelight@0: 				i = FIND_FIRST_BIT(bits);
truelight@0: 				bits = KILL_FIRST_BIT(bits);
truelight@0: 
truelight@0: 				tpf->the_dir = (_otherdir_mask[direction] & (byte)(1 << i)) ? (i+8) : i;
truelight@0: 				rd = tpf->rd;
truelight@193: 
truelight@0: #ifdef DEBUG_TILE_PUSH
truelight@0: 		dbg_push_tile(tile, tpf->the_dir);
truelight@0: #endif
truelight@0: 				if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&
truelight@0: 						!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, &tpf->rd.pft_var6) ) {
truelight@0: 					TPFMode1(tpf, tile, _tpf_new_direction[tpf->the_dir]);
truelight@0: 				}
truelight@0: #ifdef DEBUG_TILE_PUSH
truelight@0: 		dbg_pop_tile();
truelight@0: #endif
truelight@0: 				tpf->rd = rd;
truelight@0: 			} while (bits != 0);
truelight@0: 		}
truelight@0: 	}
truelight@0: 
truelight@0: 	/* the next is only used when signals are checked.
truelight@0: 	 * seems to go in 2 directions simultaneously */
truelight@193: 
truelight@0: 	/* if i can get rid of this, tail end recursion can be used to minimize
truelight@193: 	 * stack space dramatically. */
truelight@0: 	if (tpf->hasbit_13)
truelight@0: 		return;
truelight@193: 
truelight@0: 	tile = tile_org;
truelight@0: 	direction ^= 2;
truelight@0: 
truelight@0: 	bits = GetTileTrackStatus(tile, tpf->tracktype);
truelight@0: 	bits |= (bits >> 8);
truelight@0: 
truelight@0: 	if ( (byte)bits != tpf->var2) {
truelight@0: 		bits &= _bits_mask[direction];
truelight@0: 	}
truelight@0: 
truelight@0: 	bits &= 0xBF;
truelight@0: 	if (bits == 0)
truelight@0: 		return;
truelight@0: 
truelight@0: 	do {
truelight@0: 		i = FIND_FIRST_BIT(bits);
truelight@0: 		bits = KILL_FIRST_BIT(bits);
truelight@193: 
truelight@0: 		tpf->the_dir = (_otherdir_mask[direction] & (byte)(1 << i)) ? (i+8) : i;
truelight@0: 		rd = tpf->rd;
truelight@0: 		if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&
truelight@0: 				!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, &tpf->rd.pft_var6) ) {
truelight@0: 			TPFMode1(tpf, tile, _tpf_new_direction[tpf->the_dir]);
truelight@0: 		}
truelight@0: 		tpf->rd = rd;
truelight@0: 	} while (bits != 0);
truelight@0: }
truelight@0: 
truelight@0: void FollowTrack(uint tile, uint16 flags, byte direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data)
truelight@0: {
darkvater@318: 	TrackPathFinder tpf;
truelight@0: 
truelight@0: 	assert(direction < 4);
truelight@0: 
truelight@193: 	/* initialize path finder variables */
darkvater@318: 	tpf.userdata = data;
darkvater@318: 	tpf.enum_proc = enum_proc;
darkvater@318: 	tpf.new_link = tpf.links;
darkvater@318: 	tpf.num_links_left = lengthof(tpf.links);
truelight@0: 
darkvater@318: 	tpf.rd.cur_length = 0;
darkvater@318: 	tpf.rd.depth = 0;
darkvater@318: 	tpf.rd.pft_var6 = 0;
truelight@193: 
darkvater@318: 	tpf.var2 = HASBIT(flags, 15) ? 0x43 : 0xFF; /* 0x8000 */
truelight@0: 
darkvater@318: 	tpf.disable_tile_hash = HASBIT(flags, 12) != 0;     /* 0x1000 */
darkvater@318: 	tpf.hasbit_13 = HASBIT(flags, 13) != 0;		 /* 0x2000 */
truelight@0: 
truelight@0: 
darkvater@318: 	tpf.tracktype = (byte)flags;
truelight@0: 
truelight@193: 	if (HASBIT(flags, 11)) {
darkvater@318: 		tpf.rd.pft_var6 = 0xFF;
darkvater@318: 		tpf.enum_proc(tile, data, 0, 0, 0);
darkvater@318: 		TPFMode2(&tpf, tile, direction);
truelight@0: 	} else {
truelight@0: 		/* clear the hash_heads */
darkvater@318: 		memset(tpf.hash_head, 0, sizeof(tpf.hash_head));
darkvater@318: 		TPFMode1(&tpf, tile, direction);
truelight@0: 	}
truelight@0: 
truelight@0: 	if (after_proc != NULL)
darkvater@318: 		after_proc(&tpf);
truelight@0: }
truelight@0: 
truelight@0: typedef struct {
truelight@0: 	TileIndex tile;
truelight@0: 	uint16 cur_length;
truelight@0: 	byte track;
truelight@0: 	byte depth;
truelight@0: 	byte state;
truelight@0: 	byte first_track;
truelight@0: } StackedItem;
truelight@0: 
truelight@0: static const byte _new_dir[6][4] = {
truelight@0: {0,0xff,2,0xff,},
truelight@0: {0xff,1,0xff,3,},
truelight@0: {0xff,0,3,0xff,},
truelight@0: {1,0xff,0xff,2,},
truelight@0: {3,2,0xff,0xff,},
truelight@0: {0xff,0xff,1,0,},
truelight@0: };
truelight@0: 
truelight@0: static const byte _new_track[6][4] = {
truelight@0: {0,0xff,8,0xff,},
truelight@0: {0xff,1,0xff,9,},
truelight@0: {0xff,2,10,0xff,},
truelight@0: {3,0xff,0xff,11,},
truelight@0: {12,4,0xff,0xff,},
truelight@0: {0xff,0xff,5,13,},
truelight@0: };
truelight@0: 
truelight@0: typedef struct HashLink {
truelight@0: 	TileIndex tile;
truelight@0: 	uint16 typelength;
truelight@0: 	uint16 next;
truelight@0: } HashLink;
truelight@0: 
truelight@0: typedef struct {
truelight@0: 	TPFEnumProc *enum_proc;
truelight@0: 	void *userdata;
truelight@0: 
truelight@0: 	byte tracktype;
truelight@0: 	uint maxlength;
truelight@0: 
truelight@0: 	HashLink *new_link;
truelight@0: 	uint num_links_left;
truelight@0: 
truelight@0: 	int nstack;
truelight@0: 	StackedItem stack[256]; // priority queue of stacked items
truelight@0: 
truelight@0: 	uint16 hash_head[0x400]; // hash heads. 0 means unused. 0xFFC0 = length, 0x3F = type
truelight@0: 	TileIndex hash_tile[0x400]; // tiles. or links.
truelight@0: 
truelight@0: 	HashLink links[0x400]; // hash links
truelight@0: 
truelight@0: } NewTrackPathFinder;
truelight@0: #define NTP_GET_LINK_OFFS(tpf, link) ((byte*)(link) - (byte*)tpf->links)
truelight@0: #define NTP_GET_LINK_PTR(tpf, link_offs) (HashLink*)((byte*)tpf->links + (link_offs))
truelight@0: 
truelight@0: #define ARR(i) tpf->stack[(i)-1]
truelight@0: 
truelight@0: // called after a new element was added in the queue at the last index.
truelight@0: // move it down to the proper position
truelight@0: static void INLINE HeapifyUp(NewTrackPathFinder *tpf)
truelight@0: {
truelight@0: 	StackedItem si;
truelight@0: 	int i = ++tpf->nstack;
truelight@193: 
truelight@0: 	while (i != 1 && ARR(i).cur_length < ARR(i>>1).cur_length) {
truelight@0: 		// the child element is larger than the parent item.
truelight@193: 		// swap the child item and the parent item.
truelight@0: 		si = ARR(i); ARR(i) = ARR(i>>1); ARR(i>>1) = si;
truelight@0: 		i>>=1;
truelight@0: 	}
truelight@0: }
truelight@0: 
truelight@0: // called after the element 0 was eaten. fill it with a new element
truelight@0: static void INLINE HeapifyDown(NewTrackPathFinder *tpf)
truelight@0: {
truelight@0: 	StackedItem si;
truelight@0: 	int i = 1, j;
truelight@0: 	int n = --tpf->nstack;
truelight@0: 
truelight@0: 	if (n == 0) return; // heap is empty so nothing to do?
truelight@0: 
truelight@0: 	// copy the last item to index 0. we use it as base for heapify.
truelight@0: 	ARR(1) = ARR(n+1);
truelight@0: 
truelight@0: 	while ((j=i*2) <= n) {
truelight@0: 		// figure out which is smaller of the children.
truelight@193: 		if (j != n && ARR(j).cur_length > ARR(j+1).cur_length)
truelight@0: 			j++; // right item is smaller
truelight@0: 
truelight@0: 		assert(i <= n && j <= n);
truelight@0: 		if (ARR(i).cur_length <= ARR(j).cur_length)
truelight@0: 			break; // base elem smaller than smallest, done!
truelight@193: 
truelight@0: 		// swap parent with the child
truelight@0: 		si = ARR(i); ARR(i) = ARR(j); ARR(j) = si;
truelight@0: 		i = j;
truelight@0: 	}
truelight@0: }
truelight@0: 
truelight@0: // mark a tile as visited and store the length of the path.
truelight@0: // if we already had a better path to this tile, return false.
truelight@0: // otherwise return true.
truelight@0: static bool NtpVisit(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)
truelight@0: {
truelight@0: 	uint hash,head;
truelight@0: 	HashLink *link, *new_link;
truelight@0: 
truelight@0: 	assert(length < 1024);
truelight@193: 
truelight@0: 	hash = PATHFIND_HASH_TILE(tile);
truelight@0: 
truelight@0: 	// never visited before?
truelight@0: 	if ((head=tpf->hash_head[hash]) == 0) {
truelight@0: 		tpf->hash_tile[hash] = tile;
truelight@0: 		tpf->hash_head[hash] = dir | (length << 2);
truelight@0: 		return true;
truelight@0: 	}
truelight@0: 
truelight@0: 	if (head != 0xffff) {
truelight@0: 		if ( (TileIndex)tile == tpf->hash_tile[hash] && (head & 0x3) == dir ) {
truelight@193: 
truelight@0: 			// longer length
truelight@0: 			if (length >= (head >> 2)) return false;
truelight@193: 
truelight@0: 			tpf->hash_head[hash] = dir | (length << 2);
truelight@0: 			return true;
truelight@0: 		}
truelight@0: 		// two tiles with the same hash, need to make a link
truelight@0: 		// allocate a link. if out of links, handle this by returning
truelight@0: 		// that a tile was already visisted.
truelight@0: 		if (tpf->num_links_left == 0)
truelight@0: 			return false;
truelight@0: 		tpf->num_links_left--;
truelight@0: 		link = tpf->new_link++;
truelight@0: 
truelight@0: 		/* move the data that was previously in the hash_??? variables
truelight@0: 		 * to the link struct, and let the hash variables point to the link */
truelight@0: 		link->tile = tpf->hash_tile[hash];
truelight@0: 		tpf->hash_tile[hash] = NTP_GET_LINK_OFFS(tpf, link);
truelight@0: 
truelight@0: 		link->typelength = tpf->hash_head[hash];
truelight@193: 		tpf->hash_head[hash] = 0xFFFF; /* multi link */
truelight@0: 		link->next = 0xFFFF;
truelight@0: 	} else {
truelight@0: 		// a linked list of many tiles,
truelight@0: 		// find the one corresponding to the tile, if it exists.
truelight@0: 		// otherwise make a new link
truelight@193: 
truelight@0: 		uint offs = tpf->hash_tile[hash];
truelight@0: 		do {
truelight@0: 			link = NTP_GET_LINK_PTR(tpf, offs);
truelight@0: 			if ( (TileIndex)tile == link->tile && (uint)(link->typelength & 0x3) == dir) {
truelight@0: 				if (length >= (uint)(link->typelength >> 2)) return false;
truelight@0: 				link->typelength = dir | (length << 2);
truelight@0: 				return true;
truelight@0: 			}
truelight@0: 		} while ((offs=link->next) != 0xFFFF);
truelight@0: 	}
truelight@193: 
truelight@0: 	/* get here if we need to add a new link to link,
truelight@0: 	 * first, allocate a new link, in the same way as before */
truelight@0: 	if (tpf->num_links_left == 0)
truelight@0: 			return false;
truelight@0: 	tpf->num_links_left--;
truelight@0: 	new_link = tpf->new_link++;
truelight@0: 
truelight@0: 	/* then fill the link with the new info, and establish a ptr from the old
truelight@0: 	 * link to the new one */
truelight@0: 	new_link->tile = (TileIndex)tile;
truelight@0: 	new_link->typelength = dir | (length << 2);
truelight@0: 	new_link->next = 0xFFFF;
truelight@0: 
truelight@0: 	link->next = NTP_GET_LINK_OFFS(tpf, new_link);
truelight@0: 	return true;
truelight@0: }
truelight@0: 
truelight@0: static bool NtpCheck(NewTrackPathFinder *tpf, uint tile, uint dir, uint length)
truelight@0: {
truelight@0: 	uint hash,head,offs;
truelight@0: 	HashLink *link;
truelight@0: 
truelight@0: 	hash = PATHFIND_HASH_TILE(tile);
truelight@0: 	head=tpf->hash_head[hash];
truelight@0: 	assert(head);
truelight@0: 
truelight@0: 	if (head != 0xffff) {
truelight@0: 		assert( tpf->hash_tile[hash] == tile && (head & 3) == dir);
truelight@0: 		assert( (head >> 2) <= length);
truelight@0: 		return length == (head >> 2);
truelight@0: 	}
truelight@0: 
truelight@0: 	// else it's a linked list of many tiles
truelight@0: 	offs = tpf->hash_tile[hash];
truelight@0: 	for(;;) {
truelight@0: 		link = NTP_GET_LINK_PTR(tpf, offs);
truelight@0: 		if ( (TileIndex)tile == link->tile && (uint)(link->typelength & 0x3) == dir) {
truelight@0: 			assert( (uint)(link->typelength >> 2) <= length);
truelight@0: 			return length == (uint)(link->typelength >> 2);
truelight@0: 		}
truelight@0: 		offs = link->next;
truelight@0: 		assert(offs != 0xffff);
truelight@0: 	}
truelight@0: }
truelight@0: 
truelight@0: 
truelight@0: // new more optimized pathfinder for trains...
truelight@0: void NTPEnum(NewTrackPathFinder *tpf, uint tile, uint direction)
truelight@0: {
truelight@0: 	uint bits, tile_org;
truelight@0: 	int i;
truelight@0: 	StackedItem si;
truelight@0: 	FindLengthOfTunnelResult flotr;
truelight@0: 
truelight@0: 	si.cur_length = 0;
truelight@0: 	si.depth = 0;
truelight@0: 	si.state = 0;
truelight@0: 
truelight@0: restart:
truelight@0: 	if (IS_TILETYPE(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0)==0) {
truelight@148: 		/* This is a tunnel tile */
truelight@148: 		if ( (uint)(_map5[tile] & 3) != (direction ^ 2)) { /* ^ 2 is reversing the direction */
truelight@148: 			/* We are not just driving out of the tunnel */
truelight@148: 			if ( (uint)(_map5[tile] & 3) != direction || ((_map5[tile]>>1)&6) != tpf->tracktype)
truelight@148: 				/* We are not driving into the tunnel, or it
truelight@148: 				 * is an invalid tunnel */
truelight@0: 				goto popnext;
truelight@159: 			flotr = FindLengthOfTunnel(tile, direction);
truelight@148: 			si.cur_length += flotr.length;
truelight@148: 			tile = flotr.tile;
truelight@148: 		}
truelight@0: 	}
truelight@0: 
truelight@0: 	// remember the start tile so we know if we're in an inf loop.
truelight@0: 	tile_org = tile;
truelight@0: 
truelight@0: 	for(;;) {
truelight@0: 		tile += _tileoffs_by_dir[direction];
truelight@193: 
truelight@0: 		// too long search length? bail out.
truelight@0: 		if (++si.cur_length >= tpf->maxlength)
truelight@0: 			goto popnext;
truelight@0: 
truelight@0: 		// not a regular rail tile?
truelight@0: 		if (!IS_TILETYPE(tile, MP_RAILWAY) || (bits = _map5[tile]) & 0xC0) {
truelight@159: 			bits = GetTileTrackStatus(tile, TRANSPORT_RAIL) & _tpfmode1_and[direction];
truelight@0: 			bits = (bits | (bits >> 8)) & 0x3F;
truelight@0: 			break;
truelight@0: 		}
truelight@0: 
truelight@0: 		// regular rail tile, determine the tracks that are actually reachable.
truelight@0: 		bits &= _bits_mask[direction];
truelight@0: 		if (bits == 0) goto popnext; // no tracks there? stop searching.
truelight@193: 
truelight@0: 		// complex tile?, let the generic handler handle that..
truelight@0: 		if (KILL_FIRST_BIT(bits) != 0) break;
truelight@0: 
truelight@0: 		// don't bother calling the callback when we have regular tracks only.
truelight@0: 		// it's usually not needed anyway. that will speed up things.
truelight@0: 		direction = _new_dir[FIND_FIRST_BIT(bits)][direction];
truelight@0: 		assert(direction != 0xFF);
truelight@0: 		if (tile == tile_org) goto popnext; // detect infinite loop..
truelight@0: 	}
truelight@0: 
truelight@0: 	if (!bits) goto popnext;
truelight@0: 
truelight@0: 	// if only one reachable track, use tail recursion optimization.
truelight@0: 	if (KILL_FIRST_BIT(bits) == 0) {
truelight@0: 		i = _new_track[FIND_FIRST_BIT(bits)][direction];
truelight@0: 		// call the callback
truelight@0: 		if (tpf->enum_proc(tile, tpf->userdata, i, si.cur_length, &si.state))
truelight@0: 			goto popnext; // we should stop searching in this direction.
truelight@0: 
truelight@0: 		// we should continue searching. determine new direction.
truelight@0: 		direction = _tpf_new_direction[i];
truelight@0: 		goto restart; // use tail recursion optimization.
truelight@0: 	}
truelight@0: 
truelight@0: 	// too high recursion depth.. bail out..
truelight@0: 	if (si.depth >= _patches.pf_maxdepth)
truelight@0: 		goto popnext;
truelight@193: 
truelight@0: 	si.depth++; // increase recursion depth.
truelight@0: 
truelight@0: 	// see if this tile was already visited..?
truelight@0: 	if (NtpVisit(tpf, tile, direction, si.cur_length)) {
truelight@193: 		// push all possible alternatives
truelight@0: 		si.tile = tile;
truelight@0: 		do {
truelight@0: 			si.track = _new_track[FIND_FIRST_BIT(bits)][direction];
truelight@193: 
truelight@0: 			// out of stack items, bail out?
truelight@0: 			if (tpf->nstack >= lengthof(tpf->stack))
truelight@0: 				break;
truelight@0: 			tpf->stack[tpf->nstack] = si;
truelight@0: 			HeapifyUp(tpf);
truelight@0: 		} while ((bits = KILL_FIRST_BIT(bits)) != 0);
truelight@0: 
truelight@0: 		// if this is the first recursion step, we need to fill the first_track member.
truelight@0: 		// so the code outside knows which path is better.
truelight@0: 		// also randomize the order in which we search through them.
truelight@0: 		if (si.depth == 1) {
truelight@0: 			uint32 r = Random();
truelight@193: 			assert(tpf->nstack == 2 || tpf->nstack == 3);
truelight@193: 			if (r&1) swap_byte(&tpf->stack[0].track, &tpf->stack[1].track);
truelight@0: 			if (tpf->nstack != 2) {
truelight@0: 				byte t = tpf->stack[2].track;
truelight@193: 				if (r&2) swap_byte(&tpf->stack[0].track, &t);
truelight@0: 				if (r&4) swap_byte(&tpf->stack[1].track, &t);
truelight@0: 				tpf->stack[2].first_track = tpf->stack[2].track = t;
truelight@0: 			}
truelight@0: 			tpf->stack[0].first_track = tpf->stack[0].track;
truelight@0: 			tpf->stack[1].first_track = tpf->stack[1].track;
truelight@0: 		}
truelight@0: 	}
truelight@0: 
truelight@0: popnext:
truelight@0: 	// where to continue.
truelight@0: 	do {
truelight@0: 		if (tpf->nstack == 0) return; // nothing left?
truelight@0: 		si = tpf->stack[0];
truelight@0: 		tile = si.tile;
truelight@0: 		HeapifyDown(tpf);
truelight@0: 	} while (
truelight@0: 		!NtpCheck(tpf, tile, _tpf_prev_direction[si.track], si.cur_length) || // already have better path to that tile?
truelight@0: 		tpf->enum_proc(tile, tpf->userdata, si.track, si.cur_length, &si.state)
truelight@0: 	);
truelight@193: 
truelight@0: 	direction = _tpf_new_direction[si.track];
truelight@0: 	goto restart;
truelight@0: }
truelight@0: 
truelight@0: 
truelight@0: // new pathfinder for trains. better and faster.
truelight@0: void NewTrainPathfind(uint tile, byte direction, TPFEnumProc *enum_proc, void *data, byte *cache)
truelight@0: {
truelight@0: 	if (!_patches.new_pathfinding) {
truelight@159: 		FollowTrack(tile, 0x3000 | TRANSPORT_RAIL, direction, enum_proc, NULL, data);
truelight@0: 	} else {
darkvater@318: 		NewTrackPathFinder tpf;
darkvater@318: 		tpf.userdata = data;
darkvater@318: 		tpf.enum_proc = enum_proc;
darkvater@318: 		tpf.tracktype = 0;
darkvater@318: 		tpf.maxlength = _patches.pf_maxlength;
darkvater@318: 		tpf.nstack = 0;
darkvater@318: 		tpf.new_link = tpf.links;
darkvater@318: 		tpf.num_links_left = lengthof(tpf.links);
darkvater@318: 		memset(tpf.hash_head, 0, sizeof(tpf.hash_head));
truelight@0: 
darkvater@318: 		NTPEnum(&tpf, tile, direction);
truelight@0: 	}
truelight@0: }
truelight@0: