src/pathfinder/yapf/yapf_base.hpp

   1 /* $Id$ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * 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.
   6  * 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.
   7  * 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/>.
   8  */
   9
  10 /** @file yapf_base.hpp Base classes for YAPF. */
  11
  12 #ifndef YAPF_BASE_HPP
  13 #define YAPF_BASE_HPP
  14
  15 #include "../../debug.h"
  16 #include "../../settings_type.h"
  17
  18 extern int _total_pf_time_us;
  19
  20 /**
  21  * CYapfBaseT - A-star type path finder base class.
  22  *  Derive your own pathfinder from it. You must provide the following template argument:
  23  *    Types      - used as collection of local types used in pathfinder
  24  *
  25  * Requirements for the Types struct:
  26  *  ----------------------------------
  27  *  The following types must be defined in the 'Types' argument:
  28  *    - Types::Tpf - your pathfinder derived from CYapfBaseT
  29  *    - Types::NodeList - open/closed node list
  30  *  NodeList needs to have defined local type Node - defines the pathfinder node type.
  31  *  Node needs to define local type Key - the node key in the collection ()
  32  *
  33  *
  34  *  Requirements to your pathfinder class derived from CYapfBaseT:
  35  *  --------------------------------------------------------------
  36  *  Your pathfinder derived class needs to implement following methods:
  37  *    inline void PfSetStartupNodes()
  38  *    inline void PfFollowNode(Node& org)
  39  *    inline bool PfCalcCost(Node& n)
  40  *    inline bool PfCalcEstimate(Node& n)
  41  *    inline bool PfDetectDestination(Node& n)
  42  *
  43  *  For more details about those methods, look at the end of CYapfBaseT
  44  *  declaration. There are some examples. For another example look at
  45  *  test_yapf.h (part or unittest project).
  46  */
  47 template <class Types>
  48 class CYapfBaseT {
  49 public:
  50         typedef typename Types::Tpf Tpf;           ///< the pathfinder class (derived from THIS class)
  51         typedef typename Types::TrackFollower TrackFollower;
  52         typedef typename Types::NodeList NodeList; ///< our node list
  53         typedef typename Types::VehicleType VehicleType; ///< the type of vehicle
  54         typedef typename NodeList::Node Node;      ///< this will be our node type
  55         typedef typename Node::Key Key;            ///< key to hash tables
  56
  57
  58         NodeList             m_nodes;              ///< node list multi-container
  59 protected:
  60         Node                *m_pBestDestNode;      ///< pointer to the destination node found at last round
  61         Node                *m_pBestIntermediateNode; ///< here should be node closest to the destination if path not found
  62         const YAPFSettings  *m_settings;           ///< current settings (_settings_game.yapf)
  63         int                  m_max_search_nodes;   ///< maximum number of nodes we are allowed to visit before we give up
  64         const VehicleType   *m_veh;                ///< vehicle that we are trying to drive
  65
  66         int                  m_stats_cost_calcs;   ///< stats - how many node's costs were calculated
  67         int                  m_stats_cache_hits;   ///< stats - how many node's costs were reused from cache
  68
  69 public:
  70         CPerformanceTimer    m_perf_cost;          ///< stats - total CPU time of this run
  71         CPerformanceTimer    m_perf_slope_cost;    ///< stats - slope calculation CPU time
  72         CPerformanceTimer    m_perf_ts_cost;       ///< stats - GetTrackStatus() CPU time
  73         CPerformanceTimer    m_perf_other_cost;    ///< stats - other CPU time
  74
  75 public:
  76         int                  m_num_steps;          ///< this is there for debugging purposes (hope it doesn't hurt)
  77
  78 public:
  79         /** default constructor */
  80         inline CYapfBaseT()
  81                 : m_pBestDestNode(NULL)
  82                 , m_pBestIntermediateNode(NULL)
  83                 , m_settings(&_settings_game.pf.yapf)
  84                 , m_max_search_nodes(PfGetSettings().max_search_nodes)
  85                 , m_veh(NULL)
  86                 , m_stats_cost_calcs(0)
  87                 , m_stats_cache_hits(0)
  88                 , m_num_steps(0)
  89         {
  90         }
  91
  92         /** default destructor */
  93         ~CYapfBaseT() {}
  94
  95 protected:
  96         /** to access inherited path finder */
  97         inline Tpf& Yapf()
  98         {
  99                 return *static_cast<Tpf*>(this);
 100         }
 101
 102 public:
 103         /** return current settings (can be custom - company based - but later) */
 104         inline const YAPFSettings& PfGetSettings() const
 105         {
 106                 return *m_settings;
 107         }
 108
 109         /**
 110          * Main pathfinder routine:
 111          *   - set startup node(s)
 112          *   - main loop that stops if:
 113          *      - the destination was found
 114          *      - or the open list is empty (no route to destination).
 115          *      - or the maximum amount of loops reached - m_max_search_nodes (default = 10000)
 116          * @return true if the path was found
 117          */
 118         inline bool FindPath(const VehicleType *v)
 119         {
 120                 m_veh = v;
 121
 122 #ifndef NO_DEBUG_MESSAGES
 123                 CPerformanceTimer perf;
 124                 perf.Start();
 125 #endif /* !NO_DEBUG_MESSAGES */
 126
 127                 Yapf().PfSetStartupNodes();
 128                 bool bDestFound = true;
 129
 130                 for (;;) {
 131                         m_num_steps++;
 132                         Node *n = m_nodes.GetBestOpenNode();
 133                         if (n == NULL) {
 134                                 break;
 135                         }
 136
 137                         /* if the best open node was worse than the best path found, we can finish */
 138                         if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n->GetCostEstimate()) {
 139                                 break;
 140                         }
 141
 142                         Yapf().PfFollowNode(*n);
 143                         if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) {
 144                                 m_nodes.PopOpenNode(n->GetKey());
 145                                 m_nodes.InsertClosedNode(*n);
 146                         } else {
 147                                 bDestFound = false;
 148                                 break;
 149                         }
 150                 }
 151
 152                 bDestFound &= (m_pBestDestNode != NULL);
 153
 154 #ifndef NO_DEBUG_MESSAGES
 155                 perf.Stop();
 156                 if (_debug_yapf_level >= 2) {
 157                         int t = perf.Get(1000000);
 158                         _total_pf_time_us += t;
 159
 160                         if (_debug_yapf_level >= 3) {
 161                                 UnitID veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0;
 162                                 char ttc = Yapf().TransportTypeChar();
 163                                 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);
 164                                 int cost = bDestFound ? m_pBestDestNode->m_cost : -1;
 165                                 int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;
 166
 167                                 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) -- ",
 168                                         ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(),
 169                                         cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000),
 170                                         m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000)
 171                                 );
 172                         }
 173                 }
 174 #endif /* !NO_DEBUG_MESSAGES */
 175                 return bDestFound;
 176         }
 177
 178         /**
 179          * If path was found return the best node that has reached the destination. Otherwise
 180          *  return the best visited node (which was nearest to the destination).
 181          */
 182         inline Node *GetBestNode()
 183         {
 184                 return (m_pBestDestNode != NULL) ? m_pBestDestNode : m_pBestIntermediateNode;
 185         }
 186
 187         /** Add new node (created by CreateNewNode and filled with data) into open list */
 188         inline void AddStartupNode(Node& n)
 189         {
 190                 Yapf().PfNodeCacheFetch(n);
 191                 m_nodes.InsertInitialNode(&n);
 192         }
 193
 194         /** Create and add a new node */
 195         inline void AddStartupNode (const PathPos &pos, bool is_choice, int cost = 0)
 196         {
 197                 Node &node = *m_nodes.CreateNewNode (NULL, pos, is_choice);
 198                 node.m_cost = cost;
 199                 AddStartupNode (node);
 200         }
 201
 202         /** add multiple nodes - direct children of the given node */
 203         inline void AddMultipleNodes(Node *parent, const TrackFollower &tf)
 204         {
 205                 bool is_choice = !tf.m_new.is_single();
 206                 PathPos pos = tf.m_new;
 207                 for (TrackdirBits rtds = tf.m_new.trackdirs; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
 208                         pos.td = FindFirstTrackdir(rtds);
 209                         Node& n = *m_nodes.CreateNewNode(parent, pos, is_choice);
 210                         AddNewNode(n, tf);
 211                 }
 212         }
 213
 214         /**
 215          * In some cases an intermediate node branch should be pruned.
 216          * The most prominent case is when a red EOL signal is encountered, but
 217          * there was a segment change (e.g. a rail type change) before that. If
 218          * the branch would not be pruned, the rail type change location would
 219          * remain the best intermediate node, and thus the vehicle would still
 220          * go towards the red EOL signal.
 221          */
 222         void PruneIntermediateNodeBranch()
 223         {
 224                 while (m_pBestIntermediateNode != NULL && (m_pBestIntermediateNode->m_segment->m_end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) {
 225                         m_pBestIntermediateNode = m_pBestIntermediateNode->m_parent;
 226                 }
 227         }
 228
 229         /**
 230          * AddNewNode() - called by Tderived::PfFollowNode() for each child node.
 231          *  Nodes are evaluated here and added into open list
 232          */
 233         void AddNewNode(Node &n, const TrackFollower &tf)
 234         {
 235                 /* evaluate the node */
 236                 bool bCached = Yapf().PfNodeCacheFetch(n);
 237                 if (!bCached) {
 238                         m_stats_cost_calcs++;
 239                 } else {
 240                         m_stats_cache_hits++;
 241                 }
 242
 243                 bool bValid = Yapf().PfCalcCost(n, &tf);
 244
 245                 if (bCached) {
 246                         Yapf().PfNodeCacheFlush(n);
 247                 }
 248
 249                 if (bValid) bValid = Yapf().PfCalcEstimate(n);
 250
 251                 /* have the cost or estimate callbacks marked this node as invalid? */
 252                 if (!bValid) return;
 253
 254                 /* detect the destination */
 255                 bool bDestination = Yapf().PfDetectDestination(n);
 256                 if (bDestination) {
 257                         if (m_pBestDestNode == NULL || n < *m_pBestDestNode) {
 258                                 m_pBestDestNode = &n;
 259                         }
 260                         m_nodes.FoundBestNode(&n);
 261                         return;
 262                 }
 263
 264                 if (m_max_search_nodes > 0 && (m_pBestIntermediateNode == NULL || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()))) {
 265                         m_pBestIntermediateNode = &n;
 266                 }
 267
 268                 m_nodes.InsertNode(&n);
 269         }
 270
 271         const VehicleType * GetVehicle() const
 272         {
 273                 return m_veh;
 274         }
 275
 276         void DumpBase(DumpTarget &dmp) const
 277         {
 278                 dmp.WriteStructT("m_nodes", &m_nodes);
 279                 dmp.WriteLine("m_num_steps = %d", m_num_steps);
 280         }
 281
 282         /* methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT) */
 283
 284 #if 0
 285         /** Example: PfSetStartupNodes() - set source (origin) nodes */
 286         inline void PfSetStartupNodes()
 287         {
 288                 /* example: */
 289                 Node& n1 = *base::m_nodes.CreateNewNode();
 290                 .
 291                 . // setup node members here
 292                 .
 293                 base::m_nodes.InsertOpenNode(n1);
 294         }
 295
 296         /** Example: PfFollowNode() - set following (child) nodes of the given node */
 297         inline void PfFollowNode(Node& org)
 298         {
 299                 for (each follower of node org) {
 300                         Node& n = *base::m_nodes.CreateNewNode();
 301                         .
 302                         . // setup node members here
 303                         .
 304                         n.m_parent   = &org; // set node's parent to allow back tracking
 305                         AddNewNode(n);
 306                 }
 307         }
 308
 309         /** Example: PfCalcCost() - set path cost from origin to the given node */
 310         inline bool PfCalcCost(Node& n)
 311         {
 312                 /* evaluate last step cost */
 313                 int cost = ...;
 314                 /* set the node cost as sum of parent's cost and last step cost */
 315                 n.m_cost = n.m_parent->m_cost + cost;
 316                 return true; // true if node is valid follower (i.e. no obstacle was found)
 317         }
 318
 319         /** Example: PfCalcEstimate() - set path cost estimate from origin to the target through given node */
 320         inline bool PfCalcEstimate(Node& n)
 321         {
 322                 /* evaluate the distance to our destination */
 323                 int distance = ...;
 324                 /* set estimate as sum of cost from origin + distance to the target */
 325                 n.m_estimate = n.m_cost + distance;
 326                 return true; // true if node is valid (i.e. not too far away :)
 327         }
 328
 329         /** Example: PfDetectDestination() - return true if the given node is our destination */
 330         inline bool PfDetectDestination(Node& n)
 331         {
 332                 bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
 333                 return bDest;
 334         }
 335 #endif
 336 };
 337
 338 #endif /* YAPF_BASE_HPP */