tron@2186: /* $Id$ */
tron@2186: 
rubidium@9111: /** @file pathfind.cpp Implementation of the oldest supported pathfinder. */
belugas@6352: 
truelight@0: #include "stdafx.h"
Darkvater@1891: #include "openttd.h"
tron@3234: #include "bridge_map.h"
KUDr@3900: #include "station_map.h"
rubidium@8119: #include "tile_cmd.h"
maedhros@6453: #include "landscape.h"
truelight@0: #include "pathfind.h"
rubidium@8103: #include "rail_type.h"
ludde@2044: #include "debug.h"
tron@3154: #include "tunnel_map.h"
rubidium@8270: #include "settings_type.h"
smatz@8083: #include "tunnelbridge_map.h"
rubidium@8119: #include "core/random_func.hpp"
rubidium@8925: #include "core/alloc_type.hpp"
smatz@8398: #include "tunnelbridge.h"
truelight@0: 
belugas@6352: /* remember which tiles we have already visited so we don't visit them again. */
tron@1977: static bool TPFSetTileBit(TrackPathFinder *tpf, TileIndex 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;
tron@1986: 		tpf->hash_tile[hash] = tile;
truelight@0: 		return true;
truelight@0: 	} else if (!(val & 0x8000)) {
truelight@0: 		/* single tile */
truelight@0: 
tron@1986: 		if (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. */
ludde@2044: 			if (tpf->num_links_left == 0) {
truelight@0: 				return false;
ludde@2044: 			}
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];
belugas@6352: 			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);
tron@1986: 			if (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 */
ludde@2044: 	if (tpf->num_links_left == 0) {
truelight@0: 			return false;
ludde@2044: 	}
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 */
tron@1986: 	new_link->tile = 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: 
frosch@8800: static void TPFModeShip(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
truelight@0: {
rubidium@9490: 	assert(tpf->tracktype == TRANSPORT_WATER);
truelight@747: 
rubidium@9490: 	if (IsTileType(tile, MP_TUNNELBRIDGE)) {
rubidium@9490: 		/* wrong track type */
rubidium@9490: 		if (GetTunnelBridgeTransportType(tile) != tpf->tracktype) return;
rubidium@9490: 
rubidium@9490: 		DiagDirection dir = GetTunnelBridgeDirection(tile);
rubidium@9490: 		/* entering tunnel / bridge? */
rubidium@9490: 		if (dir == direction) {
rubidium@9490: 			TileIndex endtile = GetOtherTunnelBridgeEnd(tile);
rubidium@9490: 
rubidium@9490: 			tpf->rd.cur_length += GetTunnelBridgeLength(tile, endtile) + 1;
rubidium@9490: 
rubidium@9490: 			TPFSetTileBit(tpf, tile, 14);
rubidium@9490: 			TPFSetTileBit(tpf, endtile, 14);
rubidium@9490: 
rubidium@9490: 			tile = endtile;
rubidium@9490: 		} else {
rubidium@9490: 			/* leaving tunnel / bridge? */
rubidium@9490: 			if (ReverseDiagDir(dir) != direction) return;
rubidium@9490: 		}
rubidium@9490: 	}
truelight@0: 
belugas@6352: 	/* This addition will sometimes overflow by a single tile.
belugas@6352: 	 * The use of TILE_MASK here makes sure that we still point at a valid
belugas@6352: 	 * tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail. */
Darkvater@4559: 	tile = TILE_MASK(tile + TileOffsByDiagDir(direction));
truelight@0: 
truelight@0: 	if (++tpf->rd.cur_length > 50)
truelight@0: 		return;
truelight@193: 
frosch@8804: 	TrackBits bits = TrackStatusToTrackBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type)) & DiagdirReachesTracks(direction);
frosch@8611: 	if (bits == TRACK_BIT_NONE) return;
truelight@0: 
tron@926: 	assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY());
truelight@0: 
frosch@8611: 	bool only_one_track = true;
truelight@0: 	do {
frosch@8611: 		Track track = RemoveFirstTrack(&bits);
frosch@8611: 		if (bits != TRACK_BIT_NONE) only_one_track = false;
rubidium@9490: 		RememberData rd = tpf->rd;
truelight@0: 
belugas@6352: 		/* Change direction 4 times only */
frosch@8611: 		if (!only_one_track && track != tpf->rd.last_choosen_track) {
tron@2952: 			if (++tpf->rd.depth > 4) {
truelight@193: 				tpf->rd = rd;
truelight@0: 				return;
truelight@0: 			}
frosch@8611: 			tpf->rd.last_choosen_track = track;
truelight@0: 		}
truelight@0: 
frosch@8804: 		tpf->the_dir = TrackEnterdirToTrackdir(track, direction);
truelight@193: 
frosch@8611: 		if (!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length)) {
frosch@8804: 			TPFModeShip(tpf, tile, TrackdirToExitdir(tpf->the_dir));
truelight@0: 		}
truelight@0: 
truelight@0: 		tpf->rd = rd;
frosch@8611: 	} while (bits != TRACK_BIT_NONE);
truelight@0: 
truelight@0: }
truelight@0: 
smatz@8396: /**
smatz@8396:  * Checks if any vehicle can enter/leave tile in given diagdir
smatz@8396:  * Checks only for rail/road depots and road non-drivethrough stations
smatz@8396:  * @param tile tile to check
smatz@8396:  * @param side side of tile we are trying to leave/enter
smatz@8396:  * @param tracktype type of transport
smatz@8396:  * @pre tile has trackbit at that diagdir
smatz@8396:  * @return true iff vehicle can enter/leve the tile in given side
smatz@8396:  */
smatz@8396: static inline bool CanAccessTileInDir(TileIndex tile, DiagDirection side, TransportType tracktype)
smatz@8396: {
smatz@8396: 	if (tracktype == TRANSPORT_RAIL) {
smatz@8396: 		/* depot from wrong side */
smatz@8961: 		if (IsRailDepotTile(tile) && GetRailDepotDirection(tile) != side) return false;
smatz@8396: 	} else if (tracktype == TRANSPORT_ROAD) {
smatz@8396: 		/* depot from wrong side */
smatz@8961: 		if (IsRoadDepotTile(tile) && GetRoadDepotDirection(tile) != side) return false;
smatz@8396: 		/* non-driverthrough road station from wrong side */
smatz@8396: 		if (IsStandardRoadStopTile(tile) && GetRoadStopDir(tile) != side) return false;
smatz@8396: 	}
smatz@8396: 
smatz@8396: 	return true;
smatz@8396: }
smatz@8396: 
frosch@8800: static void TPFModeNormal(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
smatz@8392: {
smatz@8395: 	const TileIndex tile_org = tile;
truelight@0: 
smatz@8392: 	if (IsTileType(tile, MP_TUNNELBRIDGE)) {
smatz@8395: 		/* wrong track type */
smatz@8395: 		if (GetTunnelBridgeTransportType(tile) != tpf->tracktype) return;
smatz@8395: 
smatz@8395: 		DiagDirection dir = GetTunnelBridgeDirection(tile);
smatz@8395: 		/* entering tunnel / bridge? */
smatz@8395: 		if (dir == direction) {
smatz@8395: 			TileIndex endtile = GetOtherTunnelBridgeEnd(tile);
smatz@8395: 
smatz@8398: 			tpf->rd.cur_length += GetTunnelBridgeLength(tile, endtile) + 1;
smatz@8395: 
smatz@8392: 			TPFSetTileBit(tpf, tile, 14);
smatz@8395: 			TPFSetTileBit(tpf, endtile, 14);
smatz@8395: 
smatz@8395: 			tile = endtile;
smatz@8395: 		} else {
smatz@8395: 			/* leaving tunnel / bridge? */
smatz@8395: 			if (ReverseDiagDir(dir) != direction) return;
smatz@8392: 		}
smatz@8396: 	} else {
smatz@8396: 		/* can we leave tile in this dir? */
smatz@8396: 		if (!CanAccessTileInDir(tile, direction, tpf->tracktype)) return;
smatz@8392: 	}
smatz@8395: 
smatz@8392: 	tile += TileOffsByDiagDir(direction);
smatz@8392: 
smatz@8396: 	/* can we enter tile in this dir? */
smatz@8396: 	if (!CanAccessTileInDir(tile, ReverseDiagDir(direction), tpf->tracktype)) return;
smatz@8396: 
peter1138@5457: 	/* Check if the new tile is a tunnel or bridge head and that the direction
peter1138@5457: 	 * and transport type match */
peter1138@5457: 	if (IsTileType(tile, MP_TUNNELBRIDGE)) {
smatz@8088: 		if (GetTunnelBridgeDirection(tile) != direction ||
smatz@8088: 				GetTunnelBridgeTransportType(tile) != tpf->tracktype) {
smatz@8088: 			return;
peter1138@5457: 		}
peter1138@5457: 	}
peter1138@5457: 
frosch@8804: 	TrackdirBits trackdirbits = TrackStatusToTrackdirBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type));
smatz@8397: 
smatz@8397: 	/* Check in case of rail if the owner is the same */
smatz@8397: 	if (tpf->tracktype == TRANSPORT_RAIL) {
frosch@8804: 		if (trackdirbits != TRACKDIR_BIT_NONE && TrackStatusToTrackdirBits(GetTileTrackStatus(tile_org, TRANSPORT_RAIL, 0)) != TRACKDIR_BIT_NONE) {
smatz@8397: 			if (GetTileOwner(tile_org) != GetTileOwner(tile)) return;
smatz@8397: 		}
smatz@8397: 	}
smatz@8397: 
truelight@0: 	tpf->rd.cur_length++;
truelight@0: 
frosch@8804: 	trackdirbits &= DiagdirReachesTrackdirs(direction);
frosch@8804: 	TrackBits bits = TrackdirBitsToTrackBits(trackdirbits);
truelight@0: 
frosch@8804: 	if (bits != TRACK_BIT_NONE) {
truelight@7833: 		if (!tpf->disable_tile_hash || (tpf->rd.cur_length <= 64 && (KillFirstBit(bits) == 0 || ++tpf->rd.depth <= 7))) {
truelight@0: 			do {
frosch@8804: 				Track track = RemoveFirstTrack(&bits);
truelight@0: 
frosch@8804: 				tpf->the_dir = TrackEnterdirToTrackdir(track, direction);
peter1138@7071: 				RememberData rd = tpf->rd;
truelight@193: 
smatz@8480: 				/* make sure we are not leaving from invalid side */
smatz@8480: 				if (TPFSetTileBit(tpf, tile, tpf->the_dir) && CanAccessTileInDir(tile, TrackdirToExitdir(tpf->the_dir), tpf->tracktype) &&
frosch@8611: 						!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length) ) {
frosch@8804: 					TPFModeNormal(tpf, tile, TrackdirToExitdir(tpf->the_dir));
truelight@0: 				}
truelight@0: 				tpf->rd = rd;
frosch@8804: 			} while (bits != TRACK_BIT_NONE);
truelight@0: 		}
truelight@0: 	}
peter1138@7071: }
peter1138@7071: 
frosch@8800: void FollowTrack(TileIndex tile, PathfindFlags flags, TransportType tt, uint sub_type, DiagDirection direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data)
truelight@0: {
rubidium@8798: 	assert(IsValidDiagDirection(direction));
truelight@0: 
rubidium@8798: 	SmallStackSafeStackAlloc<TrackPathFinder, 1> tpf;
truelight@0: 
truelight@193: 	/* initialize path finder variables */
rubidium@8798: 	tpf->userdata = data;
rubidium@8798: 	tpf->enum_proc = enum_proc;
rubidium@8798: 	tpf->new_link = tpf->links;
rubidium@8798: 	tpf->num_links_left = lengthof(tpf->links);
truelight@0: 
rubidium@8798: 	tpf->rd.cur_length = 0;
rubidium@8798: 	tpf->rd.depth = 0;
rubidium@8798: 	tpf->rd.last_choosen_track = INVALID_TRACK;
truelight@193: 
frosch@8800: 	tpf->disable_tile_hash = (flags & PATHFIND_FLAGS_DISABLE_TILE_HASH) != 0;
truelight@0: 
frosch@8800: 	tpf->tracktype = tt;
rubidium@8798: 	tpf->sub_type = sub_type;
truelight@0: 
frosch@8800: 	if ((flags & PATHFIND_FLAGS_SHIP_MODE) != 0) {
rubidium@8798: 		tpf->enum_proc(tile, data, INVALID_TRACKDIR, 0);
frosch@8800: 		TPFModeShip(tpf, tile, direction);
truelight@0: 	} else {
truelight@0: 		/* clear the hash_heads */
rubidium@8798: 		memset(tpf->hash_head, 0, sizeof(tpf->hash_head));
frosch@8800: 		TPFModeNormal(tpf, tile, direction);
truelight@0: 	}
truelight@0: 
rubidium@8798: 	if (after_proc != NULL) after_proc(tpf);
truelight@0: }
truelight@0: 
rubidium@6248: struct StackedItem {
truelight@0: 	TileIndex tile;
belugas@6352: 	uint16 cur_length; ///< This is the current length to this tile.
belugas@6352: 	uint16 priority;   ///< This is the current length + estimated length to the goal.
rubidium@5587: 	TrackdirByte track;
truelight@0: 	byte depth;
truelight@0: 	byte state;
truelight@0: 	byte first_track;
rubidium@6248: };
truelight@0: 
rubidium@6248: struct HashLink {
truelight@0: 	TileIndex tile;
truelight@0: 	uint16 typelength;
truelight@0: 	uint16 next;
rubidium@6248: };
truelight@0: 
rubidium@6248: struct NewTrackPathFinder {
ludde@2125: 	NTPEnumProc *enum_proc;
truelight@0: 	void *userdata;
ludde@2125: 	TileIndex dest;
truelight@0: 
celestar@3355: 	TransportType tracktype;
rubidium@8236: 	RailTypes railtypes;
truelight@0: 	uint maxlength;
truelight@0: 
truelight@0: 	HashLink *new_link;
truelight@0: 	uint num_links_left;
truelight@0: 
tron@979: 	uint nstack;
belugas@6352: 	StackedItem stack[256];     ///< priority queue of stacked items
truelight@0: 
belugas@6352: 	uint16 hash_head[0x400];    ///< hash heads. 0 means unused. 0xFFFC = length, 0x3 = dir
belugas@6352: 	TileIndex hash_tile[0x400]; ///< tiles. or links.
truelight@0: 
belugas@6352: 	HashLink links[0x400];      ///< hash links
truelight@0: 
rubidium@6248: };
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: 
belugas@6352: /** called after a new element was added in the queue at the last index.
belugas@6352:  * move it down to the proper position */
tron@536: static inline void HeapifyUp(NewTrackPathFinder *tpf)
truelight@0: {
truelight@0: 	StackedItem si;
truelight@0: 	int i = ++tpf->nstack;
truelight@193: 
ludde@2125: 	while (i != 1 && ARR(i).priority < ARR(i>>1).priority) {
belugas@6352: 		/* the child element is larger than the parent item.
belugas@6352: 		 * swap the child item and the parent item. */
belugas@6352: 		si = ARR(i); ARR(i) = ARR(i >> 1); ARR(i >> 1) = si;
belugas@6352: 		i >>= 1;
truelight@0: 	}
truelight@0: }
truelight@0: 
belugas@6352: /** called after the element 0 was eaten. fill it with a new element */
tron@536: static inline void HeapifyDown(NewTrackPathFinder *tpf)
truelight@0: {
truelight@0: 	StackedItem si;
truelight@0: 	int i = 1, j;
tron@979: 	int n;
tron@979: 
tron@979: 	assert(tpf->nstack > 0);
tron@979: 	n = --tpf->nstack;
truelight@0: 
truelight@0: 	if (n == 0) return; // heap is empty so nothing to do?
truelight@0: 
belugas@6352: 	/* copy the last item to index 0. we use it as base for heapify. */
belugas@6352: 	ARR(1) = ARR(n + 1);
truelight@0: 
belugas@6352: 	while ((j = i * 2) <= n) {
belugas@6352: 		/* figure out which is smaller of the children. */
belugas@6352: 		if (j != n && ARR(j).priority > ARR(j + 1).priority)
truelight@0: 			j++; // right item is smaller
truelight@0: 
truelight@0: 		assert(i <= n && j <= n);
ludde@2125: 		if (ARR(i).priority <= ARR(j).priority)
truelight@0: 			break; // base elem smaller than smallest, done!
truelight@193: 
belugas@6352: 		/* 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: 
belugas@6352: /** mark a tile as visited and store the length of the path.
belugas@6352:  * if we already had a better path to this tile, return false.
belugas@6352:  * otherwise return true. */
tron@3153: static bool NtpVisit(NewTrackPathFinder* tpf, TileIndex tile, DiagDirection dir, uint length)
truelight@0: {
truelight@0: 	uint hash,head;
truelight@0: 	HashLink *link, *new_link;
truelight@0: 
ludde@2044: 	assert(length < 16384-1);
truelight@193: 
truelight@0: 	hash = PATHFIND_HASH_TILE(tile);
truelight@0: 
belugas@6352: 	/* 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) {
rubidium@5587: 		if (tile == tpf->hash_tile[hash] && (head & 0x3) == (uint)dir) {
truelight@193: 
belugas@6352: 			/* 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: 		}
belugas@6352: 		/* two tiles with the same hash, need to make a link
belugas@6352: 		 * allocate a link. if out of links, handle this by returning
belugas@6352: 		 * that a tile was already visisted. */
ludde@2125: 		if (tpf->num_links_left == 0) {
Darkvater@5380: 			DEBUG(ntp, 1, "No links left");
truelight@0: 			return false;
ludde@2125: 		}
ludde@2125: 
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];
belugas@6352: 		tpf->hash_head[hash] = 0xFFFF; // multi link
truelight@0: 		link->next = 0xFFFF;
truelight@0: 	} else {
belugas@6352: 		/* a linked list of many tiles,
belugas@6352: 		 * find the one corresponding to the tile, if it exists.
belugas@6352: 		 * 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);
rubidium@5587: 			if (tile == link->tile && (link->typelength & 0x3U) == (uint)dir) {
truelight@3019: 				if (length >= (uint)(link->typelength >> 2)) return false;
truelight@0: 				link->typelength = dir | (length << 2);
truelight@0: 				return true;
truelight@0: 			}
tron@3017: 		} 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 */
ludde@2125: 	if (tpf->num_links_left == 0) {
Darkvater@5380: 		DEBUG(ntp, 1, "No links left");
ludde@2125: 		return false;
ludde@2125: 	}
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 */
tron@1986: 	new_link->tile = 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: 
matthijs@2782: /**
matthijs@2782:  * Checks if the shortest path to the given tile/dir so far is still the given
matthijs@2782:  * length.
matthijs@2782:  * @return true if the length is still the same
matthijs@2782:  * @pre    The given tile/dir combination should be present in the hash, by a
matthijs@2782:  *         previous call to NtpVisit().
matthijs@2782:  */
tron@1977: static bool NtpCheck(NewTrackPathFinder *tpf, TileIndex 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: 
belugas@6352: 	/* else it's a linked list of many tiles */
truelight@0: 	offs = tpf->hash_tile[hash];
tron@2952: 	for (;;) {
truelight@0: 		link = NTP_GET_LINK_PTR(tpf, offs);
tron@3017: 		if (tile == link->tile && (link->typelength & 0x3U) == dir) {
truelight@3019: 			assert((uint)(link->typelength >> 2) <= length);
truelight@3019: 			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: 
ludde@2125: static uint DistanceMoo(TileIndex t0, TileIndex t1)
ludde@2125: {
skidd13@7970: 	const uint dx = Delta(TileX(t0), TileX(t1));
skidd13@7970: 	const uint dy = Delta(TileY(t0), TileY(t1));
ludde@2125: 
belugas@6352: 	const uint straightTracks = 2 * min(dx, dy); // The number of straight (not full length) tracks
ludde@2125: 	/* OPTIMISATION:
ludde@2125: 	 * Original: diagTracks = max(dx, dy) - min(dx,dy);
ludde@2125: 	 * Proof:
ludde@2125: 	 * (dx-dy) - straightTracks  == (min + max) - straightTracks = min + // max - 2 * min = max - min */
belugas@6352: 	const uint diagTracks = dx + dy - straightTracks; // The number of diagonal (full tile length) tracks.
ludde@2125: 
ludde@2125: 	return diagTracks*DIAG_FACTOR + straightTracks*STR_FACTOR;
ludde@2125: }
ludde@2125: 
belugas@6352: /* These has to be small cause the max length of a track
belugas@6352:  * is currently limited to 16384 */
ludde@2125: 
ludde@2125: static const byte _length_of_track[16] = {
rubidium@4344: 	DIAG_FACTOR, DIAG_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, 0, 0,
rubidium@4344: 	DIAG_FACTOR, DIAG_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, 0, 0
ludde@2125: };
ludde@2125: 
belugas@6352: /* new more optimized pathfinder for trains...
belugas@6352:  * Tile is the tile the train is at.
belugas@6352:  * direction is the tile the train is moving towards. */
ludde@2125: 
tron@3153: static void NTPEnum(NewTrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
truelight@0: {
matthijs@2782: 	TrackBits bits, allbits;
rubidium@5587: 	Trackdir track;
matthijs@2782: 	TileIndex tile_org;
truelight@0: 	StackedItem si;
ludde@2125: 	int estimation;
truelight@0: 
ludde@2261: 
ludde@2136: 
belugas@6352: 	/* Need to have a special case for the start.
belugas@6352: 	 * We shouldn't call the callback for the current tile. */
ludde@2125: 	si.cur_length = 1; // Need to start at 1 cause 0 is a reserved value.
truelight@0: 	si.depth = 0;
truelight@0: 	si.state = 0;
ludde@2136: 	si.first_track = 0xFF;
ludde@2125: 	goto start_at;
truelight@0: 
tron@2952: 	for (;;) {
belugas@6352: 		/* Get the next item to search from from the priority queue */
ludde@2125: 		do {
ludde@2125: 			if (tpf->nstack == 0)
ludde@2125: 				return; // nothing left? then we're done!
ludde@2125: 			si = tpf->stack[0];
ludde@2125: 			tile = si.tile;
truelight@0: 
ludde@2125: 			HeapifyDown(tpf);
belugas@6352: 			/* Make sure we havn't already visited this tile. */
frosch@8804: 		} while (!NtpCheck(tpf, tile, ReverseDiagDir(TrackdirToExitdir(ReverseTrackdir(si.track))), si.cur_length));
truelight@0: 
belugas@6352: 		/* Add the length of this track. */
ludde@2125: 		si.cur_length += _length_of_track[si.track];
truelight@193: 
ludde@2125: callback_and_continue:
ludde@2125: 		if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length))
ludde@2125: 			return;
truelight@0: 
ludde@2136: 		assert(si.track <= 13);
frosch@8804: 		direction = TrackdirToExitdir(si.track);
ludde@2044: 
ludde@2125: start_at:
belugas@6352: 		/* If the tile is the entry tile of a tunnel, and we're not going out of the tunnel,
belugas@6352: 		 *   need to find the exit of the tunnel. */
celestar@5385: 		if (IsTileType(tile, MP_TUNNELBRIDGE)) {
smatz@8682: 			if (GetTunnelBridgeDirection(tile) != ReverseDiagDir(direction)) {
smatz@8682: 				/* We are not just driving out of the tunnel/bridge */
smatz@8682: 				if (GetTunnelBridgeDirection(tile) != direction ||
smatz@8682: 						GetTunnelBridgeTransportType(tile) != tpf->tracktype) {
smatz@8682: 					/* We are not driving into the tunnel/bridge, or it is an invalid tunnel/bridge */
smatz@8682: 					continue;
smatz@8682: 				}
smatz@8682: 				if (!HasBit(tpf->railtypes, GetRailType(tile))) {
smatz@8682: 					bits = TRACK_BIT_NONE;
smatz@8682: 					break;
smatz@8682: 				}
smatz@8398: 
smatz@8682: 				TileIndex endtile = GetOtherTunnelBridgeEnd(tile);
smatz@8682: 				si.cur_length += DIAG_FACTOR * (GetTunnelBridgeLength(tile, endtile) + 1);
smatz@8682: 				tile = endtile;
smatz@8682: 				/* tile now points to the exit tile of the tunnel/bridge */
ludde@2125: 			}
ludde@2044: 		}
ludde@2044: 
belugas@6352: 		/* This is a special loop used to go through
belugas@6352: 		 * a rail net and find the first intersection */
ludde@2125: 		tile_org = tile;
tron@2952: 		for (;;) {
ludde@2136: 			assert(direction <= 3);
Darkvater@4559: 			tile += TileOffsByDiagDir(direction);
ludde@2044: 
belugas@6352: 			/* too long search length? bail out. */
ludde@2125: 			if (si.cur_length >= tpf->maxlength) {
Darkvater@5380: 				DEBUG(ntp, 1, "Cur_length too big");
rubidium@5587: 				bits = TRACK_BIT_NONE;
ludde@2125: 				break;
ludde@2044: 			}
ludde@2044: 
belugas@6352: 			/* Not a regular rail tile?
belugas@6352: 			 * Then we can't use the code below, but revert to more general code. */
ludde@2125: 			if (!IsTileType(tile, MP_RAILWAY) || !IsPlainRailTile(tile)) {
belugas@6352: 				/* We found a tile which is not a normal railway tile.
belugas@6352: 				 * Determine which tracks that exist on this tile. */
frosch@8804: 				bits = TrackdirBitsToTrackBits(TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)) & DiagdirReachesTrackdirs(direction));
ludde@2125: 
belugas@6352: 				/* Check that the tile contains exactly one track */
truelight@7833: 				if (bits == 0 || KillFirstBit(bits) != 0) break;
ludde@2125: 
skidd13@7928: 				if (!HasBit(tpf->railtypes, GetRailType(tile))) {
rubidium@5587: 					bits = TRACK_BIT_NONE;
celestar@5385: 					break;
celestar@3804: 				}
celestar@3804: 
belugas@6352: 				/*******************
belugas@6352: 				 * If we reach here, the tile has exactly one track.
belugas@6352: 				 *   tile - index to a tile that is not rail tile, but still straight (with optional signals)
belugas@6352: 				 *   bits - bitmask of which track that exist on the tile (exactly one bit is set)
belugas@6352: 				 *   direction - which direction are we moving in?
belugas@6352: 				 *******************/
frosch@8804: 				si.track = TrackEnterdirToTrackdir(FindFirstTrack(bits), direction);
ludde@2125: 				si.cur_length += _length_of_track[si.track];
ludde@2125: 				goto callback_and_continue;
ludde@2125: 			}
ludde@2125: 
matthijs@2782: 			/* Regular rail tile, determine which tracks exist. */
tron@3267: 			allbits = GetTrackBits(tile);
matthijs@2782: 			/* Which tracks are reachable? */
matthijs@2782: 			bits = allbits & DiagdirReachesTracks(direction);
ludde@2125: 
matthijs@2782: 			/* The tile has no reachable tracks => End of rail segment
matthijs@2782: 			 * or Intersection => End of rail segment. We check this agains all the
matthijs@2782: 			 * bits, not just reachable ones, to prevent infinite loops. */
rubidium@5587: 			if (bits == TRACK_BIT_NONE || TracksOverlap(allbits)) break;
ludde@2137: 
skidd13@7928: 			if (!HasBit(tpf->railtypes, GetRailType(tile))) {
rubidium@5587: 				bits = TRACK_BIT_NONE;
celestar@3355: 				break;
celestar@3355: 			}
celestar@3355: 
matthijs@2782: 			/* If we reach here, the tile has exactly one track, and this
rubidium@6491: 			 track is reachable = > Rail segment continues */
ludde@2125: 
frosch@8804: 			track = TrackEnterdirToTrackdir(FindFirstTrack(bits), direction);
rubidium@5587: 			assert(track != INVALID_TRACKDIR);
ludde@2137: 
ludde@2125: 			si.cur_length += _length_of_track[track];
ludde@2125: 
frosch@8653: 			/* Check if this rail is an upwards slope. If it is, then add a penalty. */
frosch@8653: 			if (IsDiagonalTrackdir(track) && IsUphillTrackdir(GetTileSlope(tile, NULL), track)) {
ludde@2125: 				// upwards slope. add some penalty.
belugas@6352: 				si.cur_length += 4 * DIAG_FACTOR;
ludde@2125: 			}
ludde@2125: 
belugas@6352: 			/* railway tile with signals..? */
ludde@2125: 			if (HasSignals(tile)) {
glx@4631: 				if (!HasSignalOnTrackdir(tile, track)) {
belugas@6352: 					/* if one way signal not pointing towards us, stop going in this direction => End of rail segment. */
rubidium@9792: 					if (HasSignalOnTrackdir(tile, ReverseTrackdir(track)) && IsOnewaySignal(tile, TrackdirToTrack(track))) {
rubidium@5587: 						bits = TRACK_BIT_NONE;
ludde@2125: 						break;
ludde@2125: 					}
glx@4631: 				} else if (GetSignalStateByTrackdir(tile, track) == SIGNAL_STATE_GREEN) {
belugas@6352: 					/* green signal in our direction. either one way or two way. */
ludde@2125: 					si.state |= 3;
ludde@2125: 				} else {
belugas@6352: 					/* reached a red signal. */
glx@4631: 					if (HasSignalOnTrackdir(tile, ReverseTrackdir(track))) {
belugas@6352: 						/* two way red signal. unless we passed another green signal on the way,
belugas@6352: 						 * stop going in this direction => End of rail segment.
belugas@6352: 						 * this is to prevent us from going into a full platform. */
belugas@6352: 						if (!(si.state & 1)) {
rubidium@5587: 							bits = TRACK_BIT_NONE;
ludde@2125: 							break;
ludde@2125: 						}
ludde@2125: 					}
ludde@2125: 					if (!(si.state & 2)) {
belugas@6352: 						/* Is this the first signal we see? And it's red... add penalty */
belugas@6352: 						si.cur_length += 10 * DIAG_FACTOR;
ludde@2125: 						si.state += 2; // remember that we added penalty.
belugas@6352: 						/* Because we added a penalty, we can't just continue as usual.
belugas@6352: 						 * Need to get out and let A* do it's job with
belugas@6352: 						 * possibly finding an even shorter path. */
ludde@2125: 						break;
ludde@2125: 					}
ludde@2125: 				}
ludde@2125: 
ludde@2125: 				if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length))
belugas@6352: 					return; // Don't process this tile any further
ludde@2125: 			}
ludde@2125: 
belugas@6352: 			/* continue with the next track */
frosch@8804: 			direction = TrackdirToExitdir(track);
ludde@2125: 
belugas@6352: 			/* safety check if we're running around chasing our tail... (infinite loop) */
ludde@2125: 			if (tile == tile_org) {
rubidium@5587: 				bits = TRACK_BIT_NONE;
ludde@2125: 				break;
ludde@2125: 			}
ludde@2044: 		}
ludde@2044: 
belugas@6352: 		/* There are no tracks to choose between.
belugas@6352: 		 * Stop searching in this direction */
rubidium@5587: 		if (bits == TRACK_BIT_NONE)
ludde@2125: 			continue;
truelight@0: 
belugas@6352: 		/****************
belugas@6352: 		 * We got multiple tracks to choose between (intersection).
belugas@6352: 		 * Branch the search space into several branches.
belugas@6352: 		 ****************/
truelight@193: 
belugas@6352: 		/* Check if we've already visited this intersection.
belugas@6352: 		 * If we've already visited it with a better length, then
belugas@6352: 		 * there's no point in visiting it again. */
ludde@2125: 		if (!NtpVisit(tpf, tile, direction, si.cur_length))
ludde@2125: 			continue;
truelight@0: 
belugas@6352: 		/* Push all possible alternatives that we can reach from here
belugas@6352: 		 * onto the priority heap.
belugas@6352: 		 * 'bits' contains the tracks that we can choose between. */
ludde@2125: 
belugas@6352: 		/* First compute the estimated distance to the target.
belugas@6352: 		 * This is used to implement A* */
ludde@2125: 		estimation = 0;
ludde@2125: 		if (tpf->dest != 0)
ludde@2125: 			estimation = DistanceMoo(tile, tpf->dest);
ludde@2125: 
ludde@2125: 		si.depth++;
matthijs@2774: 		if (si.depth == 0)
belugas@6352: 			continue; // We overflowed our depth. No more searching in this direction.
truelight@0: 		si.tile = tile;
rubidium@5587: 		while (bits != TRACK_BIT_NONE) {
KUDr@5598: 			Track track = RemoveFirstTrack(&bits);
frosch@8804: 			si.track = TrackEnterdirToTrackdir(track, direction);
matthijs@2782: 			assert(si.track != 0xFF);
ludde@2125: 			si.priority = si.cur_length + estimation;
ludde@2125: 
belugas@6352: 			/* out of stack items, bail out? */
ludde@2044: 			if (tpf->nstack >= lengthof(tpf->stack)) {
Darkvater@5380: 				DEBUG(ntp, 1, "Out of stack");
truelight@0: 				break;
ludde@2044: 			}
ludde@2125: 
truelight@0: 			tpf->stack[tpf->nstack] = si;
truelight@0: 			HeapifyUp(tpf);
rubidium@5587: 		};
truelight@0: 
belugas@6352: 		/* If this is the first intersection, we need to fill the first_track member.
belugas@6352: 		 * so the code outside knows which path is better.
belugas@6352: 		 * also randomize the order in which we search through them. */
truelight@0: 		if (si.depth == 1) {
ludde@2125: 			assert(tpf->nstack == 1 || tpf->nstack == 2 || tpf->nstack == 3);
ludde@2125: 			if (tpf->nstack != 1) {
ludde@2125: 				uint32 r = Random();
tron@5733: 				if (r & 1) Swap(tpf->stack[0].track, tpf->stack[1].track);
ludde@2125: 				if (tpf->nstack != 2) {
rubidium@5587: 					TrackdirByte t = tpf->stack[2].track;
tron@5733: 					if (r & 2) Swap(tpf->stack[0].track, t);
tron@5733: 					if (r & 4) Swap(tpf->stack[1].track, t);
ludde@2125: 					tpf->stack[2].first_track = tpf->stack[2].track = t;
ludde@2125: 				}
ludde@2125: 				tpf->stack[0].first_track = tpf->stack[0].track;
ludde@2125: 				tpf->stack[1].first_track = tpf->stack[1].track;
truelight@0: 			}
truelight@0: 		}
ludde@2044: 
belugas@6352: 		/* Continue with the next from the queue... */
ludde@2125: 	}
truelight@0: }
truelight@0: 
truelight@0: 
belugas@6352: /** new pathfinder for trains. better and faster. */
rubidium@8236: void NewTrainPathfind(TileIndex tile, TileIndex dest, RailTypes railtypes, DiagDirection direction, NTPEnumProc* enum_proc, void* data)
truelight@0: {
rubidium@8798: 	SmallStackSafeStackAlloc<NewTrackPathFinder, 1> tpf;
truelight@0: 
rubidium@8798: 	tpf->dest = dest;
rubidium@8798: 	tpf->userdata = data;
rubidium@8798: 	tpf->enum_proc = enum_proc;
rubidium@8798: 	tpf->tracktype = TRANSPORT_RAIL;
rubidium@8798: 	tpf->railtypes = railtypes;
rubidium@9413: 	tpf->maxlength = min(_settings_game.pf.opf.pf_maxlength * 3, 10000);
rubidium@8798: 	tpf->nstack = 0;
rubidium@8798: 	tpf->new_link = tpf->links;
rubidium@8798: 	tpf->num_links_left = lengthof(tpf->links);
rubidium@8798: 	memset(tpf->hash_head, 0, sizeof(tpf->hash_head));
ludde@2044: 
rubidium@8798: 	NTPEnum(tpf, tile, direction);
truelight@0: }