diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/lang/english.txt | 2 | ||||
| -rw-r--r-- | src/pathfind.cpp | 731 | ||||
| -rw-r--r-- | src/pathfind.h | 69 | ||||
| -rw-r--r-- | src/roadveh_cmd.cpp | 91 | ||||
| -rw-r--r-- | src/saveload/afterload.cpp | 4 | ||||
| -rw-r--r-- | src/ship_cmd.cpp | 2 | ||||
| -rw-r--r-- | src/table/settings.h | 4 | ||||
| -rw-r--r-- | src/train_cmd.cpp | 213 | ||||
| -rw-r--r-- | src/vehicle_type.h | 3 |
9 files changed, 43 insertions, 1076 deletions
diff --git a/src/lang/english.txt b/src/lang/english.txt index 251423ca2..ab2f5ac1c 100644 --- a/src/lang/english.txt +++ b/src/lang/english.txt @@ -1063,7 +1063,7 @@ STR_CONFIG_SETTING_MAMMOTHTRAINS :{LTBLUE}Enable STR_CONFIG_SETTING_TRAIN_ACCELERATION_MODEL :{LTBLUE}Train acceleration model: {ORANGE}{STRING1} STR_CONFIG_SETTING_TRAIN_ACCELERATION_MODEL_ORIGINAL :Original STR_CONFIG_SETTING_TRAIN_ACCELERATION_MODEL_REALISTIC :Realistic -STR_CONFIG_SETTING_FORBID_90_DEG :{LTBLUE}Forbid trains and ships to make 90 deg turns: {ORANGE}{STRING1} {LTBLUE} (not with NTP) +STR_CONFIG_SETTING_FORBID_90_DEG :{LTBLUE}Forbid trains and ships to make 90 deg turns: {ORANGE}{STRING1} {LTBLUE} (not with OPF) STR_CONFIG_SETTING_JOINSTATIONS :{LTBLUE}Join train stations built next to each other: {ORANGE}{STRING1} STR_CONFIG_SETTING_DISTANT_JOIN_STATIONS :{LTBLUE}Allow to join stations not directly adjacent: {ORANGE}{STRING1} STR_CONFIG_SETTING_IMPROVEDLOAD :{LTBLUE}Use improved loading algorithm: {ORANGE}{STRING1} diff --git a/src/pathfind.cpp b/src/pathfind.cpp index 6f9899bc1..2af825246 100644 --- a/src/pathfind.cpp +++ b/src/pathfind.cpp @@ -13,109 +13,27 @@ #include "pathfind.h" #include "debug.h" #include "tunnelbridge_map.h" -#include "core/random_func.hpp" #include "core/alloc_type.hpp" #include "tunnelbridge.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; +struct RememberData { + uint16 cur_length; + byte depth; + Track last_choosen_track; +}; - link->next = PATHFIND_GET_LINK_OFFS(tpf, new_link); - return true; -} +struct TrackPathFinder { + TPFEnumProc *enum_proc; + void *userdata; + RememberData rd; + TrackdirByte the_dir; +}; static void TPFModeShip(TrackPathFinder *tpf, TileIndex tile, DiagDirection direction) { - assert(tpf->tracktype == TRANSPORT_WATER); - if (IsTileType(tile, MP_TUNNELBRIDGE)) { /* wrong track type */ - if (GetTunnelBridgeTransportType(tile) != tpf->tracktype) return; + if (GetTunnelBridgeTransportType(tile) != TRANSPORT_WATER) return; DiagDirection dir = GetTunnelBridgeDirection(tile); /* entering tunnel / bridge? */ @@ -124,9 +42,6 @@ static void TPFModeShip(TrackPathFinder *tpf, TileIndex tile, DiagDirection dire tpf->rd.cur_length += GetTunnelBridgeLength(tile, endtile) + 1; - TPFSetTileBit(tpf, tile, 14); - TPFSetTileBit(tpf, endtile, 14); - tile = endtile; } else { /* leaving tunnel / bridge? */ @@ -142,7 +57,7 @@ static void TPFModeShip(TrackPathFinder *tpf, TileIndex tile, DiagDirection dire if (++tpf->rd.cur_length > 50) return; - TrackBits bits = TrackStatusToTrackBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type)) & DiagdirReachesTracks(direction); + TrackBits bits = TrackStatusToTrackBits(GetTileTrackStatus(tile, TRANSPORT_WATER, 0)) & DiagdirReachesTracks(direction); if (bits == TRACK_BIT_NONE) return; assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY()); @@ -173,106 +88,7 @@ static void TPFModeShip(TrackPathFinder *tpf, TileIndex tile, DiagDirection dire } -/** - * Checks if any vehicle can enter/leave tile in given diagdir - * Checks only for rail/road depots and road non-drivethrough stations - * @param tile tile to check - * @param side side of tile we are trying to leave/enter - * @param tracktype type of transport - * @pre tile has trackbit at that diagdir - * @return true iff vehicle can enter/leve the tile in given side - */ -static inline bool CanAccessTileInDir(TileIndex tile, DiagDirection side, TransportType tracktype) -{ - if (tracktype == TRANSPORT_RAIL) { - /* depot from wrong side */ - if (IsRailDepotTile(tile) && GetRailDepotDirection(tile) != side) return false; - } else if (tracktype == TRANSPORT_ROAD) { - /* depot from wrong side */ - if (IsRoadDepotTile(tile) && GetRoadDepotDirection(tile) != side) return false; - /* non-driverthrough road station from wrong side */ - if (IsStandardRoadStopTile(tile) && GetRoadStopDir(tile) != side) return false; - } - - return true; -} - -static void TPFModeNormal(TrackPathFinder *tpf, TileIndex tile, DiagDirection direction) -{ - const TileIndex tile_org = tile; - - if (IsTileType(tile, MP_TUNNELBRIDGE)) { - /* wrong track type */ - if (GetTunnelBridgeTransportType(tile) != tpf->tracktype) return; - - DiagDirection dir = GetTunnelBridgeDirection(tile); - /* entering tunnel / bridge? */ - if (dir == direction) { - TileIndex endtile = GetOtherTunnelBridgeEnd(tile); - - tpf->rd.cur_length += GetTunnelBridgeLength(tile, endtile) + 1; - - TPFSetTileBit(tpf, tile, 14); - TPFSetTileBit(tpf, endtile, 14); - - tile = endtile; - } else { - /* leaving tunnel / bridge? */ - if (ReverseDiagDir(dir) != direction) return; - } - } else { - /* can we leave tile in this dir? */ - if (!CanAccessTileInDir(tile, direction, tpf->tracktype)) return; - } - - tile += TileOffsByDiagDir(direction); - - /* can we enter tile in this dir? */ - if (!CanAccessTileInDir(tile, ReverseDiagDir(direction), tpf->tracktype)) 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 (GetTunnelBridgeDirection(tile) != direction || - GetTunnelBridgeTransportType(tile) != tpf->tracktype) { - return; - } - } - - TrackdirBits trackdirbits = TrackStatusToTrackdirBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type)); - - /* Check in case of rail if the owner is the same */ - if (tpf->tracktype == TRANSPORT_RAIL) { - if (trackdirbits != TRACKDIR_BIT_NONE && TrackStatusToTrackdirBits(GetTileTrackStatus(tile_org, TRANSPORT_RAIL, 0)) != TRACKDIR_BIT_NONE) { - if (GetTileOwner(tile_org) != GetTileOwner(tile)) return; - } - } - - tpf->rd.cur_length++; - - trackdirbits &= DiagdirReachesTrackdirs(direction); - TrackBits bits = TrackdirBitsToTrackBits(trackdirbits); - - if (bits != TRACK_BIT_NONE) { - if (!tpf->disable_tile_hash || (tpf->rd.cur_length <= 64 && (KillFirstBit(bits) == 0 || ++tpf->rd.depth <= 7))) { - do { - Track track = RemoveFirstTrack(&bits); - - tpf->the_dir = TrackEnterdirToTrackdir(track, direction); - RememberData rd = tpf->rd; - - /* make sure we are not leaving from invalid side */ - if (TPFSetTileBit(tpf, tile, tpf->the_dir) && CanAccessTileInDir(tile, TrackdirToExitdir(tpf->the_dir), tpf->tracktype) && - !tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length) ) { - TPFModeNormal(tpf, tile, TrackdirToExitdir(tpf->the_dir)); - } - tpf->rd = rd; - } while (bits != TRACK_BIT_NONE); - } - } -} - -void FollowTrack(TileIndex tile, PathfindFlags flags, TransportType tt, uint sub_type, DiagDirection direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data) +void OPFShipFollowTrack(TileIndex tile, DiagDirection direction, TPFEnumProc *enum_proc, void *data) { assert(IsValidDiagDirection(direction)); @@ -281,526 +97,11 @@ void FollowTrack(TileIndex tile, PathfindFlags flags, TransportType tt, uint sub /* 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.last_choosen_track = INVALID_TRACK; - tpf->disable_tile_hash = (flags & PATHFIND_FLAGS_DISABLE_TILE_HASH) != 0; - - tpf->tracktype = tt; - tpf->sub_type = sub_type; - - if ((flags & PATHFIND_FLAGS_SHIP_MODE) != 0) { - tpf->enum_proc(tile, data, INVALID_TRACKDIR, 0); - TPFModeShip(tpf, tile, direction); - } else { - /* clear the hash_heads */ - memset(tpf->hash_head, 0, sizeof(tpf->hash_head)); - TPFModeNormal(tpf, tile, direction); - } - - if (after_proc != NULL) after_proc(tpf); -} - -struct StackedItem { - 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. - TrackdirByte track; - byte depth; - byte state; - byte first_track; -}; - -struct HashLink { - TileIndex tile; - uint16 typelength; - uint16 next; -}; - -struct NewTrackPathFinder { - NTPEnumProc *enum_proc; - void *userdata; - TileIndex dest; - - TransportType tracktype; - RailTypes 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 - -}; -#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) == (uint)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) == (uint)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 uint DistanceMoo(TileIndex t0, TileIndex t1) -{ - const uint dx = Delta(TileX(t0), TileX(t1)); - const uint dy = Delta(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; - Trackdir 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, ReverseDiagDir(TrackdirToExitdir(ReverseTrackdir(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 = TrackdirToExitdir(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 (GetTunnelBridgeDirection(tile) != ReverseDiagDir(direction)) { - /* We are not just driving out of the tunnel/bridge */ - if (GetTunnelBridgeDirection(tile) != direction || - GetTunnelBridgeTransportType(tile) != tpf->tracktype) { - /* We are not driving into the tunnel/bridge, or it is an invalid tunnel/bridge */ - continue; - } - if (!HasBit(tpf->railtypes, GetRailType(tile))) { - bits = TRACK_BIT_NONE; - break; - } - - TileIndex endtile = GetOtherTunnelBridgeEnd(tile); - si.cur_length += DIAG_FACTOR * (GetTunnelBridgeLength(tile, endtile) + 1); - tile = endtile; - /* tile now points to the exit tile of the tunnel/bridge */ - } - } - - /* 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 = TRACK_BIT_NONE; - break; - } - - /* Not a regular rail tile? - * Then we can't use the code below, but revert to more general code. */ - if (!IsPlainRailTile(tile)) { - /* We found a tile which is not a normal railway tile. - * Determine which tracks that exist on this tile. */ - bits = TrackdirBitsToTrackBits(TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)) & DiagdirReachesTrackdirs(direction)); - - /* Check that the tile contains exactly one track */ - if (bits == 0 || KillFirstBit(bits) != 0) break; - - if (!HasBit(tpf->railtypes, GetRailType(tile))) { - bits = TRACK_BIT_NONE; - 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 = TrackEnterdirToTrackdir(FindFirstTrack(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 == TRACK_BIT_NONE || TracksOverlap(allbits)) break; - - if (!HasBit(tpf->railtypes, GetRailType(tile))) { - bits = TRACK_BIT_NONE; - break; - } - - /* If we reach here, the tile has exactly one track, and this - track is reachable = > Rail segment continues */ - - track = TrackEnterdirToTrackdir(FindFirstTrack(bits), direction); - assert(track != INVALID_TRACKDIR); - - si.cur_length += _length_of_track[track]; - - /* Check if this rail is an upwards slope. If it is, then add a penalty. */ - if (IsDiagonalTrackdir(track) && IsUphillTrackdir(GetTileSlope(tile, NULL), 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)) && IsOnewaySignal(tile, TrackdirToTrack(track))) { - bits = TRACK_BIT_NONE; - 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 = TRACK_BIT_NONE; - 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 = TrackdirToExitdir(track); - - /* safety check if we're running around chasing our tail... (infinite loop) */ - if (tile == tile_org) { - bits = TRACK_BIT_NONE; - break; - } - } - - /* There are no tracks to choose between. - * Stop searching in this direction */ - if (bits == TRACK_BIT_NONE) - 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; - while (bits != TRACK_BIT_NONE) { - Track track = RemoveFirstTrack(&bits); - si.track = TrackEnterdirToTrackdir(track, 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); - }; - - /* 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(tpf->stack[0].track, tpf->stack[1].track); - if (tpf->nstack != 2) { - TrackdirByte t = tpf->stack[2].track; - if (r & 2) Swap(tpf->stack[0].track, t); - if (r & 4) Swap(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, RailTypes railtypes, DiagDirection direction, NTPEnumProc *enum_proc, void *data) -{ - SmallStackSafeStackAlloc<NewTrackPathFinder, 1> tpf; - - tpf->dest = dest; - tpf->userdata = data; - tpf->enum_proc = enum_proc; - tpf->tracktype = TRANSPORT_RAIL; - tpf->railtypes = railtypes; - tpf->maxlength = min(_settings_game.pf.opf.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); + tpf->enum_proc(tile, data, INVALID_TRACKDIR, 0); + TPFModeShip(tpf, tile, direction); } diff --git a/src/pathfind.h b/src/pathfind.h index 6baedfa9a..a3bfefda2 100644 --- a/src/pathfind.h +++ b/src/pathfind.h @@ -16,76 +16,9 @@ #include "station_base.h" #include "waypoint_base.h" -enum { - STR_FACTOR = 2, - DIAG_FACTOR = 3 -}; - -//#define PF_BENCH // perform simple benchmarks on the train pathfinder (not -//supported on all archs) - -struct TrackPathFinder; typedef bool TPFEnumProc(TileIndex tile, void *data, Trackdir trackdir, uint length); -typedef void TPFAfterProc(TrackPathFinder *tpf); - -typedef bool NTPEnumProc(TileIndex tile, void *data, int track, uint length); - -#define PATHFIND_GET_LINK_OFFS(tpf, link) ((byte*)(link) - (byte*)tpf->links) -#define PATHFIND_GET_LINK_PTR(tpf, link_offs) (TrackPathFinderLink*)((byte*)tpf->links + (link_offs)) - -/* y7 y6 y5 y4 y3 y2 y1 y0 x7 x6 x5 x4 x3 x2 x1 x0 - * y7 y6 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0 0 0 0 - * 0 0 y7 y6 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0 0 - * 0 0 0 0 y5 y4 y3 y2 y1 y0 x4 x3 x2 x1 x0 0 - */ -#define PATHFIND_HASH_TILE(tile) (TileX(tile) & 0x1F) + ((TileY(tile) & 0x1F) << 5) - -struct TrackPathFinderLink { - TileIndex tile; - uint16 flags; - uint16 next; -}; - -struct RememberData { - uint16 cur_length; - byte depth; - Track last_choosen_track; -}; - -struct TrackPathFinder { - int num_links_left; - TrackPathFinderLink *new_link; - - TPFEnumProc *enum_proc; - - void *userdata; - - RememberData rd; - - TrackdirByte the_dir; - - TransportType tracktype; - uint sub_type; - - bool disable_tile_hash; - - uint16 hash_head[0x400]; - TileIndex hash_tile[0x400]; ///< stores the link index when multi link. - - TrackPathFinderLink links[0x400]; ///< hopefully, this is enough. -}; - -/** Some flags to modify the behaviour of original pathfinder */ -enum PathfindFlags { - PATHFIND_FLAGS_NONE = 0, - PATHFIND_FLAGS_SHIP_MODE = 0x0800, ///< pathfinder with some optimizations for ships, but does not work for other types. - PATHFIND_FLAGS_DISABLE_TILE_HASH = 0x1000, ///< do not check for searching in circles -}; -DECLARE_ENUM_AS_BIT_SET(PathfindFlags) - -void FollowTrack(TileIndex tile, PathfindFlags flags, TransportType tt, uint sub_type, DiagDirection direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data); -void NewTrainPathfind(TileIndex tile, TileIndex dest, RailTypes railtypes, DiagDirection direction, NTPEnumProc *enum_proc, void *data); +void OPFShipFollowTrack(TileIndex tile, DiagDirection direction, TPFEnumProc *enum_proc, void *data); /** * Calculates the tile of given station that is closest to a given tile diff --git a/src/roadveh_cmd.cpp b/src/roadveh_cmd.cpp index 49677d669..e6d90155e 100644 --- a/src/roadveh_cmd.cpp +++ b/src/roadveh_cmd.cpp @@ -375,21 +375,6 @@ static const DiagDirection _road_pf_directions[] = { DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE, INVALID_DIAGDIR, INVALID_DIAGDIR }; -static bool EnumRoadSignalFindDepot(TileIndex tile, void *data, Trackdir trackdir, uint length) -{ - RoadFindDepotData *rfdd = (RoadFindDepotData*)data; - - tile += TileOffsByDiagDir(_road_pf_directions[trackdir]); - - if (IsRoadDepotTile(tile) && - IsTileOwner(tile, rfdd->owner) && - length < rfdd->best_length) { - rfdd->best_length = length; - rfdd->tile = tile; - } - return false; -} - static RoadFindDepotData FindClosestRoadDepot(const RoadVehicle *v, int max_distance) { RoadFindDepotData rfdd; @@ -422,12 +407,7 @@ static RoadFindDepotData FindClosestRoadDepot(const RoadVehicle *v, int max_dist } break; default: - case VPF_OPF: // OPF - /* search in all directions */ - for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) { - FollowTrack(v->tile, PATHFIND_FLAGS_NONE, TRANSPORT_ROAD, v->compatible_roadtypes, d, EnumRoadSignalFindDepot, NULL, &rfdd); - } - break; + NOT_REACHED(); } return rfdd; // Target not found @@ -992,29 +972,8 @@ static int PickRandomBit(uint bits) return i; } -struct FindRoadToChooseData { - TileIndex dest; - uint maxtracklen; - uint mindist; -}; - -static bool EnumRoadTrackFindDist(TileIndex tile, void *data, Trackdir trackdir, uint length) -{ - FindRoadToChooseData *frd = (FindRoadToChooseData*)data; - uint dist = DistanceManhattan(tile, frd->dest); - - if (dist <= frd->mindist) { - if (dist != frd->mindist || length < frd->maxtracklen) { - frd->maxtracklen = length; - } - frd->mindist = dist; - } - return false; -} - static inline NPFFoundTargetData PerfNPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData *target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) { - void *perf = NpfBeginInterval(); NPFFoundTargetData ret = NPFRouteToStationOrTile(tile, trackdir, ignore_start_tile, target, type, sub_type, owner, railtypes); int t = NpfEndInterval(perf); @@ -1035,7 +994,6 @@ static Trackdir RoadFindPathToDest(RoadVehicle *v, TileIndex tile, DiagDirection #define return_track(x) { best_track = (Trackdir)x; goto found_best_track; } TileIndex desttile; - FindRoadToChooseData frd; Trackdir best_track; TrackStatus ts = GetTileTrackStatus(tile, TRANSPORT_ROAD, v->compatible_roadtypes); @@ -1141,52 +1099,7 @@ static Trackdir RoadFindPathToDest(RoadVehicle *v, TileIndex tile, DiagDirection } break; default: - case VPF_OPF: { // OPF - DiagDirection dir; - - if (IsTileType(desttile, MP_ROAD)) { - if (IsRoadDepot(desttile)) { - dir = GetRoadDepotDirection(desttile); - goto do_it; - } - } else if (IsTileType(desttile, MP_STATION)) { - /* For drive-through stops we can head for the actual station tile */ - if (IsStandardRoadStopTile(desttile)) { - dir = GetRoadStopDir(desttile); -do_it:; - /* When we are heading for a depot or station, we just - * pretend we are heading for the tile in front, we'll - * see from there */ - desttile += TileOffsByDiagDir(dir); - if (desttile == tile && (trackdirs & _road_exit_dir_to_incoming_trackdirs[dir])) { - /* If we are already in front of the - * station/depot and we can get in from here, - * we enter */ - return_track(FindFirstBit2x64(trackdirs & _road_exit_dir_to_incoming_trackdirs[dir])); - } - } - } - /* Do some pathfinding */ - frd.dest = desttile; - - best_track = INVALID_TRACKDIR; - uint best_dist = UINT_MAX; - uint best_maxlen = UINT_MAX; - uint bitmask = (uint)trackdirs; - uint i; - FOR_EACH_SET_BIT(i, bitmask) { - if (best_track == INVALID_TRACKDIR) best_track = (Trackdir)i; // in case we don't find the path, just pick a track - frd.maxtracklen = UINT_MAX; - frd.mindist = UINT_MAX; - FollowTrack(tile, PATHFIND_FLAGS_NONE, TRANSPORT_ROAD, v->compatible_roadtypes, _road_pf_directions[i], EnumRoadTrackFindDist, NULL, &frd); - - if (frd.mindist < best_dist || (frd.mindist == best_dist && frd.maxtracklen < best_maxlen)) { - best_dist = frd.mindist; - best_maxlen = frd.maxtracklen; - best_track = (Trackdir)i; - } - } - } break; + NOT_REACHED(); } found_best_track:; diff --git a/src/saveload/afterload.cpp b/src/saveload/afterload.cpp index 9b35c498b..7be54d327 100644 --- a/src/saveload/afterload.cpp +++ b/src/saveload/afterload.cpp @@ -1556,13 +1556,13 @@ bool AfterLoadGame() if (_settings_game.pf.yapf.rail_use_yapf || CheckSavegameVersion(28)) { _settings_game.pf.pathfinder_for_trains = VPF_YAPF; } else { - _settings_game.pf.pathfinder_for_trains = (_settings_game.pf.new_pathfinding_all ? VPF_NPF : VPF_NTP); + _settings_game.pf.pathfinder_for_trains = VPF_NPF; } if (_settings_game.pf.yapf.road_use_yapf || CheckSavegameVersion(28)) { _settings_game.pf.pathfinder_for_roadvehs = VPF_YAPF; } else { - _settings_game.pf.pathfinder_for_roadvehs = (_settings_game.pf.new_pathfinding_all ? VPF_NPF : VPF_OPF); + _settings_game.pf.pathfinder_for_roadvehs = VPF_NPF; } if (_settings_game.pf.yapf.ship_use_yapf) { diff --git a/src/ship_cmd.cpp b/src/ship_cmd.cpp index 27049a78f..2b7105e7e 100644 --- a/src/ship_cmd.cpp +++ b/src/ship_cmd.cpp @@ -430,7 +430,7 @@ static uint FindShipTrack(Vehicle *v, TileIndex tile, DiagDirection dir, TrackBi pfs.best_bird_dist = UINT_MAX; pfs.best_length = UINT_MAX; - FollowTrack(tile, PATHFIND_FLAGS_SHIP_MODE | PATHFIND_FLAGS_DISABLE_TILE_HASH, TRANSPORT_WATER, 0, (DiagDirection)_ship_search_directions[i][dir], (TPFEnumProc*)ShipTrackFollower, NULL, &pfs); + OPFShipFollowTrack(tile, (DiagDirection)_ship_search_directions[i][dir], (TPFEnumProc*)ShipTrackFollower, &pfs); if (best_track != INVALID_TRACK) { if (pfs.best_bird_dist != 0) { diff --git a/src/table/settings.h b/src/table/settings.h index ad784dab4..7ae041cb3 100644 --- a/src/table/settings.h +++ b/src/table/settings.h @@ -381,8 +381,8 @@ const SettingDesc _settings[] = { SDT_CONDBOOL(GameSettings, pf.yapf.road_use_yapf, 28, 86, 0, 0, true, STR_NULL, NULL), SDT_CONDBOOL(GameSettings, pf.yapf.rail_use_yapf, 28, 86, 0, 0, true, STR_NULL, NULL), - SDT_CONDVAR(GameSettings, pf.pathfinder_for_trains, SLE_UINT8, 87, SL_MAX_VERSION, 0, MS, 2, 0, 2, 1, STR_CONFIG_SETTING_PATHFINDER_FOR_TRAINS, NULL), - SDT_CONDVAR(GameSettings, pf.pathfinder_for_roadvehs, SLE_UINT8, 87, SL_MAX_VERSION, 0, MS, 2, 0, 2, 1, STR_CONFIG_SETTING_PATHFINDER_FOR_ROAD_VEHICLES, NULL), + SDT_CONDVAR(GameSettings, pf.pathfinder_for_trains, SLE_UINT8, 87, SL_MAX_VERSION, 0, MS, 2, 1, 2, 1, STR_CONFIG_SETTING_PATHFINDER_FOR_TRAINS, NULL), + SDT_CONDVAR(GameSettings, pf.pathfinder_for_roadvehs, SLE_UINT8, 87, SL_MAX_VERSION, 0, MS, 2, 1, 2, 1, STR_CONFIG_SETTING_PATHFINDER_FOR_ROAD_VEHICLES, NULL), SDT_CONDVAR(GameSettings, pf.pathfinder_for_ships, SLE_UINT8, 87, SL_MAX_VERSION, 0, MS, 0, 0, 2, 1, STR_CONFIG_SETTING_PATHFINDER_FOR_SHIPS, NULL), SDT_BOOL(GameSettings, vehicle.never_expire_vehicles, 0,NN, false, STR_CONFIG_SETTING_NEVER_EXPIRE_VEHICLES, NULL), diff --git a/src/train_cmd.cpp b/src/train_cmd.cpp index 2cc9a5d0a..480a59017 100644 --- a/src/train_cmd.cpp +++ b/src/train_cmd.cpp @@ -2149,20 +2149,6 @@ struct TrainFindDepotData { bool reverse; }; -static bool NtpCallbFindDepot(TileIndex tile, TrainFindDepotData *tfdd, int track, uint length) -{ - if (IsTileType(tile, MP_RAILWAY) && - IsTileOwner(tile, tfdd->owner) && - IsRailDepot(tile)) { - /* approximate number of tiles by dividing by DIAG_FACTOR */ - tfdd->best_length = length / DIAG_FACTOR; - tfdd->tile = tile; - return true; - } - - return false; -} - /** returns the tile of a depot to goto to. The given vehicle must not be * crashed! */ static TrainFindDepotData FindClosestTrainDepot(Train *v, int max_distance) @@ -2188,10 +2174,7 @@ static TrainFindDepotData FindClosestTrainDepot(Train *v, int max_distance) tfdd.best_length = UINT_MAX; - uint8 pathfinder = _settings_game.pf.pathfinder_for_trains; - if ((_settings_game.pf.reserve_paths || HasReservedTracks(v->tile, v->track)) && pathfinder == VPF_NTP) pathfinder = VPF_NPF; - - switch (pathfinder) { + switch (_settings_game.pf.pathfinder_for_trains) { case VPF_YAPF: { // YAPF bool found = YapfFindNearestRailDepotTwoWay(v, max_distance, NPF_INFINITE_PENALTY, &tfdd.tile, &tfdd.reverse); tfdd.best_length = found ? max_distance / 2 : UINT_MAX; // some fake distance or NOT_FOUND @@ -2217,17 +2200,7 @@ static TrainFindDepotData FindClosestTrainDepot(Train *v, int max_distance) } break; default: - case VPF_NTP: { // NTP - /* search in the forward direction first. */ - DiagDirection i = TrainExitDir(v->direction, v->track); - NewTrainPathfind(v->tile, 0, v->compatible_railtypes, i, (NTPEnumProc*)NtpCallbFindDepot, &tfdd); - if (tfdd.best_length == UINT_MAX) { - tfdd.reverse = true; - /* search in backwards direction */ - i = TrainExitDir(ReverseDir(v->direction), v->track); - NewTrainPathfind(v->tile, 0, v->compatible_railtypes, i, (NTPEnumProc*)NtpCallbFindDepot, &tfdd); - } - } break; + NOT_REACHED(); } return tfdd; @@ -2395,7 +2368,7 @@ static void CheckNextTrainTile(Train *v) if (HasPbsSignalOnTrackdir(ft.m_new_tile, FindFirstTrackdir(ft.m_new_td_bits))) { /* If the next tile is a PBS signal, try to make a reservation. */ TrackBits tracks = TrackdirBitsToTrackBits(ft.m_new_td_bits); - if (_settings_game.pf.pathfinder_for_trains != VPF_NTP && _settings_game.pf.forbid_90_deg) { + if (_settings_game.pf.forbid_90_deg) { tracks &= ~TrackCrossesTracks(TrackdirToTrack(ft.m_old_td)); } ChooseTrainTrack(v, ft.m_new_tile, ft.m_exitdir, tracks, false, NULL, false); @@ -2562,50 +2535,6 @@ void FreeTrainTrackReservation(const Train *v, TileIndex origin, Trackdir orig_t } } -/** Check for station tiles */ -struct TrainTrackFollowerData { - TileIndex dest_coords; - StationID station_index; ///< station index we're heading for - uint best_bird_dist; - uint best_track_dist; - TrackdirByte best_track; -}; - -static bool NtpCallbFindStation(TileIndex tile, TrainTrackFollowerData *ttfd, Trackdir track, uint length) -{ - /* heading for nowhere? */ - if (ttfd->dest_coords == 0) return false; - - /* did we reach the final station? */ - if ((ttfd->station_index == INVALID_STATION && tile == ttfd->dest_coords) || ( - IsRailStationTile(tile) && - GetStationIndex(tile) == ttfd->station_index - )) { - /* We do not check for dest_coords if we have a station_index, - * because in that case the dest_coords are just an - * approximation of where the station is */ - - /* found station */ - ttfd->best_track = track; - ttfd->best_bird_dist = 0; - return true; - } else { - /* didn't find station, keep track of the best path so far. */ - uint dist = DistanceManhattan(tile, ttfd->dest_coords); - if (dist < ttfd->best_bird_dist) { - ttfd->best_bird_dist = dist; - ttfd->best_track = track; - } - return false; - } -} - -static void FillWithStationData(TrainTrackFollowerData *fd, const Vehicle *v) -{ - fd->dest_coords = v->dest_tile; - fd->station_index = v->current_order.IsType(OT_GOTO_STATION) ? v->current_order.GetDestination() : INVALID_STATION; -} - static const byte _initial_tile_subcoord[6][4][3] = { {{ 15, 8, 1 }, { 0, 0, 0 }, { 0, 8, 5 }, { 0, 0, 0 }}, {{ 0, 0, 0 }, { 8, 0, 3 }, { 0, 0, 0 }, { 8, 15, 7 }}, @@ -2615,17 +2544,6 @@ static const byte _initial_tile_subcoord[6][4][3] = { {{ 0, 0, 0 }, { 0, 0, 0 }, { 0, 8, 4 }, { 7, 15, 0 }}, }; -static const byte _search_directions[6][4] = { - { 0, 9, 2, 9 }, ///< track 1 - { 9, 1, 9, 3 }, ///< track 2 - { 9, 0, 3, 9 }, ///< track upper - { 1, 9, 9, 2 }, ///< track lower - { 3, 2, 9, 9 }, ///< track left - { 9, 9, 1, 0 }, ///< track right -}; - -static const byte _pick_track_table[6] = {1, 3, 2, 2, 0, 0}; - /** * Perform pathfinding for a train. * @@ -2648,10 +2566,7 @@ static Track DoTrainPathfind(Train *v, TileIndex tile, DiagDirection enterdir, T if (path_not_found) *path_not_found = false; - uint8 pathfinder = _settings_game.pf.pathfinder_for_trains; - if (do_track_reservation && pathfinder == VPF_NTP) pathfinder = VPF_NPF; - - switch (pathfinder) { + switch (_settings_game.pf.pathfinder_for_trains) { case VPF_YAPF: { // YAPF Trackdir trackdir = YapfChooseRailTrack(v, tile, enterdir, tracks, path_not_found, do_track_reservation, dest); if (trackdir != INVALID_TRACKDIR) { @@ -2698,33 +2613,7 @@ static Track DoTrainPathfind(Train *v, TileIndex tile, DiagDirection enterdir, T } break; default: - case VPF_NTP: { // NTP - void *perf = NpfBeginInterval(); - - TrainTrackFollowerData fd; - FillWithStationData(&fd, v); - - /* New train pathfinding */ - fd.best_bird_dist = UINT_MAX; - fd.best_track_dist = UINT_MAX; - fd.best_track = INVALID_TRACKDIR; - - NewTrainPathfind(tile - TileOffsByDiagDir(enterdir), v->dest_tile, - v->compatible_railtypes, enterdir, (NTPEnumProc*)NtpCallbFindStation, &fd); - - /* check whether the path was found or only 'guessed' */ - if (fd.best_bird_dist != 0 && path_not_found != NULL) *path_not_found = true; - - if (fd.best_track == INVALID_TRACKDIR) { - /* blaha */ - best_track = FindFirstTrack(tracks); - } else { - best_track = TrackdirToTrack(fd.best_track); - } - - int time = NpfEndInterval(perf); - DEBUG(yapf, 4, "[NTPT] %d us - %d rounds - %d open - %d closed -- ", time, 0, 0, 0); - } break; + NOT_REACHED(); } #ifdef PF_BENCHMARK @@ -2741,7 +2630,6 @@ static Track DoTrainPathfind(Train *v, TileIndex tile, DiagDirection enterdir, T */ static PBSTileInfo ExtendTrainReservation(const Train *v, TrackBits *new_tracks, DiagDirection *enterdir) { - bool no_90deg_turns = _settings_game.pf.pathfinder_for_trains != VPF_NTP && _settings_game.pf.forbid_90_deg; PBSTileInfo origin = FollowTrainReservation(v); CFollowTrackRail ft(v); @@ -2754,7 +2642,7 @@ static PBSTileInfo ExtendTrainReservation(const Train *v, TrackBits *new_tracks, if (HasOnewaySignalBlockingTrackdir(ft.m_new_tile, FindFirstTrackdir(ft.m_new_td_bits))) break; } - if (no_90deg_turns) { + if (_settings_game.pf.forbid_90_deg) { ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(ft.m_old_td); if (ft.m_new_td_bits == TRACKDIR_BIT_NONE) break; } @@ -2783,8 +2671,8 @@ static PBSTileInfo ExtendTrainReservation(const Train *v, TrackBits *new_tracks, tile = ft.m_new_tile; cur_td = FindFirstTrackdir(ft.m_new_td_bits); - if (IsSafeWaitingPosition(v, tile, cur_td, true, no_90deg_turns)) { - bool wp_free = IsWaitingPositionFree(v, tile, cur_td, no_90deg_turns); + if (IsSafeWaitingPosition(v, tile, cur_td, true, _settings_game.pf.forbid_90_deg)) { + bool wp_free = IsWaitingPositionFree(v, tile, cur_td, _settings_game.pf.forbid_90_deg); if (!(wp_free && TryReserveRailTrack(tile, TrackdirToTrack(cur_td)))) break; /* Safe position is all good, path valid and okay. */ return PBSTileInfo(tile, cur_td, true); @@ -2806,7 +2694,7 @@ static PBSTileInfo ExtendTrainReservation(const Train *v, TrackBits *new_tracks, while (tile != stopped || cur_td != stopped_td) { if (!ft.Follow(tile, cur_td)) break; - if (no_90deg_turns) { + if (_settings_game.pf.forbid_90_deg) { ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(ft.m_old_td); assert(ft.m_new_td_bits != TRACKDIR_BIT_NONE); } @@ -3056,7 +2944,7 @@ static Track ChooseTrainTrack(Train *v, TileIndex tile, DiagDirection enterdir, DiagDirection exitdir = TrackdirToExitdir(res_dest.trackdir); TileIndex next_tile = TileAddByDiagDir(res_dest.tile, exitdir); TrackBits reachable = TrackdirBitsToTrackBits((TrackdirBits)(GetTileTrackStatus(next_tile, TRANSPORT_RAIL, 0))) & DiagdirReachesTracks(exitdir); - if (_settings_game.pf.pathfinder_for_trains != VPF_NTP && _settings_game.pf.forbid_90_deg) { + if (_settings_game.pf.forbid_90_deg) { reachable &= ~TrackCrossesTracks(TrackdirToTrack(res_dest.trackdir)); } @@ -3161,7 +3049,7 @@ bool TryPathReserve(Train *v, bool mark_as_stuck, bool first_tile_okay) TileIndex new_tile = TileAddByDiagDir(origin.tile, exitdir); TrackBits reachable = TrackdirBitsToTrackBits(TrackStatusToTrackdirBits(GetTileTrackStatus(new_tile, TRANSPORT_RAIL, 0)) & DiagdirReachesTrackdirs(exitdir)); - if (_settings_game.pf.pathfinder_for_trains != VPF_NTP && _settings_game.pf.forbid_90_deg) reachable &= ~TrackCrossesTracks(TrackdirToTrack(origin.trackdir)); + if (_settings_game.pf.forbid_90_deg) reachable &= ~TrackCrossesTracks(TrackdirToTrack(origin.trackdir)); bool res_made = false; ChooseTrainTrack(v, new_tile, exitdir, reachable, true, &res_made, mark_as_stuck); @@ -3189,14 +3077,11 @@ static bool CheckReverseTrain(Train *v) return false; } - uint reverse_best = 0; - assert(v->track); switch (_settings_game.pf.pathfinder_for_trains) { case VPF_YAPF: // YAPF - reverse_best = YapfCheckReverseTrain(v); - break; + return YapfCheckReverseTrain(v); case VPF_NPF: { // NPF NPFFindStationOrTileData fstd; @@ -3211,77 +3096,13 @@ static bool CheckReverseTrain(Train *v) assert(trackdir_rev != INVALID_TRACKDIR); ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, &fstd, TRANSPORT_RAIL, 0, v->owner, v->compatible_railtypes); - if (ftd.best_bird_dist != 0) { - /* We didn't find anything, just keep on going straight ahead */ - reverse_best = false; - } else { - if (NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)) { - reverse_best = true; - } else { - reverse_best = false; - } - } + /* If we didn't find anything, just keep on going straight ahead, otherwise take the reverse flag */ + return ftd.best_bird_dist != 0 && NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE); } break; default: - case VPF_NTP: { // NTP - TrainTrackFollowerData fd; - FillWithStationData(&fd, v); - - int i = _search_directions[FindFirstTrack(v->track)][DirToDiagDir(v->direction)]; - - int best_track = -1; - uint reverse = 0; - uint best_bird_dist = 0; - uint best_track_dist = 0; - - for (;;) { - fd.best_bird_dist = UINT_MAX; - fd.best_track_dist = UINT_MAX; - - NewTrainPathfind(v->tile, v->dest_tile, v->compatible_railtypes, (DiagDirection)(reverse ^ i), (NTPEnumProc*)NtpCallbFindStation, &fd); - - if (best_track != -1) { - if (best_bird_dist != 0) { - if (fd.best_bird_dist != 0) { - /* neither reached the destination, pick the one with the smallest bird dist */ - if (fd.best_bird_dist > best_bird_dist) goto bad; - if (fd.best_bird_dist < best_bird_dist) goto good; - } else { - /* we found the destination for the first time */ - goto good; - } - } else { - if (fd.best_bird_dist != 0) { - /* didn't find destination, but we've found the destination previously */ - goto bad; - } else { - /* both old & new reached the destination, compare track length */ - if (fd.best_track_dist > best_track_dist) goto bad; - if (fd.best_track_dist < best_track_dist) goto good; - } - } - - /* if we reach this position, there's two paths of equal value so far. - * pick one randomly. */ - int r = GB(Random(), 0, 8); - if (_pick_track_table[i] == (v->direction & 3)) r += 80; - if (_pick_track_table[best_track] == (v->direction & 3)) r -= 80; - if (r <= 127) goto bad; - } -good:; - best_track = i; - best_bird_dist = fd.best_bird_dist; - best_track_dist = fd.best_track_dist; - reverse_best = reverse; -bad:; - if (reverse != 0) break; - reverse = 2; - } - } break; + NOT_REACHED(); } - - return reverse_best != 0; } TileIndex Train::GetOrderStationLocation(StationID station) @@ -3714,7 +3535,7 @@ static void TrainController(Train *v, Vehicle *nomove) TrackBits red_signals = TrackdirBitsToTrackBits(TrackStatusToRedSignals(ts) & reachable_trackdirs); TrackBits bits = TrackdirBitsToTrackBits(trackdirbits); - if (_settings_game.pf.pathfinder_for_trains != VPF_NTP && _settings_game.pf.forbid_90_deg && prev == NULL) { + if (_settings_game.pf.forbid_90_deg && prev == NULL) { /* We allow wagons to make 90 deg turns, because forbid_90_deg * can be switched on halfway a turn */ bits &= ~TrackCrossesTracks(FindFirstTrack(v->track)); @@ -4279,7 +4100,7 @@ static bool TrainCheckIfLineEnds(Train *v) /* mask unreachable track bits if we are forbidden to do 90deg turns */ TrackBits bits = TrackdirBitsToTrackBits(trackdirbits); - if (_settings_game.pf.pathfinder_for_trains != VPF_NTP && _settings_game.pf.forbid_90_deg) { + if (_settings_game.pf.forbid_90_deg) { bits &= ~TrackCrossesTracks(FindFirstTrack(v->track)); } diff --git a/src/vehicle_type.h b/src/vehicle_type.h index 1d99ea897..0ccc37e29 100644 --- a/src/vehicle_type.h +++ b/src/vehicle_type.h @@ -48,8 +48,7 @@ static const VehicleID INVALID_VEHICLE = 0xFFFF; ///< Constant representing a no /** Pathfinding option states */ enum { - VPF_OPF = 0, ///< The Original PathFinder - VPF_NTP = 0, ///< New Train Pathfinder, replacing OPF for trains + VPF_OPF = 0, ///< The Original PathFinder (only for ships) VPF_NPF = 1, ///< New PathFinder VPF_YAPF = 2, ///< Yet Another PathFinder }; |