1998 { |
1998 { |
1999 assert(!(v->vehstatus & VS_CRASHED)); |
1999 assert(!(v->vehstatus & VS_CRASHED)); |
2000 |
2000 |
2001 TrainFindDepotData tfdd; |
2001 TrainFindDepotData tfdd; |
2002 tfdd.owner = v->owner; |
2002 tfdd.owner = v->owner; |
2003 tfdd.best_length = (uint)-1; |
2003 tfdd.best_length = UINT_MAX; |
2004 tfdd.reverse = false; |
2004 tfdd.reverse = false; |
2005 |
2005 |
2006 TileIndex tile = v->tile; |
2006 TileIndex tile = v->tile; |
2007 if (IsTileDepotType(tile, TRANSPORT_RAIL)) { |
2007 if (IsTileDepotType(tile, TRANSPORT_RAIL)) { |
2008 tfdd.tile = tile; |
2008 tfdd.tile = tile; |
2009 tfdd.best_length = 0; |
2009 tfdd.best_length = 0; |
2010 return tfdd; |
2010 return tfdd; |
2011 } |
2011 } |
2012 |
2012 |
2013 if (_patches.pathfinder_for_trains == VPF_YAPF) { /* YAPF is selected */ |
2013 switch (_patches.pathfinder_for_trains) { |
2014 bool found = YapfFindNearestRailDepotTwoWay(v, max_distance, NPF_INFINITE_PENALTY, &tfdd.tile, &tfdd.reverse); |
2014 case VPF_YAPF: { /* YAPF */ |
2015 tfdd.best_length = found ? max_distance / 2 : -1; // some fake distance or NOT_FOUND |
2015 bool found = YapfFindNearestRailDepotTwoWay(v, max_distance, NPF_INFINITE_PENALTY, &tfdd.tile, &tfdd.reverse); |
2016 } else if (_patches.pathfinder_for_trains == VPF_NPF) { /* NPF is selected */ |
2016 tfdd.best_length = found ? max_distance / 2 : UINT_MAX; // some fake distance or NOT_FOUND |
2017 Vehicle* last = GetLastVehicleInChain(v); |
2017 } break; |
2018 Trackdir trackdir = GetVehicleTrackdir(v); |
2018 |
2019 Trackdir trackdir_rev = ReverseTrackdir(GetVehicleTrackdir(last)); |
2019 case VPF_NPF: { /* NPF */ |
2020 |
2020 Vehicle* last = GetLastVehicleInChain(v); |
2021 assert(trackdir != INVALID_TRACKDIR); |
2021 Trackdir trackdir = GetVehicleTrackdir(v); |
2022 NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes, NPF_INFINITE_PENALTY); |
2022 Trackdir trackdir_rev = ReverseTrackdir(GetVehicleTrackdir(last)); |
2023 if (ftd.best_bird_dist == 0) { |
2023 |
2024 /* Found target */ |
2024 assert(trackdir != INVALID_TRACKDIR); |
2025 tfdd.tile = ftd.node.tile; |
2025 NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes, NPF_INFINITE_PENALTY); |
2026 /* Our caller expects a number of tiles, so we just approximate that |
2026 if (ftd.best_bird_dist == 0) { |
2027 * number by this. It might not be completely what we want, but it will |
2027 /* Found target */ |
2028 * work for now :-) We can possibly change this when the old pathfinder |
2028 tfdd.tile = ftd.node.tile; |
2029 * is removed. */ |
2029 /* Our caller expects a number of tiles, so we just approximate that |
2030 tfdd.best_length = ftd.best_path_dist / NPF_TILE_LENGTH; |
2030 * number by this. It might not be completely what we want, but it will |
2031 if (NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)) tfdd.reverse = true; |
2031 * work for now :-) We can possibly change this when the old pathfinder |
2032 } |
2032 * is removed. */ |
2033 } else { /* NTP */ |
2033 tfdd.best_length = ftd.best_path_dist / NPF_TILE_LENGTH; |
2034 /* search in the forward direction first. */ |
2034 if (NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)) tfdd.reverse = true; |
2035 DiagDirection i = TrainExitDir(v->direction, v->u.rail.track); |
2035 } |
2036 NewTrainPathfind(tile, 0, v->u.rail.compatible_railtypes, i, (NTPEnumProc*)NtpCallbFindDepot, &tfdd); |
2036 } break; |
2037 if (tfdd.best_length == (uint)-1){ |
2037 |
2038 tfdd.reverse = true; |
2038 default: |
2039 /* search in backwards direction */ |
2039 case VPF_NTP: { /* NTP */ |
2040 i = TrainExitDir(ReverseDir(v->direction), v->u.rail.track); |
2040 /* search in the forward direction first. */ |
|
2041 DiagDirection i = TrainExitDir(v->direction, v->u.rail.track); |
2041 NewTrainPathfind(tile, 0, v->u.rail.compatible_railtypes, i, (NTPEnumProc*)NtpCallbFindDepot, &tfdd); |
2042 NewTrainPathfind(tile, 0, v->u.rail.compatible_railtypes, i, (NTPEnumProc*)NtpCallbFindDepot, &tfdd); |
2042 } |
2043 if (tfdd.best_length == UINT_MAX){ |
|
2044 tfdd.reverse = true; |
|
2045 /* search in backwards direction */ |
|
2046 i = TrainExitDir(ReverseDir(v->direction), v->u.rail.track); |
|
2047 NewTrainPathfind(tile, 0, v->u.rail.compatible_railtypes, i, (NTPEnumProc*)NtpCallbFindDepot, &tfdd); |
|
2048 } |
|
2049 } break; |
2043 } |
2050 } |
2044 |
2051 |
2045 return tfdd; |
2052 return tfdd; |
2046 } |
2053 } |
2047 |
2054 |
2356 assert((tracks & ~TRACK_BIT_MASK) == 0); |
2363 assert((tracks & ~TRACK_BIT_MASK) == 0); |
2357 |
2364 |
2358 /* quick return in case only one possible track is available */ |
2365 /* quick return in case only one possible track is available */ |
2359 if (KillFirstBit(tracks) == TRACK_BIT_NONE) return FindFirstTrack(tracks); |
2366 if (KillFirstBit(tracks) == TRACK_BIT_NONE) return FindFirstTrack(tracks); |
2360 |
2367 |
2361 if (_patches.pathfinder_for_trains == VPF_YAPF) { /* YAPF is selected */ |
2368 switch (_patches.pathfinder_for_trains) { |
2362 Trackdir trackdir = YapfChooseRailTrack(v, tile, enterdir, tracks, &path_not_found); |
2369 case VPF_YAPF: { /* YAPF */ |
2363 if (trackdir != INVALID_TRACKDIR) { |
2370 Trackdir trackdir = YapfChooseRailTrack(v, tile, enterdir, tracks, &path_not_found); |
2364 best_track = TrackdirToTrack(trackdir); |
2371 if (trackdir != INVALID_TRACKDIR) { |
2365 } else { |
2372 best_track = TrackdirToTrack(trackdir); |
2366 best_track = FindFirstTrack(tracks); |
2373 } else { |
2367 } |
2374 best_track = FindFirstTrack(tracks); |
2368 } else if (_patches.pathfinder_for_trains == VPF_NPF) { /* NPF is selected */ |
2375 } |
2369 void* perf = NpfBeginInterval(); |
2376 } break; |
2370 |
2377 |
2371 NPFFindStationOrTileData fstd; |
2378 case VPF_NPF: { /* NPF */ |
2372 NPFFillWithOrderData(&fstd, v); |
2379 void *perf = NpfBeginInterval(); |
2373 /* The enterdir for the new tile, is the exitdir for the old tile */ |
2380 |
2374 Trackdir trackdir = GetVehicleTrackdir(v); |
2381 NPFFindStationOrTileData fstd; |
2375 assert(trackdir != 0xff); |
2382 NPFFillWithOrderData(&fstd, v); |
2376 |
2383 /* The enterdir for the new tile, is the exitdir for the old tile */ |
2377 NPFFoundTargetData ftd = NPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes); |
2384 Trackdir trackdir = GetVehicleTrackdir(v); |
2378 |
2385 assert(trackdir != INVALID_TRACKDIR); |
2379 if (ftd.best_trackdir == 0xff) { |
2386 |
2380 /* We are already at our target. Just do something |
2387 NPFFoundTargetData ftd = NPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes); |
2381 * @todo maybe display error? |
2388 |
2382 * @todo: go straight ahead if possible? */ |
2389 if (ftd.best_trackdir == INVALID_TRACKDIR) { |
2383 best_track = FindFirstTrack(tracks); |
2390 /* We are already at our target. Just do something |
2384 } else { |
2391 * @todo maybe display error? |
2385 /* If ftd.best_bird_dist is 0, we found our target and ftd.best_trackdir contains |
2392 * @todo: go straight ahead if possible? */ |
2386 the direction we need to take to get there, if ftd.best_bird_dist is not 0, |
2393 best_track = FindFirstTrack(tracks); |
2387 we did not find our target, but ftd.best_trackdir contains the direction leading |
2394 } else { |
2388 to the tile closest to our target. */ |
2395 /* If ftd.best_bird_dist is 0, we found our target and ftd.best_trackdir contains |
2389 if (ftd.best_bird_dist != 0) path_not_found = true; |
2396 * the direction we need to take to get there, if ftd.best_bird_dist is not 0, |
2390 /* Discard enterdir information, making it a normal track */ |
2397 * we did not find our target, but ftd.best_trackdir contains the direction leading |
2391 best_track = TrackdirToTrack(ftd.best_trackdir); |
2398 * to the tile closest to our target. */ |
2392 } |
2399 if (ftd.best_bird_dist != 0) path_not_found = true; |
2393 |
2400 /* Discard enterdir information, making it a normal track */ |
2394 int time = NpfEndInterval(perf); |
2401 best_track = TrackdirToTrack(ftd.best_trackdir); |
2395 DEBUG(yapf, 4, "[NPFT] %d us - %d rounds - %d open - %d closed -- ", time, 0, _aystar_stats_open_size, _aystar_stats_closed_size); |
2402 } |
2396 } else { /* NTP is selected */ |
2403 |
2397 void* perf = NpfBeginInterval(); |
2404 int time = NpfEndInterval(perf); |
2398 |
2405 DEBUG(yapf, 4, "[NPFT] %d us - %d rounds - %d open - %d closed -- ", time, 0, _aystar_stats_open_size, _aystar_stats_closed_size); |
2399 TrainTrackFollowerData fd; |
2406 } break; |
2400 FillWithStationData(&fd, v); |
2407 |
2401 |
2408 default: |
2402 /* New train pathfinding */ |
2409 case VPF_NTP: { /* NTP */ |
2403 fd.best_bird_dist = (uint)-1; |
2410 void *perf = NpfBeginInterval(); |
2404 fd.best_track_dist = (uint)-1; |
2411 |
2405 fd.best_track = INVALID_TRACKDIR; |
2412 TrainTrackFollowerData fd; |
2406 |
2413 FillWithStationData(&fd, v); |
2407 NewTrainPathfind(tile - TileOffsByDiagDir(enterdir), v->dest_tile, |
2414 |
2408 v->u.rail.compatible_railtypes, enterdir, (NTPEnumProc*)NtpCallbFindStation, &fd); |
2415 /* New train pathfinding */ |
2409 |
2416 fd.best_bird_dist = UINT_MAX; |
2410 /* check whether the path was found or only 'guessed' */ |
2417 fd.best_track_dist = UINT_MAX; |
2411 if (fd.best_bird_dist != 0) path_not_found = true; |
2418 fd.best_track = INVALID_TRACKDIR; |
2412 |
2419 |
2413 if (fd.best_track == 0xff) { |
2420 NewTrainPathfind(tile - TileOffsByDiagDir(enterdir), v->dest_tile, |
2414 /* blaha */ |
2421 v->u.rail.compatible_railtypes, enterdir, (NTPEnumProc*)NtpCallbFindStation, &fd); |
2415 best_track = FindFirstTrack(tracks); |
2422 |
2416 } else { |
2423 /* check whether the path was found or only 'guessed' */ |
2417 best_track = TrackdirToTrack(fd.best_track); |
2424 if (fd.best_bird_dist != 0) path_not_found = true; |
2418 } |
2425 |
2419 |
2426 if (fd.best_track == INVALID_TRACKDIR) { |
2420 int time = NpfEndInterval(perf); |
2427 /* blaha */ |
2421 DEBUG(yapf, 4, "[NTPT] %d us - %d rounds - %d open - %d closed -- ", time, 0, 0, 0); |
2428 best_track = FindFirstTrack(tracks); |
2422 } |
2429 } else { |
|
2430 best_track = TrackdirToTrack(fd.best_track); |
|
2431 } |
|
2432 |
|
2433 int time = NpfEndInterval(perf); |
|
2434 DEBUG(yapf, 4, "[NTPT] %d us - %d rounds - %d open - %d closed -- ", time, 0, 0, 0); |
|
2435 } break; |
|
2436 } |
|
2437 |
2423 /* handle "path not found" state */ |
2438 /* handle "path not found" state */ |
2424 if (path_not_found) { |
2439 if (path_not_found) { |
2425 /* PF didn't find the route */ |
2440 /* PF didn't find the route */ |
2426 if (!HasBit(v->u.rail.flags, VRF_NO_PATH_TO_DESTINATION)) { |
2441 if (!HasBit(v->u.rail.flags, VRF_NO_PATH_TO_DESTINATION)) { |
2427 /* it is first time the problem occurred, set the "path not found" flag */ |
2442 /* it is first time the problem occurred, set the "path not found" flag */ |
2467 |
2482 |
2468 assert(v->u.rail.track); |
2483 assert(v->u.rail.track); |
2469 |
2484 |
2470 int i = _search_directions[FIND_FIRST_BIT(v->u.rail.track)][DirToDiagDir(v->direction)]; |
2485 int i = _search_directions[FIND_FIRST_BIT(v->u.rail.track)][DirToDiagDir(v->direction)]; |
2471 |
2486 |
2472 if (_patches.pathfinder_for_trains == VPF_YAPF) { /* YAPF is selected */ |
2487 switch (_patches.pathfinder_for_trains) { |
2473 reverse_best = YapfCheckReverseTrain(v); |
2488 case VPF_YAPF: { /* YAPF */ |
2474 } else if (_patches.pathfinder_for_trains == VPF_NPF) { /* NPF if selected for trains */ |
2489 reverse_best = YapfCheckReverseTrain(v); |
2475 NPFFindStationOrTileData fstd; |
2490 } break; |
2476 NPFFoundTargetData ftd; |
2491 |
2477 Trackdir trackdir, trackdir_rev; |
2492 case VPF_NPF: { /* NPF */ |
2478 Vehicle* last = GetLastVehicleInChain(v); |
2493 NPFFindStationOrTileData fstd; |
2479 |
2494 NPFFoundTargetData ftd; |
2480 NPFFillWithOrderData(&fstd, v); |
2495 Vehicle* last = GetLastVehicleInChain(v); |
2481 |
2496 |
2482 trackdir = GetVehicleTrackdir(v); |
2497 NPFFillWithOrderData(&fstd, v); |
2483 trackdir_rev = ReverseTrackdir(GetVehicleTrackdir(last)); |
2498 |
2484 assert(trackdir != 0xff); |
2499 Trackdir trackdir = GetVehicleTrackdir(v); |
2485 assert(trackdir_rev != 0xff); |
2500 Trackdir trackdir_rev = ReverseTrackdir(GetVehicleTrackdir(last)); |
2486 |
2501 assert(trackdir != INVALID_TRACKDIR); |
2487 ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, &fstd, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes); |
2502 assert(trackdir_rev != INVALID_TRACKDIR); |
2488 if (ftd.best_bird_dist != 0) { |
2503 |
2489 /* We didn't find anything, just keep on going straight ahead */ |
2504 ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, &fstd, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes); |
2490 reverse_best = false; |
2505 if (ftd.best_bird_dist != 0) { |
2491 } else { |
2506 /* We didn't find anything, just keep on going straight ahead */ |
2492 if (NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)) { |
2507 reverse_best = false; |
2493 reverse_best = true; |
|
2494 } else { |
2508 } else { |
2495 reverse_best = false; |
2509 if (NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)) { |
2496 } |
2510 reverse_best = true; |
2497 } |
2511 } else { |
2498 } else { /* NTP is selected */ |
2512 reverse_best = false; |
2499 int best_track = -1; |
2513 } |
2500 uint reverse = 0; |
2514 } |
2501 uint best_bird_dist = 0; |
2515 } break; |
2502 uint best_track_dist = 0; |
2516 |
2503 |
2517 default: |
2504 for (;;) { |
2518 case VPF_NTP: { /* NTP */ |
2505 fd.best_bird_dist = (uint)-1; |
2519 int best_track = -1; |
2506 fd.best_track_dist = (uint)-1; |
2520 uint reverse = 0; |
2507 |
2521 uint best_bird_dist = 0; |
2508 NewTrainPathfind(v->tile, v->dest_tile, v->u.rail.compatible_railtypes, (DiagDirection)(reverse ^ i), (NTPEnumProc*)NtpCallbFindStation, &fd); |
2522 uint best_track_dist = 0; |
2509 |
2523 |
2510 if (best_track != -1) { |
2524 for (;;) { |
2511 if (best_bird_dist != 0) { |
2525 fd.best_bird_dist = UINT_MAX; |
2512 if (fd.best_bird_dist != 0) { |
2526 fd.best_track_dist = UINT_MAX; |
2513 /* neither reached the destination, pick the one with the smallest bird dist */ |
2527 |
2514 if (fd.best_bird_dist > best_bird_dist) goto bad; |
2528 NewTrainPathfind(v->tile, v->dest_tile, v->u.rail.compatible_railtypes, (DiagDirection)(reverse ^ i), (NTPEnumProc*)NtpCallbFindStation, &fd); |
2515 if (fd.best_bird_dist < best_bird_dist) goto good; |
2529 |
|
2530 if (best_track != -1) { |
|
2531 if (best_bird_dist != 0) { |
|
2532 if (fd.best_bird_dist != 0) { |
|
2533 /* neither reached the destination, pick the one with the smallest bird dist */ |
|
2534 if (fd.best_bird_dist > best_bird_dist) goto bad; |
|
2535 if (fd.best_bird_dist < best_bird_dist) goto good; |
|
2536 } else { |
|
2537 /* we found the destination for the first time */ |
|
2538 goto good; |
|
2539 } |
2516 } else { |
2540 } else { |
2517 /* we found the destination for the first time */ |
2541 if (fd.best_bird_dist != 0) { |
2518 goto good; |
2542 /* didn't find destination, but we've found the destination previously */ |
|
2543 goto bad; |
|
2544 } else { |
|
2545 /* both old & new reached the destination, compare track length */ |
|
2546 if (fd.best_track_dist > best_track_dist) goto bad; |
|
2547 if (fd.best_track_dist < best_track_dist) goto good; |
|
2548 } |
2519 } |
2549 } |
2520 } else { |
2550 |
2521 if (fd.best_bird_dist != 0) { |
2551 /* if we reach this position, there's two paths of equal value so far. |
2522 /* didn't find destination, but we've found the destination previously */ |
2552 * pick one randomly. */ |
2523 goto bad; |
2553 int r = GB(Random(), 0, 8); |
2524 } else { |
2554 if (_pick_track_table[i] == (v->direction & 3)) r += 80; |
2525 /* both old & new reached the destination, compare track length */ |
2555 if (_pick_track_table[best_track] == (v->direction & 3)) r -= 80; |
2526 if (fd.best_track_dist > best_track_dist) goto bad; |
2556 if (r <= 127) goto bad; |
2527 if (fd.best_track_dist < best_track_dist) goto good; |
|
2528 } |
|
2529 } |
2557 } |
2530 |
|
2531 /* if we reach this position, there's two paths of equal value so far. |
|
2532 * pick one randomly. */ |
|
2533 int r = GB(Random(), 0, 8); |
|
2534 if (_pick_track_table[i] == (v->direction & 3)) r += 80; |
|
2535 if (_pick_track_table[best_track] == (v->direction & 3)) r -= 80; |
|
2536 if (r <= 127) goto bad; |
|
2537 } |
|
2538 good:; |
2558 good:; |
2539 best_track = i; |
2559 best_track = i; |
2540 best_bird_dist = fd.best_bird_dist; |
2560 best_bird_dist = fd.best_bird_dist; |
2541 best_track_dist = fd.best_track_dist; |
2561 best_track_dist = fd.best_track_dist; |
2542 reverse_best = reverse; |
2562 reverse_best = reverse; |
2543 bad:; |
2563 bad:; |
2544 if (reverse != 0) break; |
2564 if (reverse != 0) break; |
2545 reverse = 2; |
2565 reverse = 2; |
2546 } |
2566 } |
|
2567 } break; |
2547 } |
2568 } |
2548 |
2569 |
2549 return reverse_best != 0; |
2570 return reverse_best != 0; |
2550 } |
2571 } |
2551 |
2572 |