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 */ CYapfBaseT()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 */ ~CYapfBaseT()86 ~CYapfBaseT() {} 87 88 protected: 89 /** to access inherited path finder */ Yapf()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) */ PfGetSettings() const97 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 */ FindPath(const VehicleType * v)111 inline bool FindPath(const VehicleType *v) 112 { 113 m_veh = v; 114 115 Yapf().PfSetStartupNodes(); 116 bool bDestFound = true; 117 118 for (;;) { 119 m_num_steps++; 120 Node *n = m_nodes.GetBestOpenNode(); 121 if (n == nullptr) { 122 break; 123 } 124 125 /* if the best open node was worse than the best path found, we can finish */ 126 if (m_pBestDestNode != nullptr && m_pBestDestNode->GetCost() < n->GetCostEstimate()) { 127 break; 128 } 129 130 Yapf().PfFollowNode(*n); 131 if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) { 132 m_nodes.PopOpenNode(n->GetKey()); 133 m_nodes.InsertClosedNode(*n); 134 } else { 135 bDestFound = false; 136 break; 137 } 138 } 139 140 bDestFound &= (m_pBestDestNode != nullptr); 141 142 if (_debug_yapf_level >= 3) { 143 UnitID veh_idx = (m_veh != nullptr) ? m_veh->unitnumber : 0; 144 char ttc = Yapf().TransportTypeChar(); 145 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); 146 int cost = bDestFound ? m_pBestDestNode->m_cost : -1; 147 int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1; 148 149 Debug(yapf, 3, "[YAPF{}]{}{:4d} - {} rounds - {} open - {} closed - CHR {:4.1f}% - C {} D {}", 150 ttc, bDestFound ? '-' : '!', veh_idx, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), cache_hit_ratio, cost, dist 151 ); 152 } 153 154 return bDestFound; 155 } 156 157 /** 158 * If path was found return the best node that has reached the destination. Otherwise 159 * return the best visited node (which was nearest to the destination). 160 */ GetBestNode()161 inline Node *GetBestNode() 162 { 163 return (m_pBestDestNode != nullptr) ? m_pBestDestNode : m_pBestIntermediateNode; 164 } 165 166 /** 167 * Calls NodeList::CreateNewNode() - allocates new node that can be filled and used 168 * as argument for AddStartupNode() or AddNewNode() 169 */ CreateNewNode()170 inline Node& CreateNewNode() 171 { 172 Node &node = *m_nodes.CreateNewNode(); 173 return node; 174 } 175 176 /** Add new node (created by CreateNewNode and filled with data) into open list */ AddStartupNode(Node & n)177 inline void AddStartupNode(Node &n) 178 { 179 Yapf().PfNodeCacheFetch(n); 180 /* insert the new node only if it is not there */ 181 if (m_nodes.FindOpenNode(n.m_key) == nullptr) { 182 m_nodes.InsertOpenNode(n); 183 } else { 184 /* if we are here, it means that node is already there - how it is possible? 185 * probably the train is in the position that both its ends point to the same tile/exit-dir 186 * very unlikely, but it happened */ 187 } 188 } 189 190 /** add multiple nodes - direct children of the given node */ AddMultipleNodes(Node * parent,const TrackFollower & tf)191 inline void AddMultipleNodes(Node *parent, const TrackFollower &tf) 192 { 193 bool is_choice = (KillFirstBit(tf.m_new_td_bits) != TRACKDIR_BIT_NONE); 194 for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) { 195 Trackdir td = (Trackdir)FindFirstBit2x64(rtds); 196 Node &n = Yapf().CreateNewNode(); 197 n.Set(parent, tf.m_new_tile, td, is_choice); 198 Yapf().AddNewNode(n, tf); 199 } 200 } 201 202 /** 203 * In some cases an intermediate node branch should be pruned. 204 * The most prominent case is when a red EOL signal is encountered, but 205 * there was a segment change (e.g. a rail type change) before that. If 206 * the branch would not be pruned, the rail type change location would 207 * remain the best intermediate node, and thus the vehicle would still 208 * go towards the red EOL signal. 209 */ PruneIntermediateNodeBranch(Node * n)210 void PruneIntermediateNodeBranch(Node *n) 211 { 212 bool intermediate_on_branch = false; 213 while (n != nullptr && (n->m_segment->m_end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) { 214 if (n == Yapf().m_pBestIntermediateNode) intermediate_on_branch = true; 215 n = n->m_parent; 216 } 217 if (intermediate_on_branch) Yapf().m_pBestIntermediateNode = n; 218 } 219 220 /** 221 * AddNewNode() - called by Tderived::PfFollowNode() for each child node. 222 * Nodes are evaluated here and added into open list 223 */ AddNewNode(Node & n,const TrackFollower & tf)224 void AddNewNode(Node &n, const TrackFollower &tf) 225 { 226 /* evaluate the node */ 227 bool bCached = Yapf().PfNodeCacheFetch(n); 228 if (!bCached) { 229 m_stats_cost_calcs++; 230 } else { 231 m_stats_cache_hits++; 232 } 233 234 bool bValid = Yapf().PfCalcCost(n, &tf); 235 236 if (bCached) { 237 Yapf().PfNodeCacheFlush(n); 238 } 239 240 if (bValid) bValid = Yapf().PfCalcEstimate(n); 241 242 /* have the cost or estimate callbacks marked this node as invalid? */ 243 if (!bValid) return; 244 245 /* detect the destination */ 246 bool bDestination = Yapf().PfDetectDestination(n); 247 if (bDestination) { 248 if (m_pBestDestNode == nullptr || n < *m_pBestDestNode) { 249 m_pBestDestNode = &n; 250 } 251 m_nodes.FoundBestNode(n); 252 return; 253 } 254 255 /* The new node can be set as the best intermediate node only once we're 256 * certain it will be finalized by being inserted into the open list. */ 257 bool set_intermediate = m_max_search_nodes > 0 && (m_pBestIntermediateNode == nullptr || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost())); 258 259 /* check new node against open list */ 260 Node *openNode = m_nodes.FindOpenNode(n.GetKey()); 261 if (openNode != nullptr) { 262 /* another node exists with the same key in the open list 263 * is it better than new one? */ 264 if (n.GetCostEstimate() < openNode->GetCostEstimate()) { 265 /* update the old node by value from new one */ 266 m_nodes.PopOpenNode(n.GetKey()); 267 *openNode = n; 268 /* add the updated old node back to open list */ 269 m_nodes.InsertOpenNode(*openNode); 270 if (set_intermediate) m_pBestIntermediateNode = openNode; 271 } 272 return; 273 } 274 275 /* check new node against closed list */ 276 Node *closedNode = m_nodes.FindClosedNode(n.GetKey()); 277 if (closedNode != nullptr) { 278 /* another node exists with the same key in the closed list 279 * is it better than new one? */ 280 int node_est = n.GetCostEstimate(); 281 int closed_est = closedNode->GetCostEstimate(); 282 if (node_est < closed_est) { 283 /* If this assert occurs, you have probably problem in 284 * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate(). 285 * The problem could be: 286 * - PfCalcEstimate() gives too large numbers 287 * - PfCalcCost() gives too small numbers 288 * - You have used negative cost penalty in some cases (cost bonus) */ 289 NOT_REACHED(); 290 } 291 return; 292 } 293 /* the new node is really new 294 * add it to the open list */ 295 m_nodes.InsertOpenNode(n); 296 if (set_intermediate) m_pBestIntermediateNode = &n; 297 } 298 GetVehicle() const299 const VehicleType * GetVehicle() const 300 { 301 return m_veh; 302 } 303 DumpBase(DumpTarget & dmp) const304 void DumpBase(DumpTarget &dmp) const 305 { 306 dmp.WriteStructT("m_nodes", &m_nodes); 307 dmp.WriteValue("m_num_steps", m_num_steps); 308 } 309 310 /* methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT) */ 311 312 #if 0 313 /** Example: PfSetStartupNodes() - set source (origin) nodes */ 314 inline void PfSetStartupNodes() 315 { 316 /* example: */ 317 Node &n1 = *base::m_nodes.CreateNewNode(); 318 . 319 . // setup node members here 320 . 321 base::m_nodes.InsertOpenNode(n1); 322 } 323 324 /** Example: PfFollowNode() - set following (child) nodes of the given node */ 325 inline void PfFollowNode(Node &org) 326 { 327 for (each follower of node org) { 328 Node &n = *base::m_nodes.CreateNewNode(); 329 . 330 . // setup node members here 331 . 332 n.m_parent = &org; // set node's parent to allow back tracking 333 AddNewNode(n); 334 } 335 } 336 337 /** Example: PfCalcCost() - set path cost from origin to the given node */ 338 inline bool PfCalcCost(Node &n) 339 { 340 /* evaluate last step cost */ 341 int cost = ...; 342 /* set the node cost as sum of parent's cost and last step cost */ 343 n.m_cost = n.m_parent->m_cost + cost; 344 return true; // true if node is valid follower (i.e. no obstacle was found) 345 } 346 347 /** Example: PfCalcEstimate() - set path cost estimate from origin to the target through given node */ 348 inline bool PfCalcEstimate(Node &n) 349 { 350 /* evaluate the distance to our destination */ 351 int distance = ...; 352 /* set estimate as sum of cost from origin + distance to the target */ 353 n.m_estimate = n.m_cost + distance; 354 return true; // true if node is valid (i.e. not too far away :) 355 } 356 357 /** Example: PfDetectDestination() - return true if the given node is our destination */ 358 inline bool PfDetectDestination(Node &n) 359 { 360 bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2); 361 return bDest; 362 } 363 #endif 364 }; 365 366 #endif /* YAPF_BASE_HPP */ 367