--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/pathfind.cpp Wed Jan 10 18:12:09 2007 +0000
@@ -0,0 +1,968 @@
+/* $Id$ */
+
+#include "stdafx.h"
+#include "openttd.h"
+#include "bridge_map.h"
+#include "station_map.h"
+#include "depot.h"
+#include "functions.h"
+#include "map.h"
+#include "tile.h"
+#include "pathfind.h"
+#include "rail.h"
+#include "debug.h"
+#include "tunnel_map.h"
+#include "variables.h"
+#include "depot.h"
+
+// remember which tiles we have already visited so we don't visit them again.
+static bool TPFSetTileBit(TrackPathFinder *tpf, TileIndex tile, int dir)
+{
+ uint hash, val, offs;
+ TrackPathFinderLink *link, *new_link;
+ uint bits = 1 << dir;
+
+ if (tpf->disable_tile_hash)
+ return true;
+
+ hash = PATHFIND_HASH_TILE(tile);
+
+ val = tpf->hash_head[hash];
+
+ if (val == 0) {
+ /* unused hash entry, set the appropriate bit in it and return true
+ * to indicate that a bit was set. */
+ tpf->hash_head[hash] = bits;
+ tpf->hash_tile[hash] = tile;
+ return true;
+ } else if (!(val & 0x8000)) {
+ /* single tile */
+
+ if (tile == tpf->hash_tile[hash]) {
+ /* found another bit for the same tile,
+ * check if this bit is already set, if so, return false */
+ if (val & bits)
+ return false;
+
+ /* otherwise set the bit and return true to indicate that the bit
+ * was set */
+ tpf->hash_head[hash] = val | bits;
+ return true;
+ } else {
+ /* two tiles with the same hash, need to make a link */
+
+ /* allocate a link. if out of links, handle this by returning
+ * that a tile was already visisted. */
+ if (tpf->num_links_left == 0) {
+ return false;
+ }
+ tpf->num_links_left--;
+ link = tpf->new_link++;
+
+ /* move the data that was previously in the hash_??? variables
+ * to the link struct, and let the hash variables point to the link */
+ link->tile = tpf->hash_tile[hash];
+ tpf->hash_tile[hash] = PATHFIND_GET_LINK_OFFS(tpf, link);
+
+ link->flags = tpf->hash_head[hash];
+ tpf->hash_head[hash] = 0xFFFF; /* multi link */
+
+ link->next = 0xFFFF;
+ }
+ } else {
+ /* a linked list of many tiles,
+ * find the one corresponding to the tile, if it exists.
+ * otherwise make a new link */
+
+ offs = tpf->hash_tile[hash];
+ do {
+ link = PATHFIND_GET_LINK_PTR(tpf, offs);
+ if (tile == link->tile) {
+ /* found the tile in the link list,
+ * check if the bit was alrady set, if so return false to indicate that the
+ * bit was already set */
+ if (link->flags & bits)
+ return false;
+ link->flags |= bits;
+ return true;
+ }
+ } while ((offs=link->next) != 0xFFFF);
+ }
+
+ /* get here if we need to add a new link to link,
+ * first, allocate a new link, in the same way as before */
+ if (tpf->num_links_left == 0) {
+ return false;
+ }
+ tpf->num_links_left--;
+ new_link = tpf->new_link++;
+
+ /* then fill the link with the new info, and establish a ptr from the old
+ * link to the new one */
+ new_link->tile = tile;
+ new_link->flags = bits;
+ new_link->next = 0xFFFF;
+
+ link->next = PATHFIND_GET_LINK_OFFS(tpf, new_link);
+ return true;
+}
+
+static const byte _bits_mask[4] = {
+ 0x19,
+ 0x16,
+ 0x25,
+ 0x2A,
+};
+
+static const byte _tpf_new_direction[14] = {
+ 0, 1, 0, 1, 2, 1,
+ 0, 0,
+ 2, 3, 3, 2, 3, 0,
+};
+
+static const byte _tpf_prev_direction[14] = {
+ 0, 1, 1, 0, 1, 2,
+ 0, 0,
+ 2, 3, 2, 3, 0, 3,
+};
+
+
+static const byte _otherdir_mask[4] = {
+ 0x10,
+ 0,
+ 0x5,
+ 0x2A,
+};
+
+static void TPFMode2(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
+{
+ uint bits;
+ int i;
+ RememberData rd;
+
+ assert(tpf->tracktype == TRANSPORT_WATER);
+
+ // This addition will sometimes overflow by a single tile.
+ // The use of TILE_MASK here makes sure that we still point at a valid
+ // tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail.
+ tile = TILE_MASK(tile + TileOffsByDiagDir(direction));
+
+ if (++tpf->rd.cur_length > 50)
+ return;
+
+ bits = GetTileTrackStatus(tile, tpf->tracktype);
+ bits = (byte)((bits | (bits >> 8)) & _bits_mask[direction]);
+ if (bits == 0)
+ return;
+
+ assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY());
+
+ if ( (bits & (bits - 1)) == 0 ) {
+ /* only one direction */
+ i = 0;
+ while (!(bits&1))
+ i++, bits>>=1;
+
+ rd = tpf->rd;
+ goto continue_here;
+ }
+ /* several directions */
+ i=0;
+ do {
+ if (!(bits & 1)) continue;
+ rd = tpf->rd;
+
+ // Change direction 4 times only
+ if ((byte)i != tpf->rd.pft_var6) {
+ if (++tpf->rd.depth > 4) {
+ tpf->rd = rd;
+ return;
+ }
+ tpf->rd.pft_var6 = (byte)i;
+ }
+
+continue_here:;
+ tpf->the_dir = i + (HASBIT(_otherdir_mask[direction], i) ? 8 : 0);
+
+ if (!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, NULL)) {
+ TPFMode2(tpf, tile, _tpf_new_direction[tpf->the_dir]);
+ }
+
+ tpf->rd = rd;
+ } while (++i, bits>>=1);
+
+}
+
+
+/* Returns the end tile and the length of a tunnel. The length does not
+ * include the starting tile (entry), it does include the end tile (exit).
+ */
+FindLengthOfTunnelResult FindLengthOfTunnel(TileIndex tile, DiagDirection dir)
+{
+ TileIndexDiff delta = TileOffsByDiagDir(dir);
+ uint z = GetTileZ(tile);
+ FindLengthOfTunnelResult flotr;
+
+ flotr.length = 0;
+
+ dir = ReverseDiagDir(dir);
+ do {
+ flotr.length++;
+ tile += delta;
+ } while(
+ !IsTunnelTile(tile) ||
+ GetTunnelDirection(tile) != dir ||
+ GetTileZ(tile) != z
+ );
+
+ flotr.tile = tile;
+ return flotr;
+}
+
+static const uint16 _tpfmode1_and[4] = { 0x1009, 0x16, 0x520, 0x2A00 };
+
+static uint SkipToEndOfTunnel(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
+{
+ FindLengthOfTunnelResult flotr;
+ TPFSetTileBit(tpf, tile, 14);
+ flotr = FindLengthOfTunnel(tile, direction);
+ tpf->rd.cur_length += flotr.length;
+ TPFSetTileBit(tpf, flotr.tile, 14);
+ return flotr.tile;
+}
+
+const byte _ffb_64[128] = {
+ 0, 0, 1, 0, 2, 0, 1, 0,
+ 3, 0, 1, 0, 2, 0, 1, 0,
+ 4, 0, 1, 0, 2, 0, 1, 0,
+ 3, 0, 1, 0, 2, 0, 1, 0,
+ 5, 0, 1, 0, 2, 0, 1, 0,
+ 3, 0, 1, 0, 2, 0, 1, 0,
+ 4, 0, 1, 0, 2, 0, 1, 0,
+ 3, 0, 1, 0, 2, 0, 1, 0,
+
+ 0, 0, 0, 2, 0, 4, 4, 6,
+ 0, 8, 8, 10, 8, 12, 12, 14,
+ 0, 16, 16, 18, 16, 20, 20, 22,
+16, 24, 24, 26, 24, 28, 28, 30,
+ 0, 32, 32, 34, 32, 36, 36, 38,
+32, 40, 40, 42, 40, 44, 44, 46,
+32, 48, 48, 50, 48, 52, 52, 54,
+48, 56, 56, 58, 56, 60, 60, 62,
+};
+
+static void TPFMode1(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
+{
+ uint bits;
+ int i;
+ RememberData rd;
+ TileIndex tile_org = tile;
+
+ if (IsTileType(tile, MP_TUNNELBRIDGE)) {
+ if (IsTunnel(tile)) {
+ if (GetTunnelDirection(tile) != direction ||
+ GetTunnelTransportType(tile) != tpf->tracktype) {
+ return;
+ }
+ tile = SkipToEndOfTunnel(tpf, tile, direction);
+ } else {
+ TileIndex tile_end;
+ if (GetBridgeRampDirection(tile) != direction ||
+ GetBridgeTransportType(tile) != tpf->tracktype) {
+ return;
+ }
+ //fprintf(stderr, "%s: Planning over bridge\n", __func__);
+ // TODO doesn't work - WHAT doesn't work?
+ TPFSetTileBit(tpf, tile, 14);
+ tile_end = GetOtherBridgeEnd(tile);
+ tpf->rd.cur_length += DistanceManhattan(tile, tile_end);
+ tile = tile_end;
+ TPFSetTileBit(tpf, tile, 14);
+ }
+ }
+ tile += TileOffsByDiagDir(direction);
+
+ /* Check in case of rail if the owner is the same */
+ if (tpf->tracktype == TRANSPORT_RAIL) {
+ // don't enter train depot from the back
+ if (IsTileDepotType(tile, TRANSPORT_RAIL) && GetRailDepotDirection(tile) == direction) return;
+
+ if (IsTileType(tile_org, MP_RAILWAY) || IsTileType(tile_org, MP_STATION) || IsTileType(tile_org, MP_TUNNELBRIDGE))
+ if (IsTileType(tile, MP_RAILWAY) || IsTileType(tile, MP_STATION) || IsTileType(tile, MP_TUNNELBRIDGE))
+ if (GetTileOwner(tile_org) != GetTileOwner(tile)) return;
+ }
+
+ // check if the new tile can be entered from that direction
+ if (tpf->tracktype == TRANSPORT_ROAD) {
+ // road stops and depots now have a track (r4419)
+ // don't enter road stop from the back
+ if (IsRoadStopTile(tile) && ReverseDiagDir(GetRoadStopDir(tile)) != direction) return;
+ // don't enter road depot from the back
+ if (IsTileDepotType(tile, TRANSPORT_ROAD) && ReverseDiagDir(GetRoadDepotDirection(tile)) != direction) return;
+ }
+
+ /* Check if the new tile is a tunnel or bridge head and that the direction
+ * and transport type match */
+ if (IsTileType(tile, MP_TUNNELBRIDGE)) {
+ if (IsTunnel(tile)) {
+ if (GetTunnelDirection(tile) != direction ||
+ GetTunnelTransportType(tile) != tpf->tracktype) {
+ return;
+ }
+ } else if (IsBridge(tile)) {
+ if (GetBridgeRampDirection(tile) != direction ||
+ GetBridgeTransportType(tile) != tpf->tracktype) {
+ return;
+ }
+ }
+ }
+
+ tpf->rd.cur_length++;
+
+ bits = GetTileTrackStatus(tile, tpf->tracktype);
+
+ if ((byte)bits != tpf->var2) {
+ bits &= _tpfmode1_and[direction];
+ bits = bits | (bits>>8);
+ }
+ bits &= 0xBF;
+
+ if (bits != 0) {
+ if (!tpf->disable_tile_hash || (tpf->rd.cur_length <= 64 && (KILL_FIRST_BIT(bits) == 0 || ++tpf->rd.depth <= 7))) {
+ do {
+ i = FIND_FIRST_BIT(bits);
+ bits = KILL_FIRST_BIT(bits);
+
+ tpf->the_dir = (_otherdir_mask[direction] & (byte)(1 << i)) ? (i+8) : i;
+ rd = tpf->rd;
+
+ if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&
+ !tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, &tpf->rd.pft_var6) ) {
+ TPFMode1(tpf, tile, _tpf_new_direction[tpf->the_dir]);
+ }
+ tpf->rd = rd;
+ } while (bits != 0);
+ }
+ }
+
+ /* the next is only used when signals are checked.
+ * seems to go in 2 directions simultaneously */
+
+ /* if i can get rid of this, tail end recursion can be used to minimize
+ * stack space dramatically. */
+
+ /* If we are doing signal setting, we must reverse at evere tile, so we
+ * iterate all the tracks in a signal block, even when a normal train would
+ * not reach it (for example, when two lines merge */
+ if (tpf->hasbit_13)
+ return;
+
+ direction = ReverseDiagDir(direction);
+ tile += TileOffsByDiagDir(direction);
+
+ bits = GetTileTrackStatus(tile, tpf->tracktype);
+ bits |= (bits >> 8);
+
+ if ( (byte)bits != tpf->var2) {
+ bits &= _bits_mask[direction];
+ }
+
+ bits &= 0xBF;
+ if (bits == 0)
+ return;
+
+ do {
+ i = FIND_FIRST_BIT(bits);
+ bits = KILL_FIRST_BIT(bits);
+
+ tpf->the_dir = (_otherdir_mask[direction] & (byte)(1 << i)) ? (i+8) : i;
+ rd = tpf->rd;
+ if (TPFSetTileBit(tpf, tile, tpf->the_dir) &&
+ !tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length, &tpf->rd.pft_var6) ) {
+ TPFMode1(tpf, tile, _tpf_new_direction[tpf->the_dir]);
+ }
+ tpf->rd = rd;
+ } while (bits != 0);
+}
+
+void FollowTrack(TileIndex tile, uint16 flags, DiagDirection direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data)
+{
+ TrackPathFinder tpf;
+
+ assert(direction < 4);
+
+ /* initialize path finder variables */
+ tpf.userdata = data;
+ tpf.enum_proc = enum_proc;
+ tpf.new_link = tpf.links;
+ tpf.num_links_left = lengthof(tpf.links);
+
+ tpf.rd.cur_length = 0;
+ tpf.rd.depth = 0;
+ tpf.rd.pft_var6 = 0;
+
+ tpf.var2 = HASBIT(flags, 15) ? 0x43 : 0xFF; /* 0x8000 */
+
+ tpf.disable_tile_hash = HASBIT(flags, 12); /* 0x1000 */
+ tpf.hasbit_13 = HASBIT(flags, 13); /* 0x2000 */
+
+
+ tpf.tracktype = (byte)flags;
+
+ if (HASBIT(flags, 11)) {
+ tpf.rd.pft_var6 = 0xFF;
+ tpf.enum_proc(tile, data, 0, 0, 0);
+ TPFMode2(&tpf, tile, direction);
+ } else {
+ /* clear the hash_heads */
+ memset(tpf.hash_head, 0, sizeof(tpf.hash_head));
+ TPFMode1(&tpf, tile, direction);
+ }
+
+ if (after_proc != NULL)
+ after_proc(&tpf);
+}
+
+typedef struct {
+ TileIndex tile;
+ uint16 cur_length; // This is the current length to this tile.
+ uint16 priority; // This is the current length + estimated length to the goal.
+ byte track;
+ byte depth;
+ byte state;
+ byte first_track;
+} StackedItem;
+
+static const byte _new_track[6][4] = {
+{0, 0xff, 8, 0xff,},
+{0xff, 1, 0xff, 9,},
+{0xff, 2, 10, 0xff,},
+{3, 0xff, 0xff, 11,},
+{12, 4, 0xff, 0xff,},
+{0xff, 0xff, 5, 13,},
+};
+
+typedef struct HashLink {
+ TileIndex tile;
+ uint16 typelength;
+ uint16 next;
+} HashLink;
+
+typedef struct {
+ NTPEnumProc *enum_proc;
+ void *userdata;
+ TileIndex dest;
+
+ TransportType tracktype;
+ RailTypeMask railtypes;
+ uint maxlength;
+
+ HashLink *new_link;
+ uint num_links_left;
+
+ uint nstack;
+ StackedItem stack[256]; // priority queue of stacked items
+
+ uint16 hash_head[0x400]; // hash heads. 0 means unused. 0xFFFC = length, 0x3 = dir
+ TileIndex hash_tile[0x400]; // tiles. or links.
+
+ HashLink links[0x400]; // hash links
+
+} NewTrackPathFinder;
+#define NTP_GET_LINK_OFFS(tpf, link) ((byte*)(link) - (byte*)tpf->links)
+#define NTP_GET_LINK_PTR(tpf, link_offs) (HashLink*)((byte*)tpf->links + (link_offs))
+
+#define ARR(i) tpf->stack[(i)-1]
+
+// called after a new element was added in the queue at the last index.
+// move it down to the proper position
+static inline void HeapifyUp(NewTrackPathFinder *tpf)
+{
+ StackedItem si;
+ int i = ++tpf->nstack;
+
+ while (i != 1 && ARR(i).priority < ARR(i>>1).priority) {
+ // the child element is larger than the parent item.
+ // swap the child item and the parent item.
+ si = ARR(i); ARR(i) = ARR(i>>1); ARR(i>>1) = si;
+ i>>=1;
+ }
+}
+
+// called after the element 0 was eaten. fill it with a new element
+static inline void HeapifyDown(NewTrackPathFinder *tpf)
+{
+ StackedItem si;
+ int i = 1, j;
+ int n;
+
+ assert(tpf->nstack > 0);
+ n = --tpf->nstack;
+
+ if (n == 0) return; // heap is empty so nothing to do?
+
+ // copy the last item to index 0. we use it as base for heapify.
+ ARR(1) = ARR(n+1);
+
+ while ((j=i*2) <= n) {
+ // figure out which is smaller of the children.
+ if (j != n && ARR(j).priority > ARR(j+1).priority)
+ j++; // right item is smaller
+
+ assert(i <= n && j <= n);
+ if (ARR(i).priority <= ARR(j).priority)
+ break; // base elem smaller than smallest, done!
+
+ // swap parent with the child
+ si = ARR(i); ARR(i) = ARR(j); ARR(j) = si;
+ i = j;
+ }
+}
+
+// mark a tile as visited and store the length of the path.
+// if we already had a better path to this tile, return false.
+// otherwise return true.
+static bool NtpVisit(NewTrackPathFinder* tpf, TileIndex tile, DiagDirection dir, uint length)
+{
+ uint hash,head;
+ HashLink *link, *new_link;
+
+ assert(length < 16384-1);
+
+ hash = PATHFIND_HASH_TILE(tile);
+
+ // never visited before?
+ if ((head=tpf->hash_head[hash]) == 0) {
+ tpf->hash_tile[hash] = tile;
+ tpf->hash_head[hash] = dir | (length << 2);
+ return true;
+ }
+
+ if (head != 0xffff) {
+ if (tile == tpf->hash_tile[hash] && (head & 0x3) == dir) {
+
+ // longer length
+ if (length >= (head >> 2)) return false;
+
+ tpf->hash_head[hash] = dir | (length << 2);
+ return true;
+ }
+ // two tiles with the same hash, need to make a link
+ // allocate a link. if out of links, handle this by returning
+ // that a tile was already visisted.
+ if (tpf->num_links_left == 0) {
+ DEBUG(ntp, 1, "No links left");
+ return false;
+ }
+
+ tpf->num_links_left--;
+ link = tpf->new_link++;
+
+ /* move the data that was previously in the hash_??? variables
+ * to the link struct, and let the hash variables point to the link */
+ link->tile = tpf->hash_tile[hash];
+ tpf->hash_tile[hash] = NTP_GET_LINK_OFFS(tpf, link);
+
+ link->typelength = tpf->hash_head[hash];
+ tpf->hash_head[hash] = 0xFFFF; /* multi link */
+ link->next = 0xFFFF;
+ } else {
+ // a linked list of many tiles,
+ // find the one corresponding to the tile, if it exists.
+ // otherwise make a new link
+
+ uint offs = tpf->hash_tile[hash];
+ do {
+ link = NTP_GET_LINK_PTR(tpf, offs);
+ if (tile == link->tile && (link->typelength & 0x3U) == dir) {
+ if (length >= (uint)(link->typelength >> 2)) return false;
+ link->typelength = dir | (length << 2);
+ return true;
+ }
+ } while ((offs = link->next) != 0xFFFF);
+ }
+
+ /* get here if we need to add a new link to link,
+ * first, allocate a new link, in the same way as before */
+ if (tpf->num_links_left == 0) {
+ DEBUG(ntp, 1, "No links left");
+ return false;
+ }
+ tpf->num_links_left--;
+ new_link = tpf->new_link++;
+
+ /* then fill the link with the new info, and establish a ptr from the old
+ * link to the new one */
+ new_link->tile = tile;
+ new_link->typelength = dir | (length << 2);
+ new_link->next = 0xFFFF;
+
+ link->next = NTP_GET_LINK_OFFS(tpf, new_link);
+ return true;
+}
+
+/**
+ * Checks if the shortest path to the given tile/dir so far is still the given
+ * length.
+ * @return true if the length is still the same
+ * @pre The given tile/dir combination should be present in the hash, by a
+ * previous call to NtpVisit().
+ */
+static bool NtpCheck(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint length)
+{
+ uint hash,head,offs;
+ HashLink *link;
+
+ hash = PATHFIND_HASH_TILE(tile);
+ head=tpf->hash_head[hash];
+ assert(head);
+
+ if (head != 0xffff) {
+ assert( tpf->hash_tile[hash] == tile && (head & 3) == dir);
+ assert( (head >> 2) <= length);
+ return length == (head >> 2);
+ }
+
+ // else it's a linked list of many tiles
+ offs = tpf->hash_tile[hash];
+ for (;;) {
+ link = NTP_GET_LINK_PTR(tpf, offs);
+ if (tile == link->tile && (link->typelength & 0x3U) == dir) {
+ assert((uint)(link->typelength >> 2) <= length);
+ return length == (uint)(link->typelength >> 2);
+ }
+ offs = link->next;
+ assert(offs != 0xffff);
+ }
+}
+
+
+static const uint16 _is_upwards_slope[15] = {
+ 0, // no tileh
+ (1 << TRACKDIR_X_SW) | (1 << TRACKDIR_Y_NW), // 1
+ (1 << TRACKDIR_X_SW) | (1 << TRACKDIR_Y_SE), // 2
+ (1 << TRACKDIR_X_SW), // 3
+ (1 << TRACKDIR_X_NE) | (1 << TRACKDIR_Y_SE), // 4
+ 0, // 5
+ (1 << TRACKDIR_Y_SE), // 6
+ 0, // 7
+ (1 << TRACKDIR_X_NE) | (1 << TRACKDIR_Y_NW), // 8,
+ (1 << TRACKDIR_Y_NW), // 9
+ 0, //10
+ 0, //11,
+ (1 << TRACKDIR_X_NE), //12
+ 0, //13
+ 0, //14
+};
+
+static uint DistanceMoo(TileIndex t0, TileIndex t1)
+{
+ const uint dx = abs(TileX(t0) - TileX(t1));
+ const uint dy = abs(TileY(t0) - TileY(t1));
+
+ const uint straightTracks = 2 * min(dx, dy); /* The number of straight (not full length) tracks */
+ /* OPTIMISATION:
+ * Original: diagTracks = max(dx, dy) - min(dx,dy);
+ * Proof:
+ * (dx-dy) - straightTracks == (min + max) - straightTracks = min + // max - 2 * min = max - min */
+ const uint diagTracks = dx + dy - straightTracks; /* The number of diagonal (full tile length) tracks. */
+
+ return diagTracks*DIAG_FACTOR + straightTracks*STR_FACTOR;
+}
+
+// These has to be small cause the max length of a track
+// is currently limited to 16384
+
+static const byte _length_of_track[16] = {
+ DIAG_FACTOR, DIAG_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, 0, 0,
+ DIAG_FACTOR, DIAG_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, 0, 0
+};
+
+// new more optimized pathfinder for trains...
+// Tile is the tile the train is at.
+// direction is the tile the train is moving towards.
+
+static void NTPEnum(NewTrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
+{
+ TrackBits bits, allbits;
+ uint track;
+ TileIndex tile_org;
+ StackedItem si;
+ int estimation;
+
+
+
+ // Need to have a special case for the start.
+ // We shouldn't call the callback for the current tile.
+ si.cur_length = 1; // Need to start at 1 cause 0 is a reserved value.
+ si.depth = 0;
+ si.state = 0;
+ si.first_track = 0xFF;
+ goto start_at;
+
+ for (;;) {
+ // Get the next item to search from from the priority queue
+ do {
+ if (tpf->nstack == 0)
+ return; // nothing left? then we're done!
+ si = tpf->stack[0];
+ tile = si.tile;
+
+ HeapifyDown(tpf);
+ // Make sure we havn't already visited this tile.
+ } while (!NtpCheck(tpf, tile, _tpf_prev_direction[si.track], si.cur_length));
+
+ // Add the length of this track.
+ si.cur_length += _length_of_track[si.track];
+
+callback_and_continue:
+ if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length))
+ return;
+
+ assert(si.track <= 13);
+ direction = _tpf_new_direction[si.track];
+
+start_at:
+ // If the tile is the entry tile of a tunnel, and we're not going out of the tunnel,
+ // need to find the exit of the tunnel.
+ if (IsTileType(tile, MP_TUNNELBRIDGE)) {
+ if (IsTunnel(tile)) {
+ if (GetTunnelDirection(tile) != ReverseDiagDir(direction)) {
+ FindLengthOfTunnelResult flotr;
+
+ /* We are not just driving out of the tunnel */
+ if (GetTunnelDirection(tile) != direction ||
+ GetTunnelTransportType(tile) != tpf->tracktype) {
+ // We are not driving into the tunnel, or it is an invalid tunnel
+ continue;
+ }
+ if (!HASBIT(tpf->railtypes, GetRailType(tile))) {
+ bits = 0;
+ break;
+ }
+ flotr = FindLengthOfTunnel(tile, direction);
+ si.cur_length += flotr.length * DIAG_FACTOR;
+ tile = flotr.tile;
+ // tile now points to the exit tile of the tunnel
+ }
+ } else {
+ TileIndex tile_end;
+ if (GetBridgeRampDirection(tile) != ReverseDiagDir(direction)) {
+ // We are not just leaving the bridge
+ if (GetBridgeRampDirection(tile) != direction ||
+ GetBridgeTransportType(tile) != tpf->tracktype) {
+ // Not entering the bridge or not compatible
+ continue;
+ }
+ }
+ tile_end = GetOtherBridgeEnd(tile);
+ si.cur_length += DistanceManhattan(tile, tile_end) * DIAG_FACTOR;
+ tile = tile_end;
+ }
+ }
+
+ // This is a special loop used to go through
+ // a rail net and find the first intersection
+ tile_org = tile;
+ for (;;) {
+ assert(direction <= 3);
+ tile += TileOffsByDiagDir(direction);
+
+ // too long search length? bail out.
+ if (si.cur_length >= tpf->maxlength) {
+ DEBUG(ntp, 1, "Cur_length too big");
+ bits = 0;
+ break;
+ }
+
+ // Not a regular rail tile?
+ // Then we can't use the code below, but revert to more general code.
+ if (!IsTileType(tile, MP_RAILWAY) || !IsPlainRailTile(tile)) {
+ // We found a tile which is not a normal railway tile.
+ // Determine which tracks that exist on this tile.
+ bits = GetTileTrackStatus(tile, TRANSPORT_RAIL) & _tpfmode1_and[direction];
+ bits = (bits | (bits >> 8)) & 0x3F;
+
+ // Check that the tile contains exactly one track
+ if (bits == 0 || KILL_FIRST_BIT(bits) != 0) break;
+
+ if (!HASBIT(tpf->railtypes, IsTileType(tile, MP_STREET) ? GetRailTypeCrossing(tile) : GetRailType(tile))) {
+ bits = 0;
+ break;
+ }
+
+ ///////////////////
+ // If we reach here, the tile has exactly one track.
+ // tile - index to a tile that is not rail tile, but still straight (with optional signals)
+ // bits - bitmask of which track that exist on the tile (exactly one bit is set)
+ // direction - which direction are we moving in?
+ ///////////////////
+ si.track = _new_track[FIND_FIRST_BIT(bits)][direction];
+ si.cur_length += _length_of_track[si.track];
+ goto callback_and_continue;
+ }
+
+ /* Regular rail tile, determine which tracks exist. */
+ allbits = GetTrackBits(tile);
+ /* Which tracks are reachable? */
+ bits = allbits & DiagdirReachesTracks(direction);
+
+ /* The tile has no reachable tracks => End of rail segment
+ * or Intersection => End of rail segment. We check this agains all the
+ * bits, not just reachable ones, to prevent infinite loops. */
+ if (bits == 0 || TracksOverlap(allbits)) break;
+
+ if (!HASBIT(tpf->railtypes, GetRailType(tile))) {
+ bits = 0;
+ break;
+ }
+
+ /* If we reach here, the tile has exactly one track, and this
+ track is reachable => Rail segment continues */
+
+ track = _new_track[FIND_FIRST_BIT(bits)][direction];
+ assert(track != 0xff);
+
+ si.cur_length += _length_of_track[track];
+
+ // Check if this rail is an upwards slope. If it is, then add a penalty.
+ // Small optimization here.. if (track&7)>1 then it can't be a slope so we avoid calling GetTileSlope
+ if ((track & 7) <= 1 && (_is_upwards_slope[GetTileSlope(tile, NULL)] & (1 << track)) ) {
+ // upwards slope. add some penalty.
+ si.cur_length += 4*DIAG_FACTOR;
+ }
+
+ // railway tile with signals..?
+ if (HasSignals(tile)) {
+ if (!HasSignalOnTrackdir(tile, track)) {
+ // if one way signal not pointing towards us, stop going in this direction => End of rail segment.
+ if (HasSignalOnTrackdir(tile, ReverseTrackdir(track))) {
+ bits = 0;
+ break;
+ }
+ } else if (GetSignalStateByTrackdir(tile, track) == SIGNAL_STATE_GREEN) {
+ // green signal in our direction. either one way or two way.
+ si.state |= 3;
+ } else {
+ // reached a red signal.
+ if (HasSignalOnTrackdir(tile, ReverseTrackdir(track))) {
+ // two way red signal. unless we passed another green signal on the way,
+ // stop going in this direction => End of rail segment.
+ // this is to prevent us from going into a full platform.
+ if (!(si.state&1)) {
+ bits = 0;
+ break;
+ }
+ }
+ if (!(si.state & 2)) {
+ // Is this the first signal we see? And it's red... add penalty
+ si.cur_length += 10*DIAG_FACTOR;
+ si.state += 2; // remember that we added penalty.
+ // Because we added a penalty, we can't just continue as usual.
+ // Need to get out and let A* do it's job with
+ // possibly finding an even shorter path.
+ break;
+ }
+ }
+
+ if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length))
+ return; /* Don't process this tile any further */
+ }
+
+ // continue with the next track
+ direction = _tpf_new_direction[track];
+
+ // safety check if we're running around chasing our tail... (infinite loop)
+ if (tile == tile_org) {
+ bits = 0;
+ break;
+ }
+ }
+
+ // There are no tracks to choose between.
+ // Stop searching in this direction
+ if (bits == 0)
+ continue;
+
+ ////////////////
+ // We got multiple tracks to choose between (intersection).
+ // Branch the search space into several branches.
+ ////////////////
+
+ // Check if we've already visited this intersection.
+ // If we've already visited it with a better length, then
+ // there's no point in visiting it again.
+ if (!NtpVisit(tpf, tile, direction, si.cur_length))
+ continue;
+
+ // Push all possible alternatives that we can reach from here
+ // onto the priority heap.
+ // 'bits' contains the tracks that we can choose between.
+
+ // First compute the estimated distance to the target.
+ // This is used to implement A*
+ estimation = 0;
+ if (tpf->dest != 0)
+ estimation = DistanceMoo(tile, tpf->dest);
+
+ si.depth++;
+ if (si.depth == 0)
+ continue; /* We overflowed our depth. No more searching in this direction. */
+ si.tile = tile;
+ do {
+ si.track = _new_track[FIND_FIRST_BIT(bits)][direction];
+ assert(si.track != 0xFF);
+ si.priority = si.cur_length + estimation;
+
+ // out of stack items, bail out?
+ if (tpf->nstack >= lengthof(tpf->stack)) {
+ DEBUG(ntp, 1, "Out of stack");
+ break;
+ }
+
+ tpf->stack[tpf->nstack] = si;
+ HeapifyUp(tpf);
+ } while ((bits = KILL_FIRST_BIT(bits)) != 0);
+
+ // If this is the first intersection, we need to fill the first_track member.
+ // so the code outside knows which path is better.
+ // also randomize the order in which we search through them.
+ if (si.depth == 1) {
+ assert(tpf->nstack == 1 || tpf->nstack == 2 || tpf->nstack == 3);
+ if (tpf->nstack != 1) {
+ uint32 r = Random();
+ if (r&1) swap_byte(&tpf->stack[0].track, &tpf->stack[1].track);
+ if (tpf->nstack != 2) {
+ byte t = tpf->stack[2].track;
+ if (r&2) swap_byte(&tpf->stack[0].track, &t);
+ if (r&4) swap_byte(&tpf->stack[1].track, &t);
+ tpf->stack[2].first_track = tpf->stack[2].track = t;
+ }
+ tpf->stack[0].first_track = tpf->stack[0].track;
+ tpf->stack[1].first_track = tpf->stack[1].track;
+ }
+ }
+
+ // Continue with the next from the queue...
+ }
+}
+
+
+// new pathfinder for trains. better and faster.
+void NewTrainPathfind(TileIndex tile, TileIndex dest, RailTypeMask railtypes, DiagDirection direction, NTPEnumProc* enum_proc, void* data)
+{
+ NewTrackPathFinder tpf;
+
+ tpf.dest = dest;
+ tpf.userdata = data;
+ tpf.enum_proc = enum_proc;
+ tpf.tracktype = TRANSPORT_RAIL;
+ tpf.railtypes = railtypes;
+ tpf.maxlength = min(_patches.pf_maxlength * 3, 10000);
+ tpf.nstack = 0;
+ tpf.new_link = tpf.links;
+ tpf.num_links_left = lengthof(tpf.links);
+ memset(tpf.hash_head, 0, sizeof(tpf.hash_head));
+
+ NTPEnum(&tpf, tile, direction);
+}