OpenTTD Source 20241224-master-gee860a5c8e
|
CYapfBaseT - A-star type path finder base class. More...
#include <yapf_base.hpp>
Public Types | |
typedef Types::Tpf | Tpf |
the pathfinder class (derived from THIS class) | |
typedef Types::TrackFollower | TrackFollower |
typedef Types::NodeList | NodeList |
our node list | |
typedef Types::VehicleType | VehicleType |
the type of vehicle | |
typedef NodeList::Item | Node |
this will be our node type | |
typedef Node::Key | Key |
key to hash tables | |
Public Member Functions | |
CYapfBaseT () | |
default constructor | |
~CYapfBaseT () | |
default destructor | |
const YAPFSettings & | PfGetSettings () const |
return current settings (can be custom - company based - but later) | |
bool | FindPath (const VehicleType *v) |
Main pathfinder routine: | |
Node * | GetBestNode () |
If path was found return the best node that has reached the destination. | |
Node & | CreateNewNode () |
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddStartupNode() or AddNewNode() | |
void | AddStartupNode (Node &n) |
Add new node (created by CreateNewNode and filled with data) into open list. | |
void | AddMultipleNodes (Node *parent, const TrackFollower &tf) |
add multiple nodes - direct children of the given node | |
void | PruneIntermediateNodeBranch (Node *n) |
In some cases an intermediate node branch should be pruned. | |
void | AddNewNode (Node &n, const TrackFollower &tf) |
AddNewNode() - called by Tderived::PfFollowNode() for each child node. | |
const VehicleType * | GetVehicle () const |
void | DumpBase (DumpTarget &dmp) const |
Data Fields | |
NodeList | nodes |
node list multi-container | |
int | num_steps = 0 |
this is there for debugging purposes (hope it doesn't hurt) | |
Protected Member Functions | |
Tpf & | Yapf () |
to access inherited path finder | |
Protected Attributes | |
Node * | best_dest_node = nullptr |
pointer to the destination node found at last round | |
Node * | best_intermediate_node = nullptr |
here should be node closest to the destination if path not found | |
const YAPFSettings * | settings |
current settings (_settings_game.yapf) | |
int | max_search_nodes |
maximum number of nodes we are allowed to visit before we give up | |
const VehicleType * | vehicle = nullptr |
vehicle that we are trying to drive | |
int | stats_cost_calcs = 0 |
stats - how many node's costs were calculated | |
int | stats_cache_hits = 0 |
stats - how many node's costs were reused from cache | |
CYapfBaseT - A-star type path finder base class.
Derive your own pathfinder from it. You must provide the following template argument: Types - used as collection of local types used in pathfinder
The following types must be defined in the 'Types' argument:
For node list you can use template class NodeList, for which you need to declare only your node type. Look at test_yapf.h for an example.
Your pathfinder derived class needs to implement following methods: inline void PfSetStartupNodes() inline void PfFollowNode(Node &org) inline bool PfCalcCost(Node &n) inline bool PfCalcEstimate(Node &n) inline bool PfDetectDestination(Node &n)
For more details about those methods, look at the end of CYapfBaseT declaration. There are some examples. For another example look at test_yapf.h (part or unittest project).
Definition at line 49 of file yapf_base.hpp.
typedef Node::Key CYapfBaseT< Types >::Key |
key to hash tables
Definition at line 56 of file yapf_base.hpp.
typedef NodeList::Item CYapfBaseT< Types >::Node |
this will be our node type
Definition at line 55 of file yapf_base.hpp.
typedef Types::NodeList CYapfBaseT< Types >::NodeList |
our node list
Definition at line 53 of file yapf_base.hpp.
typedef Types::Tpf CYapfBaseT< Types >::Tpf |
the pathfinder class (derived from THIS class)
Definition at line 51 of file yapf_base.hpp.
typedef Types::TrackFollower CYapfBaseT< Types >::TrackFollower |
Definition at line 52 of file yapf_base.hpp.
typedef Types::VehicleType CYapfBaseT< Types >::VehicleType |
the type of vehicle
Definition at line 54 of file yapf_base.hpp.
|
inline |
default constructor
Definition at line 75 of file yapf_base.hpp.
|
inline |
default destructor
Definition at line 78 of file yapf_base.hpp.
|
inline |
add multiple nodes - direct children of the given node
Definition at line 177 of file yapf_base.hpp.
References FindFirstBit(), KillFirstBit(), TRACKDIR_BIT_NONE, and CYapfBaseT< Types >::Yapf().
|
inline |
AddNewNode() - called by Tderived::PfFollowNode() for each child node.
Nodes are evaluated here and added into open list
Definition at line 210 of file yapf_base.hpp.
References NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindClosedNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindOpenNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertOpenNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode(), valid, and CYapfBaseT< Types >::Yapf().
|
inline |
Add new node (created by CreateNewNode and filled with data) into open list.
Definition at line 163 of file yapf_base.hpp.
References NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindOpenNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertOpenNode(), and CYapfBaseT< Types >::Yapf().
|
inline |
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddStartupNode() or AddNewNode()
Definition at line 156 of file yapf_base.hpp.
References NodeList< Titem, Thash_bits_open, Thash_bits_closed >::CreateNewNode().
|
inline |
Definition at line 276 of file yapf_base.hpp.
|
inline |
Main pathfinder routine:
Definition at line 103 of file yapf_base.hpp.
References NodeList< Titem, Thash_bits_open, Thash_bits_closed >::ClosedCount(), Debug, NodeList< Titem, Thash_bits_open, Thash_bits_closed >::GetBestOpenNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertClosedNode(), CYapfBaseT< Types >::num_steps, NodeList< Titem, Thash_bits_open, Thash_bits_closed >::OpenCount(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode(), CYapfBaseT< Types >::stats_cost_calcs, and CYapfBaseT< Types >::Yapf().
|
inline |
If path was found return the best node that has reached the destination.
Otherwise return the best visited node (which was nearest to the destination).
Definition at line 147 of file yapf_base.hpp.
References CYapfBaseT< Types >::best_dest_node, and CYapfBaseT< Types >::best_intermediate_node.
|
inline |
Definition at line 271 of file yapf_base.hpp.
|
inline |
return current settings (can be custom - company based - but later)
Definition at line 89 of file yapf_base.hpp.
References CYapfBaseT< Types >::settings.
|
inline |
In some cases an intermediate node branch should be pruned.
The most prominent case is when a red EOL signal is encountered, but there was a segment change (e.g. a rail type change) before that. If the branch would not be pruned, the rail type change location would remain the best intermediate node, and thus the vehicle would still go towards the red EOL signal.
Definition at line 196 of file yapf_base.hpp.
References CYapfBaseT< Types >::best_intermediate_node, and CYapfBaseT< Types >::Yapf().
|
inlineprotected |
to access inherited path finder
Definition at line 82 of file yapf_base.hpp.
Referenced by CYapfBaseT< Types >::AddMultipleNodes(), CYapfBaseT< Types >::AddNewNode(), CYapfBaseT< Types >::AddStartupNode(), CYapfBaseT< Types >::FindPath(), and CYapfBaseT< Types >::PruneIntermediateNodeBranch().
|
protected |
pointer to the destination node found at last round
Definition at line 61 of file yapf_base.hpp.
Referenced by CYapfBaseT< Types >::GetBestNode().
|
protected |
here should be node closest to the destination if path not found
Definition at line 62 of file yapf_base.hpp.
Referenced by CYapfBaseT< Types >::GetBestNode(), and CYapfBaseT< Types >::PruneIntermediateNodeBranch().
|
protected |
maximum number of nodes we are allowed to visit before we give up
Definition at line 64 of file yapf_base.hpp.
NodeList CYapfBaseT< Types >::nodes |
node list multi-container
Definition at line 58 of file yapf_base.hpp.
int CYapfBaseT< Types >::num_steps = 0 |
this is there for debugging purposes (hope it doesn't hurt)
Definition at line 71 of file yapf_base.hpp.
Referenced by CYapfBaseT< Types >::FindPath().
|
protected |
current settings (_settings_game.yapf)
Definition at line 63 of file yapf_base.hpp.
Referenced by CYapfBaseT< Types >::PfGetSettings().
|
protected |
stats - how many node's costs were reused from cache
Definition at line 68 of file yapf_base.hpp.
|
protected |
stats - how many node's costs were calculated
Definition at line 67 of file yapf_base.hpp.
Referenced by CYapfBaseT< Types >::FindPath().
|
protected |
vehicle that we are trying to drive
Definition at line 65 of file yapf_base.hpp.