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 #include "../../misc/dbg_helpers.h"
  14 #include "../../train.h"
  15 #include "nodelist.hpp"
  16 #include "yapf_node.hpp"
  17 #include "yapf_type.hpp"
  18
  19 /** key for cached segment cost for rail YAPF */
  20 struct CYapfRailSegmentKey
  21 {
  22         uint32_t value;
  23
  24         inline CYapfRailSegmentKey(const CYapfNodeKeyTrackDir &node_key)
  25         {
  26                 this->Set(node_key);
  27         }
  28
  29         inline void Set(const CYapfRailSegmentKey &src)
  30         {
  31                 this->value = src.value;
  32         }
  33
  34         inline void Set(const CYapfNodeKeyTrackDir &node_key)
  35         {
  36                 this->value = (node_key.tile.base() << 4) | node_key.td;
  37         }
  38
  39         inline int32_t CalcHash() const
  40         {
  41                 return this->value;
  42         }
  43
  44         inline TileIndex GetTile() const
  45         {
  46                 return (TileIndex)(this->value >> 4);
  47         }
  48
  49         inline Trackdir GetTrackdir() const
  50         {
  51                 return (Trackdir)(this->value & 0x0F);
  52         }
  53
  54         inline bool operator==(const CYapfRailSegmentKey &other) const
  55         {
  56                 return this->value == other.value;
  57         }
  58
  59         void Dump(DumpTarget &dmp) const
  60         {
  61                 dmp.WriteTile("tile", this->GetTile());
  62                 dmp.WriteEnumT("td", this->GetTrackdir());
  63         }
  64 };
  65
  66 /** cached segment cost for rail YAPF */
  67 struct CYapfRailSegment
  68 {
  69         typedef CYapfRailSegmentKey Key;
  70
  71         CYapfRailSegmentKey key;
  72         TileIndex last_tile = INVALID_TILE;
  73         Trackdir last_td = INVALID_TRACKDIR;
  74         int cost = -1;
  75         TileIndex last_signal_tile = INVALID_TILE;
  76         Trackdir last_signal_td = INVALID_TRACKDIR;
  77         EndSegmentReasonBits end_segment_reason = ESRB_NONE;
  78         CYapfRailSegment *hash_next = nullptr;
  79
  80         inline CYapfRailSegment(const CYapfRailSegmentKey &key) : key(key) {}
  81
  82         inline const Key &GetKey() const
  83         {
  84                 return this->key;
  85         }
  86
  87         inline TileIndex GetTile() const
  88         {
  89                 return this->key.GetTile();
  90         }
  91
  92         inline CYapfRailSegment *GetHashNext()
  93         {
  94                 return this->hash_next;
  95         }
  96
  97         inline void SetHashNext(CYapfRailSegment *next)
  98         {
  99                 this->hash_next = next;
 100         }
 101
 102         void Dump(DumpTarget &dmp) const
 103         {
 104                 dmp.WriteStructT("key", &this->key);
 105                 dmp.WriteTile("last_tile", this->last_tile);
 106                 dmp.WriteEnumT("last_td", this->last_td);
 107                 dmp.WriteValue("cost", this->cost);
 108                 dmp.WriteTile("last_signal_tile", this->last_signal_tile);
 109                 dmp.WriteEnumT("last_signal_td", this->last_signal_td);
 110                 dmp.WriteEnumT("end_segment_reason", this->end_segment_reason);
 111         }
 112 };
 113
 114 /** Yapf Node for rail YAPF */
 115 template <class Tkey_>
 116 struct CYapfRailNodeT
 117         : CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> >
 118 {
 119         typedef CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> > base;
 120         typedef CYapfRailSegment CachedData;
 121
 122         CYapfRailSegment *segment;
 123         uint16_t num_signals_passed;
 124         union {
 125                 uint32_t inherited_flags;
 126                 struct {
 127                         bool target_seen;
 128                         bool choice_seen;
 129                         bool last_signal_was_red;
 130                 } flags_s;
 131         } flags_u;
 132         SignalType last_red_signal_type;
 133         SignalType last_signal_type;
 134
 135         inline void Set(CYapfRailNodeT *parent, TileIndex tile, Trackdir td, bool is_choice)
 136         {
 137                 this->base::Set(parent, tile, td, is_choice);
 138                 this->segment = nullptr;
 139                 if (parent == nullptr) {
 140                         this->num_signals_passed      = 0;
 141                         this->flags_u.inherited_flags = 0;
 142                         this->last_red_signal_type    = SIGTYPE_BLOCK;
 143                         /* We use PBS as initial signal type because if we are in
 144                          * a PBS section and need to route, i.e. we're at a safe
 145                          * waiting point of a station, we need to account for the
 146                          * reservation costs. If we are in a normal block then we
 147                          * should be alone in there and as such the reservation
 148                          * costs should be 0 anyway. If there would be another
 149                          * train in the block, i.e. passing signals at danger
 150                          * then avoiding that train with help of the reservation
 151                          * costs is not a bad thing, actually it would probably
 152                          * be a good thing to do. */
 153                         this->last_signal_type        = SIGTYPE_PBS;
 154                 } else {
 155                         this->num_signals_passed      = parent->num_signals_passed;
 156                         this->flags_u.inherited_flags = parent->flags_u.inherited_flags;
 157                         this->last_red_signal_type    = parent->last_red_signal_type;
 158                         this->last_signal_type        = parent->last_signal_type;
 159                 }
 160                 this->flags_u.flags_s.choice_seen |= is_choice;
 161         }
 162
 163         inline TileIndex GetLastTile() const
 164         {
 165                 assert(this->segment != nullptr);
 166                 return this->segment->last_tile;
 167         }
 168
 169         inline Trackdir GetLastTrackdir() const
 170         {
 171                 assert(this->segment != nullptr);
 172                 return this->segment->last_td;
 173         }
 174
 175         inline void SetLastTileTrackdir(TileIndex tile, Trackdir td)
 176         {
 177                 assert(this->segment != nullptr);
 178                 this->segment->last_tile = tile;
 179                 this->segment->last_td = td;
 180         }
 181
 182         template <class Tbase, class Tfunc, class Tpf>
 183         bool IterateTiles(const Train *v, Tpf &yapf, Tbase &obj, bool (Tfunc::*func)(TileIndex, Trackdir)) const
 184         {
 185                 typename Tbase::TrackFollower ft(v, yapf.GetCompatibleRailTypes());
 186                 TileIndex cur = this->base::GetTile();
 187                 Trackdir  cur_td = this->base::GetTrackdir();
 188
 189                 while (cur != this->GetLastTile() || cur_td != this->GetLastTrackdir()) {
 190                         if (!((obj.*func)(cur, cur_td))) return false;
 191
 192                         if (!ft.Follow(cur, cur_td)) break;
 193                         cur = ft.new_tile;
 194                         assert(KillFirstBit(ft.new_td_bits) == TRACKDIR_BIT_NONE);
 195                         cur_td = FindFirstTrackdir(ft.new_td_bits);
 196                 }
 197
 198                 return (obj.*func)(cur, cur_td);
 199         }
 200
 201         void Dump(DumpTarget &dmp) const
 202         {
 203                 this->base::Dump(dmp);
 204                 dmp.WriteStructT("segment", this->segment);
 205                 dmp.WriteValue("num_signals_passed", this->num_signals_passed);
 206                 dmp.WriteValue("target_seen", this->flags_u.flags_s.target_seen ? "Yes" : "No");
 207                 dmp.WriteValue("choice_seen", this->flags_u.flags_s.choice_seen ? "Yes" : "No");
 208                 dmp.WriteValue("last_signal_was_red", this->flags_u.flags_s.last_signal_was_red ? "Yes" : "No");
 209                 dmp.WriteEnumT("last_red_signal_type", this->last_red_signal_type);
 210         }
 211 };
 212
 213 /* now define two major node types (that differ by key type) */
 214 typedef CYapfRailNodeT<CYapfNodeKeyExitDir>  CYapfRailNodeExitDir;
 215 typedef CYapfRailNodeT<CYapfNodeKeyTrackDir> CYapfRailNodeTrackDir;
 216
 217 /* Default NodeList types */
 218 typedef NodeList<CYapfRailNodeExitDir , 8, 10> CRailNodeListExitDir;
 219 typedef NodeList<CYapfRailNodeTrackDir, 8, 10> CRailNodeListTrackDir;
 220
 221 #endif /* YAPF_NODE_RAIL_HPP */