13 #include "../../debug.h"
14 #include "../../settings_type.h"
15 #include "../../misc/dbg_helpers.h"
48 template <
class Types>
51 typedef typename Types::Tpf
Tpf;
52 typedef typename Types::TrackFollower TrackFollower;
55 typedef typename NodeList::Titem
Node;
56 typedef typename Node::Key
Key;
85 return *
static_cast<Tpf *
>(
this);
108 Yapf().PfSetStartupNodes();
112 Node *best_open_node = this->nodes.GetBestOpenNode();
113 if (best_open_node ==
nullptr)
break;
115 if (
Yapf().PfDetectDestination(*best_open_node)) {
116 this->best_dest_node = best_open_node;
120 Yapf().PfFollowNode(*best_open_node);
121 if (this->max_search_nodes != 0 && this->nodes.ClosedCount() >= this->max_search_nodes)
break;
123 this->nodes.PopOpenNode(best_open_node->GetKey());
124 this->nodes.InsertClosedNode(*best_open_node);
127 const bool destination_found = (this->best_dest_node !=
nullptr);
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;
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
141 return destination_found;
159 Node &node = *this->nodes.CreateNewNode();
166 Yapf().PfNodeCacheFetch(n);
168 if (this->nodes.FindOpenNode(n.key) ==
nullptr) {
169 this->nodes.InsertOpenNode(n);
184 n.Set(parent, tf.new_tile, td, is_choice);
185 Yapf().AddNewNode(n, tf);
199 bool intermediate_on_branch =
false;
200 while (n !=
nullptr && (n->segment->end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) {
204 if (intermediate_on_branch)
Yapf().best_intermediate_node = n;
214 bool cached =
Yapf().PfNodeCacheFetch(n);
216 this->stats_cost_calcs++;
218 this->stats_cache_hits++;
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()));
233 Node *open_node = this->nodes.FindOpenNode(n.GetKey());
234 if (open_node !=
nullptr) {
237 if (n.GetCostEstimate() < open_node->GetCostEstimate()) {
239 this->nodes.PopOpenNode(n.GetKey());
242 this->nodes.InsertOpenNode(*open_node);
243 if (set_intermediate) this->best_intermediate_node = open_node;
249 Node *closed_node = this->nodes.FindClosedNode(n.GetKey());
250 if (closed_node !=
nullptr) {
253 int node_est = n.GetCostEstimate();
254 int closed_est = closed_node->GetCostEstimate();
255 if (node_est < closed_est) {
268 this->nodes.InsertOpenNode(n);
269 if (set_intermediate) this->best_intermediate_node = &n;
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.
int num_steps
this is there for debugging purposes (hope it doesn't hurt)
void PruneIntermediateNodeBranch(Node *n)
In some cases an intermediate node branch should be pruned.
Node::Key Key
key to hash tables
CYapfBaseT()
default constructor
Node * GetBestNode()
If path was found return the best node that has reached the destination.
void AddNewNode(Node &n, const TrackFollower &tf)
AddNewNode() - called by Tderived::PfFollowNode() for each child node.
const VehicleType * vehicle
vehicle that we are trying to drive
Node & CreateNewNode()
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddS...
const YAPFSettings & PfGetSettings() const
return current settings (can be custom - company based - but later)
Node * best_intermediate_node
here should be node closest to the destination if path not found
Tpf & Yapf()
to access inherited path finder
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
NodeList::Titem Node
this will be our node type
~CYapfBaseT()
default destructor
bool FindPath(const VehicleType *v)
Main pathfinder routine:
NodeList nodes
node list multi-container
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
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
Types::NodeList NodeList
our node list
#define Debug(category, level, format_string,...)
Ouptut a line of debugging information.
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.
Class that represents the dump-into-string target.
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).
Settings related to the yet another pathfinder.
Trackdir
Enumeration for tracks and directions.
TrackdirBits
Allow incrementing of Trackdir variables.
@ TRACKDIR_BIT_NONE
No track build.
uint16_t UnitID
Type for the company global vehicle unit number.
VehicleType
Available vehicle types.