From f476d861d2d945d8b873d96999e58416015ba1ec Mon Sep 17 00:00:00 2001 From: frosch Date: Fri, 8 Feb 2008 16:25:55 +0000 Subject: (svn r12085) -Fix(r12058): Road vehicles could get stuck, when NPF told them to reverse on junction tiles. (spotted by SmatZ) --- src/npf.cpp | 34 +++++++++++++++++++++++----------- src/npf.h | 17 +++++++++-------- src/roadveh_cmd.cpp | 10 +++++----- src/ship_cmd.cpp | 9 ++++----- src/train_cmd.cpp | 6 +++--- 5 files changed, 44 insertions(+), 32 deletions(-) (limited to 'src') diff --git a/src/npf.cpp b/src/npf.cpp index 9dd06f19f..ea49c075f 100644 --- a/src/npf.cpp +++ b/src/npf.cpp @@ -655,6 +655,11 @@ static void NPFFollowTrack(AyStar* aystar, OpenListNode* current) TileIndex src_tile = current->path.node.tile; DiagDirection src_exitdir = TrackdirToExitdir(src_trackdir); + /* Is src_tile valid, and can be used? + * When choosing track on a junction src_tile is the tile neighboured to the junction wrt. exitdir. + * But we must not check the validity of this move, as src_tile is totally unrelated to the move, if a roadvehicle reversed on a junction. */ + bool ignore_src_tile = (current->path.parent == NULL && NPFGetFlag(¤t->path.node, NPF_FLAG_IGNORE_START_TILE)); + /* Information about the vehicle: TransportType (road/rail/water) and SubType (compatible rail/road types) */ TransportType type = (TransportType)aystar->user_data[NPF_TYPE]; uint subtype = aystar->user_data[NPF_SUB_TYPE]; @@ -668,7 +673,11 @@ static void NPFFollowTrack(AyStar* aystar, OpenListNode* current) TrackdirBits trackdirbits; /* Find dest tile */ - if (IsTileType(src_tile, MP_TUNNELBRIDGE) && GetTunnelBridgeDirection(src_tile) == src_exitdir) { + if (ignore_src_tile) { + /* Do not perform any checks that involve src_tile */ + dst_tile = src_tile + TileOffsByDiagDir(src_exitdir); + trackdirbits = GetDriveableTrackdirBits(dst_tile, src_trackdir, type, subtype); + } else if (IsTileType(src_tile, MP_TUNNELBRIDGE) && GetTunnelBridgeDirection(src_tile) == src_exitdir) { /* We drive through the wormhole and arrive on the other side */ dst_tile = GetOtherTunnelBridgeEnd(src_tile); trackdirbits = TrackdirToTrackdirBits(src_trackdir); @@ -740,7 +749,7 @@ static void NPFFollowTrack(AyStar* aystar, OpenListNode* current) * multiple targets that are spread around, we should perform a breadth first * search by specifiying CalcZero as our heuristic. */ -static NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty) +static NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, bool ignore_start_tile1, AyStarNode* start2, bool ignore_start_tile2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty) { int r; NPFFoundTargetData result; @@ -760,10 +769,12 @@ static NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start /* Initialize Start Node(s) */ start1->user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; start1->user_data[NPF_NODE_FLAGS] = 0; + NPFSetFlag(start1, NPF_FLAG_IGNORE_START_TILE, ignore_start_tile1); _npf_aystar.addstart(&_npf_aystar, start1, 0); if (start2) { start2->user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; start2->user_data[NPF_NODE_FLAGS] = 0; + NPFSetFlag(start2, NPF_FLAG_IGNORE_START_TILE, ignore_start_tile2); NPFSetFlag(start2, NPF_FLAG_REVERSE, true); _npf_aystar.addstart(&_npf_aystar, start2, reverse_penalty); } @@ -799,7 +810,7 @@ static NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start return result; } -NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) +NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) { AyStarNode start1; AyStarNode start2; @@ -813,15 +824,15 @@ NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir track start2.direction = trackdir2; start2.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; - return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, sub_type, owner, railtypes, 0); + return NPFRouteInternal(&start1, ignore_start_tile1, (IsValidTile(tile2) ? &start2 : NULL), ignore_start_tile2, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, sub_type, owner, railtypes, 0); } -NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) +NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) { - return NPFRouteToStationOrTileTwoWay(tile, trackdir, INVALID_TILE, INVALID_TRACKDIR, target, type, sub_type, owner, railtypes); + return NPFRouteToStationOrTileTwoWay(tile, trackdir, ignore_start_tile, INVALID_TILE, INVALID_TRACKDIR, false, target, type, sub_type, owner, railtypes); } -NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty) +NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty) { AyStarNode start1; AyStarNode start2; @@ -837,15 +848,15 @@ NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir t /* perform a breadth first search. Target is NULL, * since we are just looking for any depot...*/ - return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), NULL, NPFFindDepot, NPFCalcZero, type, sub_type, owner, railtypes, reverse_penalty); + return NPFRouteInternal(&start1, ignore_start_tile1, (IsValidTile(tile2) ? &start2 : NULL), ignore_start_tile2, NULL, NPFFindDepot, NPFCalcZero, type, sub_type, owner, railtypes, reverse_penalty); } -NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) +NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) { - return NPFRouteToDepotBreadthFirstTwoWay(tile, trackdir, INVALID_TILE, INVALID_TRACKDIR, type, sub_type, owner, railtypes, 0); + return NPFRouteToDepotBreadthFirstTwoWay(tile, trackdir, ignore_start_tile, INVALID_TILE, INVALID_TRACKDIR, false, type, sub_type, owner, railtypes, 0); } -NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) +NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) { /* Okay, what we're gonna do. First, we look at all depots, calculate * the manhatten distance to get to each depot. We then sort them by @@ -920,6 +931,7 @@ NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, * return a not found then */ start.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; start.user_data[NPF_NODE_FLAGS] = 0; + NPFSetFlag(&start, NPF_FLAG_IGNORE_START_TILE, ignore_start_tile); _npf_aystar.addstart(&_npf_aystar, &start, 0); /* Initialize result */ diff --git a/src/npf.h b/src/npf.h index 10f55a6d8..8448c30b5 100644 --- a/src/npf.h +++ b/src/npf.h @@ -60,9 +60,10 @@ enum { /* Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. Use NPFGetBit() and NPFGetBit() to use them. */ enum NPFNodeFlag { - NPF_FLAG_SEEN_SIGNAL, ///< Used to mark that a signal was seen on the way, for rail only - NPF_FLAG_REVERSE, ///< Used to mark that this node was reached from the second start node, if applicable - NPF_FLAG_LAST_SIGNAL_RED, ///< Used to mark that the last signal on this path was red + NPF_FLAG_SEEN_SIGNAL, ///< Used to mark that a signal was seen on the way, for rail only + NPF_FLAG_REVERSE, ///< Used to mark that this node was reached from the second start node, if applicable + NPF_FLAG_LAST_SIGNAL_RED, ///< Used to mark that the last signal on this path was red + NPF_FLAG_IGNORE_START_TILE, ///< Used to mark that the start tile is invalid, and searching should start from the second tile on }; /* Meant to be stored in AyStar.userpath */ @@ -78,28 +79,28 @@ struct NPFFoundTargetData { /* Will search from the given tile and direction, for a route to the given * station for the given transport type. See the declaration of * NPFFoundTargetData above for the meaning of the result. */ -NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); +NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); /* Will search as above, but with two start nodes, the second being the * reverse. Look at the NPF_FLAG_REVERSE flag in the result node to see which * direction was taken (NPFGetBit(result.node, NPF_FLAG_REVERSE)) */ -NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); +NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); /* Will search a route to the closest depot. */ /* Search using breadth first. Good for little track choice and inaccurate * heuristic, such as railway/road.*/ -NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); +NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); /* Same as above but with two start nodes, the second being the reverse. Call * NPFGetBit(result.node, NPF_FLAG_REVERSE) to see from which node the path * orginated. All pathfs from the second node will have the given * reverse_penalty applied (NPF_TILE_LENGTH is the equivalent of one full * tile). */ -NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty); +NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty); /* Search by trying each depot in order of Manhattan Distance. Good for lots * of choices and accurate heuristics, such as water. */ -NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); +NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes); void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v); diff --git a/src/roadveh_cmd.cpp b/src/roadveh_cmd.cpp index 6455e1c5e..5a432837c 100644 --- a/src/roadveh_cmd.cpp +++ b/src/roadveh_cmd.cpp @@ -424,7 +424,7 @@ static const Depot* FindClosestRoadDepot(const Vehicle* v) /* See where we are now */ Trackdir trackdir = GetVehicleTrackdir(v); - ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, v->tile, ReverseTrackdir(trackdir), TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES, 0); + ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, v->tile, ReverseTrackdir(trackdir), false, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES, 0); if (ftd.best_bird_dist == 0) { return GetDepotByTile(ftd.node.tile); /* Target found */ } else { @@ -1128,11 +1128,11 @@ static bool EnumRoadTrackFindDist(TileIndex tile, void* data, Trackdir trackdir, return false; } -static inline NPFFoundTargetData PerfNPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, NPFFindStationOrTileData* target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes) +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, target, type, sub_type, owner, railtypes); + 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; @@ -1230,7 +1230,7 @@ static Trackdir RoadFindPathToDest(Vehicle* v, TileIndex tile, DiagDirection ent trackdir = DiagdirToDiagTrackdir(enterdir); //debug("Finding path. Enterdir: %d, Trackdir: %d", enterdir, trackdir); - ftd = PerfNPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, &fstd, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES); + ftd = PerfNPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_ROAD, v->u.road.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? @@ -1312,7 +1312,7 @@ static uint RoadFindPathToStop(const Vehicle *v, TileIndex tile) fstd.dest_coords = tile; fstd.station_index = INVALID_STATION; // indicates that the destination is a tile, not a station - dist = NPFRouteToStationOrTile(v->tile, trackdir, &fstd, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES).best_path_dist; + dist = NPFRouteToStationOrTile(v->tile, trackdir, false, &fstd, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES).best_path_dist; /* change units from NPF_TILE_LENGTH to # of tiles */ if (dist != UINT_MAX) dist = (dist + NPF_TILE_LENGTH - 1) / NPF_TILE_LENGTH; diff --git a/src/ship_cmd.cpp b/src/ship_cmd.cpp index 530512727..45341e149 100644 --- a/src/ship_cmd.cpp +++ b/src/ship_cmd.cpp @@ -123,7 +123,7 @@ static const Depot* FindClosestShipDepot(const Vehicle* v) if (_patches.new_pathfinding_all) { NPFFoundTargetData ftd; Trackdir trackdir = GetVehicleTrackdir(v); - ftd = NPFRouteToDepotTrialError(v->tile, trackdir, TRANSPORT_WATER, 0, v->owner, INVALID_RAILTYPES); + ftd = NPFRouteToDepotTrialError(v->tile, trackdir, false, TRANSPORT_WATER, 0, v->owner, INVALID_RAILTYPES); if (ftd.best_bird_dist == 0) { best_depot = GetDepotByTile(ftd.node.tile); /* Found target */ } else { @@ -510,11 +510,11 @@ bad:; return best_bird_dist; } -static inline NPFFoundTargetData PerfNPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner, RailTypes railtypes) +static inline NPFFoundTargetData PerfNPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData* target, TransportType type, Owner owner, RailTypes railtypes) { void* perf = NpfBeginInterval(); - NPFFoundTargetData ret = NPFRouteToStationOrTile(tile, trackdir, target, type, 0, owner, railtypes); + NPFFoundTargetData ret = NPFRouteToStationOrTile(tile, trackdir, ignore_start_tile, target, type, 0, owner, railtypes); int t = NpfEndInterval(perf); DEBUG(yapf, 4, "[NPFW] %d us - %d rounds - %d open - %d closed -- ", t, 0, _aystar_stats_open_size, _aystar_stats_closed_size); return ret; @@ -533,13 +533,12 @@ static Track ChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, } else if (_patches.new_pathfinding_all) { NPFFindStationOrTileData fstd; NPFFoundTargetData ftd; - TileIndex src_tile = TILE_ADD(tile, TileOffsByDiagDir(ReverseDiagDir(enterdir))); Trackdir trackdir = GetVehicleTrackdir(v); assert(trackdir != INVALID_TRACKDIR); // Check that we are not in a depot NPFFillWithOrderData(&fstd, v); - ftd = PerfNPFRouteToStationOrTile(src_tile, trackdir, &fstd, TRANSPORT_WATER, v->owner, INVALID_RAILTYPES); + ftd = PerfNPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_WATER, v->owner, INVALID_RAILTYPES); if (ftd.best_trackdir != 0xff) { /* If ftd.best_bird_dist is 0, we found our target and ftd.best_trackdir contains diff --git a/src/train_cmd.cpp b/src/train_cmd.cpp index a4c730939..db7a4fe9d 100644 --- a/src/train_cmd.cpp +++ b/src/train_cmd.cpp @@ -2019,7 +2019,7 @@ static TrainFindDepotData FindClosestTrainDepot(Vehicle *v, int max_distance) Trackdir trackdir_rev = ReverseTrackdir(GetVehicleTrackdir(last)); assert(trackdir != INVALID_TRACKDIR); - NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, last->tile, trackdir_rev, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes, NPF_INFINITE_PENALTY); + 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); if (ftd.best_bird_dist == 0) { /* Found target */ tfdd.tile = ftd.node.tile; @@ -2379,7 +2379,7 @@ static Track ChooseTrainTrack(Vehicle* v, TileIndex tile, DiagDirection enterdir Trackdir trackdir = GetVehicleTrackdir(v); assert(trackdir != 0xff); - NPFFoundTargetData ftd = NPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, &fstd, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes); + NPFFoundTargetData ftd = NPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes); if (ftd.best_trackdir == 0xff) { /* We are already at our target. Just do something @@ -2489,7 +2489,7 @@ static bool CheckReverseTrain(Vehicle *v) assert(trackdir != 0xff); assert(trackdir_rev != 0xff); - ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, last->tile, trackdir_rev, &fstd, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes); + ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, false, last->tile, trackdir_rev, false, &fstd, TRANSPORT_RAIL, 0, v->owner, v->u.rail.compatible_railtypes); if (ftd.best_bird_dist != 0) { /* We didn't find anything, just keep on going straight ahead */ reverse_best = false; -- cgit v1.2.3-70-g09d2