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