OpenTTD
yapf_road.cpp
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 #include "../../stdafx.h"
11 #include "yapf.hpp"
12 #include "yapf_node_road.hpp"
13 #include "../../roadstop_base.h"
14 
15 #include "../../safeguards.h"
16 
17 
18 template <class Types>
20 {
21 public:
22  typedef typename Types::Tpf Tpf;
23  typedef typename Types::TrackFollower TrackFollower;
24  typedef typename Types::NodeList::Titem Node;
25  typedef typename Node::Key Key;
26 
27 protected:
28  int m_max_cost;
29 
30  CYapfCostRoadT() : m_max_cost(0) {};
31 
33  Tpf& Yapf()
34  {
35  return *static_cast<Tpf *>(this);
36  }
37 
38  int SlopeCost(TileIndex tile, TileIndex next_tile, Trackdir trackdir)
39  {
40  /* height of the center of the current tile */
41  int x1 = TileX(tile) * TILE_SIZE;
42  int y1 = TileY(tile) * TILE_SIZE;
43  int z1 = GetSlopePixelZ(x1 + TILE_SIZE / 2, y1 + TILE_SIZE / 2);
44 
45  /* height of the center of the next tile */
46  int x2 = TileX(next_tile) * TILE_SIZE;
47  int y2 = TileY(next_tile) * TILE_SIZE;
48  int z2 = GetSlopePixelZ(x2 + TILE_SIZE / 2, y2 + TILE_SIZE / 2);
49 
50  if (z2 - z1 > 1) {
51  /* Slope up */
52  return Yapf().PfGetSettings().road_slope_penalty;
53  }
54  return 0;
55  }
56 
58  inline int OneTileCost(TileIndex tile, Trackdir trackdir)
59  {
60  int cost = 0;
61  /* set base cost */
62  if (IsDiagonalTrackdir(trackdir)) {
63  cost += YAPF_TILE_LENGTH;
64  switch (GetTileType(tile)) {
65  case MP_ROAD:
66  /* Increase the cost for level crossings */
67  if (IsLevelCrossing(tile)) {
68  cost += Yapf().PfGetSettings().road_crossing_penalty;
69  }
70  break;
71 
72  case MP_STATION: {
73  const RoadStop *rs = RoadStop::GetByTile(tile, GetRoadStopType(tile));
74  if (IsDriveThroughStopTile(tile)) {
75  /* Increase the cost for drive-through road stops */
76  cost += Yapf().PfGetSettings().road_stop_penalty;
77  DiagDirection dir = TrackdirToExitdir(trackdir);
79  /* When we're the first road stop in a 'queue' of them we increase
80  * cost based on the fill percentage of the whole queue. */
81  const RoadStop::Entry *entry = rs->GetEntry(dir);
82  cost += entry->GetOccupied() * Yapf().PfGetSettings().road_stop_occupied_penalty / entry->GetLength();
83  }
84  } else {
85  /* Increase cost for filled road stops */
86  cost += Yapf().PfGetSettings().road_stop_bay_occupied_penalty * (!rs->IsFreeBay(0) + !rs->IsFreeBay(1)) / 2;
87  }
88  break;
89  }
90 
91  default:
92  break;
93  }
94  } else {
95  /* non-diagonal trackdir */
96  cost = YAPF_TILE_CORNER_LENGTH + Yapf().PfGetSettings().road_curve_penalty;
97  }
98  return cost;
99  }
100 
101 public:
102  inline void SetMaxCost(int max_cost)
103  {
104  m_max_cost = max_cost;
105  }
106 
112  inline bool PfCalcCost(Node &n, const TrackFollower *tf)
113  {
114  int segment_cost = 0;
115  uint tiles = 0;
116  /* start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment */
117  TileIndex tile = n.m_key.m_tile;
118  Trackdir trackdir = n.m_key.m_td;
119  int parent_cost = (n.m_parent != nullptr) ? n.m_parent->m_cost : 0;
120 
121  for (;;) {
122  /* base tile cost depending on distance between edges */
123  segment_cost += Yapf().OneTileCost(tile, trackdir);
124 
125  const RoadVehicle *v = Yapf().GetVehicle();
126  /* we have reached the vehicle's destination - segment should end here to avoid target skipping */
127  if (Yapf().PfDetectDestinationTile(tile, trackdir)) break;
128 
129  /* Finish if we already exceeded the maximum path cost (i.e. when
130  * searching for the nearest depot). */
131  if (m_max_cost > 0 && (parent_cost + segment_cost) > m_max_cost) {
132  return false;
133  }
134 
135  /* stop if we have just entered the depot */
137  /* next time we will reverse and leave the depot */
138  break;
139  }
140 
141  /* if there are no reachable trackdirs on new tile, we have end of road */
142  TrackFollower F(Yapf().GetVehicle());
143  if (!F.Follow(tile, trackdir)) break;
144 
145  /* if there are more trackdirs available & reachable, we are at the end of segment */
146  if (KillFirstBit(F.m_new_td_bits) != TRACKDIR_BIT_NONE) break;
147 
148  Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits);
149 
150  /* stop if RV is on simple loop with no junctions */
151  if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) return false;
152 
153  /* if we skipped some tunnel tiles, add their cost */
154  segment_cost += F.m_tiles_skipped * YAPF_TILE_LENGTH;
155  tiles += F.m_tiles_skipped + 1;
156 
157  /* add hilly terrain penalty */
158  segment_cost += Yapf().SlopeCost(tile, F.m_new_tile, trackdir);
159 
160  /* add min/max speed penalties */
161  int min_speed = 0;
162  int max_veh_speed = v->GetDisplayMaxSpeed();
163  int max_speed = F.GetSpeedLimit(&min_speed);
164  if (max_speed < max_veh_speed) segment_cost += 1 * (max_veh_speed - max_speed);
165  if (min_speed > max_veh_speed) segment_cost += 10 * (min_speed - max_veh_speed);
166 
167  /* move to the next tile */
168  tile = F.m_new_tile;
169  trackdir = new_td;
170  if (tiles > MAX_MAP_SIZE) break;
171  }
172 
173  /* save end of segment back to the node */
174  n.m_segment_last_tile = tile;
175  n.m_segment_last_td = trackdir;
176 
177  /* save also tile cost */
178  n.m_cost = parent_cost + segment_cost;
179  return true;
180  }
181 };
182 
183 
184 template <class Types>
186 {
187 public:
188  typedef typename Types::Tpf Tpf;
189  typedef typename Types::TrackFollower TrackFollower;
190  typedef typename Types::NodeList::Titem Node;
191  typedef typename Node::Key Key;
192 
194  Tpf& Yapf()
195  {
196  return *static_cast<Tpf *>(this);
197  }
198 
200  inline bool PfDetectDestination(Node &n)
201  {
202  return IsRoadDepotTile(n.m_segment_last_tile);
203  }
204 
205  inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
206  {
207  return IsRoadDepotTile(tile);
208  }
209 
214  inline bool PfCalcEstimate(Node &n)
215  {
216  n.m_estimate = n.m_cost;
217  return true;
218  }
219 };
220 
221 
222 template <class Types>
224 {
225 public:
226  typedef typename Types::Tpf Tpf;
227  typedef typename Types::TrackFollower TrackFollower;
228  typedef typename Types::NodeList::Titem Node;
229  typedef typename Node::Key Key;
230 
231 protected:
232  TileIndex m_destTile;
233  TrackdirBits m_destTrackdirs;
234  StationID m_dest_station;
235  bool m_bus;
236  bool m_non_artic;
237 
238 public:
239  void SetDestination(const RoadVehicle *v)
240  {
241  if (v->current_order.IsType(OT_GOTO_STATION)) {
242  m_dest_station = v->current_order.GetDestination();
243  m_bus = v->IsBus();
244  m_destTile = CalcClosestStationTile(m_dest_station, v->tile, m_bus ? STATION_BUS : STATION_TRUCK);
245  m_non_artic = !v->HasArticulatedPart();
246  m_destTrackdirs = INVALID_TRACKDIR_BIT;
247  } else {
248  m_dest_station = INVALID_STATION;
249  m_destTile = v->dest_tile;
250  m_destTrackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_ROAD, GetRoadTramType(v->roadtype)));
251  }
252  }
253 
254 protected:
256  Tpf& Yapf()
257  {
258  return *static_cast<Tpf *>(this);
259  }
260 
261 public:
263  inline bool PfDetectDestination(Node &n)
264  {
265  return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
266  }
267 
268  inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
269  {
270  if (m_dest_station != INVALID_STATION) {
271  return IsTileType(tile, MP_STATION) &&
272  GetStationIndex(tile) == m_dest_station &&
273  (m_bus ? IsBusStop(tile) : IsTruckStop(tile)) &&
274  (m_non_artic || IsDriveThroughStopTile(tile));
275  }
276 
277  return tile == m_destTile && HasTrackdir(m_destTrackdirs, trackdir);
278  }
279 
284  inline bool PfCalcEstimate(Node &n)
285  {
286  static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
287  static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
288  if (PfDetectDestination(n)) {
289  n.m_estimate = n.m_cost;
290  return true;
291  }
292 
293  TileIndex tile = n.m_segment_last_tile;
294  DiagDirection exitdir = TrackdirToExitdir(n.m_segment_last_td);
295  int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
296  int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
297  int x2 = 2 * TileX(m_destTile);
298  int y2 = 2 * TileY(m_destTile);
299  int dx = abs(x1 - x2);
300  int dy = abs(y1 - y2);
301  int dmin = min(dx, dy);
302  int dxy = abs(dx - dy);
303  int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
304  n.m_estimate = n.m_cost + d;
305  assert(n.m_estimate >= n.m_parent->m_estimate);
306  return true;
307  }
308 };
309 
310 
311 
312 template <class Types>
314 {
315 public:
316  typedef typename Types::Tpf Tpf;
317  typedef typename Types::TrackFollower TrackFollower;
318  typedef typename Types::NodeList::Titem Node;
319  typedef typename Node::Key Key;
320 
321 protected:
323  inline Tpf& Yapf()
324  {
325  return *static_cast<Tpf *>(this);
326  }
327 
328 public:
329 
335  inline void PfFollowNode(Node &old_node)
336  {
337  TrackFollower F(Yapf().GetVehicle());
338  if (F.Follow(old_node.m_segment_last_tile, old_node.m_segment_last_td)) {
339  Yapf().AddMultipleNodes(&old_node, F);
340  }
341  }
342 
344  inline char TransportTypeChar() const
345  {
346  return 'r';
347  }
348 
349  static Trackdir stChooseRoadTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, bool &path_found, RoadVehPathCache &path_cache)
350  {
351  Tpf pf;
352  return pf.ChooseRoadTrack(v, tile, enterdir, path_found, path_cache);
353  }
354 
355  inline Trackdir ChooseRoadTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, bool &path_found, RoadVehPathCache &path_cache)
356  {
357  /* Handle special case - when next tile is destination tile.
358  * However, when going to a station the (initial) destination
359  * tile might not be a station, but a junction, in which case
360  * this method forces the vehicle to jump in circles. */
361  if (tile == v->dest_tile && !v->current_order.IsType(OT_GOTO_STATION)) {
362  /* choose diagonal trackdir reachable from enterdir */
363  return DiagDirToDiagTrackdir(enterdir);
364  }
365  /* our source tile will be the next vehicle tile (should be the given one) */
366  TileIndex src_tile = tile;
367  /* get available trackdirs on the start tile */
368  TrackdirBits src_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_ROAD, GetRoadTramType(v->roadtype)));
369  /* select reachable trackdirs only */
370  src_trackdirs &= DiagdirReachesTrackdirs(enterdir);
371 
372  /* set origin and destination nodes */
373  Yapf().SetOrigin(src_tile, src_trackdirs);
374  Yapf().SetDestination(v);
375 
376  /* find the best path */
377  path_found = Yapf().FindPath(v);
378 
379  /* if path not found - return INVALID_TRACKDIR */
380  Trackdir next_trackdir = INVALID_TRACKDIR;
381  Node *pNode = Yapf().GetBestNode();
382  if (pNode != nullptr) {
383  uint steps = 0;
384  for (Node *n = pNode; n->m_parent != nullptr; n = n->m_parent) steps++;
385 
386  /* path was found or at least suggested
387  * walk through the path back to its origin */
388  while (pNode->m_parent != nullptr) {
389  steps--;
390  if (pNode->GetIsChoice() && steps < YAPF_ROADVEH_PATH_CACHE_SEGMENTS) {
391  path_cache.td.push_front(pNode->GetTrackdir());
392  path_cache.tile.push_front(pNode->GetTile());
393  }
394  pNode = pNode->m_parent;
395  }
396  /* return trackdir from the best origin node (one of start nodes) */
397  Node &best_next_node = *pNode;
398  assert(best_next_node.GetTile() == tile);
399  next_trackdir = best_next_node.GetTrackdir();
400  /* remove last element for the special case when tile == dest_tile */
401  if (path_found && !path_cache.empty() && tile == v->dest_tile) {
402  path_cache.td.pop_back();
403  path_cache.tile.pop_back();
404  }
405  }
406  return next_trackdir;
407  }
408 
409  static uint stDistanceToTile(const RoadVehicle *v, TileIndex tile)
410  {
411  Tpf pf;
412  return pf.DistanceToTile(v, tile);
413  }
414 
415  inline uint DistanceToTile(const RoadVehicle *v, TileIndex dst_tile)
416  {
417  /* handle special case - when current tile is the destination tile */
418  if (dst_tile == v->tile) {
419  /* distance is zero in this case */
420  return 0;
421  }
422 
423  if (!SetOriginFromVehiclePos(v)) return UINT_MAX;
424 
425  /* get available trackdirs on the destination tile */
426  Yapf().SetDestination(v);
427 
428  /* if path not found - return distance = UINT_MAX */
429  uint dist = UINT_MAX;
430 
431  /* find the best path */
432  if (!Yapf().FindPath(v)) return dist;
433 
434  Node *pNode = Yapf().GetBestNode();
435  if (pNode != nullptr) {
436  /* path was found
437  * get the path cost estimate */
438  dist = pNode->GetCostEstimate();
439  }
440 
441  return dist;
442  }
443 
445  inline bool SetOriginFromVehiclePos(const RoadVehicle *v)
446  {
447  /* set origin (tile, trackdir) */
448  TileIndex src_tile = v->tile;
449  Trackdir src_td = v->GetVehicleTrackdir();
450  if (!HasTrackdir(TrackStatusToTrackdirBits(GetTileTrackStatus(src_tile, TRANSPORT_ROAD, this->IsTram() ? RTT_TRAM : RTT_ROAD)), src_td)) {
451  /* sometimes the roadveh is not on the road (it resides on non-existing track)
452  * how should we handle that situation? */
453  return false;
454  }
455  Yapf().SetOrigin(src_tile, TrackdirToTrackdirBits(src_td));
456  return true;
457  }
458 
459  static FindDepotData stFindNearestDepot(const RoadVehicle *v, TileIndex tile, Trackdir td, int max_distance)
460  {
461  Tpf pf;
462  return pf.FindNearestDepot(v, tile, td, max_distance);
463  }
464 
472  inline FindDepotData FindNearestDepot(const RoadVehicle *v, TileIndex tile, Trackdir td, int max_distance)
473  {
474  /* Set origin. */
475  Yapf().SetOrigin(tile, TrackdirToTrackdirBits(td));
476  Yapf().SetMaxCost(max_distance);
477 
478  /* Find the best path and return if no depot is found. */
479  if (!Yapf().FindPath(v)) return FindDepotData();
480 
481  /* Return the cost of the best path and its depot. */
482  Node *n = Yapf().GetBestNode();
483  return FindDepotData(n->m_segment_last_tile, n->m_cost);
484  }
485 };
486 
487 template <class Tpf_, class Tnode_list, template <class Types> class Tdestination>
489 {
491 
492  typedef Tpf_ Tpf;
494  typedef Tnode_list NodeList;
495  typedef RoadVehicle VehicleType;
496  typedef CYapfBaseT<Types> PfBase;
499  typedef Tdestination<Types> PfDestination;
502 };
503 
504 struct CYapfRoad1 : CYapfT<CYapfRoad_TypesT<CYapfRoad1 , CRoadNodeListTrackDir, CYapfDestinationTileRoadT > > {};
505 struct CYapfRoad2 : CYapfT<CYapfRoad_TypesT<CYapfRoad2 , CRoadNodeListExitDir , CYapfDestinationTileRoadT > > {};
506 
507 struct CYapfRoadAnyDepot1 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};
508 struct CYapfRoadAnyDepot2 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};
509 
510 
511 Trackdir YapfRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found, RoadVehPathCache &path_cache)
512 {
513  /* default is YAPF type 2 */
514  typedef Trackdir (*PfnChooseRoadTrack)(const RoadVehicle*, TileIndex, DiagDirection, bool &path_found, RoadVehPathCache &path_cache);
515  PfnChooseRoadTrack pfnChooseRoadTrack = &CYapfRoad2::stChooseRoadTrack; // default: ExitDir, allow 90-deg
516 
517  /* check if non-default YAPF type should be used */
519  pfnChooseRoadTrack = &CYapfRoad1::stChooseRoadTrack; // Trackdir
520  }
521 
522  Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir, path_found, path_cache);
523  return (td_ret != INVALID_TRACKDIR) ? td_ret : (Trackdir)FindFirstBit2x64(trackdirs);
524 }
525 
527 {
528  TileIndex tile = v->tile;
529  Trackdir trackdir = v->GetVehicleTrackdir();
530  if (!HasTrackdir(TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_ROAD, GetRoadTramType(v->roadtype))), trackdir)) {
531  return FindDepotData();
532  }
533 
534  /* default is YAPF type 2 */
535  typedef FindDepotData (*PfnFindNearestDepot)(const RoadVehicle*, TileIndex, Trackdir, int);
536  PfnFindNearestDepot pfnFindNearestDepot = &CYapfRoadAnyDepot2::stFindNearestDepot;
537 
538  /* check if non-default YAPF type should be used */
540  pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot; // Trackdir
541  }
542 
543  return pfnFindNearestDepot(v, tile, trackdir, max_distance);
544 }
static TileType GetTileType(TileIndex tile)
Get the tiletype of a given tile.
Definition: tile_map.h:96
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:79
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Definition: track_type.h:101
No track build.
Definition: track_type.h:102
bool SetOriginFromVehiclePos(const RoadVehicle *v)
Return true if the valid origin (tile/trackdir) was set from the current vehicle position.
Definition: yapf_road.cpp:445
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
Definition: yapf_common.hpp:15
Node::Key Key
key to hash tables
Definition: yapf_road.cpp:229
Node::Key Key
key to hash tables
Definition: yapf_road.cpp:191
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Definition: yapf_road.cpp:284
static RoadStopType GetRoadStopType(TileIndex t)
Get the road stop type of this tile.
Definition: station_map.h:56
int GetLength() const
Get the length of this drive through stop.
Definition: roadstop_base.h:47
int OneTileCost(TileIndex tile, Trackdir trackdir)
return one tile cost
Definition: yapf_road.cpp:58
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:70
A tile with road (or tram tracks)
Definition: tile_type.h:43
int GetDisplayMaxSpeed() const
Gets the maximum speed in km-ish/h that can be sent into SetDParam for string processing.
Definition: roadveh.h:133
int GetOccupied() const
Get the amount of occupied space in this drive through stop.
Definition: roadstop_base.h:56
VehicleType
Available vehicle types.
Definition: vehicle_type.h:21
Tpf & Yapf()
to access inherited path finder
Definition: yapf_road.cpp:323
TileIndex dest_tile
Heading for this tile.
Definition: vehicle_base.h:235
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
bool PfCalcCost(Node &n, const TrackFollower *tf)
Called by YAPF to calculate the cost from the origin to the given node.
Definition: yapf_road.cpp:112
static uint TileX(TileIndex tile)
Get the X component of a tile.
Definition: map_func.h:205
PathfinderSettings pf
settings for all pathfinders
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_road.cpp:318
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_road.cpp:190
static DiagDirection GetRoadDepotDirection(TileIndex t)
Get the direction of the exit of a road depot.
Definition: road_map.h:565
FindDepotData FindNearestDepot(const RoadVehicle *v, TileIndex tile, Trackdir td, int max_distance)
Find the best depot for a road vehicle.
Definition: yapf_road.cpp:472
static TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir)
Returns all trackdirs that can be reached when entering a tile from a given (diagonal) direction...
Definition: track_func.h:563
static bool IsLevelCrossing(TileIndex t)
Return whether a tile is a level crossing.
Definition: road_map.h:84
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
Definition: yapf_road.cpp:335
static bool IsDriveThroughStopTile(TileIndex t)
Is tile t a drive through road stop station?
Definition: station_map.h:233
static DiagDirection TrackdirToExitdir(Trackdir trackdir)
Maps a trackdir to the (4-way) direction the tile is exited when following that trackdir.
Definition: track_func.h:447
Node::Key Key
key to hash tables
Definition: yapf_road.cpp:319
static const uint TILE_SIZE
Tile size in world coordinates.
Definition: tile_type.h:13
FindDepotData YapfRoadVehicleFindNearestDepot(const RoadVehicle *v, int max_distance)
Used when user sends road vehicle to the nearest depot or if road vehicle needs servicing using YAPF...
Definition: yapf_road.cpp:526
Buses, trucks and trams belong to this class.
Definition: roadveh.h:107
RoadType roadtype
Roadtype of this vehicle.
Definition: roadveh.h:117
char TransportTypeChar() const
return debug report character to identify the transportation type
Definition: yapf_road.cpp:344
static TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
Definition: map_func.h:341
static bool IsTileType(TileIndex tile, TileType type)
Checks if a tile is a given tiletype.
Definition: tile_map.h:150
CYapfBaseT - A-star type path finder base class.
Definition: yapf_base.hpp:49
bool disable_node_optimization
whether to use exit-dir instead of trackdir in node key
YAPFSettings yapf
pathfinder settings for the yet another pathfinder
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_road.cpp:316
static bool IsTruckStop(TileIndex t)
Is the station at t a truck stop?
Definition: station_map.h:180
static TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
Definition: track_func.h:119
bool IsType(OrderType type) const
Check whether this order is of the given type.
Definition: order_base.h:61
static DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
static bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
Definition: track_func.h:348
Trackdir GetVehicleTrackdir() const
Returns the Trackdir on which the vehicle is currently located.
Types::Tpf Tpf
pathfinder (derived from THIS class)
Definition: yapf_road.cpp:22
Flag for an invalid trackdir.
Definition: track_type.h:89
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
static bool IsRoadDepotTile(TileIndex t)
Return whether a tile is a road depot tile.
Definition: road_map.h:115
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Definition: yapf_road.cpp:200
TileIndex tile
Current tile index.
Definition: vehicle_base.h:228
bool HasArticulatedPart() const
Check if an engine has an articulated part.
Definition: vehicle_base.h:899
static Trackdir DiagDirToDiagTrackdir(DiagDirection diagdir)
Maps a (4-way) direction to the diagonal trackdir that runs in that direction.
Definition: track_func.h:545
bool IsFreeBay(uint nr) const
Checks whether the given bay is free in this road stop.
Definition: roadstop_base.h:93
static T min(const T a, const T b)
Returns the minimum of two values.
Definition: math_func.hpp:40
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_road.cpp:188
Track follower helper template class (can serve pathfinders and vehicle controllers).
static TileIndex CalcClosestStationTile(StationID station, TileIndex tile, StationType station_type)
Calculates the tile of given station that is closest to a given tile for this we assume the station i...
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
Definition: landscape.cpp:589
Container for each entry point of a drive through road stop.
Definition: roadstop_base.h:32
static const int YAPF_ROADVEH_PATH_CACHE_SEGMENTS
Maximum segments of road vehicle path cache.
static StationID GetStationIndex(TileIndex t)
Get StationID from a tile.
Definition: station_map.h:28
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_road.cpp:226
static T KillFirstBit(T value)
Clear the first bit in an integer.
bool IsBus() const
Check whether a roadvehicle is a bus.
Definition: roadveh_cmd.cpp:79
Node tailored for road pathfinding.
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_road.cpp:228
DestinationID GetDestination() const
Gets the destination of this order.
Definition: order_base.h:94
Tpf & Yapf()
to access inherited path finder
Definition: yapf_road.cpp:256
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:78
Helper container to find a depot.
Base includes/functions for YAPF.
static uint TileY(TileIndex tile)
Get the Y component of a tile.
Definition: map_func.h:215
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Definition: yapf_road.cpp:263
static T abs(const T a)
Returns the absolute value of (scalar) variable.
Definition: math_func.hpp:81
static bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
Definition: track_func.h:639
A tile of a station.
Definition: tile_type.h:46
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
Transport by road vehicle.
const Entry * GetEntry(DiagDirection dir) const
Get the drive through road stop entry struct for the given direction.
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_road.cpp:24
A Stop for a Road Vehicle.
Definition: roadstop_base.h:22
static bool IsDriveThroughRoadStopContinuation(TileIndex rs, TileIndex next)
Checks whether the &#39;next&#39; tile is still part of the road same drive through stop &#39;rs&#39; in the same dir...
Definition: roadstop.cpp:305
Tpf & Yapf()
to access inherited path finder
Definition: yapf_road.cpp:194
DiagDirection
Enumeration for diagonal directions.
Trackdir YapfRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found, RoadVehPathCache &path_cache)
Finds the best path for given road vehicle using YAPF.
Definition: yapf_road.cpp:511
static const uint MAX_MAP_SIZE
Maximal map size = 4096.
Definition: map_type.h:66
Node::Key Key
key to hash tables
Definition: yapf_road.cpp:25
Tpf & Yapf()
to access inherited path finder
Definition: yapf_road.cpp:33
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
Flag for an invalid trackdirbit value.
Definition: track_type.h:117
Types::TrackFollower TrackFollower
track follower helper
Definition: yapf_road.cpp:23
static bool IsBusStop(TileIndex t)
Is the station at t a bus stop?
Definition: station_map.h:191
static TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
Definition: track_func.h:360
Order current_order
The current order (+ status, like: loading)
Definition: vehicle_base.h:316
static RoadStop * GetByTile(TileIndex tile, RoadStopType type)
Find a roadstop at given tile.
Definition: roadstop.cpp:266
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Definition: yapf_road.cpp:214