OpenTTD Source  1.11.2
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 = std::min<int>(v->GetDisplayMaxSpeed(), v->current_order.GetMaxSpeed() * 2);
163  int max_speed = F.GetSpeedLimit(&min_speed);
164  if (max_speed < max_veh_speed) segment_cost += YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (4 + F.m_tiles_skipped) / max_veh_speed;
165  if (min_speed > max_veh_speed) segment_cost += YAPF_TILE_LENGTH * (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 
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  const Station *GetDestinationStation() const
255  {
256  return m_dest_station != INVALID_STATION ? Station::GetIfValid(m_dest_station) : nullptr;
257  }
258 
259 protected:
262  {
263  return *static_cast<Tpf *>(this);
264  }
265 
266 public:
268  inline bool PfDetectDestination(Node &n)
269  {
270  return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
271  }
272 
273  inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
274  {
275  if (m_dest_station != INVALID_STATION) {
276  return IsTileType(tile, MP_STATION) &&
277  GetStationIndex(tile) == m_dest_station &&
278  (m_bus ? IsBusStop(tile) : IsTruckStop(tile)) &&
279  (m_non_artic || IsDriveThroughStopTile(tile));
280  }
281 
282  return tile == m_destTile && HasTrackdir(m_destTrackdirs, trackdir);
283  }
284 
289  inline bool PfCalcEstimate(Node &n)
290  {
291  static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
292  static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
293  if (PfDetectDestination(n)) {
294  n.m_estimate = n.m_cost;
295  return true;
296  }
297 
298  TileIndex tile = n.m_segment_last_tile;
299  DiagDirection exitdir = TrackdirToExitdir(n.m_segment_last_td);
300  int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
301  int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
302  int x2 = 2 * TileX(m_destTile);
303  int y2 = 2 * TileY(m_destTile);
304  int dx = abs(x1 - x2);
305  int dy = abs(y1 - y2);
306  int dmin = std::min(dx, dy);
307  int dxy = abs(dx - dy);
308  int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
309  n.m_estimate = n.m_cost + d;
310  assert(n.m_estimate >= n.m_parent->m_estimate);
311  return true;
312  }
313 };
314 
315 
316 
317 template <class Types>
319 {
320 public:
321  typedef typename Types::Tpf Tpf;
322  typedef typename Types::TrackFollower TrackFollower;
323  typedef typename Types::NodeList::Titem Node;
324  typedef typename Node::Key Key;
325 
326 protected:
328  inline Tpf& Yapf()
329  {
330  return *static_cast<Tpf *>(this);
331  }
332 
333 public:
334 
340  inline void PfFollowNode(Node &old_node)
341  {
342  TrackFollower F(Yapf().GetVehicle());
343  if (F.Follow(old_node.m_segment_last_tile, old_node.m_segment_last_td)) {
344  Yapf().AddMultipleNodes(&old_node, F);
345  }
346  }
347 
349  inline char TransportTypeChar() const
350  {
351  return 'r';
352  }
353 
354  static Trackdir stChooseRoadTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, bool &path_found, RoadVehPathCache &path_cache)
355  {
356  Tpf pf;
357  return pf.ChooseRoadTrack(v, tile, enterdir, path_found, path_cache);
358  }
359 
360  inline Trackdir ChooseRoadTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, bool &path_found, RoadVehPathCache &path_cache)
361  {
362  /* Handle special case - when next tile is destination tile.
363  * However, when going to a station the (initial) destination
364  * tile might not be a station, but a junction, in which case
365  * this method forces the vehicle to jump in circles. */
366  if (tile == v->dest_tile && !v->current_order.IsType(OT_GOTO_STATION)) {
367  /* choose diagonal trackdir reachable from enterdir */
368  return DiagDirToDiagTrackdir(enterdir);
369  }
370  /* our source tile will be the next vehicle tile (should be the given one) */
371  TileIndex src_tile = tile;
372  /* get available trackdirs on the start tile */
373  TrackdirBits src_trackdirs = GetTrackdirBitsForRoad(tile, GetRoadTramType(v->roadtype));
374  /* select reachable trackdirs only */
375  src_trackdirs &= DiagdirReachesTrackdirs(enterdir);
376 
377  /* set origin and destination nodes */
378  Yapf().SetOrigin(src_tile, src_trackdirs);
379  Yapf().SetDestination(v);
380 
381  /* find the best path */
382  path_found = Yapf().FindPath(v);
383 
384  /* if path not found - return INVALID_TRACKDIR */
385  Trackdir next_trackdir = INVALID_TRACKDIR;
386  Node *pNode = Yapf().GetBestNode();
387  if (pNode != nullptr) {
388  uint steps = 0;
389  for (Node *n = pNode; n->m_parent != nullptr; n = n->m_parent) steps++;
390 
391  /* path was found or at least suggested
392  * walk through the path back to its origin */
393  while (pNode->m_parent != nullptr) {
394  steps--;
395  if (pNode->GetIsChoice() && steps < YAPF_ROADVEH_PATH_CACHE_SEGMENTS) {
396  path_cache.td.push_front(pNode->GetTrackdir());
397  path_cache.tile.push_front(pNode->GetTile());
398  }
399  pNode = pNode->m_parent;
400  }
401  /* return trackdir from the best origin node (one of start nodes) */
402  Node &best_next_node = *pNode;
403  assert(best_next_node.GetTile() == tile);
404  next_trackdir = best_next_node.GetTrackdir();
405  /* remove last element for the special case when tile == dest_tile */
406  if (path_found && !path_cache.empty() && tile == v->dest_tile) {
407  path_cache.td.pop_back();
408  path_cache.tile.pop_back();
409  }
410 
411  /* Check if target is a station, and cached path ends within 8 tiles of the dest tile */
412  const Station *st = Yapf().GetDestinationStation();
413  if (st) {
414  const RoadStop *stop = st->GetPrimaryRoadStop(v);
415  if (stop != nullptr && (IsDriveThroughStopTile(stop->xy) || stop->GetNextRoadStop(v) != nullptr)) {
416  /* Destination station has at least 2 usable road stops, or first is a drive-through stop,
417  * trim end of path cache within a number of tiles of road stop tile area */
418  TileArea non_cached_area = v->IsBus() ? st->bus_station : st->truck_station;
420  while (!path_cache.empty() && non_cached_area.Contains(path_cache.tile.back())) {
421  path_cache.td.pop_back();
422  path_cache.tile.pop_back();
423  }
424  }
425  }
426  }
427  return next_trackdir;
428  }
429 
430  static uint stDistanceToTile(const RoadVehicle *v, TileIndex tile)
431  {
432  Tpf pf;
433  return pf.DistanceToTile(v, tile);
434  }
435 
436  inline uint DistanceToTile(const RoadVehicle *v, TileIndex dst_tile)
437  {
438  /* handle special case - when current tile is the destination tile */
439  if (dst_tile == v->tile) {
440  /* distance is zero in this case */
441  return 0;
442  }
443 
444  if (!SetOriginFromVehiclePos(v)) return UINT_MAX;
445 
446  /* get available trackdirs on the destination tile */
447  Yapf().SetDestination(v);
448 
449  /* if path not found - return distance = UINT_MAX */
450  uint dist = UINT_MAX;
451 
452  /* find the best path */
453  if (!Yapf().FindPath(v)) return dist;
454 
455  Node *pNode = Yapf().GetBestNode();
456  if (pNode != nullptr) {
457  /* path was found
458  * get the path cost estimate */
459  dist = pNode->GetCostEstimate();
460  }
461 
462  return dist;
463  }
464 
466  inline bool SetOriginFromVehiclePos(const RoadVehicle *v)
467  {
468  /* set origin (tile, trackdir) */
469  TileIndex src_tile = v->tile;
470  Trackdir src_td = v->GetVehicleTrackdir();
471  if (!HasTrackdir(GetTrackdirBitsForRoad(src_tile, this->IsTram() ? RTT_TRAM : RTT_ROAD), src_td)) {
472  /* sometimes the roadveh is not on the road (it resides on non-existing track)
473  * how should we handle that situation? */
474  return false;
475  }
476  Yapf().SetOrigin(src_tile, TrackdirToTrackdirBits(src_td));
477  return true;
478  }
479 
480  static FindDepotData stFindNearestDepot(const RoadVehicle *v, TileIndex tile, Trackdir td, int max_distance)
481  {
482  Tpf pf;
483  return pf.FindNearestDepot(v, tile, td, max_distance);
484  }
485 
493  inline FindDepotData FindNearestDepot(const RoadVehicle *v, TileIndex tile, Trackdir td, int max_distance)
494  {
495  /* Set origin. */
496  Yapf().SetOrigin(tile, TrackdirToTrackdirBits(td));
497  Yapf().SetMaxCost(max_distance);
498 
499  /* Find the best path and return if no depot is found. */
500  if (!Yapf().FindPath(v)) return FindDepotData();
501 
502  /* Return the cost of the best path and its depot. */
503  Node *n = Yapf().GetBestNode();
504  return FindDepotData(n->m_segment_last_tile, n->m_cost);
505  }
506 };
507 
508 template <class Tpf_, class Tnode_list, template <class Types> class Tdestination>
510 {
512 
513  typedef Tpf_ Tpf;
515  typedef Tnode_list NodeList;
516  typedef RoadVehicle VehicleType;
517  typedef CYapfBaseT<Types> PfBase;
520  typedef Tdestination<Types> PfDestination;
523 };
524 
525 struct CYapfRoad1 : CYapfT<CYapfRoad_TypesT<CYapfRoad1 , CRoadNodeListTrackDir, CYapfDestinationTileRoadT > > {};
526 struct CYapfRoad2 : CYapfT<CYapfRoad_TypesT<CYapfRoad2 , CRoadNodeListExitDir , CYapfDestinationTileRoadT > > {};
527 
528 struct CYapfRoadAnyDepot1 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};
529 struct CYapfRoadAnyDepot2 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};
530 
531 
532 Trackdir YapfRoadVehicleChooseTrack(const RoadVehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool &path_found, RoadVehPathCache &path_cache)
533 {
534  /* default is YAPF type 2 */
535  typedef Trackdir (*PfnChooseRoadTrack)(const RoadVehicle*, TileIndex, DiagDirection, bool &path_found, RoadVehPathCache &path_cache);
536  PfnChooseRoadTrack pfnChooseRoadTrack = &CYapfRoad2::stChooseRoadTrack; // default: ExitDir, allow 90-deg
537 
538  /* check if non-default YAPF type should be used */
540  pfnChooseRoadTrack = &CYapfRoad1::stChooseRoadTrack; // Trackdir
541  }
542 
543  Trackdir td_ret = pfnChooseRoadTrack(v, tile, enterdir, path_found, path_cache);
544  return (td_ret != INVALID_TRACKDIR) ? td_ret : (Trackdir)FindFirstBit2x64(trackdirs);
545 }
546 
548 {
549  TileIndex tile = v->tile;
550  Trackdir trackdir = v->GetVehicleTrackdir();
551 
552  if (!HasTrackdir(GetTrackdirBitsForRoad(tile, GetRoadTramType(v->roadtype)), trackdir)) {
553  return FindDepotData();
554  }
555 
556  /* default is YAPF type 2 */
557  typedef FindDepotData (*PfnFindNearestDepot)(const RoadVehicle*, TileIndex, Trackdir, int);
558  PfnFindNearestDepot pfnFindNearestDepot = &CYapfRoadAnyDepot2::stFindNearestDepot;
559 
560  /* check if non-default YAPF type should be used */
562  pfnFindNearestDepot = &CYapfRoadAnyDepot1::stFindNearestDepot; // Trackdir
563  }
564 
565  return pfnFindNearestDepot(v, tile, trackdir, max_distance);
566 }
RoadVehicle
Buses, trucks and trams belong to this class.
Definition: roadveh.h:107
CYapfCostRoadT::Yapf
Tpf & Yapf()
to access inherited path finder
Definition: yapf_road.cpp:33
GetRoadDepotDirection
static DiagDirection GetRoadDepotDirection(TileIndex t)
Get the direction of the exit of a road depot.
Definition: road_map.h:565
TileIndex
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:83
CYapfDestinationAnyDepotRoadT::Key
Node::Key Key
key to hash tables
Definition: yapf_road.cpp:191
Order::IsType
bool IsType(OrderType type) const
Check whether this order is of the given type.
Definition: order_base.h:61
TileOffsByDiagDir
static TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
Definition: map_func.h:341
IsBusStop
static bool IsBusStop(TileIndex t)
Is the station at t a bus stop?
Definition: station_map.h:191
FindDepotData
Helper container to find a depot.
Definition: pathfinder_type.h:53
TrackdirBits
TrackdirBits
Enumeration of bitmasks for the TrackDirs.
Definition: track_type.h:101
LinkGraph::Node
Updatable node class.
Definition: linkgraph.h:373
CYapfCostRoadT::PfCalcCost
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
RoadStop::Entry::GetOccupied
int GetOccupied() const
Get the amount of occupied space in this drive through stop.
Definition: roadstop_base.h:56
RoadStop::xy
TileIndex xy
Position on the map.
Definition: roadstop_base.h:67
Station
Station data structure.
Definition: station_base.h:450
Order::GetDestination
DestinationID GetDestination() const
Gets the destination of this order.
Definition: order_base.h:94
CYapfDestinationTileRoadT::PfCalcEstimate
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Definition: yapf_road.cpp:289
yapf.hpp
CYapfCostRoadT::OneTileCost
int OneTileCost(TileIndex tile, Trackdir trackdir)
return one tile cost
Definition: yapf_road.cpp:58
IsRoadDepotTile
static bool IsRoadDepotTile(TileIndex t)
Return whether a tile is a road depot tile.
Definition: road_map.h:115
CYapfDestinationAnyDepotRoadT::PfCalcEstimate
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
Definition: yapf_road.cpp:214
CYapfCostRoadT::TrackFollower
Types::TrackFollower TrackFollower
track follower helper
Definition: yapf_road.cpp:23
KillFirstBit
static T KillFirstBit(T value)
Clear the first bit in an integer.
Definition: bitmath_func.hpp:239
YapfRoadVehicleFindNearestDepot
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:547
DiagDirToDiagTrackdir
static Trackdir DiagDirToDiagTrackdir(DiagDirection diagdir)
Maps a (4-way) direction to the diagonal trackdir that runs in that direction.
Definition: track_func.h:545
GetRoadStopType
static RoadStopType GetRoadStopType(TileIndex t)
Get the road stop type of this tile.
Definition: station_map.h:56
RoadStop::GetByTile
static RoadStop * GetByTile(TileIndex tile, RoadStopType type)
Find a roadstop at given tile.
Definition: roadstop.cpp:266
IsDriveThroughStopTile
static bool IsDriveThroughStopTile(TileIndex t)
Is tile t a drive through road stop station?
Definition: station_map.h:233
TILE_SIZE
static const uint TILE_SIZE
Tile size in world coordinates.
Definition: tile_type.h:13
RoadStop::GetEntry
const Entry * GetEntry(DiagDirection dir) const
Get the drive through road stop entry struct for the given direction.
Definition: roadstop_base.h:122
TileY
static uint TileY(TileIndex tile)
Get the Y component of a tile.
Definition: map_func.h:215
CYapfT
YAPF template that uses Ttypes template argument to determine all YAPF components (base classes) from...
Definition: yapf_common.hpp:183
RoadVehicle::roadtype
RoadType roadtype
Roadtype of this vehicle.
Definition: roadveh.h:117
IsTruckStop
static bool IsTruckStop(TileIndex t)
Is the station at t a truck stop?
Definition: station_map.h:180
MP_ROAD
@ MP_ROAD
A tile with road (or tram tracks)
Definition: tile_type.h:48
IsLevelCrossing
static bool IsLevelCrossing(TileIndex t)
Return whether a tile is a level crossing.
Definition: road_map.h:84
CYapfDestinationAnyDepotRoadT::Node
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_road.cpp:190
INVALID_TRACKDIR_BIT
@ INVALID_TRACKDIR_BIT
Flag for an invalid trackdirbit value.
Definition: track_type.h:117
TileX
static uint TileX(TileIndex tile)
Get the X component of a tile.
Definition: map_func.h:205
GetTileTrackStatus
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
Definition: landscape.cpp:590
Order::GetMaxSpeed
uint16 GetMaxSpeed() const
Get the maxmimum speed in km-ish/h a vehicle is allowed to reach on the way to the destination.
Definition: order_base.h:192
CYapfOriginTileT
YAPF origin provider base class - used when origin is one tile / multiple trackdirs.
Definition: yapf_common.hpp:15
TRANSPORT_ROAD
@ TRANSPORT_ROAD
Transport by road vehicle.
Definition: transport_type.h:28
GameSettings::pf
PathfinderSettings pf
settings for all pathfinders
Definition: settings_type.h:570
Vehicle::dest_tile
TileIndex dest_tile
Heading for this tile.
Definition: vehicle_base.h:247
CYapfRoadAnyDepot2
Definition: yapf_road.cpp:529
CYapfCostRoadT::Tpf
Types::Tpf Tpf
pathfinder (derived from THIS class)
Definition: yapf_road.cpp:22
YAPF_TILE_LENGTH
static const int YAPF_TILE_LENGTH
Length (penalty) of one tile with YAPF.
Definition: pathfinder_type.h:28
Vehicle::tile
TileIndex tile
Current tile index.
Definition: vehicle_base.h:240
TrackdirToExitdir
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
Station::truck_station
TileArea truck_station
Tile area the truck 'station' part covers.
Definition: station_base.h:462
Vehicle::current_order
Order current_order
The current order (+ status, like: loading)
Definition: vehicle_base.h:327
FindFirstBit2x64
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
Definition: bitmath_func.hpp:216
OrthogonalTileArea
Represents the covered area of e.g.
Definition: tilearea_type.h:16
_settings_game
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:80
CYapfCostRoadT
Definition: yapf_road.cpp:19
ReverseDiagDir
static DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
Definition: direction_func.h:118
Station::bus_station
TileArea bus_station
Tile area the bus 'station' part covers.
Definition: station_base.h:460
INVALID_TRACKDIR
@ INVALID_TRACKDIR
Flag for an invalid trackdir.
Definition: track_type.h:89
CYapfDestinationTileRoadT::Tpf
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_road.cpp:226
DiagDirection
DiagDirection
Enumeration for diagonal directions.
Definition: direction_type.h:77
CYapfDestinationAnyDepotRoadT
Definition: yapf_road.cpp:185
YAPF_ROADVEH_PATH_CACHE_SEGMENTS
static const int YAPF_ROADVEH_PATH_CACHE_SEGMENTS
Maximum segments of road vehicle path cache.
Definition: pathfinder_type.h:45
CYapfRoadAnyDepot1
Definition: yapf_road.cpp:528
IsTileType
static bool IsTileType(TileIndex tile, TileType type)
Checks if a tile is a given tiletype.
Definition: tile_map.h:150
CYapfCostRoadT::Node
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_road.cpp:24
CalcClosestStationTile
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...
Definition: pathfinder_func.h:25
CYapfFollowRoadT::SetOriginFromVehiclePos
bool SetOriginFromVehiclePos(const RoadVehicle *v)
Return true if the valid origin (tile/trackdir) was set from the current vehicle position.
Definition: yapf_road.cpp:466
DiagdirReachesTrackdirs
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
CYapfFollowRoadT::Yapf
Tpf & Yapf()
to access inherited path finder
Definition: yapf_road.cpp:328
CYapfSegmentCostCacheNoneT
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
Definition: yapf_costcache.hpp:21
CYapfRoad1
Definition: yapf_road.cpp:525
GetTrackdirBitsForRoad
static TrackdirBits GetTrackdirBitsForRoad(TileIndex tile, RoadTramType rtt)
Wrapper around GetTileTrackStatus() and TrackStatusToTrackdirBits(), as for single tram bits GetTileT...
Definition: pathfinder_func.h:60
TRACKDIR_BIT_NONE
@ TRACKDIR_BIT_NONE
No track build.
Definition: track_type.h:102
CYapfDestinationTileRoadT::Node
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_road.cpp:228
CYapfDestinationTileRoadT
Definition: yapf_road.cpp:223
CYapfDestinationAnyDepotRoadT::Tpf
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_road.cpp:188
CYapfDestinationAnyDepotRoadT::PfDetectDestination
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Definition: yapf_road.cpp:200
CYapfFollowRoadT::Node
Types::NodeList::Titem Node
this will be our node type
Definition: yapf_road.cpp:323
RoadVehPathCache
Definition: roadveh.h:85
CYapfRoad_TypesT
Definition: yapf_road.cpp:509
RoadStop::IsDriveThroughRoadStopContinuation
static bool IsDriveThroughRoadStopContinuation(TileIndex rs, TileIndex next)
Checks whether the 'next' tile is still part of the road same drive through stop 'rs' in the same dir...
Definition: roadstop.cpp:305
CYapfFollowRoadT::PfFollowNode
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
Definition: yapf_road.cpp:340
YAPFSettings::disable_node_optimization
bool disable_node_optimization
whether to use exit-dir instead of trackdir in node key
Definition: settings_type.h:391
MP_STATION
@ MP_STATION
A tile of a station.
Definition: tile_type.h:51
GetStationIndex
static StationID GetStationIndex(TileIndex t)
Get StationID from a tile.
Definition: station_map.h:28
Vehicle::HasArticulatedPart
bool HasArticulatedPart() const
Check if an engine has an articulated part.
Definition: vehicle_base.h:913
CYapfDestinationTileRoadT::Yapf
Tpf & Yapf()
to access inherited path finder
Definition: yapf_road.cpp:261
CYapfFollowRoadT::Key
Node::Key Key
key to hash tables
Definition: yapf_road.cpp:324
TrackStatusToTrackdirBits
static TrackdirBits TrackStatusToTrackdirBits(TrackStatus ts)
Returns the present-trackdir-information of a TrackStatus.
Definition: track_func.h:360
RoadStop::Entry::GetLength
int GetLength() const
Get the length of this drive through stop.
Definition: roadstop_base.h:47
RoadVehicle::GetDisplayMaxSpeed
int GetDisplayMaxSpeed() const
Gets the maximum speed in km-ish/h that can be sent into SetDParam for string processing.
Definition: roadveh.h:133
abs
static T abs(const T a)
Returns the absolute value of (scalar) variable.
Definition: math_func.hpp:21
CYapfDestinationAnyDepotRoadT::Yapf
Tpf & Yapf()
to access inherited path finder
Definition: yapf_road.cpp:194
TrackdirToTrackdirBits
static TrackdirBits TrackdirToTrackdirBits(Trackdir trackdir)
Maps a Trackdir to the corresponding TrackdirBits value.
Definition: track_func.h:119
CYapfFollowRoadT::FindNearestDepot
FindDepotData FindNearestDepot(const RoadVehicle *v, TileIndex tile, Trackdir td, int max_distance)
Find the best depot for a road vehicle.
Definition: yapf_road.cpp:493
CYapfFollowRoadT::TransportTypeChar
char TransportTypeChar() const
return debug report character to identify the transportation type
Definition: yapf_road.cpp:349
PathfinderSettings::yapf
YAPFSettings yapf
pathfinder settings for the yet another pathfinder
Definition: settings_type.h:450
SpecializedStation< Station, false >::GetIfValid
static Station * GetIfValid(size_t index)
Returns station if the index is a valid index for this station type.
Definition: base_station_base.h:228
YAPF_TILE_CORNER_LENGTH
static const int YAPF_TILE_CORNER_LENGTH
Length (penalty) of a corner with YAPF.
Definition: pathfinder_type.h:31
RoadStop::IsFreeBay
bool IsFreeBay(uint nr) const
Checks whether the given bay is free in this road stop.
Definition: roadstop_base.h:93
RoadVehicle::IsBus
bool IsBus() const
Check whether a roadvehicle is a bus.
Definition: roadveh_cmd.cpp:79
CYapfRoad2
Definition: yapf_road.cpp:526
OrthogonalTileArea::Expand
OrthogonalTileArea & Expand(int rad)
Expand a tile area by rad tiles in each direction, keeping within map bounds.
Definition: tilearea.cpp:123
Trackdir
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:70
CYapfCostRoadT::Key
Node::Key Key
key to hash tables
Definition: yapf_road.cpp:25
CYapfBaseT
CYapfBaseT - A-star type path finder base class.
Definition: yapf_base.hpp:47
GetTileType
static TileType GetTileType(TileIndex tile)
Get the tiletype of a given tile.
Definition: tile_map.h:96
CYapfFollowRoadT::Tpf
Types::Tpf Tpf
the pathfinder class (derived from THIS class)
Definition: yapf_road.cpp:321
YAPF_ROADVEH_PATH_CACHE_DESTINATION_LIMIT
static const int YAPF_ROADVEH_PATH_CACHE_DESTINATION_LIMIT
Distance from destination road stops to not cache any further.
Definition: pathfinder_type.h:48
yapf_node_road.hpp
RoadStop
A Stop for a Road Vehicle.
Definition: roadstop_base.h:22
MAX_MAP_SIZE
static const uint MAX_MAP_SIZE
Maximal map size = 4096.
Definition: map_type.h:66
YapfRoadVehicleChooseTrack
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:532
HasTrackdir
static bool HasTrackdir(TrackdirBits trackdirs, Trackdir trackdir)
Checks whether a TrackdirBits has a given Trackdir.
Definition: track_func.h:348
RoadStop::Entry
Container for each entry point of a drive through road stop.
Definition: roadstop_base.h:32
CYapfFollowRoadT
Definition: yapf_road.cpp:318
CYapfDestinationTileRoadT::Key
Node::Key Key
key to hash tables
Definition: yapf_road.cpp:229
RoadStop::GetNextRoadStop
RoadStop * GetNextRoadStop(const struct RoadVehicle *v) const
Get the next road stop accessible by this vehicle.
Definition: roadstop.cpp:42
CFollowTrackT
Track follower helper template class (can serve pathfinders and vehicle controllers).
Definition: follow_track.hpp:28
RoadVehicle::GetVehicleTrackdir
Trackdir GetVehicleTrackdir() const
Returns the Trackdir on which the vehicle is currently located.
Definition: roadveh_cmd.cpp:1729
IsDiagonalTrackdir
static bool IsDiagonalTrackdir(Trackdir trackdir)
Checks if a given Trackdir is diagonal.
Definition: track_func.h:639
OrthogonalTileArea::Contains
bool Contains(TileIndex tile) const
Does this tile area contain a tile?
Definition: tilearea.cpp:104
CYapfDestinationTileRoadT::PfDetectDestination
bool PfDetectDestination(Node &n)
Called by YAPF to detect if node ends in the desired destination.
Definition: yapf_road.cpp:268