OpenTTD Source  20241108-master-g80f628063a
yapf_common.hpp
Go to the documentation of this file.
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 
10 #ifndef YAPF_COMMON_HPP
11 #define YAPF_COMMON_HPP
12 
13 #include "../../core/bitmath_func.hpp"
14 #include "../../direction_type.h"
15 #include "../../map_func.h"
16 #include "../../tile_type.h"
17 #include "../../track_type.h"
18 #include "../pathfinder_type.h"
19 
21 template <class Types>
23 {
24 public:
25  typedef typename Types::Tpf Tpf;
26  typedef typename Types::NodeList::Titem Node;
27  typedef typename Node::Key Key;
28 
29 protected:
32 
34  inline Tpf &Yapf()
35  {
36  return *static_cast<Tpf *>(this);
37  }
38 
39 public:
41  void SetOrigin(TileIndex tile, TrackdirBits trackdirs)
42  {
43  this->origin_tile = tile;
44  this->origin_trackdirs = trackdirs;
45  }
46 
49  {
50  bool is_choice = (KillFirstBit(this->origin_trackdirs) != TRACKDIR_BIT_NONE);
51  for (TrackdirBits tdb = this->origin_trackdirs; tdb != TRACKDIR_BIT_NONE; tdb = KillFirstBit(tdb)) {
52  Trackdir td = (Trackdir)FindFirstBit(tdb);
53  Node &n1 = Yapf().CreateNewNode();
54  n1.Set(nullptr, this->origin_tile, td, is_choice);
55  Yapf().AddStartupNode(n1);
56  }
57  }
58 };
59 
61 template <class Types>
63 {
64 public:
65  typedef typename Types::Tpf Tpf;
66  typedef typename Types::NodeList::Titem Node;
67  typedef typename Node::Key Key;
68 
69 protected:
76 
78  inline Tpf &Yapf()
79  {
80  return *static_cast<Tpf *>(this);
81  }
82 
83 public:
86  {
87  this->origin_tile = tile;
88  this->origin_td = td;
89  this->reverse_tile = tiler;
90  this->reverse_td = tdr;
91  this->reverse_penalty = reverse_penalty;
92  this->treat_first_red_two_way_signal_as_eol = treat_first_red_two_way_signal_as_eol;
93  }
94 
97  {
98  if (this->origin_tile != INVALID_TILE && this->origin_td != INVALID_TRACKDIR) {
99  Node &n1 = Yapf().CreateNewNode();
100  n1.Set(nullptr, this->origin_tile, this->origin_td, false);
101  Yapf().AddStartupNode(n1);
102  }
103  if (this->reverse_tile != INVALID_TILE && this->reverse_td != INVALID_TRACKDIR) {
104  Node &n2 = Yapf().CreateNewNode();
105  n2.Set(nullptr, this->reverse_tile, this->reverse_td, false);
106  n2.cost = this->reverse_penalty;
107  Yapf().AddStartupNode(n2);
108  }
109  }
110 
113  {
114  return Yapf().PfGetSettings().rail_firstred_twoway_eol && this->treat_first_red_two_way_signal_as_eol;
115  }
116 };
117 
119 template <class Types>
121 {
122 public:
123  typedef typename Types::Tpf Tpf;
124  typedef typename Types::NodeList::Titem Node;
125  typedef typename Node::Key Key;
126 
127 protected:
130 
131 public:
133  void SetDestination(TileIndex tile, TrackdirBits trackdirs)
134  {
135  this->dest_tile = tile;
136  this->dest_trackdirs = trackdirs;
137  }
138 
139 protected:
142  {
143  return *static_cast<Tpf *>(this);
144  }
145 
146 public:
148  inline bool PfDetectDestination(Node &n)
149  {
150  return (n.key.tile == this->dest_tile) && HasTrackdir(this->dest_trackdirs, n.GetTrackdir());
151  }
152 
157  inline bool PfCalcEstimate(Node &n)
158  {
159  static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
160  static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
161  if (this->PfDetectDestination(n)) {
162  n.estimate = n.cost;
163  return true;
164  }
165 
166  TileIndex tile = n.GetTile();
167  DiagDirection exitdir = TrackdirToExitdir(n.GetTrackdir());
168  int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
169  int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
170  int x2 = 2 * TileX(this->dest_tile);
171  int y2 = 2 * TileY(this->dest_tile);
172  int dx = abs(x1 - x2);
173  int dy = abs(y1 - y2);
174  int dmin = std::min(dx, dy);
175  int dxy = abs(dx - dy);
176  int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
177  n.estimate = n.cost + d;
178  assert(n.estimate >= n.parent->estimate);
179  return true;
180  }
181 };
182 
189 template <class Ttypes>
190 class CYapfT
191  : public Ttypes::PfBase
192  , public Ttypes::PfCost
193  , public Ttypes::PfCache
194  , public Ttypes::PfOrigin
195  , public Ttypes::PfDestination
196  , public Ttypes::PfFollow
197 {
198 };
199 
200 
201 
202 #endif /* YAPF_COMMON_HPP */
constexpr uint8_t FindFirstBit(T x)
Search the first set bit in a value.
constexpr T KillFirstBit(T value)
Clear the first bit in an integer.
YAPF destination provider base class - used when destination is single tile / multiple trackdirs.
Tpf & Yapf()
to access inherited path finder
TrackdirBits dest_trackdirs
destination trackdir mask
void SetDestination(TileIndex tile, TrackdirBits trackdirs)
set the destination tile / more trackdirs
Node::Key Key
key to hash tables
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
TileIndex dest_tile
destination tile
Types::NodeList::Titem Node
this will be our node type
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
Definition: yapf_common.hpp:23
Node::Key Key
key to hash tables
Definition: yapf_common.hpp:27
Tpf & Yapf()
to access inherited path finder
Definition: yapf_common.hpp:34
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_common.hpp:25
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_common.hpp:26
TrackdirBits origin_trackdirs
origin trackdir mask
Definition: yapf_common.hpp:31
void SetOrigin(TileIndex tile, TrackdirBits trackdirs)
Set origin tile / trackdir mask.
Definition: yapf_common.hpp:41
void PfSetStartupNodes()
Called when YAPF needs to place origin nodes into open list.
Definition: yapf_common.hpp:48
TileIndex origin_tile
origin tile
Definition: yapf_common.hpp:30
YAPF origin provider base class - used when there are two tile/trackdir origins.
Definition: yapf_common.hpp:63
Trackdir reverse_td
second (reverse) origin trackdir
Definition: yapf_common.hpp:73
Tpf & Yapf()
to access inherited path finder
Definition: yapf_common.hpp:78
void PfSetStartupNodes()
Called when YAPF needs to place origin nodes into open list.
Definition: yapf_common.hpp:96
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)
set origin (tiles, trackdirs, etc.)
Definition: yapf_common.hpp:85
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_common.hpp:66
bool TreatFirstRedTwoWaySignalAsEOL()
return true if first two-way signal should be treated as dead end
int reverse_penalty
penalty to be added for using the reverse origin
Definition: yapf_common.hpp:74
Node::Key Key
key to hash tables
Definition: yapf_common.hpp:67
TileIndex reverse_tile
second (reverse) origin tile
Definition: yapf_common.hpp:72
Trackdir origin_td
first origin trackdir
Definition: yapf_common.hpp:71
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_common.hpp:65
bool treat_first_red_two_way_signal_as_eol
in some cases (leaving station) we need to handle first two-way signal differently
Definition: yapf_common.hpp:75
TileIndex origin_tile
first origin tile
Definition: yapf_common.hpp:70
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
DiagDirection
Enumeration for diagonal directions.
static debug_inline uint TileY(TileIndex tile)
Get the Y component of a tile.
Definition: map_func.h:425
static debug_inline uint TileX(TileIndex tile)
Get the X component of a tile.
Definition: map_func.h:415
constexpr T abs(const T a)
Returns the absolute value of (scalar) variable.
Definition: math_func.hpp:23
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
Definition: tile_type.h:95
bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
Definition: track_func.h:340
DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
Definition: track_func.h:439
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:67
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
Definition: track_type.h:86
TrackdirBits
Allow incrementing of Trackdir variables.
Definition: track_type.h:98
@ TRACKDIR_BIT_NONE
No track build.
Definition: track_type.h:99