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
8 /** @file yapf_rail.cpp The rail pathfinding. */
9
10 #include "../../stdafx.h"
11
12 #include "yapf.hpp"
13 #include "yapf_cache.h"
14 #include "yapf_node_rail.hpp"
15 #include "yapf_costrail.hpp"
16 #include "yapf_destrail.hpp"
17 #include "../../viewport_func.h"
18 #include "../../newgrf_station.h"
19
20 #include "../../safeguards.h"
21
DumpState(Tpf & pf1,Tpf & pf2)22 template <typename Tpf> void DumpState(Tpf &pf1, Tpf &pf2)
23 {
24 DumpTarget dmp1, dmp2;
25 pf1.DumpBase(dmp1);
26 pf2.DumpBase(dmp2);
27 FILE *f1 = fopen("yapf1.txt", "wt");
28 FILE *f2 = fopen("yapf2.txt", "wt");
29 assert(f1 != nullptr);
30 assert(f2 != nullptr);
31 fwrite(dmp1.m_out.c_str(), 1, dmp1.m_out.size(), f1);
32 fwrite(dmp2.m_out.c_str(), 1, dmp2.m_out.size(), f2);
33 fclose(f1);
34 fclose(f2);
35 }
36
37 template <class Types>
38 class CYapfReserveTrack
39 {
40 public:
41 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class)
42 typedef typename Types::TrackFollower TrackFollower;
43 typedef typename Types::NodeList::Titem Node; ///< this will be our node type
44
45 protected:
46 /** to access inherited pathfinder */
Yapf()47 inline Tpf& Yapf()
48 {
49 return *static_cast<Tpf *>(this);
50 }
51
52 private:
53 TileIndex m_res_dest; ///< The reservation target tile
54 Trackdir m_res_dest_td; ///< The reservation target trackdir
55 Node *m_res_node; ///< The reservation target node
56 TileIndex m_res_fail_tile; ///< The tile where the reservation failed
57 Trackdir m_res_fail_td; ///< The trackdir where the reservation failed
58 TileIndex m_origin_tile; ///< Tile our reservation will originate from
59
FindSafePositionProc(TileIndex tile,Trackdir td)60 bool FindSafePositionProc(TileIndex tile, Trackdir td)
61 {
62 if (IsSafeWaitingPosition(Yapf().GetVehicle(), tile, td, true, !TrackFollower::Allow90degTurns())) {
63 m_res_dest = tile;
64 m_res_dest_td = td;
65 return false; // Stop iterating segment
66 }
67 return true;
68 }
69
70 /** Reserve a railway platform. Tile contains the failed tile on abort. */
ReserveRailStationPlatform(TileIndex & tile,DiagDirection dir)71 bool ReserveRailStationPlatform(TileIndex &tile, DiagDirection dir)
72 {
73 TileIndex start = tile;
74 TileIndexDiff diff = TileOffsByDiagDir(dir);
75
76 do {
77 if (HasStationReservation(tile)) return false;
78 SetRailStationReservation(tile, true);
79 MarkTileDirtyByTile(tile);
80 tile = TILE_ADD(tile, diff);
81 } while (IsCompatibleTrainStationTile(tile, start) && tile != m_origin_tile);
82
83 TriggerStationRandomisation(nullptr, start, SRT_PATH_RESERVATION);
84
85 return true;
86 }
87
88 /** Try to reserve a single track/platform. */
ReserveSingleTrack(TileIndex tile,Trackdir td)89 bool ReserveSingleTrack(TileIndex tile, Trackdir td)
90 {
91 if (IsRailStationTile(tile)) {
92 if (!ReserveRailStationPlatform(tile, TrackdirToExitdir(ReverseTrackdir(td)))) {
93 /* Platform could not be reserved, undo. */
94 m_res_fail_tile = tile;
95 m_res_fail_td = td;
96 }
97 } else {
98 if (!TryReserveRailTrack(tile, TrackdirToTrack(td))) {
99 /* Tile couldn't be reserved, undo. */
100 m_res_fail_tile = tile;
101 m_res_fail_td = td;
102 return false;
103 }
104 }
105
106 return tile != m_res_dest || td != m_res_dest_td;
107 }
108
109 /** Unreserve a single track/platform. Stops when the previous failer is reached. */
UnreserveSingleTrack(TileIndex tile,Trackdir td)110 bool UnreserveSingleTrack(TileIndex tile, Trackdir td)
111 {
112 if (IsRailStationTile(tile)) {
113 TileIndex start = tile;
114 TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(td)));
115 while ((tile != m_res_fail_tile || td != m_res_fail_td) && IsCompatibleTrainStationTile(tile, start)) {
116 SetRailStationReservation(tile, false);
117 tile = TILE_ADD(tile, diff);
118 }
119 } else if (tile != m_res_fail_tile || td != m_res_fail_td) {
120 UnreserveRailTrack(tile, TrackdirToTrack(td));
121 }
122 return (tile != m_res_dest || td != m_res_dest_td) && (tile != m_res_fail_tile || td != m_res_fail_td);
123 }
124
125 public:
126 /** Set the target to where the reservation should be extended. */
SetReservationTarget(Node * node,TileIndex tile,Trackdir td)127 inline void SetReservationTarget(Node *node, TileIndex tile, Trackdir td)
128 {
129 m_res_node = node;
130 m_res_dest = tile;
131 m_res_dest_td = td;
132 }
133
134 /** Check the node for a possible reservation target. */
FindSafePositionOnNode(Node * node)135 inline void FindSafePositionOnNode(Node *node)
136 {
137 assert(node->m_parent != nullptr);
138
139 /* We will never pass more than two signals, no need to check for a safe tile. */
140 if (node->m_parent->m_num_signals_passed >= 2) return;
141
142 if (!node->IterateTiles(Yapf().GetVehicle(), Yapf(), *this, &CYapfReserveTrack<Types>::FindSafePositionProc)) {
143 m_res_node = node;
144 }
145 }
146
147 /** Try to reserve the path till the reservation target. */
TryReservePath(PBSTileInfo * target,TileIndex origin)148 bool TryReservePath(PBSTileInfo *target, TileIndex origin)
149 {
150 m_res_fail_tile = INVALID_TILE;
151 m_origin_tile = origin;
152
153 if (target != nullptr) {
154 target->tile = m_res_dest;
155 target->trackdir = m_res_dest_td;
156 target->okay = false;
157 }
158
159 /* Don't bother if the target is reserved. */
160 if (!IsWaitingPositionFree(Yapf().GetVehicle(), m_res_dest, m_res_dest_td)) return false;
161
162 for (Node *node = m_res_node; node->m_parent != nullptr; node = node->m_parent) {
163 node->IterateTiles(Yapf().GetVehicle(), Yapf(), *this, &CYapfReserveTrack<Types>::ReserveSingleTrack);
164 if (m_res_fail_tile != INVALID_TILE) {
165 /* Reservation failed, undo. */
166 Node *fail_node = m_res_node;
167 TileIndex stop_tile = m_res_fail_tile;
168 do {
169 /* If this is the node that failed, stop at the failed tile. */
170 m_res_fail_tile = fail_node == node ? stop_tile : INVALID_TILE;
171 fail_node->IterateTiles(Yapf().GetVehicle(), Yapf(), *this, &CYapfReserveTrack<Types>::UnreserveSingleTrack);
172 } while (fail_node != node && (fail_node = fail_node->m_parent) != nullptr);
173
174 return false;
175 }
176 }
177
178 if (target != nullptr) target->okay = true;
179
180 if (Yapf().CanUseGlobalCache(*m_res_node)) {
181 YapfNotifyTrackLayoutChange(INVALID_TILE, INVALID_TRACK);
182 }
183
184 return true;
185 }
186 };
187
188 template <class Types>
189 class CYapfFollowAnyDepotRailT
190 {
191 public:
192 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class)
193 typedef typename Types::TrackFollower TrackFollower;
194 typedef typename Types::NodeList::Titem Node; ///< this will be our node type
195 typedef typename Node::Key Key; ///< key to hash tables
196
197 protected:
198 /** to access inherited path finder */
Yapf()199 inline Tpf& Yapf()
200 {
201 return *static_cast<Tpf *>(this);
202 }
203
204 public:
205 /**
206 * Called by YAPF to move from the given node to the next tile. For each
207 * reachable trackdir on the new tile creates new node, initializes it
208 * and adds it to the open list by calling Yapf().AddNewNode(n)
209 */
PfFollowNode(Node & old_node)210 inline void PfFollowNode(Node &old_node)
211 {
212 TrackFollower F(Yapf().GetVehicle());
213 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
214 Yapf().AddMultipleNodes(&old_node, F);
215 }
216 }
217
218 /** return debug report character to identify the transportation type */
TransportTypeChar() const219 inline char TransportTypeChar() const
220 {
221 return 't';
222 }
223
stFindNearestDepotTwoWay(const Train * v,TileIndex t1,Trackdir td1,TileIndex t2,Trackdir td2,int max_penalty,int reverse_penalty)224 static FindDepotData stFindNearestDepotTwoWay(const Train *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_penalty, int reverse_penalty)
225 {
226 Tpf pf1;
227 /*
228 * With caching enabled it simply cannot get a reliable result when you
229 * have limited the distance a train may travel. This means that the
230 * cached result does not match uncached result in all cases and that
231 * causes desyncs. So disable caching when finding for a depot that is
232 * nearby. This only happens with automatic servicing of vehicles,
233 * so it will only impact performance when you do not manually set
234 * depot orders and you do not disable automatic servicing.
235 */
236 if (max_penalty != 0) pf1.DisableCache(true);
237 FindDepotData result1 = pf1.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
238
239 if (_debug_desync_level >= 2) {
240 Tpf pf2;
241 pf2.DisableCache(true);
242 FindDepotData result2 = pf2.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_penalty, reverse_penalty);
243 if (result1.tile != result2.tile || (result1.reverse != result2.reverse)) {
244 Debug(desync, 2, "CACHE ERROR: FindNearestDepotTwoWay() = [{}, {}]",
245 result1.tile != INVALID_TILE ? "T" : "F",
246 result2.tile != INVALID_TILE ? "T" : "F");
247 DumpState(pf1, pf2);
248 }
249 }
250
251 return result1;
252 }
253
FindNearestDepotTwoWay(const Train * v,TileIndex t1,Trackdir td1,TileIndex t2,Trackdir td2,int max_penalty,int reverse_penalty)254 inline FindDepotData FindNearestDepotTwoWay(const Train *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_penalty, int reverse_penalty)
255 {
256 /* set origin and destination nodes */
257 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, true);
258 Yapf().SetDestination(v);
259 Yapf().SetMaxCost(max_penalty);
260
261 /* find the best path */
262 if (!Yapf().FindPath(v)) return FindDepotData();
263
264 /* Some path found. */
265 Node *n = Yapf().GetBestNode();
266
267 /* walk through the path back to the origin */
268 Node *pNode = n;
269 while (pNode->m_parent != nullptr) {
270 pNode = pNode->m_parent;
271 }
272
273 /* if the origin node is our front vehicle tile/Trackdir then we didn't reverse
274 * but we can also look at the cost (== 0 -> not reversed, == reverse_penalty -> reversed) */
275 return FindDepotData(n->GetLastTile(), n->m_cost, pNode->m_cost != 0);
276 }
277 };
278
279 template <class Types>
280 class CYapfFollowAnySafeTileRailT : public CYapfReserveTrack<Types>
281 {
282 public:
283 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class)
284 typedef typename Types::TrackFollower TrackFollower;
285 typedef typename Types::NodeList::Titem Node; ///< this will be our node type
286 typedef typename Node::Key Key; ///< key to hash tables
287
288 protected:
289 /** to access inherited path finder */
Yapf()290 inline Tpf& Yapf()
291 {
292 return *static_cast<Tpf *>(this);
293 }
294
295 public:
296 /**
297 * Called by YAPF to move from the given node to the next tile. For each
298 * reachable trackdir on the new tile creates new node, initializes it
299 * and adds it to the open list by calling Yapf().AddNewNode(n)
300 */
PfFollowNode(Node & old_node)301 inline void PfFollowNode(Node &old_node)
302 {
303 TrackFollower F(Yapf().GetVehicle(), Yapf().GetCompatibleRailTypes());
304 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()) && F.MaskReservedTracks()) {
305 Yapf().AddMultipleNodes(&old_node, F);
306 }
307 }
308
309 /** Return debug report character to identify the transportation type */
TransportTypeChar() const310 inline char TransportTypeChar() const
311 {
312 return 't';
313 }
314
stFindNearestSafeTile(const Train * v,TileIndex t1,Trackdir td,bool override_railtype)315 static bool stFindNearestSafeTile(const Train *v, TileIndex t1, Trackdir td, bool override_railtype)
316 {
317 /* Create pathfinder instance */
318 Tpf pf1;
319 bool result1;
320 if (_debug_desync_level < 2) {
321 result1 = pf1.FindNearestSafeTile(v, t1, td, override_railtype, false);
322 } else {
323 bool result2 = pf1.FindNearestSafeTile(v, t1, td, override_railtype, true);
324 Tpf pf2;
325 pf2.DisableCache(true);
326 result1 = pf2.FindNearestSafeTile(v, t1, td, override_railtype, false);
327 if (result1 != result2) {
328 Debug(desync, 2, "CACHE ERROR: FindSafeTile() = [{}, {}]", result2 ? "T" : "F", result1 ? "T" : "F");
329 DumpState(pf1, pf2);
330 }
331 }
332
333 return result1;
334 }
335
FindNearestSafeTile(const Train * v,TileIndex t1,Trackdir td,bool override_railtype,bool dont_reserve)336 bool FindNearestSafeTile(const Train *v, TileIndex t1, Trackdir td, bool override_railtype, bool dont_reserve)
337 {
338 /* Set origin and destination. */
339 Yapf().SetOrigin(t1, td);
340 Yapf().SetDestination(v, override_railtype);
341
342 bool bFound = Yapf().FindPath(v);
343 if (!bFound) return false;
344
345 /* Found a destination, set as reservation target. */
346 Node *pNode = Yapf().GetBestNode();
347 this->SetReservationTarget(pNode, pNode->GetLastTile(), pNode->GetLastTrackdir());
348
349 /* Walk through the path back to the origin. */
350 Node *pPrev = nullptr;
351 while (pNode->m_parent != nullptr) {
352 pPrev = pNode;
353 pNode = pNode->m_parent;
354
355 this->FindSafePositionOnNode(pPrev);
356 }
357
358 return dont_reserve || this->TryReservePath(nullptr, pNode->GetLastTile());
359 }
360 };
361
362 template <class Types>
363 class CYapfFollowRailT : public CYapfReserveTrack<Types>
364 {
365 public:
366 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class)
367 typedef typename Types::TrackFollower TrackFollower;
368 typedef typename Types::NodeList::Titem Node; ///< this will be our node type
369 typedef typename Node::Key Key; ///< key to hash tables
370
371 protected:
372 /** to access inherited path finder */
Yapf()373 inline Tpf& Yapf()
374 {
375 return *static_cast<Tpf *>(this);
376 }
377
378 public:
379 /**
380 * Called by YAPF to move from the given node to the next tile. For each
381 * reachable trackdir on the new tile creates new node, initializes it
382 * and adds it to the open list by calling Yapf().AddNewNode(n)
383 */
PfFollowNode(Node & old_node)384 inline void PfFollowNode(Node &old_node)
385 {
386 TrackFollower F(Yapf().GetVehicle());
387 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) {
388 Yapf().AddMultipleNodes(&old_node, F);
389 }
390 }
391
392 /** return debug report character to identify the transportation type */
TransportTypeChar() const393 inline char TransportTypeChar() const
394 {
395 return 't';
396 }
397
stChooseRailTrack(const Train * v,TileIndex tile,DiagDirection enterdir,TrackBits tracks,bool & path_found,bool reserve_track,PBSTileInfo * target)398 static Trackdir stChooseRailTrack(const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, bool reserve_track, PBSTileInfo *target)
399 {
400 /* create pathfinder instance */
401 Tpf pf1;
402 Trackdir result1;
403
404 if (_debug_desync_level < 2) {
405 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
406 } else {
407 result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_found, false, nullptr);
408 Tpf pf2;
409 pf2.DisableCache(true);
410 Trackdir result2 = pf2.ChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
411 if (result1 != result2) {
412 Debug(desync, 2, "CACHE ERROR: ChooseRailTrack() = [{}, {}]", result1, result2);
413 DumpState(pf1, pf2);
414 }
415 }
416
417 return result1;
418 }
419
ChooseRailTrack(const Train * v,TileIndex tile,DiagDirection enterdir,TrackBits tracks,bool & path_found,bool reserve_track,PBSTileInfo * target)420 inline Trackdir ChooseRailTrack(const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, bool reserve_track, PBSTileInfo *target)
421 {
422 if (target != nullptr) target->tile = INVALID_TILE;
423
424 /* set origin and destination nodes */
425 PBSTileInfo origin = FollowTrainReservation(v);
426 Yapf().SetOrigin(origin.tile, origin.trackdir, INVALID_TILE, INVALID_TRACKDIR, 1, true);
427 Yapf().SetDestination(v);
428
429 /* find the best path */
430 path_found = Yapf().FindPath(v);
431
432 /* if path not found - return INVALID_TRACKDIR */
433 Trackdir next_trackdir = INVALID_TRACKDIR;
434 Node *pNode = Yapf().GetBestNode();
435 if (pNode != nullptr) {
436 /* reserve till end of path */
437 this->SetReservationTarget(pNode, pNode->GetLastTile(), pNode->GetLastTrackdir());
438
439 /* path was found or at least suggested
440 * walk through the path back to the origin */
441 Node *pPrev = nullptr;
442 while (pNode->m_parent != nullptr) {
443 pPrev = pNode;
444 pNode = pNode->m_parent;
445
446 this->FindSafePositionOnNode(pPrev);
447 }
448 /* return trackdir from the best origin node (one of start nodes) */
449 Node &best_next_node = *pPrev;
450 next_trackdir = best_next_node.GetTrackdir();
451
452 if (reserve_track && path_found) this->TryReservePath(target, pNode->GetLastTile());
453 }
454
455 /* Treat the path as found if stopped on the first two way signal(s). */
456 path_found |= Yapf().m_stopped_on_first_two_way_signal;
457 return next_trackdir;
458 }
459
stCheckReverseTrain(const Train * v,TileIndex t1,Trackdir td1,TileIndex t2,Trackdir td2,int reverse_penalty)460 static bool stCheckReverseTrain(const Train *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int reverse_penalty)
461 {
462 Tpf pf1;
463 bool result1 = pf1.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
464
465 if (_debug_desync_level >= 2) {
466 Tpf pf2;
467 pf2.DisableCache(true);
468 bool result2 = pf2.CheckReverseTrain(v, t1, td1, t2, td2, reverse_penalty);
469 if (result1 != result2) {
470 Debug(desync, 2, "CACHE ERROR: CheckReverseTrain() = [{}, {}]", result1 ? "T" : "F", result2 ? "T" : "F");
471 DumpState(pf1, pf2);
472 }
473 }
474
475 return result1;
476 }
477
CheckReverseTrain(const Train * v,TileIndex t1,Trackdir td1,TileIndex t2,Trackdir td2,int reverse_penalty)478 inline bool CheckReverseTrain(const Train *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int reverse_penalty)
479 {
480 /* create pathfinder instance
481 * set origin and destination nodes */
482 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, false);
483 Yapf().SetDestination(v);
484
485 /* find the best path */
486 bool bFound = Yapf().FindPath(v);
487
488 if (!bFound) return false;
489
490 /* path was found
491 * walk through the path back to the origin */
492 Node *pNode = Yapf().GetBestNode();
493 while (pNode->m_parent != nullptr) {
494 pNode = pNode->m_parent;
495 }
496
497 /* check if it was reversed origin */
498 Node &best_org_node = *pNode;
499 bool reversed = (best_org_node.m_cost != 0);
500 return reversed;
501 }
502 };
503
504 template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class TdestinationT, template <class Types> class TfollowT>
505 struct CYapfRail_TypesT
506 {
507 typedef CYapfRail_TypesT<Tpf_, Ttrack_follower, Tnode_list, TdestinationT, TfollowT> Types;
508
509 typedef Tpf_ Tpf;
510 typedef Ttrack_follower TrackFollower;
511 typedef Tnode_list NodeList;
512 typedef Train VehicleType;
513 typedef CYapfBaseT<Types> PfBase;
514 typedef TfollowT<Types> PfFollow;
515 typedef CYapfOriginTileTwoWayT<Types> PfOrigin;
516 typedef TdestinationT<Types> PfDestination;
517 typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;
518 typedef CYapfCostRailT<Types> PfCost;
519 };
520
521 struct CYapfRail1 : CYapfT<CYapfRail_TypesT<CYapfRail1 , CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
522 struct CYapfRail2 : CYapfT<CYapfRail_TypesT<CYapfRail2 , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};
523
524 struct CYapfAnyDepotRail1 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
525 struct CYapfAnyDepotRail2 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {};
526
527 struct CYapfAnySafeTileRail1 : CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail1, CFollowTrackFreeRail , CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
528 struct CYapfAnySafeTileRail2 : CYapfT<CYapfRail_TypesT<CYapfAnySafeTileRail2, CFollowTrackFreeRailNo90, CRailNodeListTrackDir, CYapfDestinationAnySafeTileRailT , CYapfFollowAnySafeTileRailT> > {};
529
530
YapfTrainChooseTrack(const Train * v,TileIndex tile,DiagDirection enterdir,TrackBits tracks,bool & path_found,bool reserve_track,PBSTileInfo * target)531 Track YapfTrainChooseTrack(const Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, bool reserve_track, PBSTileInfo *target)
532 {
533 /* default is YAPF type 2 */
534 typedef Trackdir (*PfnChooseRailTrack)(const Train*, TileIndex, DiagDirection, TrackBits, bool&, bool, PBSTileInfo*);
535 PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack;
536
537 /* check if non-default YAPF type needed */
538 if (_settings_game.pf.forbid_90_deg) {
539 pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack; // Trackdir, forbid 90-deg
540 }
541
542 Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, tracks, path_found, reserve_track, target);
543 return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : FindFirstTrack(tracks);
544 }
545
YapfTrainCheckReverse(const Train * v)546 bool YapfTrainCheckReverse(const Train *v)
547 {
548 const Train *last_veh = v->Last();
549
550 /* get trackdirs of both ends */
551 Trackdir td = v->GetVehicleTrackdir();
552 Trackdir td_rev = ReverseTrackdir(last_veh->GetVehicleTrackdir());
553
554 /* tiles where front and back are */
555 TileIndex tile = v->tile;
556 TileIndex tile_rev = last_veh->tile;
557
558 int reverse_penalty = 0;
559
560 if (v->track == TRACK_BIT_WORMHOLE) {
561 /* front in tunnel / on bridge */
562 DiagDirection dir_into_wormhole = GetTunnelBridgeDirection(tile);
563
564 if (TrackdirToExitdir(td) == dir_into_wormhole) tile = GetOtherTunnelBridgeEnd(tile);
565 /* Now 'tile' is the tunnel entry/bridge ramp the train will reach when driving forward */
566
567 /* Current position of the train in the wormhole */
568 TileIndex cur_tile = TileVirtXY(v->x_pos, v->y_pos);
569
570 /* Add distance to drive in the wormhole as penalty for the forward path, i.e. bonus for the reverse path
571 * Note: Negative penalties are ok for the start tile. */
572 reverse_penalty -= DistanceManhattan(cur_tile, tile) * YAPF_TILE_LENGTH;
573 }
574
575 if (last_veh->track == TRACK_BIT_WORMHOLE) {
576 /* back in tunnel / on bridge */
577 DiagDirection dir_into_wormhole = GetTunnelBridgeDirection(tile_rev);
578
579 if (TrackdirToExitdir(td_rev) == dir_into_wormhole) tile_rev = GetOtherTunnelBridgeEnd(tile_rev);
580 /* Now 'tile_rev' is the tunnel entry/bridge ramp the train will reach when reversing */
581
582 /* Current position of the last wagon in the wormhole */
583 TileIndex cur_tile = TileVirtXY(last_veh->x_pos, last_veh->y_pos);
584
585 /* Add distance to drive in the wormhole as penalty for the revere path. */
586 reverse_penalty += DistanceManhattan(cur_tile, tile_rev) * YAPF_TILE_LENGTH;
587 }
588
589 typedef bool (*PfnCheckReverseTrain)(const Train*, TileIndex, Trackdir, TileIndex, Trackdir, int);
590 PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail1::stCheckReverseTrain;
591
592 /* check if non-default YAPF type needed */
593 if (_settings_game.pf.forbid_90_deg) {
594 pfnCheckReverseTrain = &CYapfRail2::stCheckReverseTrain; // Trackdir, forbid 90-deg
595 }
596
597 /* slightly hackish: If the pathfinders finds a path, the cost of the first node is tested to distinguish between forward- and reverse-path. */
598 if (reverse_penalty == 0) reverse_penalty = 1;
599
600 bool reverse = pfnCheckReverseTrain(v, tile, td, tile_rev, td_rev, reverse_penalty);
601
602 return reverse;
603 }
604
YapfTrainFindNearestDepot(const Train * v,int max_penalty)605 FindDepotData YapfTrainFindNearestDepot(const Train *v, int max_penalty)
606 {
607 const Train *last_veh = v->Last();
608
609 PBSTileInfo origin = FollowTrainReservation(v);
610 TileIndex last_tile = last_veh->tile;
611 Trackdir td_rev = ReverseTrackdir(last_veh->GetVehicleTrackdir());
612
613 typedef FindDepotData (*PfnFindNearestDepotTwoWay)(const Train*, TileIndex, Trackdir, TileIndex, Trackdir, int, int);
614 PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay;
615
616 /* check if non-default YAPF type needed */
617 if (_settings_game.pf.forbid_90_deg) {
618 pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay; // Trackdir, forbid 90-deg
619 }
620
621 return pfnFindNearestDepotTwoWay(v, origin.tile, origin.trackdir, last_tile, td_rev, max_penalty, YAPF_INFINITE_PENALTY);
622 }
623
YapfTrainFindNearestSafeTile(const Train * v,TileIndex tile,Trackdir td,bool override_railtype)624 bool YapfTrainFindNearestSafeTile(const Train *v, TileIndex tile, Trackdir td, bool override_railtype)
625 {
626 typedef bool (*PfnFindNearestSafeTile)(const Train*, TileIndex, Trackdir, bool);
627 PfnFindNearestSafeTile pfnFindNearestSafeTile = CYapfAnySafeTileRail1::stFindNearestSafeTile;
628
629 /* check if non-default YAPF type needed */
630 if (_settings_game.pf.forbid_90_deg) {
631 pfnFindNearestSafeTile = &CYapfAnySafeTileRail2::stFindNearestSafeTile;
632 }
633
634 return pfnFindNearestSafeTile(v, tile, td, override_railtype);
635 }
636
637 /** if any track changes, this counter is incremented - that will invalidate segment cost cache */
638 int CSegmentCostCacheBase::s_rail_change_counter = 0;
639
YapfNotifyTrackLayoutChange(TileIndex tile,Track track)640 void YapfNotifyTrackLayoutChange(TileIndex tile, Track track)
641 {
642 CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);
643 }
644