add_subdirectory(npf)

add_subdirectory(yapf)

add_files(

    follow_track.hpp

    pathfinder_func.h

    pathfinder_type.h

)

/*

 * 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 follow_track.hpp Template function for track followers */

#ifndef  FOLLOW_TRACK_HPP

#define  FOLLOW_TRACK_HPP

#include "../pbs.h"

#include "../roadveh.h"

#include "../station_base.h"

#include "../train.h"

#include "../tunnelbridge.h"

#include "../tunnelbridge_map.h"

#include "../depot_map.h"

#include "pathfinder_func.h"

/**

 * Track follower helper template class (can serve pathfinders and vehicle

 *  controllers). See 6 different typedefs below for 3 different transport

 *  types w/ or w/o 90-deg turns allowed

 */

template <TransportType Ttr_type_, typename VehicleType, bool T90deg_turns_allowed_ = true, bool Tmask_reserved_tracks = false>

struct CFollowTrackT

{

	enum ErrorCode {

		EC_NONE,

		EC_OWNER,

		EC_RAIL_ROAD_TYPE,

		EC_90DEG,

		EC_NO_WAY,

		EC_RESERVED,

	};

	const VehicleType  *m_veh;           ///< moving vehicle

	Owner               m_veh_owner;     ///< owner of the vehicle

	TileIndex           m_old_tile;      ///< the origin (vehicle moved from) before move

	Trackdir            m_old_td;        ///< the trackdir (the vehicle was on) before move

	TileIndex           m_new_tile;      ///< the new tile (the vehicle has entered)

	TrackdirBits        m_new_td_bits;   ///< the new set of available trackdirs

	DiagDirection       m_exitdir;       ///< exit direction (leaving the old tile)

	bool                m_is_tunnel;     ///< last turn passed tunnel

	bool                m_is_bridge;     ///< last turn passed bridge ramp

	bool                m_is_station;    ///< last turn passed station

	int                 m_tiles_skipped; ///< number of skipped tunnel or station tiles

	ErrorCode           m_err;

	RailTypes           m_railtypes;

	{

	}

	{

		assert(IsRailTT());

		m_veh = nullptr;

	}

	{

		assert(!IsRailTT() || (v != nullptr && v->type == VEH_TRAIN));

		m_veh = v;

	}

	{

		assert(!IsRoadTT() || m_veh != nullptr);

		assert(!IsRailTT() || railtype_override != INVALID_RAILTYPES);

		m_veh_owner = o;

		/* don't worry, all is inlined so compiler should remove unnecessary initializations */

		m_old_tile = INVALID_TILE;

		m_old_td = INVALID_TRACKDIR;

		m_new_tile = INVALID_TILE;

		m_new_td_bits = TRACKDIR_BIT_NONE;

		m_exitdir = INVALID_DIAGDIR;

		m_is_station = m_is_bridge = m_is_tunnel = false;

		m_tiles_skipped = 0;

		m_err = EC_NONE;

		m_railtypes = railtype_override;

	}

	inline static TransportType TT() { return Ttr_type_; }

	inline static bool IsWaterTT() { return TT() == TRANSPORT_WATER; }

	inline static bool IsRailTT() { return TT() == TRANSPORT_RAIL; }

	inline bool IsTram() { return IsRoadTT() && RoadTypeIsTram(RoadVehicle::From(m_veh)->roadtype); }

	inline static bool IsRoadTT() { return TT() == TRANSPORT_ROAD; }

	inline static bool Allow90degTurns() { return T90deg_turns_allowed_; }

	inline static bool DoTrackMasking() { return Tmask_reserved_tracks; }

	/** Tests if a tile is a road tile with a single tramtrack (tram can reverse) */

	inline DiagDirection GetSingleTramBit(TileIndex tile)

	{

		assert(IsTram()); // this function shouldn't be called in other cases

				} else { // IsBridge(m_old_tile)

					m_is_bridge = true;

					m_new_tile = GetOtherBridgeEnd(m_old_tile);

				}

				m_tiles_skipped = GetTunnelBridgeLength(m_new_tile, m_old_tile);

				return;

			}

			assert(ReverseDiagDir(enterdir) == m_exitdir);

		}

		/* normal or station tile, do one step */

		m_new_tile = TileAddByDiagDir(m_old_tile, m_exitdir);

		/* special handling for stations */

		if (IsRailTT() && HasStationTileRail(m_new_tile)) {

			m_is_station = true;

		} else if (IsRoadTT() && IsRoadStopTile(m_new_tile)) {

			m_is_station = true;

		}

	}

	/** stores track status (available trackdirs) for the new tile into m_new_td_bits */

	inline bool QueryNewTileTrackStatus()

	{

		if (IsRailTT() && IsPlainRailTile(m_new_tile)) {

			m_new_td_bits = (TrackdirBits)(GetTrackBits(m_new_tile) * 0x101);

		} else if (IsRoadTT()) {

			m_new_td_bits = GetTrackdirBitsForRoad(m_new_tile, this->IsTram() ? RTT_TRAM : RTT_ROAD);

		} else {

			m_new_td_bits = TrackStatusToTrackdirBits(GetTileTrackStatus(m_new_tile, TT(), 0));

		}

		return (m_new_td_bits != TRACKDIR_BIT_NONE);

	}

	/** return true if we can leave m_old_tile in m_exitdir */

	inline bool CanExitOldTile()

	{

		/* road stop can be left at one direction only unless it's a drive-through stop */

		if (IsRoadTT() && IsStandardRoadStopTile(m_old_tile)) {

			DiagDirection exitdir = GetRoadStopDir(m_old_tile);

			if (exitdir != m_exitdir) {

				m_err = EC_NO_WAY;

				return false;

			}

		}

		/* single tram bits can only be left in one direction */

		if (IsTram()) {

/*

 * 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

/*

 * 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 yapf.hpp Base includes/functions for YAPF. */

#ifndef YAPF_HPP

#define YAPF_HPP

#include "../../landscape.h"

#include "../pathfinder_func.h"

#include "yapf.h"

#include "../../misc/fixedsizearray.hpp"

#include "../../misc/array.hpp"

#include "../../misc/hashtable.hpp"

#include "../../misc/binaryheap.hpp"

#include "../../misc/dbg_helpers.h"

#include "nodelist.hpp"

#include "../follow_track.hpp"

#include "yapf_type.hpp"

#include "yapf_base.hpp"

#include "yapf_node.hpp"

#include "yapf_common.hpp"

#include "yapf_costbase.hpp"

#include "yapf_costcache.hpp"

#endif /* YAPF_HPP */

/*

 * 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 yapf_base.hpp Base classes for YAPF. */

#ifndef YAPF_BASE_HPP

#define YAPF_BASE_HPP

#include "../../debug.h"

#include "../../settings_type.h"

/**

 * CYapfBaseT - A-star type path finder base class.

 *  Derive your own pathfinder from it. You must provide the following template argument:

 *    Types      - used as collection of local types used in pathfinder

 *

 * Requirements for the Types struct:

 *  ----------------------------------

 *  The following types must be defined in the 'Types' argument:

 *    - Types::Tpf - your pathfinder derived from CYapfBaseT

 *    - Types::NodeList - open/closed node list (look at CNodeList_HashTableT)

 *  NodeList needs to have defined local type Titem - defines the pathfinder node type.

 *  Node needs to define local type Key - the node key in the collection ()

 *

 *  For node list you can use template class CNodeList_HashTableT, for which

 *  you need to declare only your node type. Look at test_yapf.h for an example.

 *

 *

 *  Requirements to your pathfinder class derived from CYapfBaseT:

 *  --------------------------------------------------------------

 *  Your pathfinder derived class needs to implement following methods:

 *    inline void PfSetStartupNodes()

 *    inline void PfFollowNode(Node &org)

 *    inline bool PfCalcCost(Node &n)

 *    inline bool PfCalcEstimate(Node &n)

 */

template <class Types>

class CYapfBaseT {

public:

	typedef typename Types::Tpf Tpf;           ///< the pathfinder class (derived from THIS class)

	typedef typename Types::TrackFollower TrackFollower;

	typedef typename Types::NodeList NodeList; ///< our node list

	typedef typename Types::VehicleType VehicleType; ///< the type of vehicle

	typedef typename NodeList::Titem Node;     ///< this will be our node type

	typedef typename Node::Key Key;            ///< key to hash tables

	NodeList             m_nodes;              ///< node list multi-container

protected:

	Node                *m_pBestDestNode;      ///< pointer to the destination node found at last round

	Node                *m_pBestIntermediateNode; ///< here should be node closest to the destination if path not found

	const YAPFSettings  *m_settings;           ///< current settings (_settings_game.yapf)

	int                  m_max_search_nodes;   ///< maximum number of nodes we are allowed to visit before we give up

	const VehicleType   *m_veh;                ///< vehicle that we are trying to drive

	int                  m_stats_cost_calcs;   ///< stats - how many node's costs were calculated

	int                  m_stats_cache_hits;   ///< stats - how many node's costs were reused from cache

public:

	int                  m_num_steps;          ///< this is there for debugging purposes (hope it doesn't hurt)

public:

	/** default constructor */

	inline CYapfBaseT()

		: m_pBestDestNode(nullptr)

		, m_pBestIntermediateNode(nullptr)

		, m_settings(&_settings_game.pf.yapf)

		, m_max_search_nodes(PfGetSettings().max_search_nodes)

		, m_veh(nullptr)

		, m_stats_cost_calcs(0)

		, m_stats_cache_hits(0)

		, m_num_steps(0)

	{

	}

	/** default destructor */

	~CYapfBaseT() {}

protected:

	/** to access inherited path finder */

	inline Tpf& Yapf()

	{

		return *static_cast<Tpf *>(this);

	}

public:

	/** return current settings (can be custom - company based - but later) */

	inline const YAPFSettings& PfGetSettings() const

	{

		return *m_settings;

	}

	/**

	 * Main pathfinder routine:

	 *   - set startup node(s)

	 *   - main loop that stops if:

	 *      - the destination was found

	 *      - or the open list is empty (no route to destination).

	 *      - or the maximum amount of loops reached - m_max_search_nodes (default = 10000)

	 * @return true if the path was found

	 */

	inline bool FindPath(const VehicleType *v)

	{

		m_veh = v;

		Yapf().PfSetStartupNodes();

		bool bDestFound = true;

		for (;;) {

			m_num_steps++;

			Node *n = m_nodes.GetBestOpenNode();

			if (n == nullptr) {

				break;

			}

			/* if the best open node was worse than the best path found, we can finish */

			if (m_pBestDestNode != nullptr && m_pBestDestNode->GetCost() < n->GetCostEstimate()) {

				break;

			}

			Yapf().PfFollowNode(*n);

			if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) {

				m_nodes.PopOpenNode(n->GetKey());

				m_nodes.InsertClosedNode(*n);

			} else {

				bDestFound = false;

				break;

			}

		}

		bDestFound &= (m_pBestDestNode != nullptr);

		return bDestFound;

	}

	/**

	 * If path was found return the best node that has reached the destination. Otherwise

	 *  return the best visited node (which was nearest to the destination).

	 */

	inline Node *GetBestNode()

	{

		return (m_pBestDestNode != nullptr) ? m_pBestDestNode : m_pBestIntermediateNode;

	}

	/**

	 * Calls NodeList::CreateNewNode() - allocates new node that can be filled and used

	 *  as argument for AddStartupNode() or AddNewNode()

	 */

	inline Node& CreateNewNode()

	{

		Node &node = *m_nodes.CreateNewNode();

		return node;

	}

	/** Add new node (created by CreateNewNode and filled with data) into open list */

	inline void AddStartupNode(Node &n)

class CYapfSegmentCostCacheGlobalT : public CYapfSegmentCostCacheLocalT<Types> {

public:

	typedef CYapfSegmentCostCacheLocalT<Types> Tlocal;

	typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)

	typedef typename Types::NodeList::Titem Node; ///< this will be our node type

	typedef typename Node::Key Key;    ///< key to hash tables

	typedef typename Node::CachedData CachedData;

	typedef typename CachedData::Key CacheKey;

	typedef CSegmentCostCacheT<CachedData> Cache;

protected:

	Cache &m_global_cache;

	inline CYapfSegmentCostCacheGlobalT() : m_global_cache(stGetGlobalCache()) {};

	/** to access inherited path finder */

	inline Tpf& Yapf()

	{

		return *static_cast<Tpf *>(this);

	}

	inline static Cache& stGetGlobalCache()

	{

		static int last_rail_change_counter = 0;

		static Cache C;

		/* delete the cache sometimes... */

		if (last_rail_change_counter != Cache::s_rail_change_counter) {

			last_rail_change_counter = Cache::s_rail_change_counter;

			C.Flush();

		}

		return C;

	}

public:

	/**

	 * Called by YAPF to attach cached or local segment cost data to the given node.

	 *  @return true if globally cached data were used or false if local data was used

	 */

	inline bool PfNodeCacheFetch(Node &n)

	{

		if (!Yapf().CanUseGlobalCache(n)) {

			return Tlocal::PfNodeCacheFetch(n);

		}

		CacheKey key(n.GetKey());

		bool found;

		CachedData &item = m_global_cache.Get(key, &found);

		Yapf().ConnectNodeToCachedData(n, item);

		return found;

	}

	static const int s_max_segment_cost = 10000;

	CYapfCostRailT() : m_max_cost(0), m_disable_cache(false), m_stopped_on_first_two_way_signal(false)

	{

		/* pre-compute look-ahead penalties into array */

		int p0 = Yapf().PfGetSettings().rail_look_ahead_signal_p0;

		int p1 = Yapf().PfGetSettings().rail_look_ahead_signal_p1;

		int p2 = Yapf().PfGetSettings().rail_look_ahead_signal_p2;

		m_sig_look_ahead_costs.clear();

		m_sig_look_ahead_costs.reserve(Yapf().PfGetSettings().rail_look_ahead_max_signals);

		for (uint i = 0; i < Yapf().PfGetSettings().rail_look_ahead_max_signals; i++) {

			m_sig_look_ahead_costs.push_back(p0 + i * (p1 + i * p2));

		}

	}

	/** to access inherited path finder */

	Tpf& Yapf()

	{

		return *static_cast<Tpf *>(this);

	}

public:

	inline int SlopeCost(TileIndex tile, Trackdir td)

	{

		if (!stSlopeCost(tile, td)) return 0;

		return Yapf().PfGetSettings().rail_slope_penalty;

	}

	inline int CurveCost(Trackdir td1, Trackdir td2)

	{

		assert(IsValidTrackdir(td1));

		assert(IsValidTrackdir(td2));

		int cost = 0;

		if (TrackFollower::Allow90degTurns()

				&& HasTrackdir(TrackdirCrossesTrackdirs(td1), td2)) {

			/* 90-deg curve penalty */

			cost += Yapf().PfGetSettings().rail_curve90_penalty;

		} else if (td2 != NextTrackdir(td1)) {

			/* 45-deg curve penalty */

			cost += Yapf().PfGetSettings().rail_curve45_penalty;

		}

		return cost;

	}

	inline int SwitchCost(TileIndex tile1, TileIndex tile2, DiagDirection exitdir)

	{

		if (IsPlainRailTile(tile1) && IsPlainRailTile(tile2)) {

			bool t1 = KillFirstBit(GetTrackBits(tile1) & DiagdirReachesTracks(ReverseDiagDir(exitdir))) != TRACK_BIT_NONE;

		}

		return false;

	}

	/** The cost for reserved tiles, including skipped ones. */

	inline int ReservationCost(Node &n, TileIndex tile, Trackdir trackdir, int skipped)

	{

		if (n.m_num_signals_passed >= m_sig_look_ahead_costs.size() / 2) return 0;

		if (!IsPbsSignal(n.m_last_signal_type)) return 0;

		if (IsRailStationTile(tile) && IsAnyStationTileReserved(tile, trackdir, skipped)) {

			return Yapf().PfGetSettings().rail_pbs_station_penalty * (skipped + 1);

		} else if (TrackOverlapsTracks(GetReservedTrackbits(tile), TrackdirToTrack(trackdir))) {

			int cost = Yapf().PfGetSettings().rail_pbs_cross_penalty;

			if (!IsDiagonalTrackdir(trackdir)) cost = (cost * YAPF_TILE_CORNER_LENGTH) / YAPF_TILE_LENGTH;

			return cost * (skipped + 1);

		}

		return 0;

	}

	int SignalCost(Node &n, TileIndex tile, Trackdir trackdir)

	{

		int cost = 0;

		/* if there is one-way signal in the opposite direction, then it is not our way */

		if (IsTileType(tile, MP_RAILWAY)) {

			bool has_signal_against = HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir));

			bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);

			if (has_signal_against && !has_signal_along && IsOnewaySignal(tile, TrackdirToTrack(trackdir))) {

				/* one-way signal in opposite direction */

				n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;

			} else {

				if (has_signal_along) {

					SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);

					SignalType sig_type = GetSignalType(tile, TrackdirToTrack(trackdir));

					n.m_last_signal_type = sig_type;

					/* cache the look-ahead polynomial constant only if we didn't pass more signals than the look-ahead limit is */

					int look_ahead_cost = (n.m_num_signals_passed < m_sig_look_ahead_costs.size()) ? m_sig_look_ahead_costs[n.m_num_signals_passed] : 0;

					if (sig_state != SIGNAL_STATE_RED) {

						/* green signal */

						n.flags_u.flags_s.m_last_signal_was_red = false;

						/* negative look-ahead red-signal penalties would cause problems later, so use them as positive penalties for green signal */

						if (look_ahead_cost < 0) {

							/* add its negation to the cost */

							cost -= look_ahead_cost;

						}

					} else {

		} else if (missing_platform_length > 0) {

			/* apply penalty for shorter platform than needed */

			cost += Yapf().PfGetSettings().rail_shorter_platform_penalty + Yapf().PfGetSettings().rail_shorter_platform_per_tile_penalty * missing_platform_length;

		}

		return cost;

	}

public:

	inline void SetMaxCost(int max_cost)

	{

		m_max_cost = max_cost;

	}

	/**

	 * Called by YAPF to calculate the cost from the origin to the given node.

	 *  Calculates only the cost of given node, adds it to the parent node cost

	 *  and stores the result into Node::m_cost member

	 */

	inline bool PfCalcCost(Node &n, const TrackFollower *tf)

	{

		assert(!n.flags_u.flags_s.m_targed_seen);

		assert(tf->m_new_tile == n.m_key.m_tile);

		assert((HasTrackdir(tf->m_new_td_bits, n.m_key.m_td)));

		/* Does the node have some parent node? */

		bool has_parent = (n.m_parent != nullptr);

		/* Do we already have a cached segment? */

		CachedData &segment = *n.m_segment;

		bool is_cached_segment = (segment.m_cost >= 0);

		int parent_cost = has_parent ? n.m_parent->m_cost : 0;

		/* Each node cost contains 2 or 3 main components:

		 *  1. Transition cost - cost of the move from previous node (tile):

		 *    - curve cost (or zero for straight move)

		 *  2. Tile cost:

		 *    - base tile cost

		 *      - YAPF_TILE_LENGTH for diagonal tiles

		 *      - YAPF_TILE_CORNER_LENGTH for non-diagonal tiles

		 *    - tile penalties

		 *      - tile slope penalty (upward slopes)

		 *      - red signal penalty

		 *      - level crossing penalty

		 *      - speed-limit penalty (bridges)

		 *      - station platform penalty

		 *      - penalty for reversing in the depot

		 *      - etc.

		 *    - last red signal penalty

		 *    - penalty for too long or too short platform on the destination station

		 */

		int transition_cost = 0;

		int extra_cost = 0;

		/* Segment: one or more tiles connected by contiguous tracks of the same type.

		 * Each segment cost includes 'Tile cost' for all its tiles (including the first

		 * and last), and the 'Transition cost' between its tiles. The first transition

		 * cost of segment entry (move from the 'parent' node) is not included!

		 */

		int segment_entry_cost = 0;

		int segment_cost = 0;

		const Train *v = Yapf().GetVehicle();

		/* start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment */

		TILE cur(n.m_key.m_tile, n.m_key.m_td);

		/* the previous tile will be needed for transition cost calculations */

		TILE prev = !has_parent ? TILE() : TILE(n.m_parent->GetLastTile(), n.m_parent->GetLastTrackdir());

		EndSegmentReasonBits end_segment_reason = ESRB_NONE;

		if (!has_parent) {

			/* We will jump to the middle of the cost calculator assuming that segment cache is not used. */

			assert(!is_cached_segment);

			/* Skip the first transition cost calculation. */

			goto no_entry_cost;

		}

		for (;;) {

			/* Transition cost (cost of the move from previous tile) */

			transition_cost = Yapf().CurveCost(prev.td, cur.td);

			transition_cost += Yapf().SwitchCost(prev.tile, cur.tile, TrackdirToExitdir(prev.td));

			/* First transition cost counts against segment entry cost, other transitions

			 * inside segment will come to segment cost (and will be cached) */

			if (segment_cost == 0) {

				/* We just entered the loop. First transition cost goes to segment entry cost)*/

				segment_entry_cost = transition_cost;

				transition_cost = 0;

				/* It is the right time now to look if we can reuse the cached segment cost. */

				if (is_cached_segment) {

					/* Yes, we already know the segment cost. */

					segment_cost = segment.m_cost;

			/* Apply min/max speed penalties only when inside the look-ahead radius. Otherwise

			 * it would cause desync in MP. */

			if (n.m_num_signals_passed < m_sig_look_ahead_costs.size())

			{

				int min_speed = 0;

				int max_speed = tf->GetSpeedLimit(&min_speed);

				int max_veh_speed = std::min<int>(v->GetDisplayMaxSpeed(), v->current_order.GetMaxSpeed());

				if (max_speed < max_veh_speed) {

					extra_cost += YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (4 + tf->m_tiles_skipped) / max_veh_speed;

				}

				if (min_speed > max_veh_speed) {

					extra_cost += YAPF_TILE_LENGTH * (min_speed - max_veh_speed);

				}

			}

			/* Finish if we already exceeded the maximum path cost (i.e. when

			 * searching for the nearest depot). */

			if (m_max_cost > 0 && (parent_cost + segment_entry_cost + segment_cost) > m_max_cost) {

				end_segment_reason |= ESRB_PATH_TOO_LONG;

			}

			/* Move to the next tile/trackdir. */

			tf = &tf_local;

			if (!tf_local.Follow(cur.tile, cur.td)) {

				assert(tf_local.m_err != TrackFollower::EC_NONE);

				/* Can't move to the next tile (EOL?). */

				if (tf_local.m_err == TrackFollower::EC_RAIL_ROAD_TYPE) {

					end_segment_reason |= ESRB_RAIL_TYPE;

				} else {