CYapfBaseT - A-star type path finder base class. More...

#include <yapf_base.hpp>

Inheritance diagram for CYapfBaseT< Types >:

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
using	PfFollowNodeFunc = void(Node &old_node)
	Called by YAPF to move from the given node to the next tile.
using	PfCalcCostFunc = bool(Node &n, const TrackFollower *follower)
	Called by YAPF to calculate the cost from the origin to the given node.
using	PfCalcEstimateFunc = bool(Node &n)
	Called by YAPF to calculate cost estimate.
using	PfDetectDestinationFunc = bool(Node &n)
	Called by YAPF to detect if node ends in the desired destination.
using	PfDetectDestinationTileFunc = bool(TileIndex tile, Trackdir td)
	Called by YAPF to detect if node ends in the desired destination.
using	TransportTypeCharFunc = char()
	Return debug report character to identify the transportation type.

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	AddNewNode (Node &n, const TrackFollower &follower)
	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 ()
	Access the 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

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 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 48 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 55 of file yapf_base.hpp.

◆ Node

template<class Types>

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

this will be our node type

Definition at line 54 of file yapf_base.hpp.

◆ NodeList

template<class Types>

typedef Types::NodeList CYapfBaseT< Types >::NodeList

our node list

Definition at line 52 of file yapf_base.hpp.

◆ PfCalcCostFunc

template<class Types>

using CYapfBaseT< Types >::PfCalcCostFunc = bool(Node &n, const TrackFollower *follower)

Called by YAPF to calculate the cost from the origin to the given node.

Calculates only the cost of given node, adds it to the parent node cost and stores the result into Node::cost member.

Parameters

n	The node to consider.
follower	The track follower to the next node.

Returns: true iff the costs could be calculated.

Definition at line 75 of file yapf_base.hpp.

◆ PfCalcEstimateFunc

template<class Types>

using CYapfBaseT< Types >::PfCalcEstimateFunc = bool(Node &n)

Called by YAPF to calculate cost estimate.

Calculates distance to the destination adds it to the actual cost from origin and stores the sum to the Node::estimate.

Parameters

n	The node to start from.

Returns: true iff the cost could be estimated.

Definition at line 83 of file yapf_base.hpp.

◆ PfDetectDestinationFunc

template<class Types>

using CYapfBaseT< Types >::PfDetectDestinationFunc = bool(Node &n)

Called by YAPF to detect if node ends in the desired destination.

Parameters

n	The current node.

Returns: true iff the destination has been reached.

Definition at line 90 of file yapf_base.hpp.

◆ PfDetectDestinationTileFunc

template<class Types>

using CYapfBaseT< Types >::PfDetectDestinationTileFunc = bool(TileIndex tile, Trackdir td)

Called by YAPF to detect if node ends in the desired destination.

Parameters

tile	The reached tile.
td	The reached track direction.

Returns: true iff the destination has been reached.

Definition at line 98 of file yapf_base.hpp.

◆ PfFollowNodeFunc

template<class Types>

using CYapfBaseT< Types >::PfFollowNodeFunc = void(Node &old_node)

Called by YAPF to move from the given node to the next tile.

For each reachable trackdir on the new tile creates new node, initializes it and adds it to the open list by calling Yapf().AddNewNode(n).

Parameters

old_node The node to follow from.

Definition at line 65 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 50 of file yapf_base.hpp.

◆ TrackFollower

template<class Types>

typedef Types::TrackFollower CYapfBaseT< Types >::TrackFollower

Definition at line 51 of file yapf_base.hpp.

◆ TransportTypeCharFunc

template<class Types>

using CYapfBaseT< Types >::TransportTypeCharFunc = char()

Return debug report character to identify the transportation type.

Returns: The debug representation

Definition at line 104 of file yapf_base.hpp.

◆ VehicleType

template<class Types>

typedef Types::VehicleType CYapfBaseT< Types >::VehicleType

the type of vehicle

Definition at line 53 of file yapf_base.hpp.

Constructor & Destructor Documentation

◆ CYapfBaseT()

template<class Types>

CYapfBaseT< Types >::CYapfBaseT ( )

inline

default constructor

Definition at line 121 of file yapf_base.hpp.

References _settings_game, max_search_nodes, PfGetSettings(), and settings.

◆ ~CYapfBaseT()

template<class Types>

CYapfBaseT< Types >::~CYapfBaseT ( )

inline

default destructor

Definition at line 124 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.

Parameters

parent	The parent of the nodes.
tf	The track follower to keep following.

Definition at line 236 of file yapf_base.hpp.

References FindFirstBit(), KillFirstBit(), TRACKDIR_BIT_NONE, and Yapf().

◆ AddNewNode()

template<class Types>

void CYapfBaseT< Types >::AddNewNode	(	Node &	n,
		const TrackFollower &	follower )

inline

AddNewNode() - called by Tderived::PfFollowNode() for each child node.

Nodes are evaluated here and added into open list

Parameters

n	The node to add.
follower	The track follower to keep calculate the cost with.

Definition at line 253 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(), and Yapf().

Referenced by YapfRiverBuilder::PfFollowNode(), and YapfShipRegions::PfFollowNode().

◆ AddStartupNode()

template<class Types>

void CYapfBaseT< Types >::AddStartupNode ( Node & n )

inline

Add new node (created by CreateNewNode and filled with data) into open list.

Parameters

n	The node to add.

Definition at line 219 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 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().

Returns: The created node.

Definition at line 209 of file yapf_base.hpp.

References NodeList< Titem, Thash_bits_open, Thash_bits_closed >::CreateNewNode().

Referenced by YapfRiverBuilder::PfFollowNode(), and YapfShipRegions::PfFollowNode().

◆ DumpBase()

template<class Types>

void CYapfBaseT< Types >::DumpBase ( DumpTarget & dmp ) const

inline

Definition at line 321 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)
  Parameters
  
  v The vehicle to find the path for.
  
  Returns
  true if the path was found

Definition at line 156 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(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::OpenCount(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode(), and Yapf().

Referenced by YapfShipRegions::FindWaterRegionPath().

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

Returns: The best node, or best intermediate node.

Definition at line 199 of file yapf_base.hpp.

Referenced by YapfShipRegions::FindWaterRegionPath().

◆ GetVehicle()

template<class Types>

const VehicleType * CYapfBaseT< Types >::GetVehicle ( ) const

inline

Definition at line 316 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).

Returns: The pathfinder settings.

Definition at line 141 of file yapf_base.hpp.

Referenced by CYapfBaseT().

◆ Yapf()

template<class Types>

Tpf & CYapfBaseT< Types >::Yapf ( )

inlineprotected

Access the inherited path finder.

Returns: The current path finder.

Definition at line 131 of file yapf_base.hpp.

Referenced by AddMultipleNodes(), AddNewNode(), AddStartupNode(), and FindPath().

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 107 of file yapf_base.hpp.

◆ 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 108 of file yapf_base.hpp.

◆ 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 110 of file yapf_base.hpp.

Referenced by CYapfBaseT().

◆ nodes

template<class Types>

NodeList CYapfBaseT< Types >::nodes

node list multi-container

Definition at line 57 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 117 of file yapf_base.hpp.

◆ settings

template<class Types>

const YAPFSettings* CYapfBaseT< Types >::settings

protected

current settings (_settings_game.yapf)

Definition at line 109 of file yapf_base.hpp.

Referenced by CYapfBaseT().

◆ 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 114 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 113 of file yapf_base.hpp.

◆ vehicle

template<class Types>

const VehicleType* CYapfBaseT< Types >::vehicle = nullptr

protected

vehicle that we are trying to drive

Definition at line 111 of file yapf_base.hpp.

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

src/pathfinder/yapf/yapf_base.hpp

Public Types

Public Member Functions

Data Fields

Protected Member Functions

Protected Attributes

Detailed Description

Requirements for the Types struct:

Requirements to your pathfinder class derived from CYapfBaseT:

Member Typedef Documentation

◆ Key

◆ Node

◆ NodeList

◆ PfCalcCostFunc

◆ PfCalcEstimateFunc

◆ PfDetectDestinationFunc

◆ PfDetectDestinationTileFunc

◆ PfFollowNodeFunc

◆ Tpf

◆ TrackFollower

◆ TransportTypeCharFunc

◆ VehicleType

Constructor & Destructor Documentation

◆ CYapfBaseT()

◆ ~CYapfBaseT()

Member Function Documentation

◆ AddMultipleNodes()

◆ AddNewNode()

◆ AddStartupNode()

◆ CreateNewNode()

◆ DumpBase()

◆ FindPath()

◆ GetBestNode()

◆ GetVehicle()

◆ PfGetSettings()

◆ Yapf()

Field Documentation

◆ best_dest_node

◆ best_intermediate_node

◆ max_search_nodes

◆ nodes

◆ num_steps

◆ settings

◆ stats_cache_hits

◆ stats_cost_calcs

◆ vehicle