src/pathfinder/yapf/yapf_base.hpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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/>.
   6  */
   7
   8 /** @file yapf_base.hpp Base classes for YAPF. */
   9
  10 #ifndef YAPF_BASE_HPP
  11 #define YAPF_BASE_HPP
  12
  13 #include "../../debug.h"
  14 #include "../../settings_type.h"
  15
  16 /**
  17  * CYapfBaseT - A-star type path finder base class.
  18  *  Derive your own pathfinder from it. You must provide the following template argument:
  19  *    Types      - used as collection of local types used in pathfinder
  20  *
  21  * Requirements for the Types struct:
  22  *  ----------------------------------
  23  *  The following types must be defined in the 'Types' argument:
  24  *    - Types::Tpf - your pathfinder derived from CYapfBaseT
  25  *    - Types::NodeList - open/closed node list (look at CNodeList_HashTableT)
  26  *  NodeList needs to have defined local type Titem - defines the pathfinder node type.
  27  *  Node needs to define local type Key - the node key in the collection ()
  28  *
  29  *  For node list you can use template class CNodeList_HashTableT, for which
  30  *  you need to declare only your node type. Look at test_yapf.h for an example.
  31  *
  32  *
  33  *  Requirements to your pathfinder class derived from CYapfBaseT:
  34  *  --------------------------------------------------------------
  35  *  Your pathfinder derived class needs to implement following methods:
  36  *    inline void PfSetStartupNodes()
  37  *    inline void PfFollowNode(Node &org)
  38  *    inline bool PfCalcCost(Node &n)
  39  *    inline bool PfCalcEstimate(Node &n)
  40  *    inline bool PfDetectDestination(Node &n)
  41  *
  42  *  For more details about those methods, look at the end of CYapfBaseT
  43  *  declaration. There are some examples. For another example look at
  44  *  test_yapf.h (part or unittest project).
  45  */
  46 template <class Types>
  47 class CYapfBaseT {
  48 public:
  49         typedef typename Types::Tpf Tpf;           ///< the pathfinder class (derived from THIS class)
  50         typedef typename Types::TrackFollower TrackFollower;
  51         typedef typename Types::NodeList NodeList; ///< our node list
  52         typedef typename Types::VehicleType VehicleType; ///< the type of vehicle
  53         typedef typename NodeList::Titem Node;     ///< this will be our node type
  54         typedef typename Node::Key Key;            ///< key to hash tables
  55
  56
  57         NodeList             m_nodes;              ///< node list multi-container
  58 protected:
  59         Node                *m_pBestDestNode;      ///< pointer to the destination node found at last round
  60         Node                *m_pBestIntermediateNode; ///< here should be node closest to the destination if path not found
  61         const YAPFSettings  *m_settings;           ///< current settings (_settings_game.yapf)
  62         int                  m_max_search_nodes;   ///< maximum number of nodes we are allowed to visit before we give up
  63         const VehicleType   *m_veh;                ///< vehicle that we are trying to drive
  64
  65         int                  m_stats_cost_calcs;   ///< stats - how many node's costs were calculated
  66         int                  m_stats_cache_hits;   ///< stats - how many node's costs were reused from cache
  67
  68 public:
  69         int                  m_num_steps;          ///< this is there for debugging purposes (hope it doesn't hurt)
  70
  71 public:
  72         /** default constructor */
  73         inline CYapfBaseT()
  74                 : m_pBestDestNode(nullptr)
  75                 , m_pBestIntermediateNode(nullptr)
  76                 , m_settings(&_settings_game.pf.yapf)
  77                 , m_max_search_nodes(PfGetSettings().max_search_nodes)
  78                 , m_veh(nullptr)
  79                 , m_stats_cost_calcs(0)
  80                 , m_stats_cache_hits(0)
  81                 , m_num_steps(0)
  82         {
  83         }
  84
  85         /** default destructor */
  86         ~CYapfBaseT() {}
  87
  88 protected:
  89         /** to access inherited path finder */
  90         inline Tpf &Yapf()
  91         {
  92                 return *static_cast<Tpf *>(this);
  93         }
  94
  95 public:
  96         /** return current settings (can be custom - company based - but later) */
  97         inline const YAPFSettings &PfGetSettings() const
  98         {
  99                 return *m_settings;
 100         }
 101
 102         /**
 103          * Main pathfinder routine:
 104          *   - set startup node(s)
 105          *   - main loop that stops if:
 106          *      - the destination was found
 107          *      - or the open list is empty (no route to destination).
 108          *      - or the maximum amount of loops reached - m_max_search_nodes (default = 10000)
 109          * @return true if the path was found
 110          */
 111         inline bool FindPath(const VehicleType *v)
 112         {
 113                 m_veh = v;
 114
 115                 Yapf().PfSetStartupNodes();
 116
 117                 for (;;) {
 118                         m_num_steps++;
 119                         Node *best_open_node = m_nodes.GetBestOpenNode();
 120                         if (best_open_node == nullptr) break;
 121
 122                         if (Yapf().PfDetectDestination(*best_open_node)) {
 123                                 m_pBestDestNode = best_open_node;
 124                                 break;
 125                         }
 126
 127                         Yapf().PfFollowNode(*best_open_node);
 128                         if (m_max_search_nodes != 0 && m_nodes.ClosedCount() >= m_max_search_nodes) break;
 129
 130                         m_nodes.PopOpenNode(best_open_node->GetKey());
 131                         m_nodes.InsertClosedNode(*best_open_node);
 132                 }
 133
 134                 const bool destination_found = (m_pBestDestNode != nullptr);
 135
 136                 if (_debug_yapf_level >= 3) {
 137                         const UnitID veh_idx = (m_veh != nullptr) ? m_veh->unitnumber : 0;
 138                         const char ttc = Yapf().TransportTypeChar();
 139                         const 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);
 140                         const int cost = destination_found ? m_pBestDestNode->m_cost : -1;
 141                         const int dist = destination_found ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;
 142
 143                         Debug(yapf, 3, "[YAPF{}]{}{:4d} - {} rounds - {} open - {} closed - CHR {:4.1f}% - C {} D {}",
 144                                 ttc, destination_found ? '-' : '!', veh_idx, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), cache_hit_ratio, cost, dist
 145                         );
 146                 }
 147
 148                 return destination_found;
 149         }
 150
 151         /**
 152          * If path was found return the best node that has reached the destination. Otherwise
 153          *  return the best visited node (which was nearest to the destination).
 154          */
 155         inline Node *GetBestNode()
 156         {
 157                 return (m_pBestDestNode != nullptr) ? m_pBestDestNode : m_pBestIntermediateNode;
 158         }
 159
 160         /**
 161          * Calls NodeList::CreateNewNode() - allocates new node that can be filled and used
 162          *  as argument for AddStartupNode() or AddNewNode()
 163          */
 164         inline Node &CreateNewNode()
 165         {
 166                 Node &node = *m_nodes.CreateNewNode();
 167                 return node;
 168         }
 169
 170         /** Add new node (created by CreateNewNode and filled with data) into open list */
 171         inline void AddStartupNode(Node &n)
 172         {
 173                 Yapf().PfNodeCacheFetch(n);
 174                 /* insert the new node only if it is not there */
 175                 if (m_nodes.FindOpenNode(n.m_key) == nullptr) {
 176                         m_nodes.InsertOpenNode(n);
 177                 } else {
 178                         /* if we are here, it means that node is already there - how it is possible?
 179                          *   probably the train is in the position that both its ends point to the same tile/exit-dir
 180                          *   very unlikely, but it happened */
 181                 }
 182         }
 183
 184         /** add multiple nodes - direct children of the given node */
 185         inline void AddMultipleNodes(Node *parent, const TrackFollower &tf)
 186         {
 187                 bool is_choice = (KillFirstBit(tf.m_new_td_bits) != TRACKDIR_BIT_NONE);
 188                 for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
 189                         Trackdir td = (Trackdir)FindFirstBit(rtds);
 190                         Node &n = Yapf().CreateNewNode();
 191                         n.Set(parent, tf.m_new_tile, td, is_choice);
 192                         Yapf().AddNewNode(n, tf);
 193                 }
 194         }
 195
 196         /**
 197          * In some cases an intermediate node branch should be pruned.
 198          * The most prominent case is when a red EOL signal is encountered, but
 199          * there was a segment change (e.g. a rail type change) before that. If
 200          * the branch would not be pruned, the rail type change location would
 201          * remain the best intermediate node, and thus the vehicle would still
 202          * go towards the red EOL signal.
 203          */
 204         void PruneIntermediateNodeBranch(Node *n)
 205         {
 206                 bool intermediate_on_branch = false;
 207                 while (n != nullptr && (n->m_segment->m_end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) {
 208                         if (n == Yapf().m_pBestIntermediateNode) intermediate_on_branch = true;
 209                         n = n->m_parent;
 210                 }
 211                 if (intermediate_on_branch) Yapf().m_pBestIntermediateNode = n;
 212         }
 213
 214         /**
 215          * AddNewNode() - called by Tderived::PfFollowNode() for each child node.
 216          *  Nodes are evaluated here and added into open list
 217          */
 218         void AddNewNode(Node &n, const TrackFollower &tf)
 219         {
 220                 /* evaluate the node */
 221                 bool bCached = Yapf().PfNodeCacheFetch(n);
 222                 if (!bCached) {
 223                         m_stats_cost_calcs++;
 224                 } else {
 225                         m_stats_cache_hits++;
 226                 }
 227
 228                 bool bValid = Yapf().PfCalcCost(n, &tf);
 229
 230                 if (bValid) bValid = Yapf().PfCalcEstimate(n);
 231
 232                 /* have the cost or estimate callbacks marked this node as invalid? */
 233                 if (!bValid) return;
 234
 235                 /* The new node can be set as the best intermediate node only once we're
 236                  * certain it will be finalized by being inserted into the open list. */
 237                 bool set_intermediate = m_max_search_nodes > 0 && (m_pBestIntermediateNode == nullptr || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()));
 238
 239                 /* check new node against open list */
 240                 Node *openNode = m_nodes.FindOpenNode(n.GetKey());
 241                 if (openNode != nullptr) {
 242                         /* another node exists with the same key in the open list
 243                          * is it better than new one? */
 244                         if (n.GetCostEstimate() < openNode->GetCostEstimate()) {
 245                                 /* update the old node by value from new one */
 246                                 m_nodes.PopOpenNode(n.GetKey());
 247                                 *openNode = n;
 248                                 /* add the updated old node back to open list */
 249                                 m_nodes.InsertOpenNode(*openNode);
 250                                 if (set_intermediate) m_pBestIntermediateNode = openNode;
 251                         }
 252                         return;
 253                 }
 254
 255                 /* check new node against closed list */
 256                 Node *closedNode = m_nodes.FindClosedNode(n.GetKey());
 257                 if (closedNode != nullptr) {
 258                         /* another node exists with the same key in the closed list
 259                          * is it better than new one? */
 260                         int node_est = n.GetCostEstimate();
 261                         int closed_est = closedNode->GetCostEstimate();
 262                         if (node_est < closed_est) {
 263                                 /* If this assert occurs, you have probably problem in
 264                                  * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
 265                                  * The problem could be:
 266                                  *  - PfCalcEstimate() gives too large numbers
 267                                  *  - PfCalcCost() gives too small numbers
 268                                  *  - You have used negative cost penalty in some cases (cost bonus) */
 269                                 NOT_REACHED();
 270                         }
 271                         return;
 272                 }
 273                 /* the new node is really new
 274                  * add it to the open list */
 275                 m_nodes.InsertOpenNode(n);
 276                 if (set_intermediate) m_pBestIntermediateNode = &n;
 277         }
 278
 279         const VehicleType * GetVehicle() const
 280         {
 281                 return m_veh;
 282         }
 283
 284         void DumpBase(DumpTarget &dmp) const
 285         {
 286                 dmp.WriteStructT("m_nodes", &m_nodes);
 287                 dmp.WriteValue("m_num_steps", m_num_steps);
 288         }
 289 };
 290
 291 #endif /* YAPF_BASE_HPP */