Mercurial > hg > openttd
changeset 13844:ec53cf83e714 draft
(svn r18373) -Codechange: unify some road pathfinder functions
author | rubidium <rubidium@openttd.org> |
---|---|
date | Wed, 02 Dec 2009 10:44:38 +0000 |
parents | 2a23885aaf5f |
children | dda8b635b89b |
files | src/pathfinder/npf/npf.cpp src/pathfinder/npf/npf_func.h src/pathfinder/yapf/yapf.h src/pathfinder/yapf/yapf_road.cpp src/pathfinder/yapf/yapf_ship.cpp src/roadveh_cmd.cpp src/ship_cmd.cpp |
diffstat | 7 files changed, 96 insertions(+), 120 deletions(-) [+] |
line wrap: on
line diff
--- a/src/pathfinder/npf/npf.cpp +++ b/src/pathfinder/npf/npf.cpp @@ -18,8 +18,9 @@ #include "../../functions.h" #include "../../tunnelbridge.h" #include "../../pbs.h" +#include "../../roadveh.h" +#include "../../ship.h" #include "../../train.h" -#include "../../ship.h" #include "../pathfinder_func.h" #include "../pathfinder_type.h" #include "npf.h" @@ -1097,6 +1098,46 @@ fstd->v = v; } +/*** Road vehicles ***/ + +FindDepotData NPFRoadVehicleFindNearestDepot(const RoadVehicle *v, int max_distance) +{ + Trackdir trackdir = v->GetVehicleTrackdir(); + + NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, v->tile, ReverseTrackdir(trackdir), false, TRANSPORT_ROAD, v->compatible_roadtypes, v->owner, INVALID_RAILTYPES, 0); + + if (ftd.best_bird_dist != 0) return FindDepotData(); + + /* Found target */ + /* Our caller expects a number of tiles, so we just approximate that + * number by this. It might not be completely what we want, but it will + * work for now :-) We can possibly change this when the old pathfinder + * is removed. */ + return FindDepotData(ftd.node.tile, ftd.best_path_dist / NPF_TILE_LENGTH); +} + +Trackdir NPFRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs) +{ + NPFFindStationOrTileData fstd; + + NPFFillWithOrderData(&fstd, v); + Trackdir trackdir = DiagDirToDiagTrackdir(enterdir); + + NPFFoundTargetData ftd = NPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_ROAD, v->compatible_roadtypes, v->owner, INVALID_RAILTYPES); + if (ftd.best_trackdir == INVALID_TRACKDIR) { + /* We are already at our target. Just do something + * @todo: maybe display error? + * @todo: go straight ahead if possible? */ + return (Trackdir)FindFirstBit2x64(trackdirs); + } + + /* If ftd.best_bird_dist is 0, we found our target and ftd.best_trackdir contains + * the direction we need to take to get there, if ftd.best_bird_dist is not 0, + * we did not find our target, but ftd.best_trackdir contains the direction leading + * to the tile closest to our target. */ + return ftd.best_trackdir; +} + /*** Ships ***/ Track NPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks) @@ -1127,7 +1168,7 @@ assert(trackdir != INVALID_TRACKDIR); NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, TRANSPORT_RAIL, 0, v->owner, v->compatible_railtypes, NPF_INFINITE_PENALTY); - if (ftd.best_bird_dist != 0) FindDepotData(); + if (ftd.best_bird_dist != 0) return FindDepotData(); /* Found target */ /* Our caller expects a number of tiles, so we just approximate that
--- a/src/pathfinder/npf/npf_func.h +++ b/src/pathfinder/npf/npf_func.h @@ -17,6 +17,26 @@ #include "../pathfinder_type.h" /** + * Used when user sends road vehicle to the nearest depot or if road vehicle needs servicing using NPF. + * @param v vehicle that needs to go to some depot + * @param max_distance max distance (number of track tiles) from the current vehicle position + * (used also as optimization - the pathfinder can stop path finding if max_distance + * was reached and no depot was seen) + * @return the data about the depot + */ +FindDepotData NPFRoadVehicleFindNearestDepot(const RoadVehicle *v, int max_distance); + +/** + * Finds the best path for given road vehicle using NPF. + * @param v the RV that needs to find a path + * @param tile the tile to find the path from (should be next tile the RV is about to enter) + * @param enterdir diagonal direction which the RV will enter this new tile from + * @param trackdirs available trackdirs on the new tile (to choose from) + * @return the best trackdir for next turn or INVALID_TRACKDIR if the path could not be found + */ +Trackdir NPFRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs); + +/** * Finds the best path for given ship using NPF. * @param v the ship that needs to find a path * @param tile the tile to find the path from (should be next tile the ship is about to enter)
--- a/src/pathfinder/yapf/yapf.h +++ b/src/pathfinder/yapf/yapf.h @@ -24,15 +24,17 @@ * @param tracks available tracks on the new tile (to choose from) * @return the best trackdir for next turn or INVALID_TRACK if the path could not be found */ -Track YapfChooseShipTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks); +Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks); -/** Finds the best path for given road vehicle. - * @param v the RV that needs to find a path - * @param tile the tile to find the path from (should be next tile the RV is about to enter) - * @param enterdir diagonal direction which the RV will enter this new tile from - * @return the best trackdir for next turn or INVALID_TRACKDIR if the path could not be found +/** + * Finds the best path for given road vehicle using YAPF. + * @param v the RV that needs to find a path + * @param tile the tile to find the path from (should be next tile the RV is about to enter) + * @param enterdir diagonal direction which the RV will enter this new tile from + * @param trackdirs available trackdirs on the new tile (to choose from) + * @return the best trackdir for next turn or INVALID_TRACKDIR if the path could not be found */ -Trackdir YapfChooseRoadTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir); +Trackdir YapfRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs); /** * Finds the best path for given train using YAPF. @@ -62,15 +64,15 @@ */ bool YapfFindNearestRoadVehicleCompatibleStop(const RoadVehicle *v, StationID station, TileIndex *stop_tile); -/** Used when user sends road vehicle to the nearest depot or if road vehicle needs servicing. +/** + * Used when user sends road vehicle to the nearest depot or if road vehicle needs servicing using YAPF. * @param v vehicle that needs to go to some depot * @param max_distance max distance (number of track tiles) from the current vehicle position * (used also as optimization - the pathfinder can stop path finding if max_distance * was reached and no depot was seen) - * @param depot_tile receives the depot tile if depot was found - * @return true if depot was found. + * @return the data about the depot */ -bool YapfFindNearestRoadDepot(const RoadVehicle *v, int max_distance, TileIndex *depot_tile); +FindDepotData YapfRoadVehicleFindNearestDepot(const RoadVehicle *v, int max_distance); /** * Used when user sends train to the nearest depot or if train needs servicing using YAPF.
--- a/src/pathfinder/yapf/yapf_road.cpp +++ b/src/pathfinder/yapf/yapf_road.cpp @@ -539,7 +539,7 @@ struct CYapfRoadAnyRoadVehicleCompatibleStopOfGivenStation2 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyRoadVehicleCompatibleStopOfGivenStation2, CRoadNodeListExitDir , CYapfDestinationAnyRoadVehicleCompatibleStopOfGivenStationT> > {}; -Trackdir YapfChooseRoadTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir) +Trackdir YapfRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs) { /* default is YAPF type 2 */ typedef Trackdir (*PfnChooseRoadTrack)(const RoadVehicle*, TileIndex, DiagDirection); @@ -551,7 +551,7 @@ } Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir); - return td_ret; + return (td_ret != INVALID_TRACKDIR) ? td_ret : (Trackdir)FindFirstBit2x64(trackdirs); } uint YapfRoadVehDistanceToTile(const RoadVehicle *v, TileIndex tile) @@ -575,21 +575,12 @@ return dist; } -bool YapfFindNearestRoadDepot(const RoadVehicle *v, int max_distance, TileIndex *depot_tile) +FindDepotData YapfRoadVehicleFindNearestDepot(const RoadVehicle *v, int max_distance) { - *depot_tile = INVALID_TILE; - TileIndex tile = v->tile; Trackdir trackdir = v->GetVehicleTrackdir(); if ((TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_ROAD, v->compatible_roadtypes)) & TrackdirToTrackdirBits(trackdir)) == 0) { - return false; - } - - /* handle the case when our vehicle is already in the depot tile */ - if (IsRoadDepotTile(tile)) { - /* only what we need to return is the Depot* */ - *depot_tile = tile; - return true; + return FindDepotData(); } /* default is YAPF type 2 */ @@ -601,7 +592,9 @@ pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot; // Trackdir, allow 90-deg } - bool ret = pfnFindNearestDepot(v, tile, trackdir, max_distance, depot_tile); + FindDepotData fdd; + bool ret = pfnFindNearestDepot(v, tile, trackdir, max_distance, &fdd.tile); + fdd.best_length = ret ? max_distance / 2 : UINT_MAX; // some fake distance or NOT_FOUND return ret; }
--- a/src/pathfinder/yapf/yapf_ship.cpp +++ b/src/pathfinder/yapf/yapf_ship.cpp @@ -169,7 +169,7 @@ struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {}; /** Ship controller helper - path finder invoker */ -Track YapfChooseShipTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks) +Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks) { /* default is YAPF type 2 */ typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackBits);
--- a/src/roadveh_cmd.cpp +++ b/src/roadveh_cmd.cpp @@ -15,6 +15,7 @@ #include "command_func.h" #include "news_func.h" #include "pathfinder/npf/npf.h" +#include "pathfinder/npf/npf_func.h" #include "station_base.h" #include "company_func.h" #include "vehicle_gui.h" @@ -76,15 +77,6 @@ TRACKDIR_RVREV_NE, TRACKDIR_RVREV_SE, TRACKDIR_RVREV_SW, TRACKDIR_RVREV_NW }; -/** 'Convert' the DiagDirection where a road vehicle should exit to - * the trackdirs it can use to drive to the exit direction*/ -static const TrackdirBits _road_exit_dir_to_incoming_trackdirs[DIAGDIR_END] = { - TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_X_SW | TRACKDIR_BIT_LEFT_S, - TRACKDIR_BIT_LEFT_N | TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_Y_NW, - TRACKDIR_BIT_RIGHT_N | TRACKDIR_BIT_UPPER_E | TRACKDIR_BIT_X_NE, - TRACKDIR_BIT_RIGHT_S | TRACKDIR_BIT_LOWER_E | TRACKDIR_BIT_Y_SE -}; - /** Converts the exit direction of a depot to trackdir the vehicle is going to drive to */ static const Trackdir _roadveh_depot_exit_trackdir[DIAGDIR_END] = { TRACKDIR_X_NE, TRACKDIR_Y_SE, TRACKDIR_X_SW, TRACKDIR_Y_NW @@ -365,58 +357,21 @@ return ret; } -struct RoadFindDepotData { - uint best_length; - TileIndex tile; - OwnerByte owner; -}; - -static const DiagDirection _road_pf_directions[] = { - DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SW, DIAGDIR_SE, INVALID_DIAGDIR, INVALID_DIAGDIR, - DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE, INVALID_DIAGDIR, INVALID_DIAGDIR -}; - -static RoadFindDepotData FindClosestRoadDepot(const RoadVehicle *v, int max_distance) +static FindDepotData FindClosestRoadDepot(const RoadVehicle *v, int max_distance) { - RoadFindDepotData rfdd; - rfdd.owner = v->owner; - - if (IsRoadDepotTile(v->tile)) { - rfdd.tile = v->tile; - rfdd.best_length = 0; - return rfdd; - } - - rfdd.best_length = UINT_MAX; + if (IsRoadDepotTile(v->tile)) return FindDepotData(v->tile, 0); switch (_settings_game.pf.pathfinder_for_roadvehs) { - case VPF_YAPF: { // YAPF - bool found = YapfFindNearestRoadDepot(v, max_distance, &rfdd.tile); - rfdd.best_length = found ? max_distance / 2 : UINT_MAX; // some fake distance or NOT_FOUND - } break; - - case VPF_NPF: { // NPF - /* See where we are now */ - Trackdir trackdir = v->GetVehicleTrackdir(); - - NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, v->tile, ReverseTrackdir(trackdir), false, TRANSPORT_ROAD, v->compatible_roadtypes, v->owner, INVALID_RAILTYPES, 0); + case VPF_NPF: return NPFRoadVehicleFindNearestDepot(v, max_distance); + case VPF_YAPF: return YapfRoadVehicleFindNearestDepot(v, max_distance); - if (ftd.best_bird_dist == 0) { - rfdd.tile = ftd.node.tile; - rfdd.best_length = ftd.best_path_dist / NPF_TILE_LENGTH; - } - } break; - - default: - NOT_REACHED(); + default: NOT_REACHED(); } - - return rfdd; // Target not found } bool RoadVehicle::FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse) { - RoadFindDepotData rfdd = FindClosestRoadDepot(this, 0); + FindDepotData rfdd = FindClosestRoadDepot(this, 0); if (rfdd.best_length == UINT_MAX) return false; if (location != NULL) *location = rfdd.tile; @@ -973,15 +928,6 @@ return i; } -static inline NPFFoundTargetData PerfNPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData *target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) -{ - void *perf = NpfBeginInterval(); - NPFFoundTargetData ret = NPFRouteToStationOrTile(tile, trackdir, ignore_start_tile, target, type, sub_type, owner, railtypes); - int t = NpfEndInterval(perf); - DEBUG(yapf, 4, "[NPFR] %d us - %d rounds - %d open - %d closed -- ", t, 0, _aystar_stats_open_size, _aystar_stats_closed_size); - return ret; -} - /** * Returns direction to for a road vehicle to take or * INVALID_TRACKDIR if the direction is currently blocked @@ -1071,36 +1017,10 @@ } switch (_settings_game.pf.pathfinder_for_roadvehs) { - case VPF_YAPF: { // YAPF - Trackdir trackdir = YapfChooseRoadTrack(v, tile, enterdir); - if (trackdir != INVALID_TRACKDIR) return_track(trackdir); - return_track(PickRandomBit(trackdirs)); - } break; - - case VPF_NPF: { // NPF - NPFFindStationOrTileData fstd; - - NPFFillWithOrderData(&fstd, v); - Trackdir trackdir = DiagDirToDiagTrackdir(enterdir); - /* debug("Finding path. Enterdir: %d, Trackdir: %d", enterdir, trackdir); */ + case VPF_NPF: return_track(NPFRoadVehicleChooseTrack(v, tile, enterdir, trackdirs)); + case VPF_YAPF: return_track(YapfRoadVehicleChooseTrack(v, tile, enterdir, trackdirs)); - NPFFoundTargetData ftd = PerfNPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_ROAD, v->compatible_roadtypes, v->owner, INVALID_RAILTYPES); - if (ftd.best_trackdir == INVALID_TRACKDIR) { - /* We are already at our target. Just do something - * @todo: maybe display error? - * @todo: go straight ahead if possible? */ - return_track(FindFirstBit2x64(trackdirs)); - } else { - /* If ftd.best_bird_dist is 0, we found our target and ftd.best_trackdir contains - * the direction we need to take to get there, if ftd.best_bird_dist is not 0, - * we did not find our target, but ftd.best_trackdir contains the direction leading - * to the tile closest to our target. */ - return_track(ftd.best_trackdir); - } - } break; - - default: - NOT_REACHED(); + default: NOT_REACHED(); } found_best_track:; @@ -1771,7 +1691,7 @@ return; } - RoadFindDepotData rfdd = FindClosestRoadDepot(v, MAX_ACCEPTABLE_DEPOT_DIST); + FindDepotData rfdd = FindClosestRoadDepot(v, MAX_ACCEPTABLE_DEPOT_DIST); /* Only go to the depot if it is not too far out of our way. */ if (rfdd.best_length == UINT_MAX || rfdd.best_length > MAX_ACCEPTABLE_DEPOT_DIST) { if (v->current_order.IsType(OT_GOTO_DEPOT)) {
--- a/src/ship_cmd.cpp +++ b/src/ship_cmd.cpp @@ -369,7 +369,7 @@ switch (_settings_game.pf.pathfinder_for_ships) { case VPF_OPF: return OPFShipChooseTrack(v, tile, enterdir, tracks); case VPF_NPF: return NPFShipChooseTrack(v, tile, enterdir, tracks); - case VPF_YAPF: return YapfChooseShipTrack(v, tile, enterdir, tracks); + case VPF_YAPF: return YapfShipChooseTrack(v, tile, enterdir, tracks); default: NOT_REACHED(); } }