m_veh = v;

#ifndef NO_DEBUG_MESSAGES

		CPerformanceTimer perf;

		perf.Start();

#endif /* !NO_DEBUG_MESSAGES */

		Yapf().PfSetStartupNodes();

		while (true) {

			m_num_steps++;

			Node *n = m_nodes.GetBestOpenNode();

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

			if (m_pBestDestNode != NULL && 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 {

				m_pBestDestNode = m_pBestIntermediateNode;

				break;

			  ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(),

			  cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000),

			  m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000)

			);

		}

#endif /* !NO_DEBUG_MESSAGES */

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

	 */

	{

	}

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

	 *  as argument for AddStartupNode() or AddNewNode()

	 */

	FORCEINLINE Node& CreateNewNode()

	{

		Node& node = *m_nodes.CreateNewNode();

		return node;

	}

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

	{

		// set origin and destination nodes

		Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, true);

		Yapf().SetDestination(v);

		Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance);

		// find the best path

		bool bFound = Yapf().FindPath(v);

		if (!bFound) return false;

		// some path found

		// get found depot tile

		// walk through the path back to the origin

		while (pNode->m_parent != NULL) {

			pNode = pNode->m_parent;

		}

		// if the origin node is our front vehicle tile/Trackdir then we didn't reverse

		// but we can also look at the cost (== 0 -> not reversed, == reverse_penalty -> reversed)

		*reversed = (pNode->m_cost != 0);

		return true;

	}

};

		Yapf().SetDestination(v);

		// find the best path

		bool path_found = Yapf().FindPath(v);

		if (path_not_found != NULL) {

			// tell controller that the path was only 'guessed'

			// treat the path as found if stopped on the first two way signal(s)

			*path_not_found = !(path_found || Yapf().m_stopped_on_first_two_way_signal);

		}

		// if path not found - return INVALID_TRACKDIR

		Trackdir next_trackdir = INVALID_TRACKDIR;

		if (pNode != NULL) {

			// path was found or at least suggested

			// walk through the path back to the origin

			Node* pPrev = NULL;

			while (pNode->m_parent != NULL) {

				pPrev = pNode;

				pNode = pNode->m_parent;

			}

			// return trackdir from the best origin node (one of start nodes)

			Node& best_next_node = *pPrev;

			assert(best_next_node.GetTile() == tile);

			next_trackdir = best_next_node.GetTrackdir();

		// create pathfinder instance

		// set origin and destination nodes

		Yapf().SetOrigin(t1, td1, t2, td2, 1, false);

		Yapf().SetDestination(v);

		// find the best path

		bool bFound = Yapf().FindPath(v);

		if (!bFound) return false;

		// path was found

		// walk through the path back to the origin

		while (pNode->m_parent != NULL) {

			pNode = pNode->m_parent;

		}

		// check if it was reversed origin

		Node& best_org_node = *pNode;

		bool reversed = (best_org_node.m_cost != 0);

		return reversed;

	}

};

template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class TdestinationT, template <class Types> class TfollowT>

		uint dest_ts = GetTileTrackStatus(dest_tile, TRANSPORT_ROAD);

		TrackdirBits dest_trackdirs = (TrackdirBits)(dest_ts & TRACKDIR_BIT_MASK);

		// set origin and destination nodes

		Yapf().SetOrigin(src_tile, src_trackdirs);

		Yapf().SetDestination(dest_tile, dest_trackdirs);

		// find the best path

		Yapf().FindPath(v);

		// if path not found - return INVALID_TRACKDIR

		Trackdir next_trackdir = INVALID_TRACKDIR;

		if (pNode != NULL) {

			// path was found or at least suggested

			// walk through the path back to its origin

			while (pNode->m_parent != NULL) {

				pNode = pNode->m_parent;

			}

			// return trackdir from the best origin node (one of start nodes)

			Node& best_next_node = *pNode;

			assert(best_next_node.GetTile() == tile);

			next_trackdir = best_next_node.GetTrackdir();

		}

		return next_trackdir;

		// set destination tile, trackdir

		//   get available trackdirs on the destination tile

		uint dest_ts = GetTileTrackStatus(dst_tile, TRANSPORT_ROAD);

		TrackdirBits dst_td_bits = (TrackdirBits)(dest_ts & TRACKDIR_BIT_MASK);

		Yapf().SetDestination(dst_tile, dst_td_bits);

		// find the best path

		Yapf().FindPath(v);

		// if path not found - return distance = UINT_MAX

		uint dist = UINT_MAX;

		if (pNode != NULL) {

			// path was found or at least suggested

			// get the path cost estimate

			dist = pNode->GetCostEstimate();

		}

		return dist;

	}

	/** Return true if the valid origin (tile/trackdir) was set from the current vehicle position. */

	FORCEINLINE bool SetOriginFromVehiclePos(const Vehicle *v)

	{

	FORCEINLINE Depot* FindNearestDepot(const Vehicle* v, TileIndex tile, Trackdir td)

	{

		// set origin and destination nodes

		Yapf().SetOrigin(tile, TrackdirToTrackdirBits(td));

		// find the best path

		bool bFound = Yapf().FindPath(v);

		if (!bFound) return false;

		// some path found

		// get found depot tile

		assert(IsTileDepotType(depot_tile, TRANSPORT_ROAD));

		Depot* ret = GetDepotByTile(depot_tile);

		return ret;

	}

};

template <class Tpf_, class Tnode_list, template <class Types> class Tdestination>

struct CYapfRoad_TypesT

{

	typedef CYapfRoad_TypesT<Tpf_, Tnode_list, Tdestination>  Types;

	typedef Tpf_                              Tpf;

		// create pathfinder instance

		Tpf pf;

		// set origin and destination nodes

		pf.SetOrigin(src_tile, trackdirs);

		pf.SetDestination(v->dest_tile, dest_trackdirs);

		// find best path

		bool bFound = pf.FindPath(v);

		Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"

		if (bFound) {

			// path was found

			// walk through the path back to the origin

			Node* pPrevNode = NULL;

			while (pNode->m_parent != NULL) {

				pPrevNode = pNode;

				pNode = pNode->m_parent;

			}

			// return trackdir from the best next node (direct child of origin)

			Node& best_next_node = *pPrevNode;

			assert(best_next_node.GetTile() == tile);

			next_trackdir = best_next_node.GetTrackdir();

		}

		return next_trackdir;

	}