# pathfind.cpp File Reference

`#include "stdafx.h"`
`#include "openttd.h"`
`#include "bridge_map.h"`
`#include "station_map.h"`
`#include "depot.h"`
`#include "tile_cmd.h"`
`#include "landscape.h"`
`#include "pathfind.h"`
`#include "rail_type.h"`
`#include "debug.h"`
`#include "tunnel_map.h"`
`#include "settings_type.h"`
`#include "tunnelbridge_map.h"`
`#include "core/random_func.hpp"`
`#include "tunnelbridge.h"`

Go to the source code of this file.

## Data Structures
struct | StackedItem
struct | HashLink
struct | NewTrackPathFinder
## Defines
#define | NTP_GET_LINK_OFFS(tpf, link) ((byte*)(link) - (byte*)tpf->links)
#define | NTP_GET_LINK_PTR(tpf, link_offs) (HashLink*)((byte*)tpf->links + (link_offs))
#define | ARR(i) tpf->stack[(i)-1]
## Functions
static bool | TPFSetTileBit (TrackPathFinder *tpf, TileIndex tile, int dir)
static void | TPFMode2 (TrackPathFinder *tpf, TileIndex tile, DiagDirection direction)
static bool | CanAccessTileInDir (TileIndex tile, DiagDirection side, TransportType tracktype)
| Checks if any vehicle can enter/leave tile in given diagdir Checks only for rail/road depots and road non-drivethrough stations.
static void | TPFMode1 (TrackPathFinder *tpf, TileIndex tile, DiagDirection direction)
void | FollowTrack (TileIndex tile, uint16 flags, uint sub_type, DiagDirection direction, TPFEnumProc *enum_proc, TPFAfterProc *after_proc, void *data)
static void | HeapifyUp (NewTrackPathFinder *tpf)
| called after a new element was added in the queue at the last index.
static void | HeapifyDown (NewTrackPathFinder *tpf)
| called after the element 0 was eaten.
static bool | NtpVisit (NewTrackPathFinder *tpf, TileIndex tile, DiagDirection dir, uint length)
| mark a tile as visited and store the length of the path.
static bool | NtpCheck (NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint length)
| Checks if the shortest path to the given tile/dir so far is still the given length.
static uint | DistanceMoo (TileIndex t0, TileIndex t1)
static void | NTPEnum (NewTrackPathFinder *tpf, TileIndex tile, DiagDirection direction)
void | NewTrainPathfind (TileIndex tile, TileIndex dest, RailTypes railtypes, DiagDirection direction, NTPEnumProc *enum_proc, void *data)
| new pathfinder for trains.
## Variables
static const byte | _bits_mask [4]
static const DiagDirection | _tpf_new_direction [14]
static const DiagDirection | _tpf_prev_direction [14]
static const byte | _otherdir_mask [4]
static const uint16 | _tpfmode1_and [4] = { 0x1009, 0x16, 0x520, 0x2A00 }
static const Trackdir | _new_trackdir [6][4]
static const byte | _length_of_track [16]

## Detailed Description

Definition in file pathfind.cpp.

## Function Documentation

static bool CanAccessTileInDir | ( | TileIndex | tile,
|  | DiagDirection | side,
|  | TransportType | tracktype |
| ) |  |  | `[inline, static]`

Checks if any vehicle can enter/leave tile in given diagdir Checks only for rail/road depots and road non-drivethrough stations.

Parameters:

  | tile | tile to check
  | side | side of tile we are trying to leave/enter
  | tracktype | type of transport

Precondition:
  tile has trackbit at that diagdir

Returns:
  true iff vehicle can enter/leve the tile in given side

Definition at line 196 of file pathfind.cpp.

References GetRailDepotDirection(), GetRoadStopDir(), and IsTileDepotType().

static void HeapifyDown | ( | NewTrackPathFinder * | tpf | ) | `[inline, static]`

called after the element 0 was eaten.

fill it with a new element

Definition at line 396 of file pathfind.cpp.

static void HeapifyUp | ( | NewTrackPathFinder * | tpf | ) | `[inline, static]`

called after a new element was added in the queue at the last index.

move it down to the proper position

Definition at line 382 of file pathfind.cpp.

void NewTrainPathfind | ( | TileIndex | tile,
|  | TileIndex | dest,
|  | RailTypes | railtypes,
|  | DiagDirection | direction,
|  | NTPEnumProc * | enum_proc,
|  | void * | data |
| ) |  |  |

new pathfinder for trains.

better and faster.

Definition at line 821 of file pathfind.cpp.

References min().

Referenced by FindClosestTrainDepot().

static bool NtpCheck | ( | NewTrackPathFinder * | tpf,
|  | TileIndex | tile,
|  | uint | dir,
|  | uint | length |
| ) |  |  | `[static]`

Checks if the shortest path to the given tile/dir so far is still the given length.

Returns:
  true if the length is still the same

Precondition:
  The given tile/dir combination should be present in the hash, by a previous call to NtpVisit().

Definition at line 514 of file pathfind.cpp.

static bool NtpVisit | ( | NewTrackPathFinder * | tpf,
|  | TileIndex | tile,
|  | DiagDirection | dir,
|  | uint | length |
| ) |  |  | `[static]`

mark a tile as visited and store the length of the path.

if we already had a better path to this tile, return false. otherwise return true.

Definition at line 428 of file pathfind.cpp.

## Variable Documentation

const byte _bits_mask[4]`[static]`

Initial value:

     {
      0x19,
      0x16,
      0x25,
      0x2A,
    }

Definition at line 114 of file pathfind.cpp.

const byte _length_of_track[16]`[static]`

Initial value:

     {
      DIAG_FACTOR, DIAG_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, 0, 0,
      DIAG_FACTOR, DIAG_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, STR_FACTOR, 0, 0
    }

Definition at line 561 of file pathfind.cpp.

const Trackdir _new_trackdir[6][4]`[static]`

Initial value:

     {
    {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,},
    }

Definition at line 339 of file pathfind.cpp.

const byte _otherdir_mask[4]`[static]`

Initial value:

     {
      0x10,
      0,
      0x5,
      0x2A,
    }

Definition at line 134 of file pathfind.cpp.

const DiagDirection _tpf_new_direction[14]`[static]`

Initial value:

     {
      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,
    }

Definition at line 121 of file pathfind.cpp.

const DiagDirection _tpf_prev_direction[14]`[static]`

Initial value:

     {
      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,
    }

Definition at line 127 of file pathfind.cpp.