187 |
187 |
188 TileIndex tile = n.m_key.m_tile; |
188 TileIndex tile = n.m_key.m_tile; |
189 Trackdir trackdir = n.m_key.m_td; |
189 Trackdir trackdir = n.m_key.m_td; |
190 TileType tile_type = GetTileType(tile); |
190 TileType tile_type = GetTileType(tile); |
191 |
191 |
|
192 DEBUG(yapf, 3, "PfCalcCost(Node:tile=%04X td=%s; Parent:tile=%04X td=%s)", tile, GetTrackdirName(trackdir), prev_tile, GetTrackdirName(prev_trackdir)); |
|
193 |
192 RailType rail_type = GetTileRailType(tile, trackdir); |
194 RailType rail_type = GetTileRailType(tile, trackdir); |
193 |
195 |
194 // detect exit from bridge wormhole |
196 // detect exit from bridge wormhole |
|
197 Trackdir intermediate_trackdir = INVALID_TRACKDIR; |
195 if (IsBridgeTile(tile) && TrackdirToExitdir(ReverseTrackdir(trackdir)) == GetBridgeRampDirection(tile)) { |
198 if (IsBridgeTile(tile) && TrackdirToExitdir(ReverseTrackdir(trackdir)) == GetBridgeRampDirection(tile)) { |
196 // we are jumping over bridge (possible now with custom bridge heads) we must add the cost of skipped tiles |
199 // we are jumping over bridge (possible now with custom bridge heads) we must add the cost of skipped tiles |
197 segment_cost += (DistanceManhattan(prev_tile, tile) - 1) * YAPF_TILE_LENGTH; |
200 int skipped_tiles = DistanceManhattan(prev_tile, tile) - 1; |
|
201 if (skipped_tiles > 0) { |
|
202 segment_cost += skipped_tiles * YAPF_TILE_LENGTH; |
|
203 DEBUG(yapf, 6, " Cost: skipped=%d", skipped_tiles * YAPF_TILE_LENGTH); |
|
204 intermediate_trackdir = DiagdirToDiagTrackdir(ReverseDiagDir(GetBridgeRampDirection(tile))); |
|
205 } |
198 } |
206 } |
199 |
207 |
200 bool target_seen = Yapf().PfDetectDestination(tile, trackdir); |
208 bool target_seen = Yapf().PfDetectDestination(tile, trackdir); |
201 |
209 |
202 while (true) { |
210 while (true) { |
203 segment_cost += Yapf().OneTileCost(tile, trackdir); |
211 int tile_cost = Yapf().OneTileCost(tile, trackdir); |
204 segment_cost += Yapf().CurveCost(prev_trackdir, trackdir); |
212 int curve_cost; |
205 segment_cost += Yapf().SlopeCost(tile, trackdir); |
213 if (intermediate_trackdir == INVALID_TRACKDIR) { |
206 segment_cost += Yapf().SignalCost(n, tile, trackdir); |
214 curve_cost = Yapf().CurveCost(prev_trackdir, trackdir); |
|
215 } else { |
|
216 curve_cost = Yapf().CurveCost(prev_trackdir, intermediate_trackdir) + Yapf().CurveCost(intermediate_trackdir, trackdir); |
|
217 intermediate_trackdir = INVALID_TRACKDIR; |
|
218 } |
|
219 int slope_cost = Yapf().SlopeCost(tile, trackdir); |
|
220 int signal_cost = Yapf().SignalCost(n, tile, trackdir); |
|
221 DEBUG(yapf, 6, " Cost: tile=%d, curve=%d, slope=%d, signal=%d", tile_cost, curve_cost, slope_cost, signal_cost); |
|
222 segment_cost += tile_cost + curve_cost + slope_cost + signal_cost; |
207 if (n.m_segment->flags_u.flags_s.m_end_of_line) { |
223 if (n.m_segment->flags_u.flags_s.m_end_of_line) { |
|
224 DEBUG(yapf, 4, " end: EOL (signal)"); |
208 break; |
225 break; |
209 } |
226 } |
210 |
227 |
211 // finish if we have reached the destination |
228 // finish if we have reached the destination |
212 if (target_seen) { |
229 if (target_seen) { |
|
230 DEBUG(yapf, 4, " end: target_seen"); |
213 break; |
231 break; |
214 } |
232 } |
215 |
233 |
216 // finish on first station tile - segment should end here to avoid target skipping |
234 // finish on first station tile - segment should end here to avoid target skipping |
217 // when cached segments are used |
235 // when cached segments are used |
218 if (tile_type == MP_STATION && prev_tile_type != MP_STATION) { |
236 if (tile_type == MP_STATION && prev_tile_type != MP_STATION) { |
|
237 DEBUG(yapf, 4, " end: first station tile"); |
219 break; |
238 break; |
220 } |
239 } |
221 |
240 |
222 // finish also on waypoint - same workaround as for first station tile |
241 // finish also on waypoint - same workaround as for first station tile |
223 if (tile_type == MP_RAILWAY && IsRailWaypoint(tile)) { |
242 if (tile_type == MP_RAILWAY && IsRailWaypoint(tile)) { |
|
243 DEBUG(yapf, 4, " end: waypoint"); |
224 break; |
244 break; |
225 } |
245 } |
226 |
246 |
227 // if there are no reachable trackdirs on the next tile, we have end of road |
247 // if there are no reachable trackdirs on the next tile, we have end of road |
228 TrackFollower F(v, &Yapf().m_perf_ts_cost); |
248 TrackFollower F(v, &Yapf().m_perf_ts_cost); |
229 if (!F.Follow(tile, trackdir)) { |
249 if (!F.Follow(tile, trackdir)) { |
230 // we can't continue? |
250 // we can't continue? |
231 // n.m_segment->flags_u.flags_s.m_end_of_line = true; |
251 // n.m_segment->flags_u.flags_s.m_end_of_line = true; |
232 break; |
252 DEBUG(yapf, 4, " end: can't foolow (dead end?)"); |
233 } |
253 break; |
|
254 } |
|
255 if (F.m_is_bridge && F.m_tiles_skipped > 0) intermediate_trackdir = F.m_intermediate_trackdir; |
|
256 DEBUG(yapf, 4, " next: tile=%04X td=%s", F.m_new_tile, GetTrackdirBitsName(F.m_new_td_bits).Data()); |
234 |
257 |
235 // if there are more trackdirs available & reachable, we are at the end of segment |
258 // if there are more trackdirs available & reachable, we are at the end of segment |
236 if (KillFirstBit2x64(F.m_new_td_bits) != 0) { |
259 if (KillFirstBit2x64(F.m_new_td_bits) != 0) { |
|
260 DEBUG(yapf, 4, " end: choice"); |
237 break; |
261 break; |
238 } |
262 } |
239 |
263 |
240 Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits); |
264 Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits); |
241 |
265 |
242 { |
266 { |
243 // end segment if train is about to enter simple loop with no junctions |
267 // end segment if train is about to enter simple loop with no junctions |
244 // so next time it should stop on the next if |
268 // so next time it should stop on the next if |
245 if (segment_cost > s_max_segment_cost && IsTileType(F.m_new_tile, MP_RAILWAY)) |
269 if (segment_cost > s_max_segment_cost && IsTileType(F.m_new_tile, MP_RAILWAY)) { |
246 break; |
270 DEBUG(yapf, 4, " end: loop fuse"); |
|
271 break; |
|
272 } |
247 |
273 |
248 // stop if train is on simple loop with no junctions |
274 // stop if train is on simple loop with no junctions |
249 if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) |
275 if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) { |
|
276 DEBUG(yapf, 4, " end: loop detected"); |
250 return false; |
277 return false; |
251 } |
278 } |
252 |
279 } |
253 // if tail type changes, finish segment (cached segment can't contain more rail types) |
280 |
|
281 // if rail type changes, finish segment (cached segment can't contain more rail types) |
254 { |
282 { |
255 RailType new_rail_type = GetTileRailType(F.m_new_tile, (Trackdir)FindFirstBit2x64(F.m_new_td_bits)); |
283 RailType new_rail_type = GetTileRailType(F.m_new_tile, (Trackdir)FindFirstBit2x64(F.m_new_td_bits)); |
256 if (new_rail_type != rail_type) { |
284 if (new_rail_type != rail_type) { |
|
285 DEBUG(yapf, 4, " end: rail type changes"); |
257 break; |
286 break; |
258 } |
287 } |
259 rail_type = new_rail_type; |
288 rail_type = new_rail_type; |
260 } |
289 } |
261 |
290 |
270 |
299 |
271 target_seen = Yapf().PfDetectDestination(tile, trackdir); |
300 target_seen = Yapf().PfDetectDestination(tile, trackdir); |
272 |
301 |
273 // reversing in depot penalty |
302 // reversing in depot penalty |
274 if (tile == prev_tile) { |
303 if (tile == prev_tile) { |
275 segment_cost += Yapf().PfGetSettings().rail_depot_reverse_penalty; |
304 int reverse_in_depot_cost = Yapf().PfGetSettings().rail_depot_reverse_penalty; |
|
305 segment_cost += reverse_in_depot_cost; |
|
306 DEBUG(yapf, 4, " end: reversing in depot (cost=%d)", reverse_in_depot_cost); |
276 break; |
307 break; |
277 } |
308 } |
278 |
309 |
279 // if we skipped some tunnel tiles, add their cost |
310 // if we skipped some tunnel tiles, add their cost |
280 segment_cost += YAPF_TILE_LENGTH * F.m_tiles_skipped; |
311 segment_cost += YAPF_TILE_LENGTH * F.m_tiles_skipped; |
|
312 DEBUG(yapf, 6, " Cost: wormhole=%d", YAPF_TILE_LENGTH * F.m_tiles_skipped); |
281 |
313 |
282 // add penalty for skipped station tiles |
314 // add penalty for skipped station tiles |
283 if (F.m_is_station) |
315 if (F.m_is_station) |
284 { |
316 { |
285 if (target_seen) { |
317 if (target_seen) { |
286 // it is our destination station |
318 // it is our destination station |
287 uint platform_length = F.m_tiles_skipped + 1; |
319 uint platform_length = F.m_tiles_skipped + 1; |
288 segment_cost += PlatformLengthPenalty(platform_length); |
320 int platform_length_cost = PlatformLengthPenalty(platform_length); |
|
321 segment_cost += platform_length_cost; |
|
322 DEBUG(yapf, 6, " Cost: platform=%d", platform_length_cost); |
289 } else { |
323 } else { |
290 // station is not our destination station, apply penalty for skipped platform tiles |
324 // station is not our destination station, apply penalty for skipped platform tiles |
291 segment_cost += Yapf().PfGetSettings().rail_station_penalty * F.m_tiles_skipped; |
325 int station_cost = Yapf().PfGetSettings().rail_station_penalty * F.m_tiles_skipped; |
|
326 segment_cost += station_cost; |
|
327 DEBUG(yapf, 6, " Cost: station=%d", station_cost); |
292 } |
328 } |
293 } |
329 } |
294 |
330 |
295 // add min/max speed penalties |
331 // add min/max speed penalties |
296 int min_speed = 0; |
332 int min_speed = 0; |
300 if (min_speed > v->max_speed) |
336 if (min_speed > v->max_speed) |
301 segment_cost += YAPF_TILE_LENGTH * (min_speed - v->max_speed); |
337 segment_cost += YAPF_TILE_LENGTH * (min_speed - v->max_speed); |
302 |
338 |
303 // finish if we already exceeded the maximum cost |
339 // finish if we already exceeded the maximum cost |
304 if (m_max_cost > 0 && (parent_cost + first_tile_cost + segment_cost) > m_max_cost) { |
340 if (m_max_cost > 0 && (parent_cost + first_tile_cost + segment_cost) > m_max_cost) { |
|
341 DEBUG(yapf, 4, " abort: maximum cost reached"); |
305 return false; |
342 return false; |
306 } |
343 } |
307 |
344 |
308 if (first_tile_cost == 0) { |
345 if (first_tile_cost == 0) { |
309 // we just have done first tile |
346 // we just have done first tile |
310 first_tile_cost = segment_cost; |
347 first_tile_cost = segment_cost; |
311 segment_cost = 0; |
348 segment_cost = 0; |
|
349 DEBUG(yapf, 5, " TotalCost: first_tile=%d", first_tile_cost); |
312 |
350 |
313 // look if we can reuse existing (cached) segment cost |
351 // look if we can reuse existing (cached) segment cost |
314 if (n.m_segment->m_cost >= 0) { |
352 if (n.m_segment->m_cost >= 0) { |
315 // reuse the cached segment cost |
353 // reuse the cached segment cost |
|
354 DEBUG(yapf, 4, " end: reusing the cached segment cost"); |
316 break; |
355 break; |
317 } |
356 } |
318 } |
357 } |
319 // segment cost was not filled yes, we have not cached it yet |
358 // segment cost was not filled yes, we have not cached it yet |
320 n.SetLastTileTrackdir(tile, trackdir); |
359 n.SetLastTileTrackdir(tile, trackdir); |