OpenTTD Source  12.0-beta2
yapf_base.hpp
Go to the documentation of this file.
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 
10 #ifndef YAPF_BASE_HPP
11 #define YAPF_BASE_HPP
12 
13 #include "../../debug.h"
14 #include "../../settings_type.h"
15 
46 template <class Types>
47 class CYapfBaseT {
48 public:
49  typedef typename Types::Tpf Tpf;
50  typedef typename Types::TrackFollower TrackFollower;
51  typedef typename Types::NodeList NodeList;
52  typedef typename Types::VehicleType VehicleType;
53  typedef typename NodeList::Titem Node;
54  typedef typename Node::Key Key;
55 
56 
58 protected:
63  const VehicleType *m_veh;
64 
67 
68 public:
70 
71 public:
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)
81  , m_num_steps(0)
82  {
83  }
84 
87 
88 protected:
90  inline Tpf& Yapf()
91  {
92  return *static_cast<Tpf *>(this);
93  }
94 
95 public:
97  inline const YAPFSettings& PfGetSettings() const
98  {
99  return *m_settings;
100  }
101 
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 
161  inline Node *GetBestNode()
162  {
164  }
165 
170  inline Node& CreateNewNode()
171  {
172  Node &node = *m_nodes.CreateNewNode();
173  return node;
174  }
175 
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 
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 
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 
224  void AddNewNode(Node &n, const TrackFollower &tf)
225  {
226  /* evaluate the node */
227  bool bCached = Yapf().PfNodeCacheFetch(n);
228  if (!bCached) {
230  } else {
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 
299  const VehicleType * GetVehicle() const
300  {
301  return m_veh;
302  }
303 
304  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 
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 
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 
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 
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 
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 */
CYapfBaseT::PfGetSettings
const YAPFSettings & PfGetSettings() const
return current settings (can be custom - company based - but later)
Definition: yapf_base.hpp:97
TrackdirBits
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Definition: track_type.h:101
LinkGraph::Node
Updatable node class.
Definition: linkgraph.h:380
UnitID
uint16 UnitID
Type for the company global vehicle unit number.
Definition: transport_type.h:16
CYapfBaseT::Tpf
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_base.hpp:49
KillFirstBit
static T KillFirstBit(T value)
Clear the first bit in an integer.
Definition: bitmath_func.hpp:239
CYapfBaseT::PruneIntermediateNodeBranch
void PruneIntermediateNodeBranch(Node *n)
In some cases an intermediate node branch should be pruned.
Definition: yapf_base.hpp:210
YAPFSettings
Settings related to the yet another pathfinder.
Definition: settings_type.h:402
CYapfBaseT::m_stats_cache_hits
int m_stats_cache_hits
stats - how many node's costs were reused from cache
Definition: yapf_base.hpp:66
CYapfBaseT::AddMultipleNodes
void AddMultipleNodes(Node *parent, const TrackFollower &tf)
add multiple nodes - direct children of the given node
Definition: yapf_base.hpp:191
CYapfBaseT::m_settings
const YAPFSettings * m_settings
current settings (_settings_game.yapf)
Definition: yapf_base.hpp:61
CYapfBaseT::CYapfBaseT
CYapfBaseT()
default constructor
Definition: yapf_base.hpp:73
FindFirstBit2x64
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
Definition: bitmath_func.hpp:216
CYapfBaseT::Yapf
Tpf & Yapf()
to access inherited path finder
Definition: yapf_base.hpp:90
DumpTarget
Class that represents the dump-into-string target.
Definition: dbg_helpers.h:97
_settings_game
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:53
CYapfBaseT::m_nodes
NodeList m_nodes
node list multi-container
Definition: yapf_base.hpp:57
CYapfBaseT::m_num_steps
int m_num_steps
this is there for debugging purposes (hope it doesn't hurt)
Definition: yapf_base.hpp:69
CYapfBaseT::VehicleType
Types::VehicleType VehicleType
the type of vehicle
Definition: yapf_base.hpp:52
VehicleType
VehicleType
Available vehicle types.
Definition: vehicle_type.h:21
CYapfBaseT::GetBestNode
Node * GetBestNode()
If path was found return the best node that has reached the destination.
Definition: yapf_base.hpp:161
CYapfBaseT::Key
Node::Key Key
key to hash tables
Definition: yapf_base.hpp:54
CYapfBaseT::AddNewNode
void AddNewNode(Node &n, const TrackFollower &tf)
AddNewNode() - called by Tderived::PfFollowNode() for each child node.
Definition: yapf_base.hpp:224
DumpTarget::WriteStructT
void WriteStructT(const char *name, const S *s)
Dump nested object (or only its name if this instance is already known).
Definition: dbg_helpers.h:149
CYapfBaseT::m_max_search_nodes
int m_max_search_nodes
maximum number of nodes we are allowed to visit before we give up
Definition: yapf_base.hpp:62
TRACKDIR_BIT_NONE
@ TRACKDIR_BIT_NONE
No track build.
Definition: track_type.h:102
CYapfBaseT::m_pBestDestNode
Node * m_pBestDestNode
pointer to the destination node found at last round
Definition: yapf_base.hpp:59
CYapfBaseT::AddStartupNode
void AddStartupNode(Node &n)
Add new node (created by CreateNewNode and filled with data) into open list.
Definition: yapf_base.hpp:177
CYapfBaseT::m_stats_cost_calcs
int m_stats_cost_calcs
stats - how many node's costs were calculated
Definition: yapf_base.hpp:65
DumpTarget::WriteValue
void WriteValue(const char *name, int value)
Write 'name = value' with indent and new-line.
Definition: dbg_helpers.cpp:115
CYapfBaseT::FindPath
bool FindPath(const VehicleType *v)
Main pathfinder routine:
Definition: yapf_base.hpp:111
CYapfBaseT::CreateNewNode
Node & CreateNewNode()
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddS...
Definition: yapf_base.hpp:170
Debug
#define Debug(name, level, format_string,...)
Ouptut a line of debugging information.
Definition: debug.h:37
CYapfBaseT::NodeList
Types::NodeList NodeList
our node list
Definition: yapf_base.hpp:51
CYapfBaseT::~CYapfBaseT
~CYapfBaseT()
default destructor
Definition: yapf_base.hpp:86
CYapfBaseT::m_pBestIntermediateNode
Node * m_pBestIntermediateNode
here should be node closest to the destination if path not found
Definition: yapf_base.hpp:60
CYapfBaseT::m_veh
const VehicleType * m_veh
vehicle that we are trying to drive
Definition: yapf_base.hpp:63
Trackdir
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:70
CYapfBaseT
CYapfBaseT - A-star type path finder base class.
Definition: yapf_base.hpp:47
CYapfBaseT::Node
NodeList::Titem Node
this will be our node type
Definition: yapf_base.hpp:53