|
|
/* $Id$ */
|
|
|
|
|
|
#ifndef YAPF_BASE_HPP
|
|
|
#define YAPF_BASE_HPP
|
|
|
|
|
|
EXTERN_C_BEGIN
|
|
|
#include "../debug.h"
|
|
|
EXTERN_C_END
|
|
|
|
|
|
#include "fixedsizearray.hpp"
|
|
|
#include "blob.hpp"
|
|
|
#include "nodelist.hpp"
|
|
|
|
|
|
extern int _total_pf_time_us;
|
|
|
|
|
|
/** 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 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)
|
|
|
|
|
|
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).
|
|
|
*/
|
|
|
* 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 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)
|
|
|
*
|
|
|
* 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::NodeList NodeList; ///< our node list
|
|
|
typedef typename NodeList::Titem Node; ///< this will be our node type
|
|
|
typedef typename Node::Key Key; ///< key to hash tables
|
|
|
|
|
|
|
|
|
NodeList m_nodes; ///< node list multi-container
|
|
|
protected:
|
|
|
Node* m_pBestDestNode; ///< pointer to the destination node found at last round
|
|
|
Node* m_pBestIntermediateNode; ///< here should be node closest to the destination if path not found
|
|
|
const YapfSettings *m_settings; ///< current settings (_patches.yapf)
|
|
|
int m_max_search_nodes; ///< maximum number of nodes we are allowed to visit before we give up
|
|
|
const Vehicle* m_veh; ///< vehicle that we are trying to drive
|
|
|
|
|
|
int m_stats_cost_calcs; ///< stats - how many node's costs were calculated
|
|
|
int m_stats_cache_hits; ///< stats - how many node's costs were reused from cache
|
|
|
|
|
|
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
|
|
@@ -84,54 +84,54 @@ public:
|
|
|
, m_max_search_nodes(PfGetSettings().max_search_nodes)
|
|
|
#endif
|
|
|
, 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() {return *static_cast<Tpf*>(this);}
|
|
|
|
|
|
public:
|
|
|
/// return current settings (can be custom - player based - but later)
|
|
|
FORCEINLINE 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 */
|
|
|
* - 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 */
|
|
|
inline bool FindPath(const Vehicle* v)
|
|
|
{
|
|
|
m_veh = v;
|
|
|
|
|
|
CPerformanceTimer perf;
|
|
|
perf.Start();
|
|
|
Yapf().PfSetStartupNodes();
|
|
|
|
|
|
while (true) {
|
|
|
m_num_steps++;
|
|
|
Node& n = m_nodes.GetBestOpenNode();
|
|
|
if (&n == NULL)
|
|
|
break;
|
|
|
|
|
|
// if the best open node was worse than the best path found, we can finish
|
|
|
if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n.GetCostEstimate())
|
|
|
break;
|
|
|
|
|
|
Yapf().PfFollowNode(n);
|
|
|
if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) {
|
|
|
m_nodes.PopOpenNode(n.GetKey());
|
|
|
m_nodes.InsertClosedNode(n);
|
|
|
} else {
|
|
|
m_pBestDestNode = m_pBestIntermediateNode;
|
|
@@ -139,92 +139,92 @@ public:
|
|
|
}
|
|
|
}
|
|
|
bool bDestFound = (m_pBestDestNode != NULL);
|
|
|
|
|
|
int16 veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0;
|
|
|
|
|
|
// if (veh_idx != 433) return bDestFound;
|
|
|
|
|
|
perf.Stop();
|
|
|
int t = perf.Get(1000000);
|
|
|
_total_pf_time_us += t;
|
|
|
char ttc = Yapf().TransportTypeChar();
|
|
|
float cache_hit_ratio = (float)m_stats_cache_hits / (float)(m_stats_cache_hits + m_stats_cost_calcs) * 100.0f;
|
|
|
int cost = bDestFound ? m_pBestDestNode->m_cost : -1;
|
|
|
int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;
|
|
|
#ifdef UNITTEST
|
|
|
printf("%c%c%4d-%6d us -%5d rounds -%4d open -%5d closed - CHR %4.1f%% - c/d(%d, %d) - c%d(sc%d, ts%d, o%d) -- \n", bDestFound ? '-' : '!', ttc, veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000), m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000));
|
|
|
#else
|
|
|
DEBUG(yapf, 3)("[YAPF][YAPF%c]%c%4d- %d us - %d rounds - %d open - %d closed - CHR %4.1f%% - c%d(sc%d, ts%d, o%d) -- ", ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000), m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000));
|
|
|
#endif
|
|
|
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).
|
|
|
*/
|
|
|
* return the best visited node (which was nearest to the destination).
|
|
|
*/
|
|
|
FORCEINLINE 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()
|
|
|
*/
|
|
|
* as argument for AddStartupNode() or AddNewNode()
|
|
|
*/
|
|
|
FORCEINLINE 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)
|
|
|
{
|
|
|
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, TileIndex tile, TrackdirBits td_bits)
|
|
|
{
|
|
|
bool is_choice = (KillFirstBit2x64(td_bits) != 0);
|
|
|
for (TrackdirBits rtds = td_bits; rtds != TRACKDIR_BIT_NONE; rtds = (TrackdirBits)KillFirstBit2x64(rtds)) {
|
|
|
Trackdir td = (Trackdir)FindFirstBit2x64(rtds);
|
|
|
Node& n = Yapf().CreateNewNode();
|
|
|
n.Set(parent, tile, td, is_choice);
|
|
|
Yapf().AddNewNode(n);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/** AddNewNode() - called by Tderived::PfFollowNode() for each child node.
|
|
|
Nodes are evaluated here and added into open list */
|
|
|
* Nodes are evaluated here and added into open list */
|
|
|
void AddNewNode(Node& n)
|
|
|
{
|
|
|
// evaluate the node
|
|
|
bool bCached = Yapf().PfNodeCacheFetch(n);
|
|
|
if (!bCached) {
|
|
|
m_stats_cost_calcs++;
|
|
|
} else {
|
|
|
m_stats_cache_hits++;
|
|
|
}
|
|
|
|
|
|
bool bValid = Yapf().PfCalcCost(n);
|
|
|
|
|
|
if (bCached) {
|
|
|
Yapf().PfNodeCacheFlush(n);
|
|
|
}
|
|
|
|
|
|
if (bValid) bValid = Yapf().PfCalcEstimate(n);
|
|
|
|
|
|
// have the cost or estimate callbacks marked this node as invalid?
|
|
|
if (!bValid) return;
|
|
|
|
|
|
// detect the destination
|
|
|
bool bDestination = Yapf().PfDetectDestination(n);
|
|
|
if (bDestination) {
|