summaryrefslogtreecommitdiff
path: root/src/pathfinder/yapf/yapf_base.hpp
diff options
context:
space:
mode:
authorrubidium <rubidium@openttd.org>2009-12-01 22:45:39 +0000
committerrubidium <rubidium@openttd.org>2009-12-01 22:45:39 +0000
commitf52e27c688b00fd2b44887f0694717cd8449d31d (patch)
tree1268b38bfce0d85fd3868c19fb1454460ef135e7 /src/pathfinder/yapf/yapf_base.hpp
parenta7beae873310c67c8761994269627ebeabf08996 (diff)
downloadopenttd-f52e27c688b00fd2b44887f0694717cd8449d31d.tar.xz
(svn r18364) -Codechange: move the pathfinders and their related files into a separate directory
Diffstat (limited to 'src/pathfinder/yapf/yapf_base.hpp')
-rw-r--r--src/pathfinder/yapf/yapf_base.hpp361
1 files changed, 361 insertions, 0 deletions
diff --git a/src/pathfinder/yapf/yapf_base.hpp b/src/pathfinder/yapf/yapf_base.hpp
new file mode 100644
index 000000000..0011e0802
--- /dev/null
+++ b/src/pathfinder/yapf/yapf_base.hpp
@@ -0,0 +1,361 @@
+/* $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 */