(svn r18364) -Codechange: move the pathfinders and their related files into a separate directory

1 files changed, 0 insertions, 361 deletions

diff --git a/src/yapf/yapf_base.hpp b/src/yapf/yapf_base.hpp
deleted file mode 100644
index d15e4edc9..000000000
--- a/src/yapf/yapf_base.hpp
+++ /dev/null
@@ -1,361 +0,0 @@
-/* $Id$ */
-
-/*
- * 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"
-
-extern int _total_pf_time_us;
-
-/** 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.
- *
- *
- *  Requrements to your pathfinder class derived from CYapfBaseT:
- *  -------------------------------------------------------------
- *  Your pathfinder derived class needs to implement following methods:
- *    FORCEINLINE void PfSetStartupNodes()
- *    FORCEINLINE void PfFollowNode(Node& org)
- *    FORCEINLINE bool PfCalcCost(Node& n)
- *    FORCEINLINE bool PfCalcEstimate(Node& n)
- *    FORCEINLINE bool PfDetectDestination(Node& n)
- *
- *  For more details about those methods, look at the end of CYapfBaseT
- *  declaration. There are some examples. For another example look at
- *  test_yapf.h (part or unittest project).
- */
-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 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 Vehicle       *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:
-	CPerformanceTimer    m_perf_cost;          ///< stats - total CPU time of this run
-	CPerformanceTimer    m_perf_slope_cost;    ///< stats - slope calculation CPU time
-	CPerformanceTimer    m_perf_ts_cost;       ///< stats - GetTrackStatus() CPU time
-	CPerformanceTimer    m_perf_other_cost;    ///< stats - other CPU time
-
-public:
-	int                  m_num_steps;          ///< this is there for debugging purposes (hope it doesn't hurt)
-
-public:
-	/** default constructor */
-	FORCEINLINE CYapfBaseT()
-		: m_pBestDestNode(NULL)
-		, m_pBestIntermediateNode(NULL)
-		, m_settings(&_settings_game.pf.yapf)
-		, m_max_search_nodes(PfGetSettings().max_search_nodes)
-		, m_veh(NULL)
-		, m_stats_cost_calcs(0)
-		, m_stats_cache_hits(0)
-		, m_num_steps(0)
-	{
-	}
-
-	/** default destructor */
-	~CYapfBaseT() {}
-
-protected:
-	/** to access inherited path finder */
-	FORCEINLINE Tpf& Yapf()
-	{
-		return *static_cast<Tpf*>(this);
-	}
-
-public:
-	/** return current settings (can be custom - company based - but later) */
-	FORCEINLINE 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 Vehicle *v)
-	{
-		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 (n == NULL) {
-				break;
-			}
-
-			/* 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;
-			}
-		}
-
-		bool bDestFound = (m_pBestDestNode != NULL) && (m_pBestDestNode != m_pBestIntermediateNode);
-
-#ifndef NO_DEBUG_MESSAGES
-		perf.Stop();
-		if (_debug_yapf_level >= 2) {
-			int t = perf.Get(1000000);
-			_total_pf_time_us += t;
-
-			if (_debug_yapf_level >= 3) {
-				UnitID veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0;
-				char ttc = Yapf().TransportTypeChar();
-				float cache_hit_ratio = (m_stats_cache_hits == 0) ? 0.0f : ((float)m_stats_cache_hits / (float)(m_stats_cache_hits + m_stats_cost_calcs) * 100.0f);
-				int cost = bDestFound ? m_pBestDestNode->m_cost : -1;
-				int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;
-
-				DEBUG(yapf, 3, "[YAPF%c]%c%4d- %d us - %d rounds - %d open - %d closed - CHR %4.1f%% - C %d D %d - c%d(sc%d, ts%d, o%d) -- ",
-					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).
-	 */
-	FORCEINLINE Node *GetBestNode()
-	{
-		return (m_pBestDestNode != NULL) ? m_pBestDestNode : m_pBestIntermediateNode;
-	}
-
-	/** 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 */
-	FORCEINLINE void AddStartupNode(Node& n)
-	{
-		Yapf().PfNodeCacheFetch(n);
-		/* insert the new node only if it is not there */
-		if (m_nodes.FindOpenNode(n.m_key) == NULL) {
-			m_nodes.InsertOpenNode(n);
-		} else {
-			/* if we are here, it means that node is already there - how it is possible?
-			 *   probably the train is in the position that both its ends point to the same tile/exit-dir
-			 *   very unlikely, but it happened */
-		}
-	}
-
-	/** add multiple nodes - direct children of the given node */
-	FORCEINLINE void AddMultipleNodes(Node *parent, const TrackFollower &tf)
-	{
-		bool is_choice = (KillFirstBit(tf.m_new_td_bits) != TRACKDIR_BIT_NONE);
-		for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
-			Trackdir td = (Trackdir)FindFirstBit2x64(rtds);
-			Node& n = Yapf().CreateNewNode();
-			n.Set(parent, tf.m_new_tile, td, is_choice);
-			Yapf().AddNewNode(n, tf);
-		}
-	}
-
-	/** AddNewNode() - called by Tderived::PfFollowNode() for each child node.
-	 *  Nodes are evaluated here and added into open list */
-	void AddNewNode(Node &n, const TrackFollower &tf)
-	{
-		/* evaluate the node */
-		bool bCached = Yapf().PfNodeCacheFetch(n);
-		if (!bCached) {
-			m_stats_cost_calcs++;
-		} else {
-			m_stats_cache_hits++;
-		}
-
-		bool bValid = Yapf().PfCalcCost(n, &tf);
-
-		if (bCached) {
-			Yapf().PfNodeCacheFlush(n);
-		}
-
-		if (bValid) bValid = Yapf().PfCalcEstimate(n);
-
-		/* have the cost or estimate callbacks marked this node as invalid? */
-		if (!bValid) return;
-
-		/* detect the destination */
-		bool bDestination = Yapf().PfDetectDestination(n);
-		if (bDestination) {
-			if (m_pBestDestNode == NULL || n < *m_pBestDestNode) {
-				m_pBestDestNode = &n;
-			}
-			m_nodes.FoundBestNode(n);
-			return;
-		}
-
-		if (m_max_search_nodes > 0 && (m_pBestIntermediateNode == NULL || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()))) {
-			m_pBestIntermediateNode = &n;
-		}
-
-		/* check new node against open list */
-		Node *openNode = m_nodes.FindOpenNode(n.GetKey());
-		if (openNode != NULL) {
-			/* another node exists with the same key in the open list
-			 * is it better than new one? */
-			if (n.GetCostEstimate() < openNode->GetCostEstimate()) {
-				/* update the old node by value from new one */
-				m_nodes.PopOpenNode(n.GetKey());
-				*openNode = n;
-				/* add the updated old node back to open list */
-				m_nodes.InsertOpenNode(*openNode);
-			}
-			return;
-		}
-
-		/* check new node against closed list */
-		Node *closedNode = m_nodes.FindClosedNode(n.GetKey());
-		if (closedNode != NULL) {
-			/* another node exists with the same key in the closed list
-			 * is it better than new one? */
-			int node_est = n.GetCostEstimate();
-			int closed_est = closedNode->GetCostEstimate();
-			if (node_est < closed_est) {
-				/* If this assert occurs, you have probably problem in
-				 * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
-				 * The problem could be:
-				 *  - PfCalcEstimate() gives too large numbers
-				 *  - PfCalcCost() gives too small numbers
-				 *  - You have used negative cost penalty in some cases (cost bonus) */
-				NOT_REACHED();
-			}
-			return;
-		}
-		/* the new node is really new
-		 * add it to the open list */
-		m_nodes.InsertOpenNode(n);
-	}
-
-	const Vehicle * GetVehicle() const
-	{
-		return m_veh;
-	}
-
-	void DumpBase(DumpTarget &dmp) const
-	{
-		dmp.WriteStructT("m_nodes", &m_nodes);
-		dmp.WriteLine("m_num_steps = %d", m_num_steps);
-	}
-
-	/* methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT) */
-
-#if 0
-	/** Example: PfSetStartupNodes() - set source (origin) nodes */
-	FORCEINLINE void PfSetStartupNodes()
-	{
-		/* example: */
-		Node& n1 = *base::m_nodes.CreateNewNode();
-		.
-		. // setup node members here
-		.
-		base::m_nodes.InsertOpenNode(n1);
-	}
-
-	/** Example: PfFollowNode() - set following (child) nodes of the given node */
-	FORCEINLINE void PfFollowNode(Node& org)
-	{
-		for (each follower of node org) {
-			Node& n = *base::m_nodes.CreateNewNode();
-			.
-			. // setup node members here
-			.
-			n.m_parent   = &org; // set node's parent to allow back tracking
-			AddNewNode(n);
-		}
-	}
-
-	/** Example: PfCalcCost() - set path cost from origin to the given node */
-	FORCEINLINE bool PfCalcCost(Node& n)
-	{
-		/* evaluate last step cost */
-		int cost = ...;
-		/* set the node cost as sum of parent's cost and last step cost */
-		n.m_cost = n.m_parent->m_cost + cost;
-		return true; // true if node is valid follower (i.e. no obstacle was found)
-	}
-
-	/** Example: PfCalcEstimate() - set path cost estimate from origin to the target through given node */
-	FORCEINLINE bool PfCalcEstimate(Node& n)
-	{
-		/* evaluate the distance to our destination */
-		int distance = ...;
-		/* set estimate as sum of cost from origin + distance to the target */
-		n.m_estimate = n.m_cost + distance;
-		return true; // true if node is valid (i.e. not too far away :)
-	}
-
-	/** Example: PfDetectDestination() - return true if the given node is our destination */
-	FORCEINLINE bool PfDetectDestination(Node& n)
-	{
-		bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
-		return bDest;
-	}
-#endif
-};
-
-#endif /* YAPF_BASE_HPP */