OpenTTD Source 20261112-master-gbcbec5e63f
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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
6 */
7
9
10#ifndef YAPF_BASE_HPP
11#define YAPF_BASE_HPP
12
13#include "../../debug.h"
14#include "../../settings_type.h"
16
46template <class Types>
48public:
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::Item Node;
54 typedef typename Node::Key Key;
55
57
64 using PfFollowNodeFunc = void(Node &old_node);
65
74 using PfCalcCostFunc = bool(Node &n, const TrackFollower *follower);
75
82 using PfCalcEstimateFunc = bool(Node &n);
83
89 using PfDetectDestinationFunc = bool(Node &n);
90
98
103 using TransportTypeCharFunc = char();
104
105protected:
106 Node *best_dest_node = nullptr;
110 const VehicleType *vehicle = nullptr;
111
114
115public:
116 int num_steps = 0;
117
118public:
121
122protected:
127 inline Tpf &Yapf()
128 {
129 return *static_cast<Tpf *>(this);
130 }
131
132public:
137 inline const YAPFSettings &PfGetSettings() const
138 {
139 return *this->settings;
140 }
141
152 inline bool FindPath(const VehicleType *v)
153 {
154 this->vehicle = v;
155
156 for (;;) {
157 this->num_steps++;
158 Node *best_open_node = this->nodes.GetBestOpenNode();
159 if (best_open_node == nullptr) break;
160
161 if (Yapf().PfDetectDestination(*best_open_node)) {
162 this->best_dest_node = best_open_node;
163 break;
164 }
165
166 Yapf().PfFollowNode(*best_open_node);
167 if (this->max_search_nodes != 0 && this->nodes.ClosedCount() >= this->max_search_nodes) break;
168
169 this->nodes.PopOpenNode(best_open_node->GetKey());
170 this->nodes.InsertClosedNode(*best_open_node);
171 }
172
173 const bool destination_found = (this->best_dest_node != nullptr);
174
176 const UnitID veh_idx = (this->vehicle != nullptr) ? this->vehicle->unitnumber : 0;
177 const char ttc = Yapf().TransportTypeChar();
178 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);
179 const int cost = destination_found ? this->best_dest_node->cost : -1;
180 const int dist = destination_found ? this->best_dest_node->estimate - this->best_dest_node->cost : -1;
181
182 Debug(Facility::Yapf, Severity::Notice, "[YAPF{}]{}{:4d} - {} rounds - {} open - {} closed - CHR {:4.1f}% - C {} D {}",
183 ttc, destination_found ? '-' : '!', veh_idx, this->num_steps, this->nodes.OpenCount(), this->nodes.ClosedCount(), cache_hit_ratio, cost, dist
184 );
185 }
186
187 return destination_found;
188 }
189
196 {
197 return (this->best_dest_node != nullptr) ? this->best_dest_node : this->best_intermediate_node;
198 }
199
206 {
207 Node &node = this->nodes.CreateNewNode();
208 return node;
209 }
210
215 inline void AddStartupNode(Node &n)
216 {
217 assert(n.parent == nullptr);
218 assert(this->num_steps == 0);
219
220 Yapf().PfNodeCacheFetch(n);
221 /* insert the new node only if it is not there */
222 if (this->nodes.FindOpenNode(n.key) == nullptr) {
223 this->nodes.InsertOpenNode(n);
224 }
225 }
226
232 inline void AddMultipleNodes(Node *parent, const TrackFollower &tf)
233 {
234 bool is_choice = tf.new_td_bits.Count() > 1;
235 for (Trackdir td : tf.new_td_bits) {
236 Node &n = Yapf().CreateNewNode();
237 n.Set(parent, tf.new_tile, td, is_choice);
238 Yapf().AddNewNode(n, tf);
239 }
240 }
241
248 void AddNewNode(Node &n, const TrackFollower &follower)
249 {
250 assert(n.parent != nullptr);
251
252 /* evaluate the node */
253 bool cached = Yapf().PfNodeCacheFetch(n);
254 if (!cached) {
255 this->stats_cost_calcs++;
256 } else {
257 this->stats_cache_hits++;
258 }
259
260 bool valid = Yapf().PfCalcCost(n, &follower);
261
262 if (valid) valid = Yapf().PfCalcEstimate(n);
263
264 /* have the cost or estimate callbacks marked this node as invalid? */
265 if (!valid) return;
266
267 /* The new node can be set as the best intermediate node only once we're
268 * certain it will be finalized by being inserted into the open list. */
269 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()));
270
271 /* check new node against open list */
272 Node *open_node = this->nodes.FindOpenNode(n.GetKey());
273 if (open_node != nullptr) {
274 /* another node exists with the same key in the open list
275 * is it better than new one? */
276 if (n.GetCostEstimate() < open_node->GetCostEstimate()) {
277 /* update the old node by value from new one */
278 this->nodes.PopOpenNode(n.GetKey());
279 *open_node = n;
280 /* add the updated old node back to open list */
281 this->nodes.InsertOpenNode(*open_node);
282 if (set_intermediate) this->best_intermediate_node = open_node;
283 }
284 return;
285 }
286
287 /* check new node against closed list */
288 Node *closed_node = this->nodes.FindClosedNode(n.GetKey());
289 if (closed_node != nullptr) {
290 /* another node exists with the same key in the closed list
291 * is it better than new one? */
292 int node_est = n.GetCostEstimate();
293 int closed_est = closed_node->GetCostEstimate();
294 if (node_est < closed_est) {
295 /* If this assert occurs, you have probably problem in
296 * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
297 * The problem could be:
298 * - PfCalcEstimate() gives too large numbers
299 * - PfCalcCost() gives too small numbers
300 * - You have used negative cost penalty in some cases (cost bonus) */
301 NOT_REACHED();
302 }
303 return;
304 }
305 /* the new node is really new
306 * add it to the open list */
307 this->nodes.InsertOpenNode(n);
308 if (set_intermediate) this->best_intermediate_node = &n;
309 }
310
311 const VehicleType * GetVehicle() const
312 {
313 return this->vehicle;
314 }
315
316 void DumpBase(DumpTarget &dmp) const
317 {
318 dmp.WriteStructT("nodes", &this->nodes);
319 dmp.WriteValue("num_steps", this->num_steps);
320 }
321};
322
323#endif /* YAPF_BASE_HPP */
int num_steps
this is there for debugging purposes (hope it doesn't hurt)
void(Node &old_node) PfFollowNodeFunc
Called by YAPF to move from the given node to the next tile.
Definition yapf_base.hpp:64
Node::Key Key
key to hash tables
Definition yapf_base.hpp:54
void AddNewNode(Node &n, const TrackFollower &follower)
AddNewNode() - called by Tderived::PfFollowNode() for each child node.
CYapfBaseT()
default constructor
const VehicleType * vehicle
vehicle that we are trying to drive
Node * best_intermediate_node
here should be node closest to the destination if path not found
char() TransportTypeCharFunc
Return debug report character to identify the transportation type.
const YAPFSettings * settings
current settings (_settings_game.yapf)
int stats_cache_hits
stats - how many node's costs were reused from cache
void AddMultipleNodes(Node *parent, const TrackFollower &tf)
Add multiple nodes - direct children of the given node.
int stats_cost_calcs
stats - how many node's costs were calculated
int max_search_nodes
maximum number of nodes we are allowed to visit before we give up
bool(TileIndex tile, Trackdir td) PfDetectDestinationTileFunc
Called by YAPF to detect if node ends in the desired destination.
Definition yapf_base.hpp:97
bool(Node &n) PfDetectDestinationFunc
Called by YAPF to detect if node ends in the desired destination.
Definition yapf_base.hpp:89
bool(Node &n, const TrackFollower *follower) PfCalcCostFunc
Called by YAPF to calculate the cost from the origin to the given node.
Definition yapf_base.hpp:74
Node * GetBestNode()
If path was found return the best node that has reached the destination.
bool FindPath(const VehicleType *v)
Main pathfinder routine:
bool(Node &n) PfCalcEstimateFunc
Called by YAPF to calculate cost estimate.
Definition yapf_base.hpp:82
Node & CreateNewNode()
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddS...
NodeList nodes
node list multi-container
Definition yapf_base.hpp:56
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition yapf_base.hpp:49
const YAPFSettings & PfGetSettings() const
Return current settings (can be custom - company based - but later).
Types::VehicleType VehicleType
the type of vehicle
Definition yapf_base.hpp:52
void AddStartupNode(Node &n)
Add new node (created by CreateNewNode and filled with data) into open list.
Node * best_dest_node
pointer to the destination node found at last round
NodeList::Item Node
this will be our node type
Definition yapf_base.hpp:53
Types::NodeList NodeList
our node list
Definition yapf_base.hpp:51
Tpf & Yapf()
Access the inherited path finder.
void InsertClosedNode(Titem &item)
Insert the given item into the closed nodes set.
Definition nodelist.hpp:157
Titem * FindClosedNode(const Key &key)
Find a closed node by its key.
Definition nodelist.hpp:168
void InsertOpenNode(Titem &item)
Insert given item as open node (into open_nodes and open_queue).
Definition nodelist.hpp:94
int OpenCount()
Get open node count.
Definition nodelist.hpp:44
int ClosedCount()
Get closed node count.
Definition nodelist.hpp:53
Titem & CreateNewNode()
Allocate new data item from items.
Definition nodelist.hpp:71
Titem * GetBestOpenNode()
Get the open node at the begin of the open queue.
Definition nodelist.hpp:108
Titem & PopOpenNode(const Key &key)
Find and remove an open node by key.
Definition nodelist.hpp:145
Titem * FindOpenNode(const Key &key)
Find an open node by key.
Definition nodelist.hpp:135
Functions to be used for debug printings.
Functions related to debugging.
bool IsVisibleSeverity(Facility facility, Severity severity)
Test if debug severity is visible for the given facility.
Definition debug.h:24
#define Debug(facility, severity, format_string,...)
Output a line of debugging information.
Definition debug.h:36
@ Yapf
Yapf message facility.
Definition debug_type.h:36
@ Notice
Notice.
Definition debug_type.h:18
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition settings.cpp:61
Types related to global configuration settings.
void WriteStructT(std::string_view name, const S *s)
Dump nested object (or only its name if this instance is already known).
void WriteValue(std::string_view name, const auto &value)
Write 'name = value' with indent and new-line.
Settings related to the yet another pathfinder.
StrongType::Typedef< uint32_t, struct TileIndexTag, StrongType::Compare, StrongType::Integer, StrongType::Compatible< int32_t >, StrongType::Compatible< int64_t > > TileIndex
The index/ID of a Tile.
Definition tile_type.h:92
Trackdir
Enumeration for tracks and directions.
Definition track_type.h:63
uint16_t UnitID
Type for the company global vehicle unit number.
VehicleType
Available vehicle types.