src/pathfinder/yapf/yapf.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.hpp Base includes/functions for YAPF. */
  11
  12 #ifndef YAPF_HPP
  13 #define YAPF_HPP
  14
  15 #include "../../landscape.h"
  16 #include "../pf_performance_timer.hpp"
  17 #include "yapf.h"
  18
  19 //#undef FORCEINLINE
  20 //#define inline inline
  21
  22 #include "../../debug.h"
  23 #include "../../misc/dbg_helpers.h"
  24 #include "../../settings_type.h"
  25 #include "astar.hpp"
  26 #include "../pos.h"
  27 #include "../follow_track.hpp"
  28
  29 extern int _total_pf_time_us;
  30
  31 /** Yapf Node Key base class. */
  32 template <class PPos>
  33 struct CYapfNodeKey : PPos {
  34         typedef PPos Pos;
  35
  36         inline void Set(const Pos &pos)
  37         {
  38                 Pos::set(pos);
  39         }
  40
  41         void Dump(DumpTarget &dmp) const
  42         {
  43                 dmp.WriteTile("m_tile", Pos::tile);
  44                 dmp.WriteEnumT("m_td", Pos::td);
  45         }
  46 };
  47
  48 /** Yapf Node Key that evaluates hash from (and compares) tile & exit dir. */
  49 template <class PPos>
  50 struct CYapfNodeKeyExitDir : public CYapfNodeKey<PPos>
  51 {
  52         DiagDirection  exitdir;
  53
  54         inline void Set(const PPos &pos)
  55         {
  56                 CYapfNodeKey<PPos>::Set(pos);
  57                 exitdir = (pos.td == INVALID_TRACKDIR) ? INVALID_DIAGDIR : TrackdirToExitdir(pos.td);
  58         }
  59
  60         inline int CalcHash() const
  61         {
  62                 return exitdir | (PPos::tile << 2);
  63         }
  64
  65         inline bool operator == (const CYapfNodeKeyExitDir& other) const
  66         {
  67                 return PPos::PathTile::operator==(other) && (exitdir == other.exitdir);
  68         }
  69
  70         void Dump(DumpTarget &dmp) const
  71         {
  72                 CYapfNodeKey<PPos>::Dump(dmp);
  73                 dmp.WriteEnumT("m_exitdir", exitdir);
  74         }
  75 };
  76
  77 /** Yapf Node Key that evaluates hash from (and compares) tile & track dir. */
  78 template <class PPos>
  79 struct CYapfNodeKeyTrackDir : public CYapfNodeKey<PPos>
  80 {
  81         inline int CalcHash() const
  82         {
  83                 return (PPos::in_wormhole() ? (PPos::td + 6) : PPos::td) | (PPos::tile << 4);
  84         }
  85
  86         inline bool operator == (const CYapfNodeKeyTrackDir& other) const
  87         {
  88                 return PPos::PathTile::operator==(other) && (PPos::td == other.td);
  89         }
  90 };
  91
  92 /** Yapf Node base */
  93 template <class Tkey_, class Tnode>
  94 struct CYapfNodeT : AstarNodeBase<Tnode> {
  95         typedef AstarNodeBase<Tnode> ABase;
  96         typedef Tkey_ Key;
  97         typedef typename Key::Pos Pos;
  98         typedef Tnode Node;
  99
 100         Tkey_       m_key;
 101
 102         inline void Set(Node *parent, const Pos &pos)
 103         {
 104                 ABase::Set (parent);
 105                 m_key.Set(pos);
 106         }
 107
 108         inline const Pos& GetPos() const {return m_key;}
 109         inline const Tkey_& GetKey() const {return m_key;}
 110
 111         void Dump(DumpTarget &dmp) const
 112         {
 113                 dmp.WriteStructT("m_parent", ABase::m_parent);
 114                 dmp.WriteLine("m_cost = %d", ABase::m_cost);
 115                 dmp.WriteLine("m_estimate = %d", ABase::m_estimate);
 116                 dmp.WriteStructT("m_key", &m_key);
 117         }
 118 };
 119
 120 /** Cost estimation helper. */
 121 static inline int YapfCalcEstimate (TileIndex src, DiagDirection dir, TileIndex dst)
 122 {
 123         static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
 124         static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
 125
 126         int x1 = 2 * TileX(src) + dg_dir_to_x_offs[(int)dir];
 127         int y1 = 2 * TileY(src) + dg_dir_to_y_offs[(int)dir];
 128         int x2 = 2 * TileX(dst);
 129         int y2 = 2 * TileY(dst);
 130         int dx = abs(x1 - x2);
 131         int dy = abs(y1 - y2);
 132         int dmin = min(dx, dy);
 133         int dxy = abs(dx - dy);
 134         return dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
 135 }
 136
 137 /** Cost estimation helper. */
 138 template <class Pos>
 139 static inline int YapfCalcEstimate (const Pos &pos, TileIndex dst)
 140 {
 141         return YapfCalcEstimate (pos.tile, TrackdirToExitdir(pos.td), dst);
 142 }
 143
 144 #endif /* YAPF_HPP */