@@ -12,31 +12,40 @@
AyStar _npf_aystar;
/* The cost of each trackdir. A diagonal piece is the full NPF_TILE_LENGTH,
* the shorter piece is sqrt(2)/2*NPF_TILE_LENGTH =~ 0.7071
*/
#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)
static const uint _trackdir_length[14] = {
static const uint _trackdir_length[TRACKDIR_END] = {
NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH,
0, 0,
NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH
};
uint NTPHash(uint key1, uint key2)
{
/* This function uses the old hash, which is fixed on 10 bits (1024 buckets) */
return PATHFIND_HASH_TILE(key1);
}
/**
* Calculates a hash value for use in the NPF.
* @param key1 The TileIndex of the tile to hash
* @param key1 The Trackdir of the track on the tile.
*
* @todo Think of a better hash.
uint NPFHash(uint key1, uint key2)
/* TODO: think of a better hash? */
uint part1 = TileX(key1) & NPF_HASH_HALFMASK;
uint part2 = TileY(key1) & NPF_HASH_HALFMASK;
/* The value of 14 below is based on the maximum value of key2 (13) */
return ((((part1 << NPF_HASH_HALFBITS) | part2)) + (NPF_HASH_SIZE * key2 / 14)) % NPF_HASH_SIZE;
assert(IsValidTrackdir(key2));
assert(IsValidTile(key1));
return ((((part1 << NPF_HASH_HALFBITS) | part2)) + (NPF_HASH_SIZE * key2 / TRACKDIR_END)) % NPF_HASH_SIZE;
int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent) {
return 0;
@@ -108,13 +117,13 @@ int32 NPFCalcStationOrTileHeuristic(AySt
/* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to
* get here, either getting it from the current choice or from the parent's
* choice */
void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent)
if (parent->path.parent == NULL) {
byte trackdir = current->direction;
Trackdir trackdir = (Trackdir)current->direction;
/* This is a first order decision, so we'd better save the
* direction we chose */
current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;
DEBUG(npf, 6)("Saving trackdir: %#x", trackdir);
} else {
/* We've already made the decision, so just save our parent's
@@ -125,15 +134,15 @@ void NPFFillTrackdirChoice(AyStarNode* c
/* Will return the cost of the tunnel. If it is an entry, it will return the
* cost of that tile. If the tile is an exit, it will return the tunnel length
* including the exit tile. Requires that this is a Tunnel tile */
uint NPFTunnelCost(AyStarNode* current) {
byte exitdir = TrackdirToExitdir(current->direction);
DiagDirection exitdir = TrackdirToExitdir((Trackdir)current->direction);
TileIndex tile = current->tile;
if ( (uint)(_map5[tile] & 3) == ReverseDiagdir(exitdir)) {
if ( (DiagDirection)(_map5[tile] & 3) == ReverseDiagdir(exitdir)) {
/* We just popped out if this tunnel, since were
* facing the tunnel exit */
FindLengthOfTunnelResult flotr;
flotr = FindLengthOfTunnel(tile, ReverseDiagdir(exitdir));
return flotr.length * NPF_TILE_LENGTH;
//TODO: Penalty for tunnels?
@@ -196,20 +205,20 @@ void NPFMarkTile(TileIndex tile) {
#endif
int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {
//TileIndex tile = current->tile;
int32 cost = 0;
cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */
if (IsBuoyTile(current->tile) && IsDiagonalTrackdir(current->direction))
if (IsBuoyTile(current->tile) && IsDiagonalTrackdir(trackdir))
cost += _patches.npf_buoy_penalty; /* A small penalty for going over buoys */
if (current->direction != NextTrackdir(parent->path.node.direction))
if (current->direction != NextTrackdir((Trackdir)parent->path.node.direction))
cost += _patches.npf_water_curve_penalty;
/* TODO More penalties? */
return cost;
@@ -251,13 +260,13 @@ int32 NPFRoadPathCost(AyStar* as, AyStar
/* Determine the cost of this node, for railway tracks */
int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {
/* HACK: We create a OpenListNode manualy, so we can call EndNodeCheck */
OpenListNode new_node;
/* Determine base length */
switch (GetTileType(tile)) {
@@ -315,21 +324,23 @@ int32 NPFRailPathCost(AyStar* as, AyStar
NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);
/* Penalise the tile if it is a target tile and the last signal was
* red */
/* HACK: We create a new_node here so we can call EndNodeCheck. Ugly as hell
* of course... */
new_node.path.node = *current;
if (as->EndNodeCheck(as, &new_node)==AYSTAR_FOUND_END_NODE && NPFGetFlag(current, NPF_FLAG_LAST_SIGNAL_RED))
if (as->EndNodeCheck(as, &new_node) == AYSTAR_FOUND_END_NODE && NPFGetFlag(current, NPF_FLAG_LAST_SIGNAL_RED))
cost += _patches.npf_rail_lastred_penalty;
/* Check for slope */
cost += NPFSlopeCost(current);
/* Check for turns */
cost += _patches.npf_rail_curve_penalty;
//TODO, with realistic acceleration, also the amount of straight track between
// curves should be taken into account, as this affects the speed limit.
/* Check for reverse in depot */
if (IsTileDepotType(tile, TRANSPORT_RAIL) && !as->EndNodeCheck(as, &new_node)==AYSTAR_FOUND_END_NODE)
@@ -379,73 +390,31 @@ int32 NPFFindStationOrTile(AyStar* as, O
/* To be called when current contains the (shortest route to) the target node.
* Will fill the contents of the NPFFoundTargetData using
* AyStarNode[NPF_TRACKDIR_CHOICE].
void NPFSaveTargetData(AyStar* as, OpenListNode* current) {
NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path;
ftd->best_trackdir = current->path.node.user_data[NPF_TRACKDIR_CHOICE];
ftd->best_trackdir = (Trackdir)current->path.node.user_data[NPF_TRACKDIR_CHOICE];
ftd->best_path_dist = current->g;
ftd->best_bird_dist = 0;
ftd->node = current->path.node;
* Return the rail type of tile, or INVALID_RAILTYPE if this is no rail tile.
* Note that there is no check if the given trackdir is actually present on
* the tile!
* The given trackdir is used when there are (could be) multiple rail types on
* one tile.
static inline RailType GetTileRailType(TileIndex tile, byte trackdir)
byte type = INVALID_RAILTYPE;
case MP_RAILWAY:
/* railway track */
type = _map3_lo[tile] & RAILTYPE_MASK;
break;
case MP_STREET:
/* rail/road crossing */
if (IsLevelCrossing(tile))
type = _map3_hi[tile] & RAILTYPE_MASK;
case MP_STATION:
if (IsTrainStationTile(tile))
case MP_TUNNELBRIDGE:
/* railway tunnel */
if ((_map5[tile] & 0xFC) == 0) type = _map3_lo[tile] & RAILTYPE_MASK;
/* railway bridge ending */
if ((_map5[tile] & 0xC6) == 0x80) type = _map3_lo[tile] & RAILTYPE_MASK;
/* on railway bridge */
if ((_map5[tile] & 0xC6) == 0xC0 && ((unsigned)(_map5[tile] & 0x1)) == (TrackdirToExitdir(trackdir) & 0x1))
type = (_map3_lo[tile] >> 4) & RAILTYPE_MASK;
/* under bridge (any type) */
if ((_map5[tile] & 0xC0) == 0xC0 && (_map5[tile] & 0x1) != (trackdir & 0x1))
default:
return type;
/* Will just follow the results of GetTileTrackStatus concerning where we can
* go and where not. Uses AyStar.user_data[NPF_TYPE] as the transport type and
* an argument to GetTileTrackStatus. Will skip tunnels, meaning that the
* entry and exit are neighbours. Will fill
* AyStarNode.user_data[NPF_TRACKDIR_CHOICE] with an appropriate value, and
* copy AyStarNode.user_data[NPF_NODE_FLAGS] from the parent */
void NPFFollowTrack(AyStar* aystar, OpenListNode* current) {
Trackdir src_trackdir = current->path.node.direction;
Trackdir src_trackdir = (Trackdir)current->path.node.direction;
TileIndex src_tile = current->path.node.tile;
DiagDirection src_exitdir = TrackdirToExitdir(src_trackdir);
TileIndex dst_tile;
int i = 0;
int i;
TrackdirBits trackdirbits, ts;
TransportType type = aystar->user_data[NPF_TYPE];
/* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */
aystar->num_neighbours = 0;
DEBUG(npf, 4)("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile);
@@ -459,13 +428,13 @@ void NPFFollowTrack(AyStar* aystar, Open
if (type != TRANSPORT_WATER && (IsRoadStationTile(src_tile) || IsTileDepotType(src_tile, type))){
/* This is a road station or a train or road depot. We can enter and exit
* those from one side only. Trackdirs don't support that (yet), so we'll
* do this here. */
byte exitdir;
DiagDirection exitdir;
/* Find out the exit direction first */
if (IsRoadStationTile(src_tile))
exitdir = GetRoadStationDir(src_tile);
else /* Train or road depot. Direction is stored the same for both, in map5 */
exitdir = GetDepotDirection(src_tile, type);
@@ -494,14 +463,14 @@ void NPFFollowTrack(AyStar* aystar, Open
/* check correct rail type (mono, maglev, etc)
* XXX: This now compares with the previous tile, which should not pose a
* problem, but it might be nicer to compare with the first tile, or even
* the type of the vehicle... Maybe an NPF_RAILTYPE userdata sometime? */
if (type == TRANSPORT_RAIL) {
byte src_type = GetTileRailType(src_tile, src_trackdir);
byte dst_type = GetTileRailType(dst_tile, TrackdirToExitdir(src_trackdir));
RailType src_type = GetTileRailType(src_tile, src_trackdir);
RailType dst_type = GetTileRailType(dst_tile, TrackdirToExitdir(src_trackdir));
if (src_type != dst_type) {
return;
/* Check the owner of the tile */
@@ -516,13 +485,13 @@ void NPFFollowTrack(AyStar* aystar, Open
if (!IsTileOwner(dst_tile, aystar->user_data[NPF_OWNER]))
/* Determine available tracks */
if (type != TRANSPORT_WATER && (IsRoadStationTile(dst_tile) || IsTileDepotType(dst_tile, type))){
/* Road stations and road and train depots return 0 on GTTS, so we have to do this by hand... */
if (IsRoadStationTile(dst_tile))
exitdir = GetRoadStationDir(dst_tile);
else /* Road or train depot */
exitdir = GetDepotDirection(dst_tile, type);
/* Find the trackdirs that are available for a depot or station with this
* orientation. They are only "inwards", since we are reaching this tile
@@ -538,15 +507,16 @@ void NPFFollowTrack(AyStar* aystar, Open
/* Select only trackdirs we can reach from our current trackdir */
trackdirbits &= TrackdirReachesTrackdirs(src_trackdir);
if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */
trackdirbits &= ~TrackdirCrossesTrackdirs(src_trackdir);
DEBUG(npf,6)("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirbits);
i = 0;
/* Enumerate possible track */
while (trackdirbits != 0) {
byte dst_trackdir;
Trackdir dst_trackdir;
dst_trackdir = FindFirstBit2x64(trackdirbits);
trackdirbits = KillFirstBit2x64(trackdirbits);
DEBUG(npf, 5)("Expanded into trackdir: %d, remaining trackdirs: %#x", dst_trackdir, trackdirbits);
/* Check for oneway signal against us */
if (IsTileType(dst_tile, MP_RAILWAY) && GetRailTileType(dst_tile) == RAIL_TYPE_SIGNALS) {
#include "stdafx.h"
#include "openttd.h"
#include "rail.h"
#include "station.h"
/* XXX: Below 3 tables store duplicate data. Maybe remove some? */
/* Maps a trackdir to the bit that stores its status in the map arrays, in the
* direction along with the trackdir */
const byte _signal_along_trackdir[] = {
0x80, 0x80, 0x80, 0x20, 0x40, 0x10, 0, 0,
@@ -92,6 +93,42 @@ const DiagDirection _reverse_diagdir[] =
const Trackdir _reverse_trackdir[] = {
TRACKDIR_DIAG1_SW, TRACKDIR_DIAG2_NW, TRACKDIR_UPPER_W, TRACKDIR_LOWER_W, TRACKDIR_LEFT_N, TRACKDIR_RIGHT_N, INVALID_TRACKDIR, INVALID_TRACKDIR,
TRACKDIR_DIAG1_NE, TRACKDIR_DIAG2_SE, TRACKDIR_UPPER_E, TRACKDIR_LOWER_E, TRACKDIR_LEFT_S, TRACKDIR_RIGHT_S
RailType GetTileRailType(TileIndex tile, byte trackdir)
RailType type = INVALID_RAILTYPE;
if ((_map5[tile] & 0xC6) == 0xC0 && ((DiagDirection)(_map5[tile] & 0x1)) == (TrackdirToExitdir(trackdir) & 0x1))
@@ -431,7 +431,16 @@ static inline SignalType GetSignalType(T
static inline bool HasSemaphores(TileIndex tile, Track track)
assert(IsValidTrack(track));
return (_map3_hi[tile] & SIG_SEMAPHORE_MASK);
RailType GetTileRailType(TileIndex tile, byte trackdir);
#endif // RAIL_H
Status change: