author | KUDr |
Sat, 21 Apr 2007 08:23:57 +0000 | |
branch | cpp_gui |
changeset 6308 | 646711c5feaa |
parent 6268 | 4b5241e5dd10 |
permissions | -rw-r--r-- |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
1 |
/* $Id$ */ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
2 |
|
6268
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
3 |
/** @file yapf_base.hpp */ |
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
4 |
|
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
5 |
#ifndef YAPF_BASE_HPP |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
6 |
#define YAPF_BASE_HPP |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
7 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
8 |
#include "../debug.h" |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
9 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
10 |
extern int _total_pf_time_us; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
11 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
12 |
/** CYapfBaseT - A-star type path finder base class. |
4549
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
13 |
* Derive your own pathfinder from it. You must provide the following template argument: |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
14 |
* Types - used as collection of local types used in pathfinder |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
15 |
* |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
16 |
* Requirements for the Types struct: |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
17 |
* ---------------------------------- |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
18 |
* The following types must be defined in the 'Types' argument: |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
19 |
* - Types::Tpf - your pathfinder derived from CYapfBaseT |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
20 |
* - Types::NodeList - open/closed node list (look at CNodeList_HashTableT) |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
21 |
* NodeList needs to have defined local type Titem - defines the pathfinder node type. |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
22 |
* Node needs to define local type Key - the node key in the collection () |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
23 |
* |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
24 |
* For node list you can use template class CNodeList_HashTableT, for which |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
25 |
* you need to declare only your node type. Look at test_yapf.h for an example. |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
26 |
* |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
27 |
* |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
28 |
* Requrements to your pathfinder class derived from CYapfBaseT: |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
29 |
* ------------------------------------------------------------- |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
30 |
* Your pathfinder derived class needs to implement following methods: |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
31 |
* FORCEINLINE void PfSetStartupNodes() |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
32 |
* FORCEINLINE void PfFollowNode(Node& org) |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
33 |
* FORCEINLINE bool PfCalcCost(Node& n) |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
34 |
* FORCEINLINE bool PfCalcEstimate(Node& n) |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
35 |
* FORCEINLINE bool PfDetectDestination(Node& n) |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
36 |
* |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
37 |
* For more details about those methods, look at the end of CYapfBaseT |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
38 |
* declaration. There are some examples. For another example look at |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
39 |
* test_yapf.h (part or unittest project). |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
40 |
*/ |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
41 |
template <class Types> |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
42 |
class CYapfBaseT { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
43 |
public: |
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
44 |
typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) |
6268
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
45 |
typedef typename Types::TrackFollower TrackFollower; |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
46 |
typedef typename Types::NodeList NodeList; ///< our node list |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
47 |
typedef typename NodeList::Titem Node; ///< this will be our node type |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
48 |
typedef typename Node::Key Key; ///< key to hash tables |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
49 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
50 |
|
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
51 |
NodeList m_nodes; ///< node list multi-container |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
52 |
protected: |
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
53 |
Node* m_pBestDestNode; ///< pointer to the destination node found at last round |
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
54 |
Node* m_pBestIntermediateNode; ///< here should be node closest to the destination if path not found |
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
55 |
const YapfSettings *m_settings; ///< current settings (_patches.yapf) |
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
56 |
int m_max_search_nodes; ///< maximum number of nodes we are allowed to visit before we give up |
3915
281c7ebd27e0
(svn r5033) -CodeChange: [YAPF] RoadFindPathToStop() can now use YAPF for multistop handling.
KUDr
parents:
3914
diff
changeset
|
57 |
const Vehicle* m_veh; ///< vehicle that we are trying to drive |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
58 |
|
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
59 |
int m_stats_cost_calcs; ///< stats - how many node's costs were calculated |
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
60 |
int m_stats_cache_hits; ///< stats - how many node's costs were reused from cache |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
61 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
62 |
public: |
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
63 |
CPerformanceTimer m_perf_cost; ///< stats - total CPU time of this run |
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
64 |
CPerformanceTimer m_perf_slope_cost; ///< stats - slope calculation CPU time |
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
65 |
CPerformanceTimer m_perf_ts_cost; ///< stats - GetTrackStatus() CPU time |
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
66 |
CPerformanceTimer m_perf_other_cost; ///< stats - other CPU time |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
67 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
68 |
public: |
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
69 |
int m_num_steps; ///< this is there for debugging purposes (hope it doesn't hurt) |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
70 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
71 |
public: |
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
72 |
/// default constructor |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
73 |
FORCEINLINE CYapfBaseT() |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
74 |
: m_pBestDestNode(NULL) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
75 |
, m_pBestIntermediateNode(NULL) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
76 |
, m_settings(&_patches.yapf) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
77 |
, m_max_search_nodes(PfGetSettings().max_search_nodes) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
78 |
, m_veh(NULL) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
79 |
, m_stats_cost_calcs(0) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
80 |
, m_stats_cache_hits(0) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
81 |
, m_num_steps(0) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
82 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
83 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
84 |
|
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
85 |
/// default destructor |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
86 |
~CYapfBaseT() {} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
87 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
88 |
protected: |
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
89 |
/// to access inherited path finder |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
90 |
FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
91 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
92 |
public: |
3914
f5118020cd84
(svn r5018) [YAPF] Added some comments to YAPF implementation.
KUDr
parents:
3900
diff
changeset
|
93 |
/// return current settings (can be custom - player based - but later) |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
94 |
FORCEINLINE const YapfSettings& PfGetSettings() const |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
95 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
96 |
return *m_settings; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
97 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
98 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
99 |
/** Main pathfinder routine: |
4549
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
100 |
* - set startup node(s) |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
101 |
* - main loop that stops if: |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
102 |
* - the destination was found |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
103 |
* - or the open list is empty (no route to destination). |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
104 |
* - or the maximum amount of loops reached - m_max_search_nodes (default = 10000) |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
105 |
* @return true if the path was found */ |
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
106 |
inline bool FindPath(const Vehicle *v) |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
107 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
108 |
m_veh = v; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
109 |
|
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
110 |
#ifndef NO_DEBUG_MESSAGES |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
111 |
CPerformanceTimer perf; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
112 |
perf.Start(); |
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
113 |
#endif /* !NO_DEBUG_MESSAGES */ |
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
114 |
|
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
115 |
Yapf().PfSetStartupNodes(); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
116 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
117 |
while (true) { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
118 |
m_num_steps++; |
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
119 |
Node *n = m_nodes.GetBestOpenNode(); |
6308 | 120 |
if (n == NULL) |
121 |
break; |
|
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
122 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
123 |
// if the best open node was worse than the best path found, we can finish |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
124 |
if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n->GetCostEstimate()) |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
125 |
break; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
126 |
|
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
127 |
Yapf().PfFollowNode(*n); |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
128 |
if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) { |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
129 |
m_nodes.PopOpenNode(n->GetKey()); |
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
130 |
m_nodes.InsertClosedNode(*n); |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
131 |
} else { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
132 |
m_pBestDestNode = m_pBestIntermediateNode; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
133 |
break; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
134 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
135 |
} |
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
136 |
|
6268
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
137 |
bool bDestFound = (m_pBestDestNode != NULL) && (m_pBestDestNode != m_pBestIntermediateNode); |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
138 |
|
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
139 |
#ifndef NO_DEBUG_MESSAGES |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
140 |
perf.Stop(); |
5871
52a265080dab
(svn r8079) -Fix [YAPF]: float division by zero when calculating stats (YAPF cache hit ratio). Caused BSOD on Win9x. (thanks 3iff for report, Darkvater for help)
KUDr
parents:
5838
diff
changeset
|
141 |
if (_debug_yapf_level >= 3) { |
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
142 |
int t = perf.Get(1000000); |
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
143 |
_total_pf_time_us += t; |
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
144 |
|
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
145 |
UnitID veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0; |
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
146 |
char ttc = Yapf().TransportTypeChar(); |
5871
52a265080dab
(svn r8079) -Fix [YAPF]: float division by zero when calculating stats (YAPF cache hit ratio). Caused BSOD on Win9x. (thanks 3iff for report, Darkvater for help)
KUDr
parents:
5838
diff
changeset
|
147 |
float cache_hit_ratio = (m_stats_cache_hits == 0) ? 0.0f : ((float)m_stats_cache_hits / (float)(m_stats_cache_hits + m_stats_cost_calcs) * 100.0f); |
52a265080dab
(svn r8079) -Fix [YAPF]: float division by zero when calculating stats (YAPF cache hit ratio). Caused BSOD on Win9x. (thanks 3iff for report, Darkvater for help)
KUDr
parents:
5838
diff
changeset
|
148 |
int cost = bDestFound ? m_pBestDestNode->m_cost : -1; |
52a265080dab
(svn r8079) -Fix [YAPF]: float division by zero when calculating stats (YAPF cache hit ratio). Caused BSOD on Win9x. (thanks 3iff for report, Darkvater for help)
KUDr
parents:
5838
diff
changeset
|
149 |
int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1; |
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
150 |
|
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
151 |
DEBUG(yapf, 3, "[YAPF%c]%c%4d- %d us - %d rounds - %d open - %d closed - CHR %4.1f%% - c%d(sc%d, ts%d, o%d) -- ", |
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
152 |
ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), |
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
153 |
cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000), |
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
154 |
m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000) |
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
155 |
); |
5871
52a265080dab
(svn r8079) -Fix [YAPF]: float division by zero when calculating stats (YAPF cache hit ratio). Caused BSOD on Win9x. (thanks 3iff for report, Darkvater for help)
KUDr
parents:
5838
diff
changeset
|
156 |
} |
5872
fbd56d2f8149
(svn r8080) -Codechange (r8079): Move the *WHOLE* performance code into the #ifndef and some style changes.
Darkvater
parents:
5871
diff
changeset
|
157 |
#endif /* !NO_DEBUG_MESSAGES */ |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
158 |
return bDestFound; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
159 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
160 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
161 |
/** If path was found return the best node that has reached the destination. Otherwise |
4549
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
162 |
* return the best visited node (which was nearest to the destination). |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
163 |
*/ |
6308 | 164 |
FORCEINLINE Node* GetBestNode() |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
165 |
{ |
6308 | 166 |
return (m_pBestDestNode != NULL) ? m_pBestDestNode : m_pBestIntermediateNode; |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
167 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
168 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
169 |
/** Calls NodeList::CreateNewNode() - allocates new node that can be filled and used |
4549
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
170 |
* as argument for AddStartupNode() or AddNewNode() |
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
171 |
*/ |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
172 |
FORCEINLINE Node& CreateNewNode() |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
173 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
174 |
Node& node = *m_nodes.CreateNewNode(); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
175 |
return node; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
176 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
177 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
178 |
/** Add new node (created by CreateNewNode and filled with data) into open list */ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
179 |
FORCEINLINE void AddStartupNode(Node& n) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
180 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
181 |
Yapf().PfNodeCacheFetch(n); |
4413
91cbf110f0d9
(svn r6166) -Fix: [YAPF] fixes one very improbable assert when adding startup node that already exists in the open-list (thanks Panzerfather)
KUDr
parents:
3978
diff
changeset
|
182 |
// insert the new node only if it is not there |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
183 |
if (m_nodes.FindOpenNode(n.m_key) == NULL) { |
4413
91cbf110f0d9
(svn r6166) -Fix: [YAPF] fixes one very improbable assert when adding startup node that already exists in the open-list (thanks Panzerfather)
KUDr
parents:
3978
diff
changeset
|
184 |
m_nodes.InsertOpenNode(n); |
91cbf110f0d9
(svn r6166) -Fix: [YAPF] fixes one very improbable assert when adding startup node that already exists in the open-list (thanks Panzerfather)
KUDr
parents:
3978
diff
changeset
|
185 |
} else { |
91cbf110f0d9
(svn r6166) -Fix: [YAPF] fixes one very improbable assert when adding startup node that already exists in the open-list (thanks Panzerfather)
KUDr
parents:
3978
diff
changeset
|
186 |
// if we are here, it means that node is already there - how it is possible? |
91cbf110f0d9
(svn r6166) -Fix: [YAPF] fixes one very improbable assert when adding startup node that already exists in the open-list (thanks Panzerfather)
KUDr
parents:
3978
diff
changeset
|
187 |
// probably the train is in the position that both its ends point to the same tile/exit-dir |
91cbf110f0d9
(svn r6166) -Fix: [YAPF] fixes one very improbable assert when adding startup node that already exists in the open-list (thanks Panzerfather)
KUDr
parents:
3978
diff
changeset
|
188 |
// very unlikely, but it happened |
91cbf110f0d9
(svn r6166) -Fix: [YAPF] fixes one very improbable assert when adding startup node that already exists in the open-list (thanks Panzerfather)
KUDr
parents:
3978
diff
changeset
|
189 |
} |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
190 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
191 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
192 |
/** add multiple nodes - direct children of the given node */ |
6268
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
193 |
FORCEINLINE void AddMultipleNodes(Node* parent, const TrackFollower &tf) |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
194 |
{ |
6268
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
195 |
bool is_choice = (KillFirstBit2x64(tf.m_new_td_bits) != 0); |
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
196 |
for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = (TrackdirBits)KillFirstBit2x64(rtds)) { |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
197 |
Trackdir td = (Trackdir)FindFirstBit2x64(rtds); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
198 |
Node& n = Yapf().CreateNewNode(); |
6268
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
199 |
n.Set(parent, tf.m_new_tile, td, is_choice); |
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
200 |
Yapf().AddNewNode(n, tf); |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
201 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
202 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
203 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
204 |
/** AddNewNode() - called by Tderived::PfFollowNode() for each child node. |
4549
60410aa1aa88
(svn r6381) -Cleanup: make the '/* */' comments that span multiple lines more uniform.
rubidium
parents:
4413
diff
changeset
|
205 |
* Nodes are evaluated here and added into open list */ |
6268
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
206 |
void AddNewNode(Node &n, const TrackFollower &tf) |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
207 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
208 |
// evaluate the node |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
209 |
bool bCached = Yapf().PfNodeCacheFetch(n); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
210 |
if (!bCached) { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
211 |
m_stats_cost_calcs++; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
212 |
} else { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
213 |
m_stats_cache_hits++; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
214 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
215 |
|
6268
4b5241e5dd10
(svn r8938) [cpp_gui] -Sync with trunk (r8772..r8900)
bjarni
parents:
5884
diff
changeset
|
216 |
bool bValid = Yapf().PfCalcCost(n, tf); |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
217 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
218 |
if (bCached) { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
219 |
Yapf().PfNodeCacheFlush(n); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
220 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
221 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
222 |
if (bValid) bValid = Yapf().PfCalcEstimate(n); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
223 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
224 |
// have the cost or estimate callbacks marked this node as invalid? |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
225 |
if (!bValid) return; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
226 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
227 |
// detect the destination |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
228 |
bool bDestination = Yapf().PfDetectDestination(n); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
229 |
if (bDestination) { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
230 |
if (m_pBestDestNode == NULL || n < *m_pBestDestNode) { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
231 |
m_pBestDestNode = &n; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
232 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
233 |
m_nodes.FoundBestNode(n); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
234 |
return; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
235 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
236 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
237 |
if (m_max_search_nodes > 0 && (m_pBestIntermediateNode == NULL || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()))) { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
238 |
m_pBestIntermediateNode = &n; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
239 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
240 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
241 |
// check new node against open list |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
242 |
Node* openNode = m_nodes.FindOpenNode(n.GetKey()); |
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
243 |
if (openNode != NULL) { |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
244 |
// another node exists with the same key in the open list |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
245 |
// is it better than new one? |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
246 |
if (n.GetCostEstimate() < openNode->GetCostEstimate()) { |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
247 |
// update the old node by value from new one |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
248 |
m_nodes.PopOpenNode(n.GetKey()); |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
249 |
*openNode = n; |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
250 |
// add the updated old node back to open list |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
251 |
m_nodes.InsertOpenNode(*openNode); |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
252 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
253 |
return; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
254 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
255 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
256 |
// check new node against closed list |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
257 |
Node* closedNode = m_nodes.FindClosedNode(n.GetKey()); |
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
258 |
if (closedNode != NULL) { |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
259 |
// another node exists with the same key in the closed list |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
260 |
// is it better than new one? |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
261 |
int node_est = n.GetCostEstimate(); |
5083
6da97b6fbbd6
(svn r7147) -CodeChange: Don't use references if they can refer to NULL (Tron)
KUDr
parents:
4563
diff
changeset
|
262 |
int closed_est = closedNode->GetCostEstimate(); |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
263 |
if (node_est < closed_est) { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
264 |
// If this assert occurs, you have probably problem in |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
265 |
// your Tderived::PfCalcCost() or Tderived::PfCalcEstimate(). |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
266 |
// The problem could be: |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
267 |
// - PfCalcEstimate() gives too large numbers |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
268 |
// - PfCalcCost() gives too small numbers |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
269 |
// - You have used negative cost penalty in some cases (cost bonus) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
270 |
assert(0); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
271 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
272 |
return; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
273 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
274 |
return; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
275 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
276 |
// the new node is really new |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
277 |
// add it to the open list |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
278 |
m_nodes.InsertOpenNode(n); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
279 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
280 |
|
3915
281c7ebd27e0
(svn r5033) -CodeChange: [YAPF] RoadFindPathToStop() can now use YAPF for multistop handling.
KUDr
parents:
3914
diff
changeset
|
281 |
const Vehicle* GetVehicle() const {return m_veh;} |
3900
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
282 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
283 |
// methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
284 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
285 |
#if 0 |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
286 |
/** Example: PfSetStartupNodes() - set source (origin) nodes */ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
287 |
FORCEINLINE void PfSetStartupNodes() |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
288 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
289 |
// example: |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
290 |
Node& n1 = *base::m_nodes.CreateNewNode(); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
291 |
. |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
292 |
. // setup node members here |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
293 |
. |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
294 |
base::m_nodes.InsertOpenNode(n1); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
295 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
296 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
297 |
/** Example: PfFollowNode() - set following (child) nodes of the given node */ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
298 |
FORCEINLINE void PfFollowNode(Node& org) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
299 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
300 |
for (each follower of node org) { |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
301 |
Node& n = *base::m_nodes.CreateNewNode(); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
302 |
. |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
303 |
. // setup node members here |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
304 |
. |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
305 |
n.m_parent = &org; // set node's parent to allow back tracking |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
306 |
AddNewNode(n); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
307 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
308 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
309 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
310 |
/** Example: PfCalcCost() - set path cost from origin to the given node */ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
311 |
FORCEINLINE bool PfCalcCost(Node& n) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
312 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
313 |
// evaluate last step cost |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
314 |
int cost = ...; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
315 |
// set the node cost as sum of parent's cost and last step cost |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
316 |
n.m_cost = n.m_parent->m_cost + cost; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
317 |
return true; // true if node is valid follower (i.e. no obstacle was found) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
318 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
319 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
320 |
/** Example: PfCalcEstimate() - set path cost estimate from origin to the target through given node */ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
321 |
FORCEINLINE bool PfCalcEstimate(Node& n) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
322 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
323 |
// evaluate the distance to our destination |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
324 |
int distance = ...; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
325 |
// set estimate as sum of cost from origin + distance to the target |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
326 |
n.m_estimate = n.m_cost + distance; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
327 |
return true; // true if node is valid (i.e. not too far away :) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
328 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
329 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
330 |
/** Example: PfDetectDestination() - return true if the given node is our destination */ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
331 |
FORCEINLINE bool PfDetectDestination(Node& n) |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
332 |
{ |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
333 |
bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2); |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
334 |
return bDest; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
335 |
} |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
336 |
#endif |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
337 |
}; |
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
338 |
|
4984308f9125
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
diff
changeset
|
339 |
#endif /* YAPF_BASE_HPP */ |