src/pathfinder/yapf/yapf_common.hpp

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