diff options
Diffstat (limited to 'src/pathfinder/npf')
-rw-r--r-- | src/pathfinder/npf/npf.cpp | 120 | ||||
-rw-r--r-- | src/pathfinder/npf/npf.h | 9 | ||||
-rw-r--r-- | src/pathfinder/npf/npf_func.h | 45 |
3 files changed, 143 insertions, 31 deletions
diff --git a/src/pathfinder/npf/npf.cpp b/src/pathfinder/npf/npf.cpp index 13410a0f5..f50106fb2 100644 --- a/src/pathfinder/npf/npf.cpp +++ b/src/pathfinder/npf/npf.cpp @@ -21,6 +21,7 @@ #include "../../train.h" #include "../../ship.h" #include "../pathfinder_func.h" +#include "../pathfinder_type.h" #include "npf.h" static AyStar _npf_aystar; @@ -1059,30 +1060,6 @@ NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, return best_result; } -NPFFoundTargetData NPFRouteToSafeTile(const Train *v, TileIndex tile, Trackdir trackdir, bool override_railtype) -{ - assert(v->type == VEH_TRAIN); - - NPFFindStationOrTileData fstd; - fstd.v = v; - fstd.reserve_path = true; - - AyStarNode start1; - start1.tile = tile; - /* We set this in case the target is also the start tile, we will just - * return a not found then */ - start1.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; - start1.direction = trackdir; - NPFSetFlag(&start1, NPF_FLAG_IGNORE_RESERVED, true); - - RailTypes railtypes = v->compatible_railtypes; - if (override_railtype) railtypes |= GetRailTypeInfo(v->railtype)->compatible_railtypes; - - /* perform a breadth first search. Target is NULL, - * since we are just looking for any safe tile...*/ - return NPFRouteInternal(&start1, true, NULL, false, &fstd, NPFFindSafeTile, NPFCalcZero, TRANSPORT_RAIL, 0, v->owner, railtypes, 0); -} - void InitializeNPF() { static bool first_init = true; @@ -1139,3 +1116,98 @@ Track NPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, if (ftd.best_trackdir == 0xff) return INVALID_TRACK; return TrackdirToTrack(ftd.best_trackdir); } + +/*** Trains ***/ + +FindDepotData NPFTrainFindNearestDepot(const Train *v, int max_distance) +{ + const Train *last = v->Last(); + Trackdir trackdir = v->GetVehicleTrackdir(); + Trackdir trackdir_rev = ReverseTrackdir(last->GetVehicleTrackdir()); + + 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(); + + /* 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, NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)); +} + +bool NPFTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir trackdir, bool override_railtype) +{ + assert(v->type == VEH_TRAIN); + + NPFFindStationOrTileData fstd; + fstd.v = v; + fstd.reserve_path = true; + + AyStarNode start1; + start1.tile = tile; + /* We set this in case the target is also the start tile, we will just + * return a not found then */ + start1.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; + start1.direction = trackdir; + NPFSetFlag(&start1, NPF_FLAG_IGNORE_RESERVED, true); + + RailTypes railtypes = v->compatible_railtypes; + if (override_railtype) railtypes |= GetRailTypeInfo(v->railtype)->compatible_railtypes; + + /* perform a breadth first search. Target is NULL, + * since we are just looking for any safe tile...*/ + return NPFRouteInternal(&start1, true, NULL, false, &fstd, NPFFindSafeTile, NPFCalcZero, TRANSPORT_RAIL, 0, v->owner, railtypes, 0).res_okay; +} + +bool NPFTrainCheckReverse(const Train *v) +{ + NPFFindStationOrTileData fstd; + NPFFoundTargetData ftd; + const Train *last = v->Last(); + + NPFFillWithOrderData(&fstd, v); + + Trackdir trackdir = v->GetVehicleTrackdir(); + Trackdir trackdir_rev = ReverseTrackdir(last->GetVehicleTrackdir()); + assert(trackdir != INVALID_TRACKDIR); + assert(trackdir_rev != INVALID_TRACKDIR); + + ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, &fstd, TRANSPORT_RAIL, 0, v->owner, v->compatible_railtypes); + /* If we didn't find anything, just keep on going straight ahead, otherwise take the reverse flag */ + return ftd.best_bird_dist != 0 && NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE); +} + +Track NPFTrainChooseTrack(const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found, bool reserve_track, struct PBSTileInfo *target) +{ + NPFFindStationOrTileData fstd; + NPFFillWithOrderData(&fstd, v, reserve_track); + + PBSTileInfo origin = FollowTrainReservation(v); + assert(IsValidTrackdir(origin.trackdir)); + + NPFFoundTargetData ftd = NPFRouteToStationOrTile(origin.tile, origin.trackdir, true, &fstd, TRANSPORT_RAIL, 0, v->owner, v->compatible_railtypes); + + if (target != NULL) { + target->tile = ftd.node.tile; + target->trackdir = (Trackdir)ftd.node.direction; + target->okay = ftd.res_okay; + } + + 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? */ + if (path_not_found) *path_not_found = false; + return FindFirstTrack(tracks); + } + + /* 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. */ + if (path_not_found != NULL) *path_not_found = (ftd.best_bird_dist != 0); + /* Discard enterdir information, making it a normal track */ + return TrackdirToTrack(ftd.best_trackdir); +} diff --git a/src/pathfinder/npf/npf.h b/src/pathfinder/npf/npf.h index fcd75db4d..fb10c07ec 100644 --- a/src/pathfinder/npf/npf.h +++ b/src/pathfinder/npf/npf.h @@ -38,7 +38,8 @@ enum { }; enum { - /** This penalty is the equivalent of "inifite", which means that paths that + /** + * This penalty is the equivalent of "infite", which means that paths that * get this penalty will be chosen, but only if there is no other route * without it. Be careful with not applying this penalty to often, or the * total path cost might overflow.. @@ -119,12 +120,6 @@ NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir t * of choices and accurate heuristics, such as water. */ NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); -/** - * Search for any safe tile using a breadth first search and try to reserve a path. - */ -NPFFoundTargetData NPFRouteToSafeTile(const struct Train *v, TileIndex tile, Trackdir trackdir, bool override_railtype); - - void NPFFillWithOrderData(NPFFindStationOrTileData *fstd, const Vehicle *v, bool reserve_path = false); diff --git a/src/pathfinder/npf/npf_func.h b/src/pathfinder/npf/npf_func.h index ef3b1001c..027e8c794 100644 --- a/src/pathfinder/npf/npf_func.h +++ b/src/pathfinder/npf/npf_func.h @@ -12,6 +12,10 @@ #ifndef NPF_FUNC_H #define NPF_FUNC_H +#include "../../track_type.h" +#include "../../direction_type.h" +#include "../pathfinder_type.h" + /** * Finds the best path for given ship using NPF. * @param v the ship that needs to find a path @@ -22,4 +26,45 @@ */ Track NPFShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks); +/** + * Used when user sends train to the nearest depot or if train needs servicing using NPF + * @param v train that needs to go to some depot + * @param max_distance max distance (number of track tiles) from the current train 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 NPFTrainFindNearestDepot(const Train *v, int max_distance); + +/** + * Try to extend the reserved path of a train to the nearest safe tile using NPF. + * + * @param v The train that needs to find a safe tile. + * @param tile Last tile of the current reserved path. + * @param td Last trackdir of the current reserved path. + * @param override_railtype Should all physically compatible railtypes be searched, even if the vehicle can't run on them on its own? + * @return True if the path could be extended to a safe tile. + */ +bool NPFTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype); + +/** + * Returns true if it is better to reverse the train before leaving station using NPF. + * @param v the train leaving the station + * @return true if reversing is better + */ +bool NPFTrainCheckReverse(const Train *v); + +/** + * Finds the best path for given train using NPF. + * @param v the train that needs to find a path + * @param tile the tile to find the path from (should be next tile the train is about to enter) + * @param enterdir diagonal direction which the RV will enter this new tile from + * @param tracks available trackdirs on the new tile (to choose from) + * @param path_not_found [out] true is returned if no path can be found (returned Trackdir is only a 'guess') + * @param reserve_track indicates whether YAPF should try to reserve the found path + * @param target [out] the target tile of the reservation, free is set to true if path was reserved + * @return the best track for next turn + */ +Track NPFTrainChooseTrack(const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found, bool reserve_track, struct PBSTileInfo *target); + #endif /* NPF_FUNC_H */ |