49 typedef typename Types::Tpf
Tpf;
50 typedef typename Types::TrackFollower TrackFollower;
53 typedef typename NodeList::Item
Node;
54 typedef typename Node::Key
Key;
129 return *
static_cast<Tpf *
>(
this);
139 return *this->settings;
159 if (best_open_node ==
nullptr)
break;
161 if (
Yapf().PfDetectDestination(*best_open_node)) {
162 this->best_dest_node = best_open_node;
166 Yapf().PfFollowNode(*best_open_node);
167 if (this->max_search_nodes != 0 && this->nodes.
ClosedCount() >= this->max_search_nodes)
break;
173 const bool destination_found = (this->best_dest_node !=
nullptr);
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;
183 ttc, destination_found ?
'-' :
'!', veh_idx, this->num_steps, this->nodes.
OpenCount(), this->nodes.ClosedCount(), cache_hit_ratio, cost, dist
187 return destination_found;
197 return (this->best_dest_node !=
nullptr) ? this->best_dest_node : this->best_intermediate_node;
217 assert(n.parent ==
nullptr);
218 assert(this->num_steps == 0);
220 Yapf().PfNodeCacheFetch(n);
234 bool is_choice = tf.new_td_bits.Count() > 1;
235 for (
Trackdir td : tf.new_td_bits) {
237 n.Set(parent, tf.new_tile, td, is_choice);
238 Yapf().AddNewNode(n, tf);
250 assert(n.parent !=
nullptr);
253 bool cached =
Yapf().PfNodeCacheFetch(n);
255 this->stats_cost_calcs++;
257 this->stats_cache_hits++;
260 bool valid =
Yapf().PfCalcCost(n, &follower);
262 if (valid) valid =
Yapf().PfCalcEstimate(n);
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()));
273 if (open_node !=
nullptr) {
276 if (n.GetCostEstimate() < open_node->GetCostEstimate()) {
282 if (set_intermediate) this->best_intermediate_node = open_node;
289 if (closed_node !=
nullptr) {
292 int node_est = n.GetCostEstimate();
293 int closed_est = closed_node->GetCostEstimate();
294 if (node_est < closed_est) {
308 if (set_intermediate) this->best_intermediate_node = &n;
313 return this->vehicle;
316 void DumpBase(DumpTarget &dmp)
const
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.
Node::Key Key
key to hash tables
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.
bool(Node &n) PfDetectDestinationFunc
Called by YAPF to detect if node ends in the desired destination.
bool(Node &n, const TrackFollower *follower) PfCalcCostFunc
Called by YAPF to calculate the cost from the origin to the given node.
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.
Node & CreateNewNode()
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddS...
NodeList nodes
node list multi-container
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
const YAPFSettings & PfGetSettings() const
Return current settings (can be custom - company based - but later).
Types::VehicleType VehicleType
the type of vehicle
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
Types::NodeList NodeList
our node list
Tpf & Yapf()
Access the inherited path finder.
void InsertClosedNode(Titem &item)
Insert the given item into the closed nodes set.
Titem * FindClosedNode(const Key &key)
Find a closed node by its key.
void InsertOpenNode(Titem &item)
Insert given item as open node (into open_nodes and open_queue).
int OpenCount()
Get open node count.
int ClosedCount()
Get closed node count.
Titem & CreateNewNode()
Allocate new data item from items.
Titem * GetBestOpenNode()
Get the open node at the begin of the open queue.
Titem & PopOpenNode(const Key &key)
Find and remove an open node by key.
Titem * FindOpenNode(const Key &key)
Find an open node by key.
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.
#define Debug(facility, severity, format_string,...)
Output a line of debugging information.
@ Yapf
Yapf message facility.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
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.
Trackdir
Enumeration for tracks and directions.
uint16_t UnitID
Type for the company global vehicle unit number.
VehicleType
Available vehicle types.