OpenTTD Source  1.11.2
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%c]%c%4d- %d rounds - %d open - %d closed - CHR %4.1f%% - C %d D %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  while (Yapf().m_pBestIntermediateNode != nullptr && (Yapf().m_pBestIntermediateNode->m_segment->m_end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) {
213  Yapf().m_pBestIntermediateNode = Yapf().m_pBestIntermediateNode->m_parent;
214  }
215  }
216 
221  void AddNewNode(Node &n, const TrackFollower &tf)
222  {
223  /* evaluate the node */
224  bool bCached = Yapf().PfNodeCacheFetch(n);
225  if (!bCached) {
227  } else {
229  }
230 
231  bool bValid = Yapf().PfCalcCost(n, &tf);
232 
233  if (bCached) {
234  Yapf().PfNodeCacheFlush(n);
235  }
236 
237  if (bValid) bValid = Yapf().PfCalcEstimate(n);
238 
239  /* have the cost or estimate callbacks marked this node as invalid? */
240  if (!bValid) return;
241 
242  /* detect the destination */
243  bool bDestination = Yapf().PfDetectDestination(n);
244  if (bDestination) {
245  if (m_pBestDestNode == nullptr || n < *m_pBestDestNode) {
246  m_pBestDestNode = &n;
247  }
248  m_nodes.FoundBestNode(n);
249  return;
250  }
251 
252  if (m_max_search_nodes > 0 && (m_pBestIntermediateNode == nullptr || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()))) {
254  }
255 
256  /* check new node against open list */
257  Node *openNode = m_nodes.FindOpenNode(n.GetKey());
258  if (openNode != nullptr) {
259  /* another node exists with the same key in the open list
260  * is it better than new one? */
261  if (n.GetCostEstimate() < openNode->GetCostEstimate()) {
262  /* update the old node by value from new one */
263  m_nodes.PopOpenNode(n.GetKey());
264  *openNode = n;
265  /* add the updated old node back to open list */
266  m_nodes.InsertOpenNode(*openNode);
267  }
268  return;
269  }
270 
271  /* check new node against closed list */
272  Node *closedNode = m_nodes.FindClosedNode(n.GetKey());
273  if (closedNode != nullptr) {
274  /* another node exists with the same key in the closed list
275  * is it better than new one? */
276  int node_est = n.GetCostEstimate();
277  int closed_est = closedNode->GetCostEstimate();
278  if (node_est < closed_est) {
279  /* If this assert occurs, you have probably problem in
280  * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
281  * The problem could be:
282  * - PfCalcEstimate() gives too large numbers
283  * - PfCalcCost() gives too small numbers
284  * - You have used negative cost penalty in some cases (cost bonus) */
285  NOT_REACHED();
286  }
287  return;
288  }
289  /* the new node is really new
290  * add it to the open list */
291  m_nodes.InsertOpenNode(n);
292  }
293 
294  const VehicleType * GetVehicle() const
295  {
296  return m_veh;
297  }
298 
299  void DumpBase(DumpTarget &dmp) const
300  {
301  dmp.WriteStructT("m_nodes", &m_nodes);
302  dmp.WriteLine("m_num_steps = %d", m_num_steps);
303  }
304 
305  /* methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT) */
306 
307 #if 0
308 
309  inline void PfSetStartupNodes()
310  {
311  /* example: */
312  Node &n1 = *base::m_nodes.CreateNewNode();
313  .
314  . // setup node members here
315  .
316  base::m_nodes.InsertOpenNode(n1);
317  }
318 
320  inline void PfFollowNode(Node &org)
321  {
322  for (each follower of node org) {
323  Node &n = *base::m_nodes.CreateNewNode();
324  .
325  . // setup node members here
326  .
327  n.m_parent = &org; // set node's parent to allow back tracking
328  AddNewNode(n);
329  }
330  }
331 
333  inline bool PfCalcCost(Node &n)
334  {
335  /* evaluate last step cost */
336  int cost = ...;
337  /* set the node cost as sum of parent's cost and last step cost */
338  n.m_cost = n.m_parent->m_cost + cost;
339  return true; // true if node is valid follower (i.e. no obstacle was found)
340  }
341 
343  inline bool PfCalcEstimate(Node &n)
344  {
345  /* evaluate the distance to our destination */
346  int distance = ...;
347  /* set estimate as sum of cost from origin + distance to the target */
348  n.m_estimate = n.m_cost + distance;
349  return true; // true if node is valid (i.e. not too far away :)
350  }
351 
353  inline bool PfDetectDestination(Node &n)
354  {
355  bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
356  return bDest;
357  }
358 #endif
359 };
360 
361 #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:373
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
DumpTarget::WriteLine
void CDECL WriteLine(const char *format,...) WARN_FORMAT(2
Write a line with indent at the beginning and <LF> at the end.
Definition: dbg_helpers.cpp:119
YAPFSettings
Settings related to the yet another pathfinder.
Definition: settings_type.h:390
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
DEBUG
#define DEBUG(name, level,...)
Output a line of debugging information.
Definition: debug.h:35
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
CYapfBaseT::PruneIntermediateNodeBranch
void PruneIntermediateNodeBranch()
In some cases an intermediate node branch should be pruned.
Definition: yapf_base.hpp:210
DumpTarget
Class that represents the dump-into-string target.
Definition: dbg_helpers.h:94
_settings_game
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:80
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:221
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:152
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
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
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