168 } |
203 } |
169 |
204 |
170 public: |
205 public: |
171 FORCEINLINE void SetMaxCost(int max_cost) {m_max_cost = max_cost;} |
206 FORCEINLINE void SetMaxCost(int max_cost) {m_max_cost = max_cost;} |
172 |
207 |
|
208 |
|
209 |
173 /** Called by YAPF to calculate the cost from the origin to the given node. |
210 /** Called by YAPF to calculate the cost from the origin to the given node. |
174 * Calculates only the cost of given node, adds it to the parent node cost |
211 * Calculates only the cost of given node, adds it to the parent node cost |
175 * and stores the result into Node::m_cost member */ |
212 * and stores the result into Node::m_cost member */ |
176 FORCEINLINE bool PfCalcCost(Node &n, const TrackFollower &tf) |
213 FORCEINLINE bool PfCalcCost(Node &n, const TrackFollower *tf) |
177 { |
214 { |
178 assert(!n.flags_u.flags_s.m_targed_seen); |
215 assert(!n.flags_u.flags_s.m_targed_seen); |
|
216 assert(tf->m_new_tile == n.m_key.m_tile); |
|
217 assert((TrackdirToTrackdirBits(n.m_key.m_td) & tf->m_new_td_bits) != TRACKDIR_BIT_NONE); |
|
218 |
179 CPerfStart perf_cost(Yapf().m_perf_cost); |
219 CPerfStart perf_cost(Yapf().m_perf_cost); |
180 int parent_cost = (n.m_parent != NULL) ? n.m_parent->m_cost : 0; |
220 |
181 int first_tile_cost = 0; |
221 /* Does the node have some parent node? */ |
|
222 bool has_parent = (n.m_parent != NULL); |
|
223 |
|
224 /* Do we already have a cached segment? */ |
|
225 CachedData &segment = *n.m_segment; |
|
226 bool is_cached_segment = (segment.m_cost >= 0); |
|
227 |
|
228 int parent_cost = has_parent ? n.m_parent->m_cost : 0; |
|
229 |
|
230 /* Each node cost contains 2 or 3 main components: |
|
231 * 1. Transition cost - cost of the move from previous node (tile): |
|
232 * - curve cost (or zero for straight move) |
|
233 * 2. Tile cost: |
|
234 * - base tile cost |
|
235 * - YAPF_TILE_LENGTH for diagonal tiles |
|
236 * - YAPF_TILE_CORNER_LENGTH for non-diagonal tiles |
|
237 * - tile penalties |
|
238 * - tile slope penalty (upward slopes) |
|
239 * - red signal penalty |
|
240 * - level crossing penalty |
|
241 * - speed-limit penalty (bridges) |
|
242 * - station platform penalty |
|
243 * - penalty for reversing in the depot |
|
244 * - etc. |
|
245 * 3. Extra cost (applies to the last node only) |
|
246 * - last red signal penalty |
|
247 * - penalty for too long or too short platform on the destination station |
|
248 */ |
|
249 int transition_cost = 0; |
|
250 int tile_cost = 0; |
|
251 int extra_cost = 0; |
|
252 |
|
253 /* Segment: one or more tiles connected by contiguous tracks of the same type. |
|
254 * Each segment cost includes 'Tile cost' for all its tiles (including the first |
|
255 * and last), and the 'Transition cost' between its tiles. The first transition |
|
256 * cost of segment entry (move from the 'parent' node) is not included! |
|
257 */ |
|
258 int segment_entry_cost = 0; |
182 int segment_cost = 0; |
259 int segment_cost = 0; |
183 int extra_cost = 0; |
260 |
184 const Vehicle* v = Yapf().GetVehicle(); |
261 const Vehicle* v = Yapf().GetVehicle(); |
185 |
262 |
186 // start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment |
263 // start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment |
187 TileIndex prev_tile = (n.m_parent != NULL) ? n.m_parent->GetLastTile() : INVALID_TILE; |
264 TILE cur(n.m_key.m_tile, n.m_key.m_td); |
188 Trackdir prev_trackdir = (n.m_parent != NULL) ? n.m_parent->GetLastTrackdir() : INVALID_TRACKDIR; |
265 |
189 TileType prev_tile_type = (n.m_parent != NULL) ? GetTileType(n.m_parent->GetLastTile()) : MP_VOID; |
266 // the previous tile will be needed for transition cost calculations |
190 |
267 TILE prev = has_parent ? TILE() : TILE(n.m_parent->GetLastTile(), n.m_parent->GetLastTrackdir()); |
191 TileIndex tile = n.m_key.m_tile; |
268 |
192 Trackdir trackdir = n.m_key.m_td; |
269 EndSegmentReasonBits end_segment_reason = ESRB_NONE; |
193 TileType tile_type = GetTileType(tile); |
270 |
194 |
271 TrackFollower tf_local(v, &Yapf().m_perf_ts_cost); |
195 RailType rail_type = GetTileRailType(tile); |
272 |
196 |
273 if (!has_parent) { |
197 bool target_seen = Yapf().PfDetectDestination(tile, trackdir); |
274 /* We will jump to the middle of the cost calculator assuming that segment cache is not used. */ |
198 bool end_by_target_seen = false; |
275 assert(!is_cached_segment); |
199 |
276 /* Skip the first transition cost calculation. */ |
200 if (tf.m_is_station) { |
277 goto no_entry_cost; |
201 // station tiles have an extra penalty |
278 } |
202 segment_cost += Yapf().PfGetSettings().rail_station_penalty * (tf.m_tiles_skipped + 1); |
279 |
203 } |
280 for (;;) { |
204 |
281 /* Transition cost (cost of the move from previous tile) */ |
205 while (true) { |
282 transition_cost = Yapf().CurveCost(prev.td, cur.td); |
206 segment_cost += Yapf().OneTileCost(prev_tile, tile, trackdir); |
283 |
207 segment_cost += Yapf().CurveCost(prev_trackdir, trackdir); |
284 /* First transition cost counts against segment entry cost, other transitions |
208 segment_cost += Yapf().SlopeCost(tile, trackdir); |
285 * inside segment will come to segment cost (and will be cached) */ |
209 segment_cost += Yapf().SignalCost(n, tile, trackdir); |
286 if (segment_cost == 0) { |
210 if (n.m_segment->flags_u.flags_s.m_end_of_line) { |
287 /* We just entered the loop. First transition cost goes to segment entry cost)*/ |
211 break; |
288 segment_entry_cost = transition_cost; |
212 } |
289 transition_cost = 0; |
213 |
290 |
214 // finish if we have reached the destination |
291 /* It is the right time now to look if we can reuse the cached segment cost. */ |
215 if (target_seen) { |
292 if (is_cached_segment) { |
216 end_by_target_seen = true; |
293 /* Yes, we already know the segment cost. */ |
217 break; |
294 segment_cost = segment.m_cost; |
218 } |
295 /* We know also the reason why the segment ends. */ |
219 |
296 end_segment_reason = segment.m_end_segment_reason; |
220 // finish on first station tile - segment should end here to avoid target skipping |
297 /* No further calculation needed. */ |
221 // when cached segments are used |
298 cur = TILE(n.GetLastTile(), n.GetLastTrackdir()); |
222 if (tile_type == MP_STATION && prev_tile_type != MP_STATION) { |
|
223 break; |
|
224 } |
|
225 |
|
226 // finish also on waypoint - same workaround as for first station tile |
|
227 if (tile_type == MP_RAILWAY && IsRailWaypoint(tile)) { |
|
228 break; |
|
229 } |
|
230 |
|
231 // if there are no reachable trackdirs on the next tile, we have end of road |
|
232 TrackFollower F(v, &Yapf().m_perf_ts_cost); |
|
233 if (!F.Follow(tile, trackdir)) { |
|
234 // we can't continue? |
|
235 // n.m_segment->flags_u.flags_s.m_end_of_line = true; |
|
236 break; |
|
237 } |
|
238 |
|
239 // if there are more trackdirs available & reachable, we are at the end of segment |
|
240 if (KillFirstBit2x64(F.m_new_td_bits) != 0) { |
|
241 break; |
|
242 } |
|
243 |
|
244 Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits); |
|
245 |
|
246 { |
|
247 // end segment if train is about to enter simple loop with no junctions |
|
248 // so next time it should stop on the next if |
|
249 if (segment_cost > s_max_segment_cost && IsTileType(F.m_new_tile, MP_RAILWAY)) |
|
250 break; |
|
251 |
|
252 // stop if train is on simple loop with no junctions |
|
253 if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) |
|
254 return false; |
|
255 } |
|
256 |
|
257 // if tail type changes, finish segment (cached segment can't contain more rail types) |
|
258 { |
|
259 RailType new_rail_type = GetTileRailType(F.m_new_tile); |
|
260 if (new_rail_type != rail_type) { |
|
261 break; |
299 break; |
262 } |
300 } |
263 rail_type = new_rail_type; |
301 } else { |
264 } |
302 /* Other than first transition cost count as the regular segment cost. */ |
265 |
303 segment_cost += transition_cost; |
266 // move to the next tile |
304 } |
267 prev_tile = tile; |
305 |
268 prev_trackdir = trackdir; |
306 no_entry_cost: // jump here at the beginning if the node has no parent (it is the first node) |
269 prev_tile_type = tile_type; |
307 |
270 |
308 /* All other tile costs will be calculated here. */ |
271 tile = F.m_new_tile; |
309 segment_cost += Yapf().OneTileCost(cur.tile, cur.td); |
272 trackdir = new_td; |
310 |
273 tile_type = GetTileType(tile); |
311 /* If we skipped some tunnel/bridge/station tiles, add their base cost */ |
274 |
312 segment_cost += YAPF_TILE_LENGTH * tf->m_tiles_skipped; |
275 target_seen = Yapf().PfDetectDestination(tile, trackdir); |
313 |
276 |
314 /* Slope cost. */ |
277 // reversing in depot penalty |
315 segment_cost += Yapf().SlopeCost(cur.tile, cur.td); |
278 if (tile == prev_tile) { |
316 |
|
317 /* Signal cost (routine can modify segment data). */ |
|
318 segment_cost += Yapf().SignalCost(n, cur.tile, cur.td); |
|
319 end_segment_reason = segment.m_end_segment_reason; |
|
320 |
|
321 /* Tests for 'potential target' reasons to close the segment. */ |
|
322 if (cur.tile == prev.tile) { |
|
323 /* Penalty for reversing in a depot. */ |
|
324 assert(IsRailDepot(cur.tile)); |
279 segment_cost += Yapf().PfGetSettings().rail_depot_reverse_penalty; |
325 segment_cost += Yapf().PfGetSettings().rail_depot_reverse_penalty; |
|
326 /* We will end in this pass (depot is possible target) */ |
|
327 end_segment_reason |= ESRB_DEPOT; |
|
328 |
|
329 } else if (tf->m_is_station) { |
|
330 /* Station penalties. */ |
|
331 uint platform_length = tf->m_tiles_skipped + 1; |
|
332 /* We don't know yet if the station is our target or not. Act like |
|
333 * if it is pass-through station (not our destination). */ |
|
334 segment_cost += Yapf().PfGetSettings().rail_station_penalty * platform_length; |
|
335 /* We will end in this pass (station is possible target) */ |
|
336 end_segment_reason |= ESRB_STATION; |
|
337 |
|
338 } else if (cur.tile_type == MP_RAILWAY && IsRailWaypoint(cur.tile)) { |
|
339 /* Waypoint is also a good reason to finish. */ |
|
340 end_segment_reason |= ESRB_WAYPOINT; |
|
341 } |
|
342 |
|
343 /* Apply min/max speed penalties only when inside the look-ahead radius. Otherwise |
|
344 * it would cause desync in MP. */ |
|
345 if (n.m_num_signals_passed < m_sig_look_ahead_costs.Size()) |
|
346 { |
|
347 int min_speed = 0; |
|
348 int max_speed = tf->GetSpeedLimit(&min_speed); |
|
349 if (max_speed < v->max_speed) |
|
350 extra_cost += YAPF_TILE_LENGTH * (v->max_speed - max_speed) * (4 + tf->m_tiles_skipped) / v->max_speed; |
|
351 if (min_speed > v->max_speed) |
|
352 extra_cost += YAPF_TILE_LENGTH * (min_speed - v->max_speed); |
|
353 } |
|
354 |
|
355 /* Finish if we already exceeded the maximum path cost (i.e. when |
|
356 * searching for the nearest depot). */ |
|
357 if (m_max_cost > 0 && (parent_cost + segment_entry_cost + segment_cost) > m_max_cost) { |
|
358 end_segment_reason |= ESRB_PATH_TOO_LONG; |
|
359 } |
|
360 |
|
361 /* Move to the next tile/trackdir. */ |
|
362 tf = &tf_local; |
|
363 tf_local.Init(v, &Yapf().m_perf_ts_cost); |
|
364 |
|
365 if (!tf_local.Follow(cur.tile, cur.td)) { |
|
366 /* Can't move to the next tile (EOL?). */ |
|
367 end_segment_reason |= ESRB_DEAD_END; |
280 break; |
368 break; |
281 } |
369 } |
282 |
370 |
283 // if we skipped some tunnel tiles, add their cost |
371 /* Check if the next tile is not a choice. */ |
284 segment_cost += YAPF_TILE_LENGTH * F.m_tiles_skipped; |
372 if (KillFirstBit2x64(tf_local.m_new_td_bits) != 0) { |
285 |
373 /* More than one segment will follow. Close this one. */ |
286 // add penalty for skipped station tiles |
374 end_segment_reason |= ESRB_CHOICE_FOLLOWS; |
287 if (F.m_is_station) |
375 break; |
288 { |
376 } |
289 uint platform_length = F.m_tiles_skipped + 1; |
377 |
290 if (target_seen) { |
378 /* Gather the next tile/trackdir/tile_type/rail_type. */ |
291 // it is our destination station |
379 TILE next(tf_local.m_new_tile, (Trackdir)FindFirstBit2x64(tf_local.m_new_td_bits)); |
292 segment_cost += PlatformLengthPenalty(platform_length); |
380 |
293 } else { |
381 /* Check the next tile for the rail type. */ |
294 // station is not our destination station, apply penalty for skipped platform tiles |
382 if (next.rail_type != cur.rail_type) { |
295 segment_cost += Yapf().PfGetSettings().rail_station_penalty * platform_length; |
383 /* Segment must consist from the same rail_type tiles. */ |
296 } |
384 end_segment_reason |= ESRB_RAIL_TYPE; |
297 } |
385 break; |
298 |
386 } |
299 // add min/max speed penalties |
387 |
300 int min_speed = 0; |
388 /* Avoid infinite looping. */ |
301 int max_speed = F.GetSpeedLimit(&min_speed); |
389 if (next.tile == n.m_key.m_tile && next.td == n.m_key.m_td) { |
302 if (max_speed < v->max_speed) |
390 end_segment_reason |= ESRB_INFINITE_LOOP; |
303 segment_cost += YAPF_TILE_LENGTH * (v->max_speed - max_speed) / v->max_speed; |
391 break; |
304 if (min_speed > v->max_speed) |
392 } |
305 segment_cost += YAPF_TILE_LENGTH * (min_speed - v->max_speed); |
393 |
306 |
394 if (segment_cost > s_max_segment_cost) { |
307 // finish if we already exceeded the maximum cost |
395 /* Potentially in the infinite loop (or only very long segment?). We should |
308 if (m_max_cost > 0 && (parent_cost + first_tile_cost + segment_cost) > m_max_cost) { |
396 * not force it to finish prematurely unless we are on a regular tile. */ |
309 return false; |
397 if (IsTileType(tf->m_new_tile, MP_RAILWAY)) { |
310 } |
398 end_segment_reason |= ESRB_SEGMENT_TOO_LONG; |
311 |
|
312 if (first_tile_cost == 0) { |
|
313 // we just have done first tile |
|
314 first_tile_cost = segment_cost; |
|
315 segment_cost = 0; |
|
316 |
|
317 // look if we can reuse existing (cached) segment cost |
|
318 if (n.m_segment->m_cost >= 0) { |
|
319 // reuse the cached segment cost |
|
320 break; |
399 break; |
321 } |
400 } |
322 } |
401 } |
323 // segment cost was not filled yes, we have not cached it yet |
402 |
324 n.SetLastTileTrackdir(tile, trackdir); |
403 /* Any other reason bit set? */ |
325 |
404 if (end_segment_reason != ESRB_NONE) { |
326 } // while (true) |
405 break; |
327 |
406 } |
328 if (first_tile_cost == 0) { |
407 |
329 // we have just finished first tile |
408 /* For the next loop set new prev and cur tile info. */ |
330 first_tile_cost = segment_cost; |
409 prev = cur; |
331 segment_cost = 0; |
410 cur = next; |
332 } |
411 |
333 |
412 } // for (;;) |
334 // do we have cached segment cost? |
413 |
335 if (n.m_segment->m_cost >= 0) { |
414 bool target_seen = false; |
336 // reuse the cached segment cost |
415 if ((end_segment_reason & ESRB_POSSIBLE_TARGET) != ESRB_NONE) { |
337 segment_cost = n.m_segment->m_cost; |
416 /* Depot, station or waypoint. */ |
338 } else { |
417 if (Yapf().PfDetectDestination(cur.tile, cur.td)) { |
339 // save segment cost |
418 /* Destination found. */ |
340 n.m_segment->m_cost = segment_cost; |
419 target_seen = true; |
341 |
420 } |
342 // save end of segment back to the node |
421 } |
343 n.SetLastTileTrackdir(tile, trackdir); |
422 |
344 } |
423 /* Update the segment if needed. */ |
345 |
424 if (!is_cached_segment) { |
346 // special costs for the case we have reached our target |
425 /* Write back the segment information so it can be reused the next time. */ |
347 if (end_by_target_seen) { |
426 segment.m_cost = segment_cost; |
|
427 segment.m_end_segment_reason = end_segment_reason & ESRB_CACHED_MASK; |
|
428 assert(segment.m_end_segment_reason != ESRB_NONE); |
|
429 /* Save end of segment back to the node. */ |
|
430 n.SetLastTileTrackdir(cur.tile, cur.td); |
|
431 } |
|
432 |
|
433 /* Do we have an excuse why not to continue pathfinding in this direction? */ |
|
434 if (!target_seen && (end_segment_reason & ESRB_ABORT_PF_MASK) != ESRB_NONE) { |
|
435 /* Reason to not continue. Stop this PF branch. */ |
|
436 return false; |
|
437 } |
|
438 |
|
439 /* Special costs for the case we have reached our target. */ |
|
440 if (target_seen) { |
348 n.flags_u.flags_s.m_targed_seen = true; |
441 n.flags_u.flags_s.m_targed_seen = true; |
|
442 /* Last-red and last-red-exit penalties. */ |
349 if (n.flags_u.flags_s.m_last_signal_was_red) { |
443 if (n.flags_u.flags_s.m_last_signal_was_red) { |
350 if (n.m_last_red_signal_type == SIGTYPE_EXIT) { |
444 if (n.m_last_red_signal_type == SIGTYPE_EXIT) { |
351 // last signal was red pre-signal-exit |
445 // last signal was red pre-signal-exit |
352 extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty; |
446 extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty; |
353 } else { |
447 } else { |
354 // last signal was red, but not exit |
448 // last signal was red, but not exit |
355 extra_cost += Yapf().PfGetSettings().rail_lastred_penalty; |
449 extra_cost += Yapf().PfGetSettings().rail_lastred_penalty; |
356 } |
450 } |
357 } |
451 } |
|
452 |
|
453 /* Station platform-length penalty. */ |
|
454 if ((end_segment_reason & ESRB_STATION) != ESRB_NONE) { |
|
455 Station *st = GetStationByTile(n.GetLastTile()); |
|
456 assert(st != NULL); |
|
457 uint platform_length = st->GetPlatformLength(n.GetLastTile(), ReverseDiagDir(TrackdirToExitdir(n.GetLastTrackdir()))); |
|
458 /* Reduce the extra cost caused by passing-station penalty (each station receives it in the segment cost). */ |
|
459 extra_cost -= Yapf().PfGetSettings().rail_station_penalty * platform_length; |
|
460 /* Add penalty for the inappropriate platform length. */ |
|
461 extra_cost += PlatformLengthPenalty(platform_length); |
|
462 } |
358 } |
463 } |
359 |
464 |
360 // total node cost |
465 // total node cost |
361 n.m_cost = parent_cost + first_tile_cost + segment_cost + extra_cost; |
466 n.m_cost = parent_cost + segment_entry_cost + segment_cost + extra_cost; |
362 |
467 |
363 return !n.m_segment->flags_u.flags_s.m_end_of_line || end_by_target_seen; |
468 return true; |
364 } |
469 } |
365 |
470 |
366 FORCEINLINE bool CanUseGlobalCache(Node& n) const |
471 FORCEINLINE bool CanUseGlobalCache(Node& n) const |
367 { |
472 { |
368 return (n.m_parent != NULL) |
473 return (n.m_parent != NULL) |