OpenTTD Source  20241108-master-g80f628063a
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 #include "../../misc/dbg_helpers.h"
16 #include "yapf_type.hpp"
17 
48 template <class Types>
49 class CYapfBaseT {
50 public:
51  typedef typename Types::Tpf Tpf;
52  typedef typename Types::TrackFollower TrackFollower;
53  typedef typename Types::NodeList NodeList;
54  typedef typename Types::VehicleType VehicleType;
55  typedef typename NodeList::Titem Node;
56  typedef typename Node::Key Key;
57 
58 
60 
61 protected:
62  Node *best_dest_node = nullptr;
66  const VehicleType *vehicle = nullptr;
67 
68  int stats_cost_calcs = 0;
69  int stats_cache_hits = 0;
70 
71 public:
72  int num_steps = 0;
73 
74 public:
77 
80 
81 protected:
83  inline Tpf &Yapf()
84  {
85  return *static_cast<Tpf *>(this);
86  }
87 
88 public:
90  inline const YAPFSettings &PfGetSettings() const
91  {
92  return *this->settings;
93  }
94 
104  inline bool FindPath(const VehicleType *v)
105  {
106  this->vehicle = v;
107 
108  Yapf().PfSetStartupNodes();
109 
110  for (;;) {
111  this->num_steps++;
112  Node *best_open_node = this->nodes.GetBestOpenNode();
113  if (best_open_node == nullptr) break;
114 
115  if (Yapf().PfDetectDestination(*best_open_node)) {
116  this->best_dest_node = best_open_node;
117  break;
118  }
119 
120  Yapf().PfFollowNode(*best_open_node);
121  if (this->max_search_nodes != 0 && this->nodes.ClosedCount() >= this->max_search_nodes) break;
122 
123  this->nodes.PopOpenNode(best_open_node->GetKey());
124  this->nodes.InsertClosedNode(*best_open_node);
125  }
126 
127  const bool destination_found = (this->best_dest_node != nullptr);
128 
129  if (_debug_yapf_level >= 3) {
130  const UnitID veh_idx = (this->vehicle != nullptr) ? this->vehicle->unitnumber : 0;
131  const char ttc = Yapf().TransportTypeChar();
132  const float cache_hit_ratio = (this->stats_cache_hits == 0) ? 0.0f : ((float)this->stats_cache_hits / (float)(this->stats_cache_hits + this->stats_cost_calcs) * 100.0f);
133  const int cost = destination_found ? this->best_dest_node->cost : -1;
134  const int dist = destination_found ? this->best_dest_node->estimate - this->best_dest_node->cost : -1;
135 
136  Debug(yapf, 3, "[YAPF{}]{}{:4d} - {} rounds - {} open - {} closed - CHR {:4.1f}% - C {} D {}",
137  ttc, destination_found ? '-' : '!', veh_idx, this->num_steps, this->nodes.OpenCount(), this->nodes.ClosedCount(), cache_hit_ratio, cost, dist
138  );
139  }
140 
141  return destination_found;
142  }
143 
148  inline Node *GetBestNode()
149  {
150  return (this->best_dest_node != nullptr) ? this->best_dest_node : this->best_intermediate_node;
151  }
152 
157  inline Node &CreateNewNode()
158  {
159  Node &node = *this->nodes.CreateNewNode();
160  return node;
161  }
162 
164  inline void AddStartupNode(Node &n)
165  {
166  Yapf().PfNodeCacheFetch(n);
167  /* insert the new node only if it is not there */
168  if (this->nodes.FindOpenNode(n.key) == nullptr) {
169  this->nodes.InsertOpenNode(n);
170  } else {
171  /* if we are here, it means that node is already there - how it is possible?
172  * probably the train is in the position that both its ends point to the same tile/exit-dir
173  * very unlikely, but it happened */
174  }
175  }
176 
178  inline void AddMultipleNodes(Node *parent, const TrackFollower &tf)
179  {
180  bool is_choice = (KillFirstBit(tf.new_td_bits) != TRACKDIR_BIT_NONE);
181  for (TrackdirBits rtds = tf.new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
182  Trackdir td = (Trackdir)FindFirstBit(rtds);
183  Node &n = Yapf().CreateNewNode();
184  n.Set(parent, tf.new_tile, td, is_choice);
185  Yapf().AddNewNode(n, tf);
186  }
187  }
188 
198  {
199  bool intermediate_on_branch = false;
200  while (n != nullptr && (n->segment->end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) {
201  if (n == Yapf().best_intermediate_node) intermediate_on_branch = true;
202  n = n->parent;
203  }
204  if (intermediate_on_branch) Yapf().best_intermediate_node = n;
205  }
206 
211  void AddNewNode(Node &n, const TrackFollower &tf)
212  {
213  /* evaluate the node */
214  bool cached = Yapf().PfNodeCacheFetch(n);
215  if (!cached) {
216  this->stats_cost_calcs++;
217  } else {
218  this->stats_cache_hits++;
219  }
220 
221  bool valid = Yapf().PfCalcCost(n, &tf);
222 
223  if (valid) valid = Yapf().PfCalcEstimate(n);
224 
225  /* have the cost or estimate callbacks marked this node as invalid? */
226  if (!valid) return;
227 
228  /* The new node can be set as the best intermediate node only once we're
229  * certain it will be finalized by being inserted into the open list. */
230  bool set_intermediate = this->max_search_nodes > 0 && (this->best_intermediate_node == nullptr || (this->best_intermediate_node->GetCostEstimate() - this->best_intermediate_node->GetCost()) > (n.GetCostEstimate() - n.GetCost()));
231 
232  /* check new node against open list */
233  Node *open_node = this->nodes.FindOpenNode(n.GetKey());
234  if (open_node != nullptr) {
235  /* another node exists with the same key in the open list
236  * is it better than new one? */
237  if (n.GetCostEstimate() < open_node->GetCostEstimate()) {
238  /* update the old node by value from new one */
239  this->nodes.PopOpenNode(n.GetKey());
240  *open_node = n;
241  /* add the updated old node back to open list */
242  this->nodes.InsertOpenNode(*open_node);
243  if (set_intermediate) this->best_intermediate_node = open_node;
244  }
245  return;
246  }
247 
248  /* check new node against closed list */
249  Node *closed_node = this->nodes.FindClosedNode(n.GetKey());
250  if (closed_node != nullptr) {
251  /* another node exists with the same key in the closed list
252  * is it better than new one? */
253  int node_est = n.GetCostEstimate();
254  int closed_est = closed_node->GetCostEstimate();
255  if (node_est < closed_est) {
256  /* If this assert occurs, you have probably problem in
257  * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
258  * The problem could be:
259  * - PfCalcEstimate() gives too large numbers
260  * - PfCalcCost() gives too small numbers
261  * - You have used negative cost penalty in some cases (cost bonus) */
262  NOT_REACHED();
263  }
264  return;
265  }
266  /* the new node is really new
267  * add it to the open list */
268  this->nodes.InsertOpenNode(n);
269  if (set_intermediate) this->best_intermediate_node = &n;
270  }
271 
272  const VehicleType * GetVehicle() const
273  {
274  return this->vehicle;
275  }
276 
277  void DumpBase(DumpTarget &dmp) const
278  {
279  dmp.WriteStructT("nodes", &this->nodes);
280  dmp.WriteValue("num_steps", this->num_steps);
281  }
282 };
283 
284 #endif /* YAPF_BASE_HPP */
constexpr uint8_t FindFirstBit(T x)
Search the first set bit in a value.
constexpr T KillFirstBit(T value)
Clear the first bit in an integer.
CYapfBaseT - A-star type path finder base class.
Definition: yapf_base.hpp:49
int num_steps
this is there for debugging purposes (hope it doesn't hurt)
Definition: yapf_base.hpp:72
void PruneIntermediateNodeBranch(Node *n)
In some cases an intermediate node branch should be pruned.
Definition: yapf_base.hpp:197
Node::Key Key
key to hash tables
Definition: yapf_base.hpp:56
CYapfBaseT()
default constructor
Definition: yapf_base.hpp:76
Node * GetBestNode()
If path was found return the best node that has reached the destination.
Definition: yapf_base.hpp:148
void AddNewNode(Node &n, const TrackFollower &tf)
AddNewNode() - called by Tderived::PfFollowNode() for each child node.
Definition: yapf_base.hpp:211
const VehicleType * vehicle
vehicle that we are trying to drive
Definition: yapf_base.hpp:66
Node & CreateNewNode()
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddS...
Definition: yapf_base.hpp:157
const YAPFSettings & PfGetSettings() const
return current settings (can be custom - company based - but later)
Definition: yapf_base.hpp:90
Node * best_intermediate_node
here should be node closest to the destination if path not found
Definition: yapf_base.hpp:63
Tpf & Yapf()
to access inherited path finder
Definition: yapf_base.hpp:83
const YAPFSettings * settings
current settings (_settings_game.yapf)
Definition: yapf_base.hpp:64
int stats_cache_hits
stats - how many node's costs were reused from cache
Definition: yapf_base.hpp:69
void AddMultipleNodes(Node *parent, const TrackFollower &tf)
add multiple nodes - direct children of the given node
Definition: yapf_base.hpp:178
int stats_cost_calcs
stats - how many node's costs were calculated
Definition: yapf_base.hpp:68
int max_search_nodes
maximum number of nodes we are allowed to visit before we give up
Definition: yapf_base.hpp:65
NodeList::Titem Node
this will be our node type
Definition: yapf_base.hpp:55
~CYapfBaseT()
default destructor
Definition: yapf_base.hpp:79
bool FindPath(const VehicleType *v)
Main pathfinder routine:
Definition: yapf_base.hpp:104
NodeList nodes
node list multi-container
Definition: yapf_base.hpp:59
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_base.hpp:51
Types::VehicleType VehicleType
the type of vehicle
Definition: yapf_base.hpp:54
void AddStartupNode(Node &n)
Add new node (created by CreateNewNode and filled with data) into open list.
Definition: yapf_base.hpp:164
Node * best_dest_node
pointer to the destination node found at last round
Definition: yapf_base.hpp:62
Types::NodeList NodeList
our node list
Definition: yapf_base.hpp:53
#define Debug(category, level, format_string,...)
Ouptut a line of debugging information.
Definition: debug.h:37
uint8_t valid
Bits indicating what variable is valid (for each bit, 0 is invalid, 1 is valid).
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:57
Class that represents the dump-into-string target.
Definition: dbg_helpers.h:95
void WriteValue(const std::string &name, int value)
Write 'name = value' with indent and new-line.
void WriteStructT(const std::string &name, const S *s)
Dump nested object (or only its name if this instance is already known).
Definition: dbg_helpers.h:147
Settings related to the yet another pathfinder.
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:67
TrackdirBits
Allow incrementing of Trackdir variables.
Definition: track_type.h:98
@ TRACKDIR_BIT_NONE
No track build.
Definition: track_type.h:99
uint16_t UnitID
Type for the company global vehicle unit number.
VehicleType
Available vehicle types.
Definition: vehicle_type.h:21
Types used by YAPF.