|
@@ -72,97 +72,97 @@ struct NPFFoundTargetData {
|
|
|
AyStarNode node; ///< The node within the target the search led us to
|
|
|
bool res_okay; ///< True if a path reservation could be made
|
|
|
};
|
|
|
|
|
|
static 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[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
|
|
|
};
|
|
|
|
|
|
/**
|
|
|
* Returns the current value of the given flag on the given AyStarNode.
|
|
|
*/
|
|
|
static inline bool NPFGetFlag(const AyStarNode *node, NPFNodeFlag flag)
|
|
|
{
|
|
|
return HasBit(node->user_data[NPF_NODE_FLAGS], flag);
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Sets the given flag on the given AyStarNode to the given value.
|
|
|
*/
|
|
|
static inline void NPFSetFlag(AyStarNode *node, NPFNodeFlag flag, bool value)
|
|
|
{
|
|
|
SB(node->user_data[NPF_NODE_FLAGS], flag, 1, value);
|
|
|
}
|
|
|
|
|
|
bool CheckIgnoreFirstTile(const PathNode *node)
|
|
|
{
|
|
|
return (node->parent == nullptr && HasBit(node->node.user_data[NPF_NODE_FLAGS], NPF_FLAG_IGNORE_START_TILE));
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Calculates the minimum distance travelled to get from t0 to t1 when only
|
|
|
* using tracks (ie, only making 45 degree turns). Returns the distance in the
|
|
|
* NPF scale, ie the number of full tiles multiplied by NPF_TILE_LENGTH to
|
|
|
* prevent rounding.
|
|
|
*/
|
|
|
static uint NPFDistanceTrack(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
|
|
|
const uint straightTracks = 2 * std::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.
|
|
|
|
|
|
/* Don't factor out NPF_TILE_LENGTH below, this will round values and lose
|
|
|
* precision */
|
|
|
return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Calculates a hash value for use in the NPF.
|
|
|
* @param key1 The TileIndex of the tile to hash
|
|
|
* @param key2 The Trackdir of the track on the tile.
|
|
|
*
|
|
|
* @todo Think of a better hash.
|
|
|
*/
|
|
|
static 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;
|
|
|
|
|
|
assert(IsValidTrackdir((Trackdir)key2));
|
|
|
assert(IsValidTile(key1));
|
|
|
return ((part1 << NPF_HASH_HALFBITS | part2) + (NPF_HASH_SIZE * key2 / TRACKDIR_END)) % NPF_HASH_SIZE;
|
|
|
}
|
|
|
|
|
|
static int32 NPFCalcZero(AyStar *as, AyStarNode *current, OpenListNode *parent)
|
|
|
{
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
/* Calculates the heuristic to the target station or tile. For train stations, it
|
|
|
* takes into account the direction of approach.
|
|
|
*/
|
|
|
static int32 NPFCalcStationOrTileHeuristic(AyStar *as, AyStarNode *current, OpenListNode *parent)
|
|
|
{
|
|
|
NPFFindStationOrTileData *fstd = (NPFFindStationOrTileData*)as->user_target;
|
|
|
NPFFoundTargetData *ftd = (NPFFoundTargetData*)as->user_path;
|
|
|
TileIndex from = current->tile;
|
|
|
TileIndex to = fstd->dest_coords;
|
|
|
uint dist;
|
|
|
AyStarUserData *user = (AyStarUserData *)as->user_data;
|
|
|
|
|
|
/* aim for the closest station tile */
|
|
|
if (fstd->station_index != INVALID_STATION) {
|