44 */ |
40 */ |
45 template <class Types> |
41 template <class Types> |
46 class CYapfBaseT { |
42 class CYapfBaseT { |
47 public: |
43 public: |
48 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) |
44 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) |
|
45 typedef typename Types::TrackFollower TrackFollower; |
49 typedef typename Types::NodeList NodeList; ///< our node list |
46 typedef typename Types::NodeList NodeList; ///< our node list |
50 typedef typename NodeList::Titem Node; ///< this will be our node type |
47 typedef typename NodeList::Titem Node; ///< this will be our node type |
51 typedef typename Node::Key Key; ///< key to hash tables |
48 typedef typename Node::Key Key; ///< key to hash tables |
52 |
49 |
53 |
50 |
133 } else { |
130 } else { |
134 m_pBestDestNode = m_pBestIntermediateNode; |
131 m_pBestDestNode = m_pBestIntermediateNode; |
135 break; |
132 break; |
136 } |
133 } |
137 } |
134 } |
138 bool bDestFound = (m_pBestDestNode != NULL); |
135 bool bDestFound = (m_pBestDestNode != NULL) && (m_pBestDestNode != m_pBestIntermediateNode); |
139 |
136 |
140 #ifndef NO_DEBUG_MESSAGES |
137 #ifndef NO_DEBUG_MESSAGES |
141 perf.Stop(); |
138 perf.Stop(); |
142 if (_debug_yapf_level >= 3) { |
139 if (_debug_yapf_level >= 3) { |
143 int t = perf.Get(1000000); |
140 int t = perf.Get(1000000); |
189 // very unlikely, but it happened |
186 // very unlikely, but it happened |
190 } |
187 } |
191 } |
188 } |
192 |
189 |
193 /** add multiple nodes - direct children of the given node */ |
190 /** add multiple nodes - direct children of the given node */ |
194 FORCEINLINE void AddMultipleNodes(Node* parent, TileIndex tile, TrackdirBits td_bits) |
191 FORCEINLINE void AddMultipleNodes(Node* parent, const TrackFollower &tf) |
195 { |
192 { |
196 bool is_choice = (KillFirstBit2x64(td_bits) != 0); |
193 bool is_choice = (KillFirstBit2x64(tf.m_new_td_bits) != 0); |
197 for (TrackdirBits rtds = td_bits; rtds != TRACKDIR_BIT_NONE; rtds = (TrackdirBits)KillFirstBit2x64(rtds)) { |
194 for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = (TrackdirBits)KillFirstBit2x64(rtds)) { |
198 Trackdir td = (Trackdir)FindFirstBit2x64(rtds); |
195 Trackdir td = (Trackdir)FindFirstBit2x64(rtds); |
199 Node& n = Yapf().CreateNewNode(); |
196 Node& n = Yapf().CreateNewNode(); |
200 n.Set(parent, tile, td, is_choice); |
197 n.Set(parent, tf.m_new_tile, td, is_choice); |
201 Yapf().AddNewNode(n); |
198 Yapf().AddNewNode(n, tf); |
202 } |
199 } |
203 } |
200 } |
204 |
201 |
205 /** AddNewNode() - called by Tderived::PfFollowNode() for each child node. |
202 /** AddNewNode() - called by Tderived::PfFollowNode() for each child node. |
206 * Nodes are evaluated here and added into open list */ |
203 * Nodes are evaluated here and added into open list */ |
207 void AddNewNode(Node& n) |
204 void AddNewNode(Node &n, const TrackFollower &tf) |
208 { |
205 { |
209 // evaluate the node |
206 // evaluate the node |
210 bool bCached = Yapf().PfNodeCacheFetch(n); |
207 bool bCached = Yapf().PfNodeCacheFetch(n); |
211 if (!bCached) { |
208 if (!bCached) { |
212 m_stats_cost_calcs++; |
209 m_stats_cost_calcs++; |
213 } else { |
210 } else { |
214 m_stats_cache_hits++; |
211 m_stats_cache_hits++; |
215 } |
212 } |
216 |
213 |
217 bool bValid = Yapf().PfCalcCost(n); |
214 bool bValid = Yapf().PfCalcCost(n, tf); |
218 |
215 |
219 if (bCached) { |
216 if (bCached) { |
220 Yapf().PfNodeCacheFlush(n); |
217 Yapf().PfNodeCacheFlush(n); |
221 } |
218 } |
222 |
219 |