OpenTTD
yapf_base.hpp
Go to the documentation of this file.
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 
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 
50 template <class Types>
51 class CYapfBaseT {
52 public:
53  typedef typename Types::Tpf Tpf;
54  typedef typename Types::TrackFollower TrackFollower;
55  typedef typename Types::NodeList NodeList;
56  typedef typename Types::VehicleType VehicleType;
57  typedef typename NodeList::Titem Node;
58  typedef typename Node::Key Key;
59 
60 
61  NodeList m_nodes;
62 protected:
67  const VehicleType *m_veh;
68 
71 
72 public:
77 
78 public:
80 
81 public:
83  inline CYapfBaseT()
84  : m_pBestDestNode(NULL)
85  , m_pBestIntermediateNode(NULL)
86  , m_settings(&_settings_game.pf.yapf)
87  , m_max_search_nodes(PfGetSettings().max_search_nodes)
88  , m_veh(NULL)
89  , m_stats_cost_calcs(0)
90  , m_stats_cache_hits(0)
91  , m_num_steps(0)
92  {
93  }
94 
97 
98 protected:
100  inline Tpf& Yapf()
101  {
102  return *static_cast<Tpf *>(this);
103  }
104 
105 public:
107  inline const YAPFSettings& PfGetSettings() const
108  {
109  return *m_settings;
110  }
111 
121  inline bool FindPath(const VehicleType *v)
122  {
123  m_veh = v;
124 
125  CPerformanceTimer perf;
126  perf.Start();
127 
128  Yapf().PfSetStartupNodes();
129  bool bDestFound = true;
130 
131  for (;;) {
132  m_num_steps++;
133  Node *n = m_nodes.GetBestOpenNode();
134  if (n == NULL) {
135  break;
136  }
137 
138  /* if the best open node was worse than the best path found, we can finish */
139  if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n->GetCostEstimate()) {
140  break;
141  }
142 
143  Yapf().PfFollowNode(*n);
144  if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) {
145  m_nodes.PopOpenNode(n->GetKey());
146  m_nodes.InsertClosedNode(*n);
147  } else {
148  bDestFound = false;
149  break;
150  }
151  }
152 
153  bDestFound &= (m_pBestDestNode != NULL);
154 
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  return bDestFound;
175  }
176 
181  inline Node *GetBestNode()
182  {
183  return (m_pBestDestNode != NULL) ? m_pBestDestNode : m_pBestIntermediateNode;
184  }
185 
190  inline Node& CreateNewNode()
191  {
192  Node &node = *m_nodes.CreateNewNode();
193  return node;
194  }
195 
197  inline void AddStartupNode(Node &n)
198  {
199  Yapf().PfNodeCacheFetch(n);
200  /* insert the new node only if it is not there */
201  if (m_nodes.FindOpenNode(n.m_key) == NULL) {
202  m_nodes.InsertOpenNode(n);
203  } else {
204  /* if we are here, it means that node is already there - how it is possible?
205  * probably the train is in the position that both its ends point to the same tile/exit-dir
206  * very unlikely, but it happened */
207  }
208  }
209 
211  inline void AddMultipleNodes(Node *parent, const TrackFollower &tf)
212  {
213  bool is_choice = (KillFirstBit(tf.m_new_td_bits) != TRACKDIR_BIT_NONE);
214  for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
215  Trackdir td = (Trackdir)FindFirstBit2x64(rtds);
216  Node &n = Yapf().CreateNewNode();
217  n.Set(parent, tf.m_new_tile, td, is_choice);
218  Yapf().AddNewNode(n, tf);
219  }
220  }
221 
231  {
232  while (Yapf().m_pBestIntermediateNode != NULL && (Yapf().m_pBestIntermediateNode->m_segment->m_end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) {
233  Yapf().m_pBestIntermediateNode = Yapf().m_pBestIntermediateNode->m_parent;
234  }
235  }
236 
241  void AddNewNode(Node &n, const TrackFollower &tf)
242  {
243  /* evaluate the node */
244  bool bCached = Yapf().PfNodeCacheFetch(n);
245  if (!bCached) {
246  m_stats_cost_calcs++;
247  } else {
248  m_stats_cache_hits++;
249  }
250 
251  bool bValid = Yapf().PfCalcCost(n, &tf);
252 
253  if (bCached) {
254  Yapf().PfNodeCacheFlush(n);
255  }
256 
257  if (bValid) bValid = Yapf().PfCalcEstimate(n);
258 
259  /* have the cost or estimate callbacks marked this node as invalid? */
260  if (!bValid) return;
261 
262  /* detect the destination */
263  bool bDestination = Yapf().PfDetectDestination(n);
264  if (bDestination) {
265  if (m_pBestDestNode == NULL || n < *m_pBestDestNode) {
266  m_pBestDestNode = &n;
267  }
268  m_nodes.FoundBestNode(n);
269  return;
270  }
271 
272  if (m_max_search_nodes > 0 && (m_pBestIntermediateNode == NULL || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()))) {
273  m_pBestIntermediateNode = &n;
274  }
275 
276  /* check new node against open list */
277  Node *openNode = m_nodes.FindOpenNode(n.GetKey());
278  if (openNode != NULL) {
279  /* another node exists with the same key in the open list
280  * is it better than new one? */
281  if (n.GetCostEstimate() < openNode->GetCostEstimate()) {
282  /* update the old node by value from new one */
283  m_nodes.PopOpenNode(n.GetKey());
284  *openNode = n;
285  /* add the updated old node back to open list */
286  m_nodes.InsertOpenNode(*openNode);
287  }
288  return;
289  }
290 
291  /* check new node against closed list */
292  Node *closedNode = m_nodes.FindClosedNode(n.GetKey());
293  if (closedNode != NULL) {
294  /* another node exists with the same key in the closed list
295  * is it better than new one? */
296  int node_est = n.GetCostEstimate();
297  int closed_est = closedNode->GetCostEstimate();
298  if (node_est < closed_est) {
299  /* If this assert occurs, you have probably problem in
300  * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
301  * The problem could be:
302  * - PfCalcEstimate() gives too large numbers
303  * - PfCalcCost() gives too small numbers
304  * - You have used negative cost penalty in some cases (cost bonus) */
305  NOT_REACHED();
306  }
307  return;
308  }
309  /* the new node is really new
310  * add it to the open list */
311  m_nodes.InsertOpenNode(n);
312  }
313 
314  const VehicleType * GetVehicle() const
315  {
316  return m_veh;
317  }
318 
319  void DumpBase(DumpTarget &dmp) const
320  {
321  dmp.WriteStructT("m_nodes", &m_nodes);
322  dmp.WriteLine("m_num_steps = %d", m_num_steps);
323  }
324 
325  /* methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT) */
326 
327 #if 0
328 
329  inline void PfSetStartupNodes()
330  {
331  /* example: */
332  Node &n1 = *base::m_nodes.CreateNewNode();
333  .
334  . // setup node members here
335  .
336  base::m_nodes.InsertOpenNode(n1);
337  }
338 
340  inline void PfFollowNode(Node &org)
341  {
342  for (each follower of node org) {
343  Node &n = *base::m_nodes.CreateNewNode();
344  .
345  . // setup node members here
346  .
347  n.m_parent = &org; // set node's parent to allow back tracking
348  AddNewNode(n);
349  }
350  }
351 
353  inline bool PfCalcCost(Node &n)
354  {
355  /* evaluate last step cost */
356  int cost = ...;
357  /* set the node cost as sum of parent's cost and last step cost */
358  n.m_cost = n.m_parent->m_cost + cost;
359  return true; // true if node is valid follower (i.e. no obstacle was found)
360  }
361 
363  inline bool PfCalcEstimate(Node &n)
364  {
365  /* evaluate the distance to our destination */
366  int distance = ...;
367  /* set estimate as sum of cost from origin + distance to the target */
368  n.m_estimate = n.m_cost + distance;
369  return true; // true if node is valid (i.e. not too far away :)
370  }
371 
373  inline bool PfDetectDestination(Node &n)
374  {
375  bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
376  return bDest;
377  }
378 #endif
379 };
380 
381 #endif /* YAPF_BASE_HPP */
CPerformanceTimer m_perf_other_cost
stats - other CPU time
Definition: yapf_base.hpp:76
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:77
void AddNewNode(Node &n, const TrackFollower &tf)
AddNewNode() - called by Tderived::PfFollowNode() for each child node.
Definition: yapf_base.hpp:241
Types::VehicleType VehicleType
the type of vehicle
Definition: yapf_base.hpp:56
Node::Key Key
key to hash tables
Definition: yapf_base.hpp:58
Node * GetBestNode()
If path was found return the best node that has reached the destination.
Definition: yapf_base.hpp:181
int m_max_search_nodes
maximum number of nodes we are allowed to visit before we give up
Definition: yapf_base.hpp:66
int m_stats_cost_calcs
stats - how many node&#39;s costs were calculated
Definition: yapf_base.hpp:69
void CDECL WriteLine(const char *format,...) WARN_FORMAT(2
Write a line with indent at the beginning and <LF> at the end.
Node * m_pBestDestNode
pointer to the destination node found at last round
Definition: yapf_base.hpp:63
void AddStartupNode(Node &n)
Add new node (created by CreateNewNode and filled with data) into open list.
Definition: yapf_base.hpp:197
Settings related to the yet another pathfinder.
Node & CreateNewNode()
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddS...
Definition: yapf_base.hpp:190
Types::NodeList NodeList
our node list
Definition: yapf_base.hpp:55
Node * m_pBestIntermediateNode
here should be node closest to the destination if path not found
Definition: yapf_base.hpp:64
bool FindPath(const VehicleType *v)
Main pathfinder routine:
Definition: yapf_base.hpp:121
const VehicleType * m_veh
vehicle that we are trying to drive
Definition: yapf_base.hpp:67
~CYapfBaseT()
default destructor
Definition: yapf_base.hpp:96
CYapfBaseT - A-star type path finder base class.
Definition: yapf_base.hpp:51
NodeList::Titem Node
this will be our node type
Definition: yapf_base.hpp:57
VehicleType
Available vehicle types.
Definition: vehicle_type.h:23
CPerformanceTimer m_perf_ts_cost
stats - GetTrackStatus() CPU time
Definition: yapf_base.hpp:75
CPerformanceTimer m_perf_cost
stats - total CPU time of this run
Definition: yapf_base.hpp:73
const YAPFSettings & PfGetSettings() const
return current settings (can be custom - company based - but later)
Definition: yapf_base.hpp:107
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:74
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_base.hpp:53
#define DEBUG(name, level,...)
Output a line of debugging information.
Definition: debug.h:36
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:154
static T KillFirstBit(T value)
Clear the first bit in an integer.
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
int m_stats_cache_hits
stats - how many node&#39;s costs were reused from cache
Definition: yapf_base.hpp:70
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Definition: track_type.h:106
uint16 UnitID
Type for the company global vehicle unit number.
void AddMultipleNodes(Node *parent, const TrackFollower &tf)
add multiple nodes - direct children of the given node
Definition: yapf_base.hpp:211
No track build.
Definition: track_type.h:107
CPerformanceTimer m_perf_slope_cost
stats - slope calculation CPU time
Definition: yapf_base.hpp:74
int m_num_steps
this is there for debugging purposes (hope it doesn&#39;t hurt)
Definition: yapf_base.hpp:79
NodeList m_nodes
node list multi-container
Definition: yapf_base.hpp:61
const YAPFSettings * m_settings
current settings (_settings_game.yapf)
Definition: yapf_base.hpp:65
Class that represents the dump-into-string target.
Definition: dbg_helpers.h:96
CYapfBaseT()
default constructor
Definition: yapf_base.hpp:83
void PruneIntermediateNodeBranch()
In some cases an intermediate node branch should be pruned.
Definition: yapf_base.hpp:230
Tpf & Yapf()
to access inherited path finder
Definition: yapf_base.hpp:100