|
@@ -28,29 +28,29 @@ extern int _total_pf_time_us;
|
|
|
* - 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 CNodeList_HashTableT, for which
|
|
|
* you need to declare only your node type. Look at test_yapf.h for an example.
|
|
|
*
|
|
|
*
|
|
|
* Requrements to your pathfinder class derived from CYapfBaseT:
|
|
|
* -------------------------------------------------------------
|
|
|
* Your pathfinder derived class needs to implement following methods:
|
|
|
* FORCEINLINE void PfSetStartupNodes()
|
|
|
* FORCEINLINE void PfFollowNode(Node& org)
|
|
|
* FORCEINLINE bool PfCalcCost(Node& n)
|
|
|
* FORCEINLINE bool PfCalcEstimate(Node& n)
|
|
|
* FORCEINLINE bool PfDetectDestination(Node& n)
|
|
|
* 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).
|
|
|
*/
|
|
|
template <class Types>
|
|
|
class CYapfBaseT {
|
|
|
public:
|
|
|
typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class)
|
|
|
typedef typename Types::TrackFollower TrackFollower;
|
|
|
typedef typename Types::NodeList NodeList; ///< our node list
|
|
|
typedef typename Types::VehicleType VehicleType; ///< the type of vehicle
|
|
@@ -71,49 +71,49 @@ protected:
|
|
|
|
|
|
public:
|
|
|
CPerformanceTimer m_perf_cost; ///< stats - total CPU time of this run
|
|
|
CPerformanceTimer m_perf_slope_cost; ///< stats - slope calculation CPU time
|
|
|
CPerformanceTimer m_perf_ts_cost; ///< stats - GetTrackStatus() CPU time
|
|
|
CPerformanceTimer m_perf_other_cost; ///< stats - other CPU time
|
|
|
|
|
|
public:
|
|
|
int m_num_steps; ///< this is there for debugging purposes (hope it doesn't hurt)
|
|
|
|
|
|
public:
|
|
|
/** default constructor */
|
|
|
FORCEINLINE CYapfBaseT()
|
|
|
inline CYapfBaseT()
|
|
|
: m_pBestDestNode(NULL)
|
|
|
, m_pBestIntermediateNode(NULL)
|
|
|
, m_settings(&_settings_game.pf.yapf)
|
|
|
, m_max_search_nodes(PfGetSettings().max_search_nodes)
|
|
|
, m_veh(NULL)
|
|
|
, m_stats_cost_calcs(0)
|
|
|
, m_stats_cache_hits(0)
|
|
|
, m_num_steps(0)
|
|
|
{
|
|
|
}
|
|
|
|
|
|
/** default destructor */
|
|
|
~CYapfBaseT() {}
|
|
|
|
|
|
protected:
|
|
|
/** to access inherited path finder */
|
|
|
FORCEINLINE Tpf& Yapf()
|
|
|
inline Tpf& Yapf()
|
|
|
{
|
|
|
return *static_cast<Tpf*>(this);
|
|
|
}
|
|
|
|
|
|
public:
|
|
|
/** return current settings (can be custom - company based - but later) */
|
|
|
FORCEINLINE const YAPFSettings& PfGetSettings() const
|
|
|
inline const YAPFSettings& PfGetSettings() const
|
|
|
{
|
|
|
return *m_settings;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* 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 - m_max_search_nodes (default = 10000)
|
|
|
* @return true if the path was found
|
|
@@ -173,55 +173,55 @@ public:
|
|
|
m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000)
|
|
|
);
|
|
|
}
|
|
|
}
|
|
|
#endif /* !NO_DEBUG_MESSAGES */
|
|
|
return bDestFound;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* 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).
|
|
|
*/
|
|
|
FORCEINLINE Node *GetBestNode()
|
|
|
inline Node *GetBestNode()
|
|
|
{
|
|
|
return (m_pBestDestNode != NULL) ? m_pBestDestNode : m_pBestIntermediateNode;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Calls NodeList::CreateNewNode() - allocates new node that can be filled and used
|
|
|
* as argument for AddStartupNode() or AddNewNode()
|
|
|
*/
|
|
|
FORCEINLINE Node& CreateNewNode()
|
|
|
inline Node& CreateNewNode()
|
|
|
{
|
|
|
Node& node = *m_nodes.CreateNewNode();
|
|
|
return node;
|
|
|
}
|
|
|
|
|
|
/** Add new node (created by CreateNewNode and filled with data) into open list */
|
|
|
FORCEINLINE void AddStartupNode(Node& n)
|
|
|
inline void AddStartupNode(Node& n)
|
|
|
{
|
|
|
Yapf().PfNodeCacheFetch(n);
|
|
|
/* insert the new node only if it is not there */
|
|
|
if (m_nodes.FindOpenNode(n.m_key) == NULL) {
|
|
|
m_nodes.InsertOpenNode(n);
|
|
|
} else {
|
|
|
/* if we are here, it means that node is already there - how it is possible?
|
|
|
* probably the train is in the position that both its ends point to the same tile/exit-dir
|
|
|
* very unlikely, but it happened */
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/** add multiple nodes - direct children of the given node */
|
|
|
FORCEINLINE void AddMultipleNodes(Node *parent, const TrackFollower &tf)
|
|
|
inline void AddMultipleNodes(Node *parent, const TrackFollower &tf)
|
|
|
{
|
|
|
bool is_choice = (KillFirstBit(tf.m_new_td_bits) != TRACKDIR_BIT_NONE);
|
|
|
for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
|
|
|
Trackdir td = (Trackdir)FindFirstBit2x64(rtds);
|
|
|
Node& n = Yapf().CreateNewNode();
|
|
|
n.Set(parent, tf.m_new_tile, td, is_choice);
|
|
|
Yapf().AddNewNode(n, tf);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* AddNewNode() - called by Tderived::PfFollowNode() for each child node.
|
|
@@ -306,65 +306,65 @@ public:
|
|
|
}
|
|
|
|
|
|
void DumpBase(DumpTarget &dmp) const
|
|
|
{
|
|
|
dmp.WriteStructT("m_nodes", &m_nodes);
|
|
|
dmp.WriteLine("m_num_steps = %d", m_num_steps);
|
|
|
}
|
|
|
|
|
|
/* methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT) */
|
|
|
|
|
|
#if 0
|
|
|
/** Example: PfSetStartupNodes() - set source (origin) nodes */
|
|
|
FORCEINLINE void PfSetStartupNodes()
|
|
|
inline void PfSetStartupNodes()
|
|
|
{
|
|
|
/* example: */
|
|
|
Node& n1 = *base::m_nodes.CreateNewNode();
|
|
|
.
|
|
|
. // setup node members here
|
|
|
.
|
|
|
base::m_nodes.InsertOpenNode(n1);
|
|
|
}
|
|
|
|
|
|
/** Example: PfFollowNode() - set following (child) nodes of the given node */
|
|
|
FORCEINLINE void PfFollowNode(Node& org)
|
|
|
inline void PfFollowNode(Node& org)
|
|
|
{
|
|
|
for (each follower of node org) {
|
|
|
Node& n = *base::m_nodes.CreateNewNode();
|
|
|
.
|
|
|
. // setup node members here
|
|
|
.
|
|
|
n.m_parent = &org; // set node's parent to allow back tracking
|
|
|
AddNewNode(n);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/** Example: PfCalcCost() - set path cost from origin to the given node */
|
|
|
FORCEINLINE bool PfCalcCost(Node& n)
|
|
|
inline bool PfCalcCost(Node& n)
|
|
|
{
|
|
|
/* evaluate last step cost */
|
|
|
int cost = ...;
|
|
|
/* set the node cost as sum of parent's cost and last step cost */
|
|
|
n.m_cost = n.m_parent->m_cost + cost;
|
|
|
return true; // true if node is valid follower (i.e. no obstacle was found)
|
|
|
}
|
|
|
|
|
|
/** Example: PfCalcEstimate() - set path cost estimate from origin to the target through given node */
|
|
|
FORCEINLINE bool PfCalcEstimate(Node& n)
|
|
|
inline bool PfCalcEstimate(Node& n)
|
|
|
{
|
|
|
/* evaluate the distance to our destination */
|
|
|
int distance = ...;
|
|
|
/* set estimate as sum of cost from origin + distance to the target */
|
|
|
n.m_estimate = n.m_cost + distance;
|
|
|
return true; // true if node is valid (i.e. not too far away :)
|
|
|
}
|
|
|
|
|
|
/** Example: PfDetectDestination() - return true if the given node is our destination */
|
|
|
FORCEINLINE bool PfDetectDestination(Node& n)
|
|
|
inline bool PfDetectDestination(Node& n)
|
|
|
{
|
|
|
bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
|
|
|
return bDest;
|
|
|
}
|
|
|
#endif
|
|
|
};
|
|
|
|
|
|
#endif /* YAPF_BASE_HPP */
|