src/pathfinder/yapf/yapf_common.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_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 */
  27         inline Tpf &Yapf()
  28         {
  29                 return *static_cast<Tpf *>(this);
  30         }
  31
  32 public:
  33         /** Set origin tile / trackdir mask */
  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 */
  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)FindFirstBit(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 */
  71         inline Tpf &Yapf()
  72         {
  73                 return *static_cast<Tpf *>(this);
  74         }
  75
  76 public:
  77         /** set origin (tiles, trackdirs, etc.) */
  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 */
  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 */
 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 */
 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 */
 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 */
 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          */
 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 */