add_subdirectory(npf)

add_subdirectory(yapf)

add_files(

    follow_track.hpp

    pathfinder_func.h

    pathfinder_type.h

)

#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,

	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;

	}

		/* 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()

/*

 * 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"

 * 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"

 * 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 ()

	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)

	 * 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()) {

			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;

	}

	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

		}

	}

	/** 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 */

		} 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;

	/**

	 * 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)

		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));

					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 {

					end_segment_reason |= ESRB_DEAD_END;

				}

				if (TrackFollower::DoTrackMasking() && !HasOnewaySignalBlockingTrackdir(cur.tile, cur.td)) {

					end_segment_reason |= ESRB_SAFE_TILE;

	pf1.DumpBase(dmp1);

	pf2.DumpBase(dmp2);

	FILE *f1 = fopen("yapf1.txt", "wt");

	FILE *f2 = fopen("yapf2.txt", "wt");

	assert(f1 != nullptr);

	assert(f2 != nullptr);

	fwrite(dmp1.m_out.c_str(), 1, dmp1.m_out.size(), f1);

	fwrite(dmp2.m_out.c_str(), 1, dmp2.m_out.size(), f2);

	fclose(f1);

	fclose(f2);

}

template <class Types>

class CYapfReserveTrack

{

public:

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

	typedef typename Types::TrackFollower TrackFollower;

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

protected:

	/** to access inherited pathfinder */

	inline Tpf& Yapf()

	{