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