summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/lang/english.txt2
-rw-r--r--src/pathfind.cpp731
-rw-r--r--src/pathfind.h69
-rw-r--r--src/roadveh_cmd.cpp91
-rw-r--r--src/saveload/afterload.cpp4
-rw-r--r--src/ship_cmd.cpp2
-rw-r--r--src/table/settings.h4
-rw-r--r--src/train_cmd.cpp213
-rw-r--r--src/vehicle_type.h3
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
};