1 /* 2 * This file is part of OpenTTD. 3 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2. 4 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 5 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>. 6 */ 7 8 /** @file yapf_common.hpp Commonly used classes for YAPF. */ 9 10 #ifndef YAPF_COMMON_HPP 11 #define YAPF_COMMON_HPP 12 13 /** YAPF origin provider base class - used when origin is one tile / multiple trackdirs */ 14 template <class Types> 15 class CYapfOriginTileT 16 { 17 public: 18 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) 19 typedef typename Types::NodeList::Titem Node; ///< this will be our node type 20 typedef typename Node::Key Key; ///< key to hash tables 21 22 protected: 23 TileIndex m_orgTile; ///< origin tile 24 TrackdirBits m_orgTrackdirs; ///< origin trackdir mask 25 26 /** to access inherited path finder */ Yapf()27 inline Tpf& Yapf() 28 { 29 return *static_cast<Tpf *>(this); 30 } 31 32 public: 33 /** Set origin tile / trackdir mask */ SetOrigin(TileIndex tile,TrackdirBits trackdirs)34 void SetOrigin(TileIndex tile, TrackdirBits trackdirs) 35 { 36 m_orgTile = tile; 37 m_orgTrackdirs = trackdirs; 38 } 39 40 /** Called when YAPF needs to place origin nodes into open list */ PfSetStartupNodes()41 void PfSetStartupNodes() 42 { 43 bool is_choice = (KillFirstBit(m_orgTrackdirs) != TRACKDIR_BIT_NONE); 44 for (TrackdirBits tdb = m_orgTrackdirs; tdb != TRACKDIR_BIT_NONE; tdb = KillFirstBit(tdb)) { 45 Trackdir td = (Trackdir)FindFirstBit2x64(tdb); 46 Node &n1 = Yapf().CreateNewNode(); 47 n1.Set(nullptr, m_orgTile, td, is_choice); 48 Yapf().AddStartupNode(n1); 49 } 50 } 51 }; 52 53 /** YAPF origin provider base class - used when there are two tile/trackdir origins */ 54 template <class Types> 55 class CYapfOriginTileTwoWayT 56 { 57 public: 58 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) 59 typedef typename Types::NodeList::Titem Node; ///< this will be our node type 60 typedef typename Node::Key Key; ///< key to hash tables 61 62 protected: 63 TileIndex m_orgTile; ///< first origin tile 64 Trackdir m_orgTd; ///< first origin trackdir 65 TileIndex m_revTile; ///< second (reversed) origin tile 66 Trackdir m_revTd; ///< second (reversed) origin trackdir 67 int m_reverse_penalty; ///< penalty to be added for using the reversed origin 68 bool m_treat_first_red_two_way_signal_as_eol; ///< in some cases (leaving station) we need to handle first two-way signal differently 69 70 /** to access inherited path finder */ Yapf()71 inline Tpf& Yapf() 72 { 73 return *static_cast<Tpf *>(this); 74 } 75 76 public: 77 /** set origin (tiles, trackdirs, etc.) */ SetOrigin(TileIndex tile,Trackdir td,TileIndex tiler=INVALID_TILE,Trackdir tdr=INVALID_TRACKDIR,int reverse_penalty=0,bool treat_first_red_two_way_signal_as_eol=true)78 void SetOrigin(TileIndex tile, Trackdir td, TileIndex tiler = INVALID_TILE, Trackdir tdr = INVALID_TRACKDIR, int reverse_penalty = 0, bool treat_first_red_two_way_signal_as_eol = true) 79 { 80 m_orgTile = tile; 81 m_orgTd = td; 82 m_revTile = tiler; 83 m_revTd = tdr; 84 m_reverse_penalty = reverse_penalty; 85 m_treat_first_red_two_way_signal_as_eol = treat_first_red_two_way_signal_as_eol; 86 } 87 88 /** Called when YAPF needs to place origin nodes into open list */ PfSetStartupNodes()89 void PfSetStartupNodes() 90 { 91 if (m_orgTile != INVALID_TILE && m_orgTd != INVALID_TRACKDIR) { 92 Node &n1 = Yapf().CreateNewNode(); 93 n1.Set(nullptr, m_orgTile, m_orgTd, false); 94 Yapf().AddStartupNode(n1); 95 } 96 if (m_revTile != INVALID_TILE && m_revTd != INVALID_TRACKDIR) { 97 Node &n2 = Yapf().CreateNewNode(); 98 n2.Set(nullptr, m_revTile, m_revTd, false); 99 n2.m_cost = m_reverse_penalty; 100 Yapf().AddStartupNode(n2); 101 } 102 } 103 104 /** return true if first two-way signal should be treated as dead end */ TreatFirstRedTwoWaySignalAsEOL()105 inline bool TreatFirstRedTwoWaySignalAsEOL() 106 { 107 return Yapf().PfGetSettings().rail_firstred_twoway_eol && m_treat_first_red_two_way_signal_as_eol; 108 } 109 }; 110 111 /** YAPF destination provider base class - used when destination is single tile / multiple trackdirs */ 112 template <class Types> 113 class CYapfDestinationTileT 114 { 115 public: 116 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) 117 typedef typename Types::NodeList::Titem Node; ///< this will be our node type 118 typedef typename Node::Key Key; ///< key to hash tables 119 120 protected: 121 TileIndex m_destTile; ///< destination tile 122 TrackdirBits m_destTrackdirs; ///< destination trackdir mask 123 124 public: 125 /** set the destination tile / more trackdirs */ SetDestination(TileIndex tile,TrackdirBits trackdirs)126 void SetDestination(TileIndex tile, TrackdirBits trackdirs) 127 { 128 m_destTile = tile; 129 m_destTrackdirs = trackdirs; 130 } 131 132 protected: 133 /** to access inherited path finder */ Yapf()134 Tpf& Yapf() 135 { 136 return *static_cast<Tpf *>(this); 137 } 138 139 public: 140 /** Called by YAPF to detect if node ends in the desired destination */ PfDetectDestination(Node & n)141 inline bool PfDetectDestination(Node &n) 142 { 143 return (n.m_key.m_tile == m_destTile) && HasTrackdir(m_destTrackdirs, n.GetTrackdir()); 144 } 145 146 /** 147 * Called by YAPF to calculate cost estimate. Calculates distance to the destination 148 * adds it to the actual cost from origin and stores the sum to the Node::m_estimate 149 */ PfCalcEstimate(Node & n)150 inline bool PfCalcEstimate(Node &n) 151 { 152 static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0}; 153 static const int dg_dir_to_y_offs[] = {0, 1, 0, -1}; 154 if (PfDetectDestination(n)) { 155 n.m_estimate = n.m_cost; 156 return true; 157 } 158 159 TileIndex tile = n.GetTile(); 160 DiagDirection exitdir = TrackdirToExitdir(n.GetTrackdir()); 161 int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir]; 162 int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir]; 163 int x2 = 2 * TileX(m_destTile); 164 int y2 = 2 * TileY(m_destTile); 165 int dx = abs(x1 - x2); 166 int dy = abs(y1 - y2); 167 int dmin = std::min(dx, dy); 168 int dxy = abs(dx - dy); 169 int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2); 170 n.m_estimate = n.m_cost + d; 171 assert(n.m_estimate >= n.m_parent->m_estimate); 172 return true; 173 } 174 }; 175 176 /** 177 * YAPF template that uses Ttypes template argument to determine all YAPF 178 * components (base classes) from which the actual YAPF is composed. 179 * For example classes consult: CYapfRail_TypesT template and its instantiations: 180 * CYapfRail1, CYapfRail2, CYapfRail3, CYapfAnyDepotRail1, CYapfAnyDepotRail2, CYapfAnyDepotRail3 181 */ 182 template <class Ttypes> 183 class CYapfT 184 : public Ttypes::PfBase ///< Instance of CYapfBaseT - main YAPF loop and support base class 185 , public Ttypes::PfCost ///< Cost calculation provider base class 186 , public Ttypes::PfCache ///< Segment cost cache provider 187 , public Ttypes::PfOrigin ///< Origin (tile or two-tile origin) 188 , public Ttypes::PfDestination ///< Destination detector and distance (estimate) calculation provider 189 , public Ttypes::PfFollow ///< Node follower (stepping provider) 190 { 191 }; 192 193 194 195 #endif /* YAPF_COMMON_HPP */ 196