|
@@ -109,39 +109,12 @@ static bool TPFSetTileBit(TrackPathFinde
|
|
|
new_link->next = 0xFFFF;
|
|
|
|
|
|
link->next = PATHFIND_GET_LINK_OFFS(tpf, new_link);
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
static const byte _bits_mask[4] = {
|
|
|
0x19,
|
|
|
0x16,
|
|
|
0x25,
|
|
|
0x2A,
|
|
|
};
|
|
|
|
|
|
static const DiagDirection _tpf_new_direction[14] = {
|
|
|
DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SW, DIAGDIR_SE,
|
|
|
INVALID_DIAGDIR, INVALID_DIAGDIR,
|
|
|
DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE,
|
|
|
};
|
|
|
|
|
|
static const DiagDirection _tpf_prev_direction[14] = {
|
|
|
DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SE, DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SW,
|
|
|
INVALID_DIAGDIR, INVALID_DIAGDIR,
|
|
|
DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE, DIAGDIR_NW,
|
|
|
};
|
|
|
|
|
|
|
|
|
static const byte _otherdir_mask[4] = {
|
|
|
0x10,
|
|
|
0,
|
|
|
0x5,
|
|
|
0x2A,
|
|
|
};
|
|
|
|
|
|
static void TPFModeShip(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
|
|
|
{
|
|
|
RememberData rd;
|
|
|
|
|
|
assert(tpf->tracktype == TRANSPORT_WATER);
|
|
|
|
|
@@ -150,14 +123,13 @@ static void TPFModeShip(TrackPathFinder*
|
|
|
* tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail. */
|
|
|
tile = TILE_MASK(tile + TileOffsByDiagDir(direction));
|
|
|
|
|
|
if (++tpf->rd.cur_length > 50)
|
|
|
return;
|
|
|
|
|
|
TrackStatus ts = GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type);
|
|
|
TrackBits bits = (TrackBits)(TrackStatusToTrackBits(ts) & _bits_mask[direction]);
|
|
|
TrackBits bits = TrackStatusToTrackBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type)) & DiagdirReachesTracks(direction);
|
|
|
if (bits == TRACK_BIT_NONE) return;
|
|
|
|
|
|
assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY());
|
|
|
|
|
|
bool only_one_track = true;
|
|
|
do {
|
|
@@ -171,16 +143,16 @@ static void TPFModeShip(TrackPathFinder*
|
|
|
tpf->rd = rd;
|
|
|
return;
|
|
|
}
|
|
|
tpf->rd.last_choosen_track = track;
|
|
|
}
|
|
|
|
|
|
tpf->the_dir = (Trackdir)(track + (HasBit(_otherdir_mask[direction], track) ? 8 : 0));
|
|
|
tpf->the_dir = TrackEnterdirToTrackdir(track, direction);
|
|
|
|
|
|
if (!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length)) {
|
|
|
TPFModeShip(tpf, tile, _tpf_new_direction[tpf->the_dir]);
|
|
|
TPFModeShip(tpf, tile, TrackdirToExitdir(tpf->the_dir));
|
|
|
}
|
|
|
|
|
|
tpf->rd = rd;
|
|
|
} while (bits != TRACK_BIT_NONE);
|
|
|
|
|
|
}
|
|
@@ -206,14 +178,12 @@ static inline bool CanAccessTileInDir(Ti
|
|
|
if (IsStandardRoadStopTile(tile) && GetRoadStopDir(tile) != side) return false;
|
|
|
}
|
|
|
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
static const uint16 _tpfmode1_and[4] = { 0x1009, 0x16, 0x520, 0x2A00 };
|
|
|
|
|
|
static void TPFModeNormal(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction)
|
|
|
{
|
|
|
const TileIndex tile_org = tile;
|
|
|
|
|
|
if (IsTileType(tile, MP_TUNNELBRIDGE)) {
|
|
|
/* wrong track type */
|
|
@@ -250,43 +220,41 @@ static void TPFModeNormal(TrackPathFinde
|
|
|
if (GetTunnelBridgeDirection(tile) != direction ||
|
|
|
GetTunnelBridgeTransportType(tile) != tpf->tracktype) {
|
|
|
return;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
uint32 bits = TrackStatusToTrackdirBits(GetTileTrackStatus(tile, tpf->tracktype, tpf->sub_type));
|
|
|
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 (bits != 0 && TrackStatusToTrackdirBits(GetTileTrackStatus(tile_org, TRANSPORT_RAIL, 0)) != TRACKDIR_BIT_NONE) {
|
|
|
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++;
|
|
|
|
|
|
bits &= _tpfmode1_and[direction];
|
|
|
bits |= bits >> 8;
|
|
|
bits &= 0xBF;
|
|
|
trackdirbits &= DiagdirReachesTrackdirs(direction);
|
|
|
TrackBits bits = TrackdirBitsToTrackBits(trackdirbits);
|
|
|
|
|
|
if (bits != 0) {
|
|
|
if (bits != TRACK_BIT_NONE) {
|
|
|
if (!tpf->disable_tile_hash || (tpf->rd.cur_length <= 64 && (KillFirstBit(bits) == 0 || ++tpf->rd.depth <= 7))) {
|
|
|
do {
|
|
|
int i = FIND_FIRST_BIT(bits);
|
|
|
bits = KillFirstBit(bits);
|
|
|
Track track = RemoveFirstTrack(&bits);
|
|
|
|
|
|
tpf->the_dir = (Trackdir)((_otherdir_mask[direction] & (byte)(1 << i)) ? (i + 8) : i);
|
|
|
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, _tpf_new_direction[tpf->the_dir]);
|
|
|
TPFModeNormal(tpf, tile, TrackdirToExitdir(tpf->the_dir));
|
|
|
}
|
|
|
tpf->rd = rd;
|
|
|
} while (bits != 0);
|
|
|
} 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)
|
|
|
{
|
|
@@ -328,21 +296,12 @@ struct StackedItem {
|
|
|
TrackdirByte track;
|
|
|
byte depth;
|
|
|
byte state;
|
|
|
byte first_track;
|
|
|
};
|
|
|
|
|
|
static const Trackdir _new_trackdir[6][4] = {
|
|
|
{TRACKDIR_X_NE, INVALID_TRACKDIR, TRACKDIR_X_SW, INVALID_TRACKDIR,},
|
|
|
{INVALID_TRACKDIR, TRACKDIR_Y_SE, INVALID_TRACKDIR, TRACKDIR_Y_NW,},
|
|
|
{INVALID_TRACKDIR, TRACKDIR_UPPER_E, TRACKDIR_UPPER_W, INVALID_TRACKDIR,},
|
|
|
{TRACKDIR_LOWER_E, INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_LOWER_W,},
|
|
|
{TRACKDIR_LEFT_N, TRACKDIR_LEFT_S, INVALID_TRACKDIR, INVALID_TRACKDIR,},
|
|
|
{INVALID_TRACKDIR, INVALID_TRACKDIR, TRACKDIR_RIGHT_S, TRACKDIR_RIGHT_N,},
|
|
|
};
|
|
|
|
|
|
struct HashLink {
|
|
|
TileIndex tile;
|
|
|
uint16 typelength;
|
|
|
uint16 next;
|
|
|
};
|
|
|
|
|
@@ -587,23 +546,23 @@ static void NTPEnum(NewTrackPathFinder*
|
|
|
return; // nothing left? then we're done!
|
|
|
si = tpf->stack[0];
|
|
|
tile = si.tile;
|
|
|
|
|
|
HeapifyDown(tpf);
|
|
|
/* Make sure we havn't already visited this tile. */
|
|
|
} while (!NtpCheck(tpf, tile, _tpf_prev_direction[si.track], si.cur_length));
|
|
|
} 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 = _tpf_new_direction[si.track];
|
|
|
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)) {
|
|
@@ -641,14 +600,13 @@ start_at:
|
|
|
|
|
|
/* Not a regular rail tile?
|
|
|
* Then we can't use the code below, but revert to more general code. */
|
|
|
if (!IsTileType(tile, MP_RAILWAY) || !IsPlainRailTile(tile)) {
|
|
|
/* We found a tile which is not a normal railway tile.
|
|
|
* Determine which tracks that exist on this tile. */
|
|
|
TrackStatus ts = GetTileTrackStatus(tile, TRANSPORT_RAIL, 0) & _tpfmode1_and[direction];
|
|
|
bits = TrackStatusToTrackBits(ts);
|
|
|
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;
|
|
@@ -658,13 +616,13 @@ start_at:
|
|
|
/*******************
|
|
|
* If we reach here, the tile has exactly one track.
|
|
|
* tile - index to a tile that is not rail tile, but still straight (with optional signals)
|
|
|
* bits - bitmask of which track that exist on the tile (exactly one bit is set)
|
|
|
* direction - which direction are we moving in?
|
|
|
*******************/
|
|
|
si.track = _new_trackdir[FIND_FIRST_BIT(bits)][direction];
|
|
|
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);
|
|
@@ -681,13 +639,13 @@ start_at:
|
|
|
break;
|
|
|
}
|
|
|
|
|
|
/* If we reach here, the tile has exactly one track, and this
|
|
|
track is reachable = > Rail segment continues */
|
|
|
|
|
|
track = _new_trackdir[FIND_FIRST_BIT(bits)][direction];
|
|
|
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)) {
|
|
@@ -730,13 +688,13 @@ start_at:
|
|
|
|
|
|
if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length))
|
|
|
return; // Don't process this tile any further
|
|
|
}
|
|
|
|
|
|
/* continue with the next track */
|
|
|
direction = _tpf_new_direction[track];
|
|
|
direction = TrackdirToExitdir(track);
|
|
|
|
|
|
/* safety check if we're running around chasing our tail... (infinite loop) */
|
|
|
if (tile == tile_org) {
|
|
|
bits = TRACK_BIT_NONE;
|
|
|
break;
|
|
|
}
|
|
@@ -771,13 +729,13 @@ start_at:
|
|
|
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 = _new_trackdir[track][direction];
|
|
|
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");
|