|
|
/*
|
|
|
* This file is part of OpenTTD.
|
|
|
* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
|
|
|
* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
|
|
|
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
|
|
|
*/
|
|
|
|
|
|
/** @file npf.cpp Implementation of the NPF pathfinder. */
|
|
|
|
|
|
#include "../../stdafx.h"
|
|
|
#include "../../network/network.h"
|
|
|
#include "../../viewport_func.h"
|
|
|
#include "../../ship.h"
|
|
|
#include "../../roadstop_base.h"
|
|
|
#include "../../vehicle_func.h"
|
|
|
#include "../pathfinder_func.h"
|
|
|
#include "../pathfinder_type.h"
|
|
|
#include "../follow_track.hpp"
|
|
|
#include "aystar.h"
|
|
|
|
|
|
#include "../../safeguards.h"
|
|
|
|
|
|
static const uint NPF_HASH_BITS = 12; ///< The size of the hash used in pathfinding. Just changing this value should be sufficient to change the hash size. Should be an even value.
|
|
|
/* Do no change below values */
|
|
|
static const uint NPF_HASH_SIZE = 1 << NPF_HASH_BITS;
|
|
|
static const uint NPF_HASH_HALFBITS = NPF_HASH_BITS / 2;
|
|
|
static const uint NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1;
|
|
|
|
|
|
/** Meant to be stored in AyStar.targetdata */
|
|
|
struct NPFFindStationOrTileData {
|
|
|
TileIndex dest_coords; ///< An indication of where the station is, for heuristic purposes, or the target tile
|
|
|
StationID station_index; ///< station index we're heading for, or INVALID_STATION when we're heading for a tile
|
|
|
bool reserve_path; ///< Indicates whether the found path should be reserved
|
|
|
StationType station_type; ///< The type of station we're heading for
|
|
|
bool not_articulated; ///< The (road) vehicle is not articulated
|
|
|
const Vehicle *v; ///< The vehicle we are pathfinding for
|
|
|
};
|
|
|
|
|
|
/** Indices into AyStar.userdata[] */
|
|
|
struct AyStarUserData {
|
|
|
Owner owner;
|
|
|
TransportType type;
|
|
|
RailTypes railtypes;
|
|
|
RoadTypes roadtypes;
|
|
|
uint subtype;
|
|
|
};
|
|
|
|
|
|
/** Indices into AyStarNode.userdata[] */
|
|
|
enum AyStarNodeUserDataType {
|
|
|
NPF_TRACKDIR_CHOICE = 0, ///< The trackdir chosen to get here
|
|
|
NPF_NODE_FLAGS,
|
|
|
};
|
|
|
|
|
|
/** Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. Use NPFSetFlag() and NPFGetFlag() to use them. */
|
|
|
enum NPFNodeFlag {
|
|
|
NPF_FLAG_SEEN_SIGNAL, ///< Used to mark that a signal was seen on the way, for rail only
|
|
|
NPF_FLAG_2ND_SIGNAL, ///< Used to mark that two signals were seen, rail only
|
|
|
NPF_FLAG_3RD_SIGNAL, ///< Used to mark that three signals were seen, rail only
|
|
|
NPF_FLAG_REVERSE, ///< Used to mark that this node was reached from the second start node, if applicable
|
|
|
NPF_FLAG_LAST_SIGNAL_RED, ///< Used to mark that the last signal on this path was red
|
|
|
NPF_FLAG_LAST_SIGNAL_BLOCK, ///< Used to mark that the last signal on this path was a block signal
|
|
|
NPF_FLAG_IGNORE_START_TILE, ///< Used to mark that the start tile is invalid, and searching should start from the second tile on
|
|
|
NPF_FLAG_TARGET_RESERVED, ///< Used to mark that the possible reservation target is already reserved
|
|
|
NPF_FLAG_IGNORE_RESERVED, ///< Used to mark that reserved tiles should be considered impassable
|
|
|
};
|
|
|
|
|
|
/** Meant to be stored in AyStar.userpath */
|
|
|
struct NPFFoundTargetData {
|
|
|
uint best_bird_dist; ///< The best heuristic found. Is 0 if the target was found
|
|
|
uint best_path_dist; ///< The shortest path. Is UINT_MAX if no path is found
|
|
|
Trackdir best_trackdir; ///< The trackdir that leads to the shortest path/closest birds dist
|
|
|
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) {
|
|
|
to = CalcClosestStationTile(fstd->station_index, from, fstd->station_type);
|
|
|
}
|
|
|
|
|
|
if (user->type == TRANSPORT_ROAD) {
|
|
|
/* Since roads only have diagonal pieces, we use manhattan distance here */
|
|
|
dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;
|
|
|
} else {
|
|
|
/* Ships and trains can also go diagonal, so the minimum distance is shorter */
|
|
|
dist = NPFDistanceTrack(from, to);
|
|
|
}
|
|
|
|
|
|
DEBUG(npf, 4, "Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist);
|
|
|
|
|
|
if (dist < ftd->best_bird_dist) {
|
|
|
ftd->best_bird_dist = dist;
|
|
|
ftd->best_trackdir = (Trackdir)current->user_data[NPF_TRACKDIR_CHOICE];
|
|
|
}
|
|
|
return dist;
|
|
|
}
|
|
|
|
|
|
|
|
|
/* 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 */
|
|
|
static void NPFFillTrackdirChoice(AyStarNode *current, OpenListNode *parent)
|
|
|
{
|
|
|
if (parent->path.parent == nullptr) {
|
|
|
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: 0x%X", trackdir);
|
|
|
} else {
|
|
|
/* We've already made the decision, so just save our parent's decision */
|
|
|
current->user_data[NPF_TRACKDIR_CHOICE] = parent->path.node.user_data[NPF_TRACKDIR_CHOICE];
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/* 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 */
|
|
|
static uint NPFTunnelCost(AyStarNode *current)
|
|
|
{
|
|
|
DiagDirection exitdir = TrackdirToExitdir(current->direction);
|
|
|
TileIndex tile = current->tile;
|
|
|
if (GetTunnelBridgeDirection(tile) == ReverseDiagDir(exitdir)) {
|
|
|
/* We just popped out if this tunnel, since were
|
|
|
* facing the tunnel exit */
|
|
|
return NPF_TILE_LENGTH * (GetTunnelBridgeLength(current->tile, GetOtherTunnelEnd(current->tile)) + 1);
|
|
|
/* @todo: Penalty for tunnels? */
|
|
|
} else {
|
|
|
/* We are entering the tunnel, the enter tile is just a
|
|
|
* straight track */
|
|
|
return NPF_TILE_LENGTH;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
static inline uint NPFBridgeCost(AyStarNode *current)
|
|
|
{
|
|
|
return NPF_TILE_LENGTH * GetTunnelBridgeLength(current->tile, GetOtherBridgeEnd(current->tile));
|
|
|
}
|
|
|
|
|
|
static uint NPFSlopeCost(AyStarNode *current)
|
|
|
{
|
|
|
TileIndex next = current->tile + TileOffsByDiagDir(TrackdirToExitdir(current->direction));
|
|
|
|
|
|
/* Get center of tiles */
|
|
|
int x1 = TileX(current->tile) * TILE_SIZE + TILE_SIZE / 2;
|
|
|
int y1 = TileY(current->tile) * TILE_SIZE + TILE_SIZE / 2;
|
|
|
int x2 = TileX(next) * TILE_SIZE + TILE_SIZE / 2;
|
|
|
int y2 = TileY(next) * TILE_SIZE + TILE_SIZE / 2;
|
|
|
|
|
|
int dx4 = (x2 - x1) / 4;
|
|
|
int dy4 = (y2 - y1) / 4;
|
|
|
|
|
|
/* Get the height on both sides of the tile edge.
|
|
|
* Avoid testing the height on the tile-center. This will fail for halftile-foundations.
|
|
|
*/
|
|
|
int z1 = GetSlopePixelZ(x1 + dx4, y1 + dy4);
|
|
|
int z2 = GetSlopePixelZ(x2 - dx4, y2 - dy4);
|
|
|
|
|
|
if (z2 - z1 > 1) {
|
|
|
/* Slope up */
|
|
|
return _settings_game.pf.npf.npf_rail_slope_penalty;
|
|
|
}
|
|
|
return 0;
|
|
|
/* Should we give a bonus for slope down? Probably not, we
|
|
|
* could just subtract that bonus from the penalty, because
|
|
|
* there is only one level of steepness... */
|
|
|
}
|
|
|
|
|
|
static uint NPFReservedTrackCost(AyStarNode *current)
|
|
|
{
|
|
|
TileIndex tile = current->tile;
|
|
|
TrackBits track = TrackToTrackBits(TrackdirToTrack(current->direction));
|
|
|
TrackBits res = GetReservedTrackbits(tile);
|
|
|
|
|
|
if (NPFGetFlag(current, NPF_FLAG_3RD_SIGNAL) || NPFGetFlag(current, NPF_FLAG_LAST_SIGNAL_BLOCK) || ((res & track) == TRACK_BIT_NONE && !TracksOverlap(res | track))) return 0;
|
|
|
|
|
|
if (IsTileType(tile, MP_TUNNELBRIDGE)) {
|
|
|
DiagDirection exitdir = TrackdirToExitdir(current->direction);
|
|
|
if (GetTunnelBridgeDirection(tile) == ReverseDiagDir(exitdir)) {
|
|
|
return _settings_game.pf.npf.npf_rail_pbs_cross_penalty * (GetTunnelBridgeLength(tile, GetOtherTunnelBridgeEnd(tile)) + 1);
|
|
|
}
|
|
|
}
|
|
|
return _settings_game.pf.npf.npf_rail_pbs_cross_penalty;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Mark tiles by mowing the grass when npf debug level >= 1.
|
|
|
* Will not work for multiplayer games, since it can (will) cause desyncs.
|
|
|
*/
|
|
|
static void NPFMarkTile(TileIndex tile)
|
|
|
{
|
|
|
if (_debug_npf_level < 1 || _networking) return;
|
|
|
switch (GetTileType(tile)) {
|
|
|
case MP_RAILWAY:
|
|
|
/* DEBUG: mark visited tiles by mowing the grass under them ;-) */
|
|
|
if (!IsRailDepot(tile)) {
|
|
|
SetRailGroundType(tile, RAIL_GROUND_BARREN);
|
|
|
MarkTileDirtyByTile(tile);
|
|
|
}
|
|
|
break;
|
|
|
|
|
|
case MP_ROAD:
|
|
|
if (!IsRoadDepot(tile)) {
|
|
|
SetRoadside(tile, ROADSIDE_BARREN);
|
|
|
MarkTileDirtyByTile(tile);
|
|
|
}
|
|
|
break;
|
|
|
|
|
|
default:
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
static Vehicle *CountShipProc(Vehicle *v, void *data)
|
|
|
{
|
|
|
uint *count = (uint *)data;
|
|
|
/* Ignore other vehicles (aircraft) and ships inside depot. */
|
|
|
if (v->type == VEH_SHIP && (v->vehstatus & VS_HIDDEN) == 0) (*count)++;
|
|
|
|
|
|
return nullptr;
|
|
|
}
|