OpenTTD Source 20241224-master-gf74b0cf984
CYapfBaseT< Types > Class Template Reference

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 YAPFSettingsPfGetSettings () const
 return current settings (can be custom - company based - but later)
 
bool FindPath (const VehicleType *v)
 Main pathfinder routine:
 
NodeGetBestNode ()
 If path was found return the best node that has reached the destination.
 
NodeCreateNewNode ()
 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 VehicleTypeGetVehicle () 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

TpfYapf ()
 to access inherited path finder
 

Protected Attributes

Nodebest_dest_node = nullptr
 pointer to the destination node found at last round
 
Nodebest_intermediate_node = nullptr
 here should be node closest to the destination if path not found
 
const YAPFSettingssettings
 current settings (_settings_game.yapf)
 
int max_search_nodes
 maximum number of nodes we are allowed to visit before we give up
 
const VehicleTypevehicle = 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
 

Detailed Description

template<class Types>
class CYapfBaseT< Types >

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

Requirements for the Types struct:

The following types must be defined in the 'Types' argument:

  • Types::Tpf - your pathfinder derived from CYapfBaseT
  • Types::NodeList - open/closed node list (look at CNodeList_HashTableT) NodeList needs to have defined local type Titem - defines the pathfinder node type. Node needs to define local type Key - the node key in the collection ()

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.

Requirements to your pathfinder class derived from CYapfBaseT:

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.

Member Typedef Documentation

◆ Key

template<class Types >
typedef Node::Key CYapfBaseT< Types >::Key

key to hash tables

Definition at line 56 of file yapf_base.hpp.

◆ Node

template<class Types >
typedef NodeList::Item CYapfBaseT< Types >::Node

this will be our node type

Definition at line 55 of file yapf_base.hpp.

◆ NodeList

template<class Types >
typedef Types::NodeList CYapfBaseT< Types >::NodeList

our node list

Definition at line 53 of file yapf_base.hpp.

◆ Tpf

template<class Types >
typedef Types::Tpf CYapfBaseT< Types >::Tpf

the pathfinder class (derived from THIS class)

Definition at line 51 of file yapf_base.hpp.

◆ TrackFollower

template<class Types >
typedef Types::TrackFollower CYapfBaseT< Types >::TrackFollower

Definition at line 52 of file yapf_base.hpp.

◆ VehicleType

template<class Types >
typedef Types::VehicleType CYapfBaseT< Types >::VehicleType

the type of vehicle

Definition at line 54 of file yapf_base.hpp.

Constructor & Destructor Documentation

◆ CYapfBaseT()

template<class Types >
CYapfBaseT< Types >::CYapfBaseT ( )
inline

default constructor

Definition at line 75 of file yapf_base.hpp.

◆ ~CYapfBaseT()

template<class Types >
CYapfBaseT< Types >::~CYapfBaseT ( )
inline

default destructor

Definition at line 78 of file yapf_base.hpp.

Member Function Documentation

◆ AddMultipleNodes()

template<class Types >
void CYapfBaseT< Types >::AddMultipleNodes ( Node parent,
const TrackFollower &  tf 
)
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().

◆ AddNewNode()

template<class Types >
void CYapfBaseT< Types >::AddNewNode ( Node n,
const TrackFollower &  tf 
)
inline

◆ AddStartupNode()

template<class Types >
void CYapfBaseT< Types >::AddStartupNode ( Node n)
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().

◆ CreateNewNode()

template<class Types >
Node & CYapfBaseT< Types >::CreateNewNode ( )
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().

◆ DumpBase()

template<class Types >
void CYapfBaseT< Types >::DumpBase ( DumpTarget dmp) const
inline

Definition at line 276 of file yapf_base.hpp.

◆ FindPath()

template<class Types >
bool CYapfBaseT< Types >::FindPath ( const VehicleType v)
inline

Main pathfinder routine:

  • set startup node(s)
  • main loop that stops if:
    • the destination was found
    • or the open list is empty (no route to destination).
    • or the maximum amount of loops reached - max_search_nodes (default = 10000)
      Returns
      true if the path was found

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().

◆ GetBestNode()

template<class Types >
Node * CYapfBaseT< Types >::GetBestNode ( )
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.

◆ GetVehicle()

template<class Types >
const VehicleType * CYapfBaseT< Types >::GetVehicle ( ) const
inline

Definition at line 271 of file yapf_base.hpp.

◆ PfGetSettings()

template<class Types >
const YAPFSettings & CYapfBaseT< Types >::PfGetSettings ( ) const
inline

return current settings (can be custom - company based - but later)

Definition at line 89 of file yapf_base.hpp.

References CYapfBaseT< Types >::settings.

◆ PruneIntermediateNodeBranch()

template<class Types >
void CYapfBaseT< Types >::PruneIntermediateNodeBranch ( Node n)
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().

◆ Yapf()

template<class Types >
Tpf & CYapfBaseT< Types >::Yapf ( )
inlineprotected

Field Documentation

◆ best_dest_node

template<class Types >
Node* CYapfBaseT< Types >::best_dest_node = nullptr
protected

pointer to the destination node found at last round

Definition at line 61 of file yapf_base.hpp.

Referenced by CYapfBaseT< Types >::GetBestNode().

◆ best_intermediate_node

template<class Types >
Node* CYapfBaseT< Types >::best_intermediate_node = nullptr
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().

◆ max_search_nodes

template<class Types >
int CYapfBaseT< Types >::max_search_nodes
protected

maximum number of nodes we are allowed to visit before we give up

Definition at line 64 of file yapf_base.hpp.

◆ nodes

template<class Types >
NodeList CYapfBaseT< Types >::nodes

node list multi-container

Definition at line 58 of file yapf_base.hpp.

◆ num_steps

template<class Types >
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().

◆ settings

template<class Types >
const YAPFSettings* CYapfBaseT< Types >::settings
protected

current settings (_settings_game.yapf)

Definition at line 63 of file yapf_base.hpp.

Referenced by CYapfBaseT< Types >::PfGetSettings().

◆ stats_cache_hits

template<class Types >
int CYapfBaseT< Types >::stats_cache_hits = 0
protected

stats - how many node's costs were reused from cache

Definition at line 68 of file yapf_base.hpp.

◆ stats_cost_calcs

template<class Types >
int CYapfBaseT< Types >::stats_cost_calcs = 0
protected

stats - how many node's costs were calculated

Definition at line 67 of file yapf_base.hpp.

Referenced by CYapfBaseT< Types >::FindPath().

◆ vehicle

template<class Types >
const VehicleType* CYapfBaseT< Types >::vehicle = nullptr
protected

vehicle that we are trying to drive

Definition at line 65 of file yapf_base.hpp.


The documentation for this class was generated from the following file: