102 * - main loop that stops if: |
102 * - main loop that stops if: |
103 * - the destination was found |
103 * - the destination was found |
104 * - or the open list is empty (no route to destination). |
104 * - or the open list is empty (no route to destination). |
105 * - or the maximum amount of loops reached - m_max_search_nodes (default = 10000) |
105 * - or the maximum amount of loops reached - m_max_search_nodes (default = 10000) |
106 * @return true if the path was found */ |
106 * @return true if the path was found */ |
107 inline bool FindPath(const Vehicle* v) |
107 inline bool FindPath(const Vehicle *v) |
108 { |
108 { |
109 m_veh = v; |
109 m_veh = v; |
110 |
110 |
|
111 #ifndef NO_DEBUG_MESSAGES |
111 CPerformanceTimer perf; |
112 CPerformanceTimer perf; |
112 perf.Start(); |
113 perf.Start(); |
|
114 #endif /* !NO_DEBUG_MESSAGES */ |
|
115 |
113 Yapf().PfSetStartupNodes(); |
116 Yapf().PfSetStartupNodes(); |
114 |
117 |
115 while (true) { |
118 while (true) { |
116 m_num_steps++; |
119 m_num_steps++; |
117 Node* n = m_nodes.GetBestOpenNode(); |
120 Node *n = m_nodes.GetBestOpenNode(); |
118 if (n == NULL) |
121 if (n == NULL) break; |
119 break; |
|
120 |
122 |
121 // if the best open node was worse than the best path found, we can finish |
123 // if the best open node was worse than the best path found, we can finish |
122 if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n->GetCostEstimate()) |
124 if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n->GetCostEstimate()) |
123 break; |
125 break; |
124 |
126 |
129 } else { |
131 } else { |
130 m_pBestDestNode = m_pBestIntermediateNode; |
132 m_pBestDestNode = m_pBestIntermediateNode; |
131 break; |
133 break; |
132 } |
134 } |
133 } |
135 } |
|
136 |
134 bool bDestFound = (m_pBestDestNode != NULL); |
137 bool bDestFound = (m_pBestDestNode != NULL); |
135 |
138 |
136 int16 veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0; |
139 #ifndef NO_DEBUG_MESSAGES |
137 |
|
138 // if (veh_idx != 433) return bDestFound; |
|
139 |
|
140 perf.Stop(); |
140 perf.Stop(); |
141 int t = perf.Get(1000000); |
|
142 _total_pf_time_us += t; |
|
143 char ttc = Yapf().TransportTypeChar(); |
|
144 #ifndef NO_DEBUG_MESSAGES |
|
145 if (_debug_yapf_level >= 3) { |
141 if (_debug_yapf_level >= 3) { |
|
142 int t = perf.Get(1000000); |
|
143 _total_pf_time_us += t; |
|
144 |
|
145 UnitID veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0; |
|
146 char ttc = Yapf().TransportTypeChar(); |
146 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); |
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); |
147 int cost = bDestFound ? m_pBestDestNode->m_cost : -1; |
148 int cost = bDestFound ? m_pBestDestNode->m_cost : -1; |
148 int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1; |
149 int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1; |
149 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) -- ", 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)); |
150 |
150 } |
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) -- ", |
151 #endif //!NO_DEBUG_MESSAGES |
152 ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), |
|
153 cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000), |
|
154 m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000) |
|
155 ); |
|
156 } |
|
157 #endif /* !NO_DEBUG_MESSAGES */ |
152 return bDestFound; |
158 return bDestFound; |
153 } |
159 } |
154 |
160 |
155 /** If path was found return the best node that has reached the destination. Otherwise |
161 /** If path was found return the best node that has reached the destination. Otherwise |
156 * return the best visited node (which was nearest to the destination). |
162 * return the best visited node (which was nearest to the destination). |