diff options
author | rubidium <rubidium@openttd.org> | 2007-01-02 19:19:48 +0000 |
---|---|---|
committer | rubidium <rubidium@openttd.org> | 2007-01-02 19:19:48 +0000 |
commit | 66bbf336c6af7353ef0aeed58002c46543b30635 (patch) | |
tree | ad4a63860df2626b22f77e7dac712e958bea54cb /pathfind.c | |
parent | ccc0a3f4dbf58c005b22341ac8874252924690cd (diff) | |
download | openttd-66bbf336c6af7353ef0aeed58002c46543b30635.tar.xz |
(svn r7759) -Merge: makefile rewrite. This merge features:
- A proper ./configure, so everything needs to be configured only once, not for every make.
- Usage of makedepend when available. This greatly reduces the time needed for generating the dependencies.
- A generator for all project files. There is a single file with sources, which is used to generate Makefiles and the project files for MSVC.
- Proper support for OSX universal binaries.
- Object files for non-MSVC compiles are also placed in separate directories, making is faster to switch between debug and release compiles and it does not touch the directory with the source files.
- Functionality to make a bundle of all needed files for for example a nightly or distribution of a binary with all needed GRFs and language files.
Note: as this merge moves almost all files, it is recommended to make a backup of your working copy before updating your working copy.
Diffstat (limited to 'pathfind.c')
-rw-r--r-- | pathfind.c | 968 |
1 files changed, 0 insertions, 968 deletions
diff --git a/pathfind.c b/pathfind.c deleted file mode 100644 index 81ccc699c..000000000 --- a/pathfind.c +++ /dev/null @@ -1,968 +0,0 @@ -/* $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); -} |