src/pathfinder/yapf/yapf_node_rail.hpp

   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_t    m_value;
  17
  18         inline CYapfRailSegmentKey(const CYapfNodeKeyTrackDir &node_key)
  19         {
  20                 Set(node_key);
  21         }
  22
  23         inline void Set(const CYapfRailSegmentKey &src)
  24         {
  25                 m_value = src.m_value;
  26         }
  27
  28         inline void Set(const CYapfNodeKeyTrackDir &node_key)
  29         {
  30                 m_value = (node_key.m_tile.base() << 4) | node_key.m_td;
  31         }
  32
  33         inline int32_t CalcHash() const
  34         {
  35                 return m_value;
  36         }
  37
  38         inline TileIndex GetTile() const
  39         {
  40                 return (TileIndex)(m_value >> 4);
  41         }
  42
  43         inline Trackdir GetTrackdir() const
  44         {
  45                 return (Trackdir)(m_value & 0x0F);
  46         }
  47
  48         inline bool operator==(const CYapfRailSegmentKey &other) const
  49         {
  50                 return m_value == other.m_value;
  51         }
  52
  53         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
  74         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
  85         inline const Key &GetKey() const
  86         {
  87                 return m_key;
  88         }
  89
  90         inline TileIndex GetTile() const
  91         {
  92                 return m_key.GetTile();
  93         }
  94
  95         inline CYapfRailSegment *GetHashNext()
  96         {
  97                 return m_hash_next;
  98         }
  99
 100         inline void SetHashNext(CYapfRailSegment *next)
 101         {
 102                 m_hash_next = next;
 103         }
 104
 105         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_t            m_num_signals_passed;
 127         union {
 128                 uint32_t          m_inherited_flags;
 129                 struct {
 130                         bool          m_targed_seen;
 131                         bool          m_choice_seen;
 132                         bool          m_last_signal_was_red;
 133                 } flags_s;
 134         } flags_u;
 135         SignalType        m_last_red_signal_type;
 136         SignalType        m_last_signal_type;
 137
 138         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_BLOCK;
 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
 166         inline TileIndex GetLastTile() const
 167         {
 168                 assert(m_segment != nullptr);
 169                 return m_segment->m_last_tile;
 170         }
 171
 172         inline Trackdir GetLastTrackdir() const
 173         {
 174                 assert(m_segment != nullptr);
 175                 return m_segment->m_last_td;
 176         }
 177
 178         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>
 186         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
 204         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 */