OpenTTD
Data Structures | Macros | Enumerations | Functions | Variables
npf.cpp File Reference

Implementation of the NPF pathfinder. More...

#include "../../stdafx.h"
#include "../../network/network.h"
#include "../../viewport_func.h"
#include "../../ship.h"
#include "../../roadstop_base.h"
#include "../pathfinder_func.h"
#include "../pathfinder_type.h"
#include "../follow_track.hpp"
#include "aystar.h"
#include "../../safeguards.h"

Go to the source code of this file.

Data Structures

struct  NPFFindStationOrTileData
 Meant to be stored in AyStar.targetdata. More...
struct  AyStarUserData
 Indices into AyStar.userdata[]. More...
struct  NPFFoundTargetData
 Meant to be stored in AyStar.userpath. More...

Macros

#define NPF_STRAIGHT_LENGTH   (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)

Enumerations

enum  AyStarNodeUserDataType { NPF_TRACKDIR_CHOICE = 0, NPF_NODE_FLAGS }
 Indices into AyStarNode.userdata[]. More...
enum  NPFNodeFlag {
  NPF_FLAG_SEEN_SIGNAL, NPF_FLAG_2ND_SIGNAL, NPF_FLAG_3RD_SIGNAL, NPF_FLAG_REVERSE,
  NPF_FLAG_LAST_SIGNAL_RED, NPF_FLAG_LAST_SIGNAL_BLOCK, NPF_FLAG_IGNORE_START_TILE, NPF_FLAG_TARGET_RESERVED,
  NPF_FLAG_IGNORE_RESERVED
}
 Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. More...

Functions

static bool NPFGetFlag (const AyStarNode *node, NPFNodeFlag flag)
 Returns the current value of the given flag on the given AyStarNode.
static void NPFSetFlag (AyStarNode *node, NPFNodeFlag flag, bool value)
 Sets the given flag on the given AyStarNode to the given value.
static uint NPFDistanceTrack (TileIndex t0, TileIndex t1)
 Calculates the minimum distance travelled to get from t0 to t1 when only using tracks (ie, only making 45 degree turns).
static uint NPFHash (uint key1, uint key2)
 Calculates a hash value for use in the NPF.
static int32 NPFCalcZero (AyStar *as, AyStarNode *current, OpenListNode *parent)
static int32 NPFCalcStationOrTileHeuristic (AyStar *as, AyStarNode *current, OpenListNode *parent)
static void NPFFillTrackdirChoice (AyStarNode *current, OpenListNode *parent)
static uint NPFTunnelCost (AyStarNode *current)
static uint NPFBridgeCost (AyStarNode *current)
static uint NPFSlopeCost (AyStarNode *current)
static uint NPFReservedTrackCost (AyStarNode *current)
static void NPFMarkTile (TileIndex tile)
 Mark tiles by mowing the grass when npf debug level >= 1.
static int32 NPFWaterPathCost (AyStar *as, AyStarNode *current, OpenListNode *parent)
static int32 NPFRoadPathCost (AyStar *as, AyStarNode *current, OpenListNode *parent)
static int32 NPFRailPathCost (AyStar *as, AyStarNode *current, OpenListNode *parent)
static int32 NPFFindDepot (AyStar *as, OpenListNode *current)
static int32 NPFFindSafeTile (AyStar *as, OpenListNode *current)
 Find any safe and free tile.
static int32 NPFFindStationOrTile (AyStar *as, OpenListNode *current)
static const PathNodeFindSafePosition (PathNode *path, const Train *v)
 Find the node containing the first signal on the path.
static void ClearPathReservation (const PathNode *start, const PathNode *end)
 Lift the reservation of the tiles from start till end, excluding end itself.
static void NPFSaveTargetData (AyStar *as, OpenListNode *current)
 To be called when current contains the (shortest route to) the target node.
static bool CanEnterTileOwnerCheck (Owner owner, TileIndex tile, DiagDirection enterdir)
 Finds out if a given company's vehicles are allowed to enter a given tile.
static DiagDirection GetDepotDirection (TileIndex tile, TransportType type)
 Returns the direction the exit of the depot on the given tile is facing.
static DiagDirection GetSingleTramBit (TileIndex tile)
 Tests if a tile is a road tile with a single tramtrack (tram can reverse)
static DiagDirection GetTileSingleEntry (TileIndex tile, TransportType type, uint subtype)
 Tests if a tile can be entered or left only from one side.
static bool ForceReverse (TileIndex tile, DiagDirection dir, TransportType type, uint subtype)
 Tests if a vehicle must reverse on a tile.
static bool CanEnterTile (TileIndex tile, DiagDirection dir, AyStarUserData *user)
 Tests if a vehicle can enter a tile.
static TrackdirBits GetDriveableTrackdirBits (TileIndex dst_tile, Trackdir src_trackdir, TransportType type, uint subtype)
 Returns the driveable Trackdirs on a tile.
static void NPFFollowTrack (AyStar *aystar, OpenListNode *current)
static NPFFoundTargetData NPFRouteInternal (AyStarNode *start1, bool ignore_start_tile1, AyStarNode *start2, bool ignore_start_tile2, NPFFindStationOrTileData *target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, AyStarUserData *user, uint reverse_penalty, bool ignore_reserved=false)
static NPFFoundTargetData NPFRouteToStationOrTileTwoWay (TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, NPFFindStationOrTileData *target, AyStarUserData *user)
static NPFFoundTargetData NPFRouteToStationOrTile (TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData *target, AyStarUserData *user)
static NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay (TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, NPFFindStationOrTileData *target, AyStarUserData *user, uint reverse_penalty)
void InitializeNPF ()
static void NPFFillWithOrderData (NPFFindStationOrTileData *fstd, const Vehicle *v, bool reserve_path=false)
FindDepotData NPFRoadVehicleFindNearestDepot (const RoadVehicle *v, int max_penalty)
 Used when user sends road vehicle to the nearest depot or if road vehicle needs servicing using NPF.
Trackdir NPFRoadVehicleChooseTrack (const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found)
 Finds the best path for given road vehicle using NPF.
Track NPFShipChooseTrack (const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found)
 Finds the best path for given ship using NPF.
bool NPFShipCheckReverse (const Ship *v)
 Returns true if it is better to reverse the ship before leaving depot using NPF.
FindDepotData NPFTrainFindNearestDepot (const Train *v, int max_penalty)
 Used when user sends train to the nearest depot or if train needs servicing using NPF.
bool NPFTrainFindNearestSafeTile (const Train *v, TileIndex tile, Trackdir trackdir, bool override_railtype)
 Try to extend the reserved path of a train to the nearest safe tile using NPF.
bool NPFTrainCheckReverse (const Train *v)
 Returns true if it is better to reverse the train before leaving station using NPF.
Track NPFTrainChooseTrack (const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, bool reserve_track, struct PBSTileInfo *target)
 Finds the best path for given train using NPF.

Variables

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.
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
static AyStar _npf_aystar
static const uint _trackdir_length [TRACKDIR_END]

Detailed Description

Implementation of the NPF pathfinder.

Definition in file npf.cpp.

Enumeration Type Documentation

Indices into AyStarNode.userdata[].

Enumerator:
NPF_TRACKDIR_CHOICE 

The trackdir chosen to get here.

Definition at line 49 of file npf.cpp.

Flags for AyStarNode.userdata[NPF_NODE_FLAGS].

Use NPFSetFlag() and NPFGetFlag() to use them.

Enumerator:
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.

Definition at line 55 of file npf.cpp.

Function Documentation

static bool CanEnterTile ( TileIndex  tile,
DiagDirection  dir,
AyStarUserData user 
)
static

Tests if a vehicle can enter a tile.

Parameters
tileThe tile of interest.
dirThe direction in which the vehicle drives onto a tile.
userVehicle information.
Returns
true iff the vehicle can enter the tile.

Definition at line 776 of file npf.cpp.

References CanEnterTileOwnerCheck(), GetTileRailType(), GetTileSingleEntry(), GetTunnelBridgeDirection(), HasBit(), INVALID_DIAGDIR, IsTileType(), MP_TUNNELBRIDGE, ReverseDiagDir(), and TRANSPORT_RAIL.

static bool CanEnterTileOwnerCheck ( Owner  owner,
TileIndex  tile,
DiagDirection  enterdir 
)
static

Finds out if a given company's vehicles are allowed to enter a given tile.

Parameters
ownerThe owner of the vehicle.
tileThe tile that is about to be entered.
enterdirThe direction in which the vehicle wants to enter the tile.
Returns
true if the vehicle can enter the tile.
Todo:
This function should be used in other places than just NPF, maybe moved to another file too.

Definition at line 668 of file npf.cpp.

References DiagDirToAxis(), GetCrossingRoadAxis(), GetTileType(), GetTunnelBridgeTransportType(), HasStationTileRail(), IsLevelCrossing(), IsRoadDepotTile(), IsStandardRoadStopTile(), IsTileOwner(), IsTileType(), MP_RAILWAY, MP_ROAD, MP_TUNNELBRIDGE, and TRANSPORT_RAIL.

Referenced by CanEnterTile().

static const PathNode* FindSafePosition ( PathNode path,
const Train v 
)
static

Find the node containing the first signal on the path.

If the first signal is on the very first two tiles of the path, the second signal is returned. If no suitable signal is present, the last node of the path is returned.

Definition at line 579 of file npf.cpp.

References _settings_game, PathfinderSettings::forbid_90_deg, IsSafeWaitingPosition(), PathNode::parent, and GameSettings::pf.

Referenced by NPFSaveTargetData().

static bool ForceReverse ( TileIndex  tile,
DiagDirection  dir,
TransportType  type,
uint  subtype 
)
inlinestatic

Tests if a vehicle must reverse on a tile.

Parameters
tileThe tile of interest.
dirThe direction in which the vehicle drives on a tile.
typeThe transporttype of the vehicle.
subtypeFor TRANSPORT_ROAD the compatible RoadTypes of the vehicle.
Returns
true iff the vehicle must reverse on the tile.

Definition at line 762 of file npf.cpp.

References GetTileSingleEntry(), and INVALID_DIAGDIR.

static TrackdirBits GetDriveableTrackdirBits ( TileIndex  dst_tile,
Trackdir  src_trackdir,
TransportType  type,
uint  subtype 
)
static

Returns the driveable Trackdirs on a tile.

One-way-roads are taken into account. Signals are not tested.

Parameters
dst_tileThe tile of interest.
src_trackdirThe direction the vehicle is currently moving.
typeThe transporttype of the vehicle.
subtypeFor TRANSPORT_ROAD the compatible RoadTypes of the vehicle.
Returns
The Trackdirs the vehicle can continue moving on.

Definition at line 808 of file npf.cpp.

References _settings_game, DEBUG, DIAGDIR_NE, DIAGDIR_NW, DIAGDIR_SE, DIAGDIR_SW, PathfinderSettings::forbid_90_deg, GetSingleTramBit(), GetTileTrackStatus(), HasBit(), GameSettings::pf, ROADTYPE_TRAM, TileX(), TileY(), TRACKDIR_BIT_X_NE, TRACKDIR_BIT_X_SW, TRACKDIR_BIT_Y_NW, TRACKDIR_BIT_Y_SE, TrackdirCrossesTrackdirs(), TrackdirReachesTrackdirs(), TrackStatusToTrackdirBits(), TRANSPORT_RAIL, TRANSPORT_ROAD, and TRANSPORT_WATER.

static DiagDirection GetTileSingleEntry ( TileIndex  tile,
TransportType  type,
uint  subtype 
)
static

Tests if a tile can be entered or left only from one side.

Depots, non-drive-through roadstops, and tiles with single trambits are tested.

Parameters
tileThe tile of interest.
typeThe transporttype of the vehicle.
subtypeFor TRANSPORT_ROAD the compatible RoadTypes of the vehicle.
Returns
The single entry/exit-direction of the tile, or INVALID_DIAGDIR if there are more or less directions

Definition at line 741 of file npf.cpp.

References GetDepotDirection(), GetRoadStopDir(), GetSingleTramBit(), HasBit(), INVALID_DIAGDIR, IsDepotTypeTile(), IsStandardRoadStopTile(), ROADTYPE_TRAM, TRANSPORT_ROAD, and TRANSPORT_WATER.

Referenced by CanEnterTile(), and ForceReverse().

static uint NPFDistanceTrack ( TileIndex  t0,
TileIndex  t1 
)
static

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.

Definition at line 110 of file npf.cpp.

References Delta(), min(), NPF_TILE_LENGTH, STRAIGHT_TRACK_LENGTH, TileX(), and TileY().

static int32 NPFFindSafeTile ( AyStar as,
OpenListNode current 
)
static
static uint NPFHash ( uint  key1,
uint  key2 
)
static

Calculates a hash value for use in the NPF.

Parameters
key1The TileIndex of the tile to hash
key2The Trackdir of the track on the tile.
Todo:
Think of a better hash.

Definition at line 134 of file npf.cpp.

References IsValidTile(), IsValidTrackdir(), TileX(), TileY(), and TRACKDIR_END.

static void NPFMarkTile ( TileIndex  tile)
static

Mark tiles by mowing the grass when npf debug level >= 1.

Will not work for multiplayer games, since it can (will) cause desyncs.

Definition at line 276 of file npf.cpp.

References _networking, GetTileType(), IsRailDepot(), IsRoadDepot(), MarkTileDirtyByTile(), MP_RAILWAY, MP_ROAD, RAIL_GROUND_BARREN, ROADSIDE_BARREN, and SetRoadside().

Trackdir NPFRoadVehicleChooseTrack ( const RoadVehicle v,
TileIndex  tile,
DiagDirection  enterdir,
TrackdirBits  trackdirs,
bool &  path_found 
)

Finds the best path for given road vehicle using NPF.

Parameters
vthe RV that needs to find a path
tilethe tile to find the path from (should be next tile the RV is about to enter)
enterdirdiagonal direction which the RV will enter this new tile from
trackdirsavailable trackdirs on the new tile (to choose from)
path_found[out] Whether a path has been found (true) or has been guessed (false)
Returns
the best trackdir for next turn or INVALID_TRACKDIR if the path could not be found

Definition at line 1131 of file npf.cpp.

References NPFFoundTargetData::best_bird_dist, NPFFoundTargetData::best_trackdir, DiagDirToDiagTrackdir(), FindFirstBit2x64(), INVALID_RAILTYPES, INVALID_TRACKDIR, Vehicle::owner, TileOffsByDiagDir(), and TRANSPORT_ROAD.

Referenced by RoadFindPathToDest().

FindDepotData NPFRoadVehicleFindNearestDepot ( const RoadVehicle v,
int  max_penalty 
)

Used when user sends road vehicle to the nearest depot or if road vehicle needs servicing using NPF.

Parameters
vvehicle that needs to go to some depot
max_penaltymax distance (in pathfinder penalty) from the current vehicle position (used also as optimization - the pathfinder can stop path finding if max_penalty was reached and no depot was seen)
Returns
the data about the depot

Definition at line 1114 of file npf.cpp.

References NPFFoundTargetData::best_bird_dist, NPFFoundTargetData::best_path_dist, RoadVehicle::GetVehicleTrackdir(), INVALID_RAILTYPES, NPFFoundTargetData::node, Vehicle::owner, ReverseTrackdir(), Vehicle::tile, and TRANSPORT_ROAD.

static void NPFSaveTargetData ( AyStar as,
OpenListNode current 
)
static
bool NPFShipCheckReverse ( const Ship v)

Returns true if it is better to reverse the ship before leaving depot using NPF.

Parameters
vthe ship leaving the depot
Returns
true if reversing is better

Definition at line 1178 of file npf.cpp.

References NPFFoundTargetData::best_bird_dist, Ship::GetVehicleTrackdir(), INVALID_RAILTYPES, INVALID_TRACKDIR, NPFFoundTargetData::node, NPF_FLAG_REVERSE, NPFGetFlag(), Vehicle::owner, ReverseTrackdir(), ROADTYPES_NONE, Vehicle::tile, and TRANSPORT_WATER.

Track NPFShipChooseTrack ( const Ship v,
TileIndex  tile,
DiagDirection  enterdir,
TrackBits  tracks,
bool &  path_found 
)

Finds the best path for given ship using NPF.

Parameters
vthe ship that needs to find a path
tilethe tile to find the path from (should be next tile the ship is about to enter)
enterdirdiagonal direction which the ship will enter this new tile from
tracksavailable tracks on the new tile (to choose from)
path_found[out] Whether a path has been found (true) or has been guessed (false)
Returns
the best trackdir for next turn or INVALID_TRACK if the path could not be found

Definition at line 1158 of file npf.cpp.

References NPFFoundTargetData::best_bird_dist, NPFFoundTargetData::best_trackdir, Ship::GetVehicleTrackdir(), INVALID_RAILTYPES, INVALID_TRACK, INVALID_TRACKDIR, Vehicle::owner, ROADTYPES_NONE, TileOffsByDiagDir(), TrackdirToTrack(), and TRANSPORT_WATER.

Referenced by ChooseShipTrack().

bool NPFTrainCheckReverse ( const Train v)

Returns true if it is better to reverse the train before leaving station using NPF.

Parameters
vthe train leaving the station
Returns
true if reversing is better

Definition at line 1241 of file npf.cpp.

References NPFFoundTargetData::best_bird_dist, Train::GetVehicleTrackdir(), INVALID_TRACKDIR, SpecializedVehicle< T, Type >::Last(), NPFFoundTargetData::node, NPF_FLAG_REVERSE, NPFGetFlag(), Vehicle::owner, ReverseTrackdir(), ROADTYPES_NONE, Vehicle::tile, and TRANSPORT_RAIL.

Track NPFTrainChooseTrack ( const Train v,
TileIndex  tile,
DiagDirection  enterdir,
TrackBits  tracks,
bool &  path_found,
bool  reserve_track,
struct PBSTileInfo target 
)

Finds the best path for given train using NPF.

Parameters
vthe train that needs to find a path
tilethe tile to find the path from (should be next tile the train is about to enter)
enterdirdiagonal direction which the RV will enter this new tile from
tracksavailable trackdirs on the new tile (to choose from)
path_found[out] Whether a path has been found (true) or has been guessed (false)
reserve_trackindicates whether YAPF should try to reserve the found path
target[out] the target tile of the reservation, free is set to true if path was reserved
Returns
the best track for next turn

Definition at line 1260 of file npf.cpp.

References NPFFoundTargetData::best_bird_dist, NPFFoundTargetData::best_trackdir, FindFirstTrack(), FollowTrainReservation(), INVALID_TRACKDIR, IsValidTrackdir(), NPFFoundTargetData::node, PBSTileInfo::okay, Vehicle::owner, NPFFoundTargetData::res_okay, ROADTYPES_NONE, PBSTileInfo::tile, PBSTileInfo::trackdir, TrackdirToTrack(), and TRANSPORT_RAIL.

Referenced by DoTrainPathfind().

FindDepotData NPFTrainFindNearestDepot ( const Train v,
int  max_penalty 
)

Used when user sends train to the nearest depot or if train needs servicing using NPF.

Parameters
vtrain that needs to go to some depot
max_penaltymax max_penalty (in pathfinder penalty) from the current train position (used also as optimization - the pathfinder can stop path finding if max_penalty was reached and no depot was seen)
Returns
the data about the depot

Definition at line 1198 of file npf.cpp.

References NPFFoundTargetData::best_bird_dist, NPFFoundTargetData::best_path_dist, Train::GetVehicleTrackdir(), INVALID_TRACKDIR, SpecializedVehicle< T, Type >::Last(), NPFFoundTargetData::node, NPF_FLAG_REVERSE, NPF_INFINITE_PENALTY, NPFGetFlag(), Vehicle::owner, ReverseTrackdir(), ROADTYPES_NONE, Vehicle::tile, TRANSPORT_RAIL, and NPFFindStationOrTileData::v.

Referenced by FindClosestTrainDepot().

bool NPFTrainFindNearestSafeTile ( const Train v,
TileIndex  tile,
Trackdir  td,
bool  override_railtype 
)

Try to extend the reserved path of a train to the nearest safe tile using NPF.

Parameters
vThe train that needs to find a safe tile.
tileLast tile of the current reserved path.
tdLast trackdir of the current reserved path.
override_railtypeShould all physically compatible railtypes be searched, even if the vehicle can't run on them on its own?
Returns
True if the path could be extended to a safe tile.

Definition at line 1220 of file npf.cpp.

References RailtypeInfo::compatible_railtypes, GetRailTypeInfo(), NPFFindSafeTile(), Vehicle::owner, NPFFoundTargetData::res_okay, NPFFindStationOrTileData::reserve_path, ROADTYPES_NONE, TRANSPORT_RAIL, BaseVehicle::type, NPFFindStationOrTileData::v, and VEH_TRAIN.

Referenced by TryReserveSafeTrack().

Variable Documentation

const uint _trackdir_length[TRACKDIR_END]
static
Initial value:
{
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
}

Definition at line 82 of file npf.cpp.