KUDr@3900: /* $Id$ */ KUDr@3900: rubidium@10455: /** @file yapf_rail.cpp The rail pathfinding. */ celestar@6447: KUDr@3900: #include "../stdafx.h" KUDr@3900: KUDr@3900: #include "yapf.hpp" KUDr@3900: #include "yapf_node_rail.hpp" KUDr@3900: #include "yapf_costrail.hpp" KUDr@3900: #include "yapf_destrail.hpp" rubidium@9723: #include "../vehicle_func.h" KUDr@3900: rubidium@9631: #define DEBUG_YAPF_CACHE 0 rubidium@9631: KUDr@3900: int _total_pf_time_us = 0; KUDr@3900: KUDr@3900: KUDr@3900: KUDr@3900: KUDr@3900: KUDr@3900: template KUDr@3900: class CYapfFollowAnyDepotRailT KUDr@3900: { KUDr@3900: public: KUDr@3914: typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) KUDr@3900: typedef typename Types::TrackFollower TrackFollower; KUDr@3914: typedef typename Types::NodeList::Titem Node; ///< this will be our node type KUDr@3914: typedef typename Node::Key Key; ///< key to hash tables KUDr@3900: KUDr@3900: protected: KUDr@3914: /// to access inherited path finder KUDr@3900: FORCEINLINE Tpf& Yapf() {return *static_cast(this);} KUDr@3900: KUDr@3900: public: KUDr@3914: /** Called by YAPF to move from the given node to the next tile. For each rubidium@4549: * reachable trackdir on the new tile creates new node, initializes it rubidium@4549: * and adds it to the open list by calling Yapf().AddNewNode(n) */ KUDr@3900: inline void PfFollowNode(Node& old_node) KUDr@3900: { KUDr@3900: TrackFollower F(Yapf().GetVehicle()); KUDr@3900: if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) KUDr@6458: Yapf().AddMultipleNodes(&old_node, F); KUDr@3900: } KUDr@3900: KUDr@3914: /// return debug report character to identify the transportation type KUDr@3900: FORCEINLINE char TransportTypeChar() const {return 't';} KUDr@3900: glx@10829: static bool stFindNearestDepotTwoWay(const Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed) KUDr@3900: { rubidium@9631: Tpf pf1; rubidium@9631: bool result1 = pf1.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, depot_tile, reversed); rubidium@9631: rubidium@9631: #if DEBUG_YAPF_CACHE rubidium@9631: Tpf pf2; rubidium@9631: TileIndex depot_tile2 = INVALID_TILE; rubidium@9631: bool reversed2 = false; rubidium@9631: pf2.DisableCache(true); rubidium@9631: bool result2 = pf2.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, &depot_tile2, &reversed2); rubidium@9631: if (result1 != result2 || (result1 && (*depot_tile != depot_tile2 || *reversed != reversed2))) { rubidium@9631: DEBUG(yapf, 0, "CACHE ERROR: FindNearestDepotTwoWay() = [%s, %s]", result1 ? "T" : "F", result2 ? "T" : "F"); rubidium@9631: } rubidium@9631: #endif rubidium@9631: rubidium@9631: return result1; KUDr@3900: } KUDr@3900: glx@10829: FORCEINLINE bool FindNearestDepotTwoWay(const Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed) KUDr@3900: { KUDr@3900: // set origin and destination nodes KUDr@3900: Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, true); KUDr@3900: Yapf().SetDestination(v); KUDr@3923: Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance); KUDr@3900: KUDr@3900: // find the best path KUDr@3900: bool bFound = Yapf().FindPath(v); KUDr@3900: if (!bFound) return false; KUDr@3900: KUDr@3900: // some path found KUDr@3900: // get found depot tile rubidium@9601: Node *n = Yapf().GetBestNode(); rubidium@9601: *depot_tile = n->GetLastTile(); KUDr@3900: KUDr@3900: // walk through the path back to the origin rubidium@9601: Node *pNode = n; KUDr@3900: while (pNode->m_parent != NULL) { KUDr@3900: pNode = pNode->m_parent; KUDr@3900: } KUDr@3900: KUDr@3900: // if the origin node is our front vehicle tile/Trackdir then we didn't reverse KUDr@3900: // but we can also look at the cost (== 0 -> not reversed, == reverse_penalty -> reversed) KUDr@3900: *reversed = (pNode->m_cost != 0); KUDr@3900: KUDr@3900: return true; KUDr@3900: } KUDr@3900: }; KUDr@3900: KUDr@3900: template KUDr@3900: class CYapfFollowRailT KUDr@3900: { KUDr@3900: public: KUDr@3914: typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) KUDr@3900: typedef typename Types::TrackFollower TrackFollower; KUDr@3914: typedef typename Types::NodeList::Titem Node; ///< this will be our node type KUDr@3914: typedef typename Node::Key Key; ///< key to hash tables KUDr@3900: KUDr@3900: protected: KUDr@3914: /// to access inherited path finder KUDr@3900: FORCEINLINE Tpf& Yapf() {return *static_cast(this);} KUDr@3900: KUDr@3900: public: KUDr@3914: /** Called by YAPF to move from the given node to the next tile. For each rubidium@4549: * reachable trackdir on the new tile creates new node, initializes it rubidium@4549: * and adds it to the open list by calling Yapf().AddNewNode(n) */ KUDr@3900: inline void PfFollowNode(Node& old_node) KUDr@3900: { KUDr@3900: TrackFollower F(Yapf().GetVehicle()); KUDr@3900: if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) KUDr@6458: Yapf().AddMultipleNodes(&old_node, F); KUDr@3900: } KUDr@3900: KUDr@3914: /// return debug report character to identify the transportation type KUDr@3900: FORCEINLINE char TransportTypeChar() const {return 't';} KUDr@3900: glx@10829: static Trackdir stChooseRailTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found) KUDr@3900: { KUDr@3900: // create pathfinder instance rubidium@9631: Tpf pf1; rubidium@9631: Trackdir result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_not_found); rubidium@9631: rubidium@9631: #if DEBUG_YAPF_CACHE rubidium@9631: Tpf pf2; rubidium@9631: pf2.DisableCache(true); rubidium@9631: Trackdir result2 = pf2.ChooseRailTrack(v, tile, enterdir, tracks, path_not_found); rubidium@9631: if (result1 != result2) { rubidium@9631: DEBUG(yapf, 0, "CACHE ERROR: ChooseRailTrack() = [%d, %d]", result1, result2); rubidium@9631: DumpTarget dmp1, dmp2; rubidium@9631: pf1.DumpBase(dmp1); rubidium@9631: pf2.DumpBase(dmp2); rubidium@9631: FILE *f1 = fopen("C:\\yapf1.txt", "wt"); rubidium@9631: FILE *f2 = fopen("C:\\yapf2.txt", "wt"); rubidium@9631: fwrite(dmp1.m_out.Data(), 1, dmp1.m_out.Size(), f1); rubidium@9631: fwrite(dmp2.m_out.Data(), 1, dmp2.m_out.Size(), f2); rubidium@9631: fclose(f1); rubidium@9631: fclose(f2); rubidium@9631: } rubidium@9631: #endif rubidium@9631: rubidium@9631: return result1; KUDr@3900: } KUDr@3900: glx@10829: FORCEINLINE Trackdir ChooseRailTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found) KUDr@3900: { KUDr@3900: // set origin and destination nodes KUDr@3900: Yapf().SetOrigin(v->tile, GetVehicleTrackdir(v), INVALID_TILE, INVALID_TRACKDIR, 1, true); KUDr@3900: Yapf().SetDestination(v); KUDr@3900: KUDr@3900: // find the best path KUDr@4870: bool path_found = Yapf().FindPath(v); KUDr@5675: if (path_not_found != NULL) { KUDr@4870: // tell controller that the path was only 'guessed' KUDr@5675: // treat the path as found if stopped on the first two way signal(s) KUDr@5675: *path_not_found = !(path_found || Yapf().m_stopped_on_first_two_way_signal); KUDr@4870: } KUDr@3900: KUDr@3900: // if path not found - return INVALID_TRACKDIR KUDr@3900: Trackdir next_trackdir = INVALID_TRACKDIR; rubidium@9601: Node *pNode = Yapf().GetBestNode(); KUDr@3900: if (pNode != NULL) { KUDr@3900: // path was found or at least suggested KUDr@3900: // walk through the path back to the origin KUDr@3900: Node* pPrev = NULL; KUDr@3900: while (pNode->m_parent != NULL) { KUDr@3900: pPrev = pNode; KUDr@3900: pNode = pNode->m_parent; KUDr@3900: } KUDr@3900: // return trackdir from the best origin node (one of start nodes) KUDr@3900: Node& best_next_node = *pPrev; KUDr@3900: assert(best_next_node.GetTile() == tile); KUDr@3900: next_trackdir = best_next_node.GetTrackdir(); KUDr@3900: } KUDr@3900: return next_trackdir; KUDr@3900: } KUDr@3900: glx@10829: static bool stCheckReverseTrain(const Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int reverse_penalty) KUDr@3900: { rubidium@9631: Tpf pf1; glx@9732: bool result1 = pf1.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty); rubidium@9631: rubidium@9631: #if DEBUG_YAPF_CACHE rubidium@9631: Tpf pf2; rubidium@9631: pf2.DisableCache(true); glx@9732: bool result2 = pf2.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty); rubidium@9631: if (result1 != result2) { rubidium@9631: DEBUG(yapf, 0, "CACHE ERROR: CheckReverseTrain() = [%s, %s]", result1 ? "T" : "F", result2 ? "T" : "F"); rubidium@9631: } rubidium@9631: #endif rubidium@9631: rubidium@9631: return result1; KUDr@3900: } KUDr@3900: glx@10829: FORCEINLINE bool CheckReverseTrain(const Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int reverse_penalty) KUDr@3900: { KUDr@3900: // create pathfinder instance KUDr@3900: // set origin and destination nodes glx@9732: Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, false); KUDr@3900: Yapf().SetDestination(v); KUDr@3900: KUDr@3900: // find the best path KUDr@3900: bool bFound = Yapf().FindPath(v); KUDr@3900: KUDr@3900: if (!bFound) return false; KUDr@3900: KUDr@3900: // path was found KUDr@3900: // walk through the path back to the origin rubidium@9601: Node *pNode = Yapf().GetBestNode(); KUDr@3900: while (pNode->m_parent != NULL) { KUDr@3900: pNode = pNode->m_parent; KUDr@3900: } KUDr@3900: KUDr@3900: // check if it was reversed origin KUDr@3900: Node& best_org_node = *pNode; KUDr@3900: bool reversed = (best_org_node.m_cost != 0); KUDr@3900: return reversed; KUDr@3900: } KUDr@3900: }; KUDr@3900: KUDr@3900: template class TdestinationT, template class TfollowT> KUDr@3900: struct CYapfRail_TypesT KUDr@3900: { KUDr@3900: typedef CYapfRail_TypesT Types; KUDr@3900: KUDr@3900: typedef Tpf_ Tpf; KUDr@3900: typedef Ttrack_follower TrackFollower; KUDr@3900: typedef Tnode_list NodeList; KUDr@3900: typedef CYapfBaseT PfBase; KUDr@3900: typedef TfollowT PfFollow; KUDr@3900: typedef CYapfOriginTileTwoWayT PfOrigin; KUDr@3900: typedef TdestinationT PfDestination; KUDr@3900: typedef CYapfSegmentCostCacheGlobalT PfCache; KUDr@3900: typedef CYapfCostRailT PfCost; KUDr@3900: }; KUDr@3900: KUDr@3900: struct CYapfRail1 : CYapfT > {}; glx@9629: struct CYapfRail2 : CYapfT > {}; KUDr@3900: KUDr@3900: struct CYapfAnyDepotRail1 : CYapfT > {}; glx@9629: struct CYapfAnyDepotRail2 : CYapfT > {}; KUDr@3900: KUDr@3900: glx@10829: Trackdir YapfChooseRailTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found) KUDr@3900: { KUDr@3900: // default is YAPF type 2 glx@10829: typedef Trackdir (*PfnChooseRailTrack)(const Vehicle*, TileIndex, DiagDirection, TrackBits, bool*); glx@9629: PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack; KUDr@3900: KUDr@3900: // check if non-default YAPF type needed glx@10776: if (_settings_game.pf.forbid_90_deg) { glx@9629: pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack; // Trackdir, forbid 90-deg glx@9629: } KUDr@3900: rubidium@5838: Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, tracks, path_not_found); KUDr@3900: KUDr@3900: return td_ret; KUDr@3900: } KUDr@3900: glx@10829: bool YapfCheckReverseTrain(const Vehicle* v) KUDr@3900: { glx@9732: /* last wagon */ glx@10829: const Vehicle *last_veh = GetLastVehicleInChain(v); glx@9732: KUDr@3900: // get trackdirs of both ends KUDr@3900: Trackdir td = GetVehicleTrackdir(v); KUDr@3900: Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh)); KUDr@3900: glx@9732: /* tiles where front and back are */ glx@9732: TileIndex tile = v->tile; glx@9732: TileIndex tile_rev = last_veh->tile; KUDr@3900: glx@9732: int reverse_penalty = 0; glx@9732: glx@9732: if (v->u.rail.track == TRACK_BIT_WORMHOLE) { glx@9732: /* front in tunnel / on bridge */ glx@9732: DiagDirection dir_into_wormhole = GetTunnelBridgeDirection(tile); glx@9732: glx@9732: if (TrackdirToExitdir(td) == dir_into_wormhole) tile = GetOtherTunnelBridgeEnd(tile); glx@9732: /* Now 'tile' is the tunnel entry/bridge ramp the train will reach when driving forward */ glx@9732: glx@9732: /* Current position of the train in the wormhole */ glx@9732: TileIndex cur_tile = TileVirtXY(v->x_pos, v->y_pos); glx@9732: glx@9732: /* Add distance to drive in the wormhole as penalty for the forward path, i.e. bonus for the reverse path glx@9732: * Note: Negative penalties are ok for the start tile. */ glx@9732: reverse_penalty -= DistanceManhattan(cur_tile, tile) * YAPF_TILE_LENGTH; glx@9732: } glx@9732: glx@9732: if (last_veh->u.rail.track == TRACK_BIT_WORMHOLE) { glx@9732: /* back in tunnel / on bridge */ glx@9732: DiagDirection dir_into_wormhole = GetTunnelBridgeDirection(tile_rev); glx@9732: glx@9732: if (TrackdirToExitdir(td_rev) == dir_into_wormhole) tile_rev = GetOtherTunnelBridgeEnd(tile_rev); glx@9732: /* Now 'tile_rev' is the tunnel entry/bridge ramp the train will reach when reversing */ glx@9732: glx@9732: /* Current position of the last wagon in the wormhole */ glx@9732: TileIndex cur_tile = TileVirtXY(last_veh->x_pos, last_veh->y_pos); glx@9732: glx@9732: /* Add distance to drive in the wormhole as penalty for the revere path. */ glx@9732: reverse_penalty += DistanceManhattan(cur_tile, tile_rev) * YAPF_TILE_LENGTH; glx@9732: } glx@9732: glx@10829: typedef bool (*PfnCheckReverseTrain)(const Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir, int); glx@9629: PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail1::stCheckReverseTrain; KUDr@3900: KUDr@3900: // check if non-default YAPF type needed glx@10776: if (_settings_game.pf.forbid_90_deg) { glx@9629: pfnCheckReverseTrain = &CYapfRail2::stCheckReverseTrain; // Trackdir, forbid 90-deg glx@9629: } KUDr@3900: glx@9732: /* slightly hackish: If the pathfinders finds a path, the cost of the first node is tested to distinguish between forward- and reverse-path. */ glx@9732: if (reverse_penalty == 0) reverse_penalty = 1; glx@9732: glx@9732: bool reverse = pfnCheckReverseTrain(v, tile, td, tile_rev, td_rev, reverse_penalty); KUDr@3900: KUDr@3900: return reverse; KUDr@3900: } KUDr@3900: glx@10829: bool YapfFindNearestRailDepotTwoWay(const Vehicle *v, int max_distance, int reverse_penalty, TileIndex *depot_tile, bool *reversed) KUDr@3900: { KUDr@3900: *depot_tile = INVALID_TILE; KUDr@3900: *reversed = false; KUDr@3900: glx@10829: const Vehicle *last_veh = GetLastVehicleInChain(v); KUDr@3900: celestar@5573: TileIndex tile = v->tile; celestar@5573: TileIndex last_tile = last_veh->tile; KUDr@3900: KUDr@3900: // their trackdirs KUDr@4865: Trackdir td = GetVehicleTrackdir(v); KUDr@4865: Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh)); KUDr@3900: glx@10829: typedef bool (*PfnFindNearestDepotTwoWay)(const Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir, int, int, TileIndex*, bool*); glx@9629: PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay; KUDr@3900: KUDr@3900: // check if non-default YAPF type needed glx@10776: if (_settings_game.pf.forbid_90_deg) { glx@9629: pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay; // Trackdir, forbid 90-deg glx@9629: } KUDr@3900: KUDr@3900: bool ret = pfnFindNearestDepotTwoWay(v, tile, td, last_tile, td_rev, max_distance, reverse_penalty, depot_tile, reversed); KUDr@3900: return ret; KUDr@3900: } KUDr@3900: KUDr@3910: /** if any track changes, this counter is incremented - that will invalidate segment cost cache */ KUDr@3900: int CSegmentCostCacheBase::s_rail_change_counter = 0; KUDr@3900: KUDr@3900: void YapfNotifyTrackLayoutChange(TileIndex tile, Track track) {CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);}