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_node_rail.hpp Node tailored for rail pathfinding. */ 9 10 #ifndef YAPF_NODE_RAIL_HPP 11 #define YAPF_NODE_RAIL_HPP 12 13 /** key for cached segment cost for rail YAPF */ 14 struct CYapfRailSegmentKey 15 { 16 uint32 m_value; 17 CYapfRailSegmentKeyCYapfRailSegmentKey18 inline CYapfRailSegmentKey(const CYapfNodeKeyTrackDir &node_key) 19 { 20 Set(node_key); 21 } 22 SetCYapfRailSegmentKey23 inline void Set(const CYapfRailSegmentKey &src) 24 { 25 m_value = src.m_value; 26 } 27 SetCYapfRailSegmentKey28 inline void Set(const CYapfNodeKeyTrackDir &node_key) 29 { 30 m_value = (((int)node_key.m_tile) << 4) | node_key.m_td; 31 } 32 CalcHashCYapfRailSegmentKey33 inline int32 CalcHash() const 34 { 35 return m_value; 36 } 37 GetTileCYapfRailSegmentKey38 inline TileIndex GetTile() const 39 { 40 return (TileIndex)(m_value >> 4); 41 } 42 GetTrackdirCYapfRailSegmentKey43 inline Trackdir GetTrackdir() const 44 { 45 return (Trackdir)(m_value & 0x0F); 46 } 47 operator ==CYapfRailSegmentKey48 inline bool operator==(const CYapfRailSegmentKey &other) const 49 { 50 return m_value == other.m_value; 51 } 52 DumpCYapfRailSegmentKey53 void Dump(DumpTarget &dmp) const 54 { 55 dmp.WriteTile("tile", GetTile()); 56 dmp.WriteEnumT("td", GetTrackdir()); 57 } 58 }; 59 60 /** cached segment cost for rail YAPF */ 61 struct CYapfRailSegment 62 { 63 typedef CYapfRailSegmentKey Key; 64 65 CYapfRailSegmentKey m_key; 66 TileIndex m_last_tile; 67 Trackdir m_last_td; 68 int m_cost; 69 TileIndex m_last_signal_tile; 70 Trackdir m_last_signal_td; 71 EndSegmentReasonBits m_end_segment_reason; 72 CYapfRailSegment *m_hash_next; 73 CYapfRailSegmentCYapfRailSegment74 inline CYapfRailSegment(const CYapfRailSegmentKey &key) 75 : m_key(key) 76 , m_last_tile(INVALID_TILE) 77 , m_last_td(INVALID_TRACKDIR) 78 , m_cost(-1) 79 , m_last_signal_tile(INVALID_TILE) 80 , m_last_signal_td(INVALID_TRACKDIR) 81 , m_end_segment_reason(ESRB_NONE) 82 , m_hash_next(nullptr) 83 {} 84 GetKeyCYapfRailSegment85 inline const Key& GetKey() const 86 { 87 return m_key; 88 } 89 GetTileCYapfRailSegment90 inline TileIndex GetTile() const 91 { 92 return m_key.GetTile(); 93 } 94 GetHashNextCYapfRailSegment95 inline CYapfRailSegment *GetHashNext() 96 { 97 return m_hash_next; 98 } 99 SetHashNextCYapfRailSegment100 inline void SetHashNext(CYapfRailSegment *next) 101 { 102 m_hash_next = next; 103 } 104 DumpCYapfRailSegment105 void Dump(DumpTarget &dmp) const 106 { 107 dmp.WriteStructT("m_key", &m_key); 108 dmp.WriteTile("m_last_tile", m_last_tile); 109 dmp.WriteEnumT("m_last_td", m_last_td); 110 dmp.WriteValue("m_cost", m_cost); 111 dmp.WriteTile("m_last_signal_tile", m_last_signal_tile); 112 dmp.WriteEnumT("m_last_signal_td", m_last_signal_td); 113 dmp.WriteEnumT("m_end_segment_reason", m_end_segment_reason); 114 } 115 }; 116 117 /** Yapf Node for rail YAPF */ 118 template <class Tkey_> 119 struct CYapfRailNodeT 120 : CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> > 121 { 122 typedef CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> > base; 123 typedef CYapfRailSegment CachedData; 124 125 CYapfRailSegment *m_segment; 126 uint16 m_num_signals_passed; 127 union { 128 uint32 m_inherited_flags; 129 struct { 130 bool m_targed_seen : 1; 131 bool m_choice_seen : 1; 132 bool m_last_signal_was_red : 1; 133 } flags_s; 134 } flags_u; 135 SignalType m_last_red_signal_type; 136 SignalType m_last_signal_type; 137 SetCYapfRailNodeT138 inline void Set(CYapfRailNodeT *parent, TileIndex tile, Trackdir td, bool is_choice) 139 { 140 base::Set(parent, tile, td, is_choice); 141 m_segment = nullptr; 142 if (parent == nullptr) { 143 m_num_signals_passed = 0; 144 flags_u.m_inherited_flags = 0; 145 m_last_red_signal_type = SIGTYPE_NORMAL; 146 /* We use PBS as initial signal type because if we are in 147 * a PBS section and need to route, i.e. we're at a safe 148 * waiting point of a station, we need to account for the 149 * reservation costs. If we are in a normal block then we 150 * should be alone in there and as such the reservation 151 * costs should be 0 anyway. If there would be another 152 * train in the block, i.e. passing signals at danger 153 * then avoiding that train with help of the reservation 154 * costs is not a bad thing, actually it would probably 155 * be a good thing to do. */ 156 m_last_signal_type = SIGTYPE_PBS; 157 } else { 158 m_num_signals_passed = parent->m_num_signals_passed; 159 flags_u.m_inherited_flags = parent->flags_u.m_inherited_flags; 160 m_last_red_signal_type = parent->m_last_red_signal_type; 161 m_last_signal_type = parent->m_last_signal_type; 162 } 163 flags_u.flags_s.m_choice_seen |= is_choice; 164 } 165 GetLastTileCYapfRailNodeT166 inline TileIndex GetLastTile() const 167 { 168 assert(m_segment != nullptr); 169 return m_segment->m_last_tile; 170 } 171 GetLastTrackdirCYapfRailNodeT172 inline Trackdir GetLastTrackdir() const 173 { 174 assert(m_segment != nullptr); 175 return m_segment->m_last_td; 176 } 177 SetLastTileTrackdirCYapfRailNodeT178 inline void SetLastTileTrackdir(TileIndex tile, Trackdir td) 179 { 180 assert(m_segment != nullptr); 181 m_segment->m_last_tile = tile; 182 m_segment->m_last_td = td; 183 } 184 185 template <class Tbase, class Tfunc, class Tpf> IterateTilesCYapfRailNodeT186 bool IterateTiles(const Train *v, Tpf &yapf, Tbase &obj, bool (Tfunc::*func)(TileIndex, Trackdir)) const 187 { 188 typename Tbase::TrackFollower ft(v, yapf.GetCompatibleRailTypes()); 189 TileIndex cur = base::GetTile(); 190 Trackdir cur_td = base::GetTrackdir(); 191 192 while (cur != GetLastTile() || cur_td != GetLastTrackdir()) { 193 if (!((obj.*func)(cur, cur_td))) return false; 194 195 if (!ft.Follow(cur, cur_td)) break; 196 cur = ft.m_new_tile; 197 assert(KillFirstBit(ft.m_new_td_bits) == TRACKDIR_BIT_NONE); 198 cur_td = FindFirstTrackdir(ft.m_new_td_bits); 199 } 200 201 return (obj.*func)(cur, cur_td); 202 } 203 DumpCYapfRailNodeT204 void Dump(DumpTarget &dmp) const 205 { 206 base::Dump(dmp); 207 dmp.WriteStructT("m_segment", m_segment); 208 dmp.WriteValue("m_num_signals_passed", m_num_signals_passed); 209 dmp.WriteValue("m_targed_seen", flags_u.flags_s.m_targed_seen ? "Yes" : "No"); 210 dmp.WriteValue("m_choice_seen", flags_u.flags_s.m_choice_seen ? "Yes" : "No"); 211 dmp.WriteValue("m_last_signal_was_red", flags_u.flags_s.m_last_signal_was_red ? "Yes" : "No"); 212 dmp.WriteEnumT("m_last_red_signal_type", m_last_red_signal_type); 213 } 214 }; 215 216 /* now define two major node types (that differ by key type) */ 217 typedef CYapfRailNodeT<CYapfNodeKeyExitDir> CYapfRailNodeExitDir; 218 typedef CYapfRailNodeT<CYapfNodeKeyTrackDir> CYapfRailNodeTrackDir; 219 220 /* Default NodeList types */ 221 typedef CNodeList_HashTableT<CYapfRailNodeExitDir , 8, 10> CRailNodeListExitDir; 222 typedef CNodeList_HashTableT<CYapfRailNodeTrackDir, 8, 10> CRailNodeListTrackDir; 223 224 #endif /* YAPF_NODE_RAIL_HPP */ 225