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         CYapfNodeKey (const Pos &pos) : Pos (pos)
  37         {
  38         }
  39
  40         void Dump(DumpTarget &dmp) const
  41         {
  42                 dmp.WriteTile("m_tile", Pos::tile);
  43                 dmp.WriteEnumT("m_td", Pos::td);
  44         }
  45 };
  46
  47 /** Yapf Node Key that evaluates hash from (and compares) tile & exit dir. */
  48 template <class PPos>
  49 struct CYapfNodeKeyExitDir : public CYapfNodeKey<PPos> {
  50         DiagDirection  exitdir;
  51
  52         CYapfNodeKeyExitDir (const PPos &pos)
  53                 : CYapfNodeKey<PPos> (pos),
  54                   exitdir ((pos.td == INVALID_TRACKDIR) ? INVALID_DIAGDIR : TrackdirToExitdir (pos.td))
  55         {
  56         }
  57
  58         inline int CalcHash() const
  59         {
  60                 return exitdir | (PPos::tile << 2);
  61         }
  62
  63         inline bool operator == (const CYapfNodeKeyExitDir &other) const
  64         {
  65                 return PPos::PathTile::operator==(other) && (exitdir == other.exitdir);
  66         }
  67
  68         void Dump(DumpTarget &dmp) const
  69         {
  70                 CYapfNodeKey<PPos>::Dump(dmp);
  71                 dmp.WriteEnumT("m_exitdir", exitdir);
  72         }
  73 };
  74
  75 /** Yapf Node Key that evaluates hash from (and compares) tile & track dir. */
  76 template <class PPos>
  77 struct CYapfNodeKeyTrackDir : public CYapfNodeKey<PPos> {
  78         CYapfNodeKeyTrackDir (const PPos &pos)
  79                 : CYapfNodeKey<PPos> (pos)
  80         {
  81         }
  82
  83         inline int CalcHash() const
  84         {
  85                 return (PPos::in_wormhole() ? (PPos::td + 6) : PPos::td) | (PPos::tile << 4);
  86         }
  87
  88         inline bool operator == (const CYapfNodeKeyTrackDir &other) const
  89         {
  90                 return PPos::PathTile::operator==(other) && (PPos::td == other.td);
  91         }
  92 };
  93
  94 /** Yapf Node base */
  95 template <class Tkey_, class Tnode>
  96 struct CYapfNodeT : AstarNode <Tnode> {
  97         typedef AstarNode <Tnode> ABase;
  98         typedef Tkey_ Key;
  99         typedef typename Key::Pos Pos;
 100         typedef Tnode Node;
 101
 102         Tkey_       m_key;
 103
 104         CYapfNodeT (const Node *parent, const Pos &pos)
 105                 : ABase (parent), m_key (pos)
 106         {
 107         }
 108
 109         inline const Pos& GetPos() const
 110         {
 111                 return m_key;
 112         }
 113
 114         inline const Tkey_& GetKey() const
 115         {
 116                 return m_key;
 117         }
 118
 119         void Dump(DumpTarget &dmp) const
 120         {
 121                 dmp.WriteStructT("m_parent", ABase::m_parent);
 122                 dmp.WriteLine("m_cost = %d", ABase::m_cost);
 123                 dmp.WriteLine("m_estimate = %d", ABase::m_estimate);
 124                 dmp.WriteStructT("m_key", &m_key);
 125         }
 126 };
 127
 128 /** Cost estimation helper. */
 129 static inline int YapfCalcEstimate (TileIndex src, DiagDirection dir, TileIndex dst)
 130 {
 131         static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
 132         static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
 133
 134         int x1 = 2 * TileX(src) + dg_dir_to_x_offs[(int)dir];
 135         int y1 = 2 * TileY(src) + dg_dir_to_y_offs[(int)dir];
 136         int x2 = 2 * TileX(dst);
 137         int y2 = 2 * TileY(dst);
 138         int dx = abs(x1 - x2);
 139         int dy = abs(y1 - y2);
 140         int dmin = min(dx, dy);
 141         int dxy = abs(dx - dy);
 142         return dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
 143 }
 144
 145 /** Cost estimation helper. */
 146 template <class Pos>
 147 static inline int YapfCalcEstimate (const Pos &pos, TileIndex dst)
 148 {
 149         return YapfCalcEstimate (pos.tile, TrackdirToExitdir(pos.td), dst);
 150 }
 151
 152 #endif /* YAPF_HPP */