|
1 /* $Id$ */ |
|
2 |
|
3 #include "../stdafx.h" |
|
4 |
|
5 #include "yapf.hpp" |
|
6 #include "yapf_node_rail.hpp" |
|
7 #include "yapf_costrail.hpp" |
|
8 #include "yapf_destrail.hpp" |
|
9 |
|
10 int _total_pf_time_us = 0; |
|
11 |
|
12 |
|
13 |
|
14 |
|
15 |
|
16 template <class Types> |
|
17 class CYapfFollowAnyDepotRailT |
|
18 { |
|
19 public: |
|
20 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) |
|
21 typedef typename Types::TrackFollower TrackFollower; |
|
22 typedef typename Types::NodeList::Titem Node; ///< this will be our node type |
|
23 typedef typename Node::Key Key; ///< key to hash tables |
|
24 |
|
25 protected: |
|
26 /// to access inherited path finder |
|
27 FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} |
|
28 |
|
29 public: |
|
30 /** Called by YAPF to move from the given node to the next tile. For each |
|
31 * reachable trackdir on the new tile creates new node, initializes it |
|
32 * and adds it to the open list by calling Yapf().AddNewNode(n) */ |
|
33 inline void PfFollowNode(Node& old_node) |
|
34 { |
|
35 TrackFollower F(Yapf().GetVehicle()); |
|
36 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) |
|
37 Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits); |
|
38 } |
|
39 |
|
40 /// return debug report character to identify the transportation type |
|
41 FORCEINLINE char TransportTypeChar() const {return 't';} |
|
42 |
|
43 static bool stFindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed) |
|
44 { |
|
45 Tpf pf; |
|
46 return pf.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, depot_tile, reversed); |
|
47 } |
|
48 |
|
49 FORCEINLINE bool FindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed) |
|
50 { |
|
51 // set origin and destination nodes |
|
52 Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, true); |
|
53 Yapf().SetDestination(v); |
|
54 Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance); |
|
55 |
|
56 // find the best path |
|
57 bool bFound = Yapf().FindPath(v); |
|
58 if (!bFound) return false; |
|
59 |
|
60 // some path found |
|
61 // get found depot tile |
|
62 Node& n = Yapf().GetBestNode(); |
|
63 *depot_tile = n.GetLastTile(); |
|
64 |
|
65 // walk through the path back to the origin |
|
66 Node* pNode = &n; |
|
67 while (pNode->m_parent != NULL) { |
|
68 pNode = pNode->m_parent; |
|
69 } |
|
70 |
|
71 // if the origin node is our front vehicle tile/Trackdir then we didn't reverse |
|
72 // but we can also look at the cost (== 0 -> not reversed, == reverse_penalty -> reversed) |
|
73 *reversed = (pNode->m_cost != 0); |
|
74 |
|
75 return true; |
|
76 } |
|
77 }; |
|
78 |
|
79 template <class Types> |
|
80 class CYapfFollowRailT |
|
81 { |
|
82 public: |
|
83 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) |
|
84 typedef typename Types::TrackFollower TrackFollower; |
|
85 typedef typename Types::NodeList::Titem Node; ///< this will be our node type |
|
86 typedef typename Node::Key Key; ///< key to hash tables |
|
87 |
|
88 protected: |
|
89 /// to access inherited path finder |
|
90 FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} |
|
91 |
|
92 public: |
|
93 /** Called by YAPF to move from the given node to the next tile. For each |
|
94 * reachable trackdir on the new tile creates new node, initializes it |
|
95 * and adds it to the open list by calling Yapf().AddNewNode(n) */ |
|
96 inline void PfFollowNode(Node& old_node) |
|
97 { |
|
98 TrackFollower F(Yapf().GetVehicle()); |
|
99 if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir())) |
|
100 Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits); |
|
101 } |
|
102 |
|
103 /// return debug report character to identify the transportation type |
|
104 FORCEINLINE char TransportTypeChar() const {return 't';} |
|
105 |
|
106 static Trackdir stChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found) |
|
107 { |
|
108 // create pathfinder instance |
|
109 Tpf pf; |
|
110 return pf.ChooseRailTrack(v, tile, enterdir, trackdirs, path_not_found); |
|
111 } |
|
112 |
|
113 FORCEINLINE Trackdir ChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found) |
|
114 { |
|
115 // set origin and destination nodes |
|
116 Yapf().SetOrigin(v->tile, GetVehicleTrackdir(v), INVALID_TILE, INVALID_TRACKDIR, 1, true); |
|
117 Yapf().SetDestination(v); |
|
118 |
|
119 // find the best path |
|
120 bool path_found = Yapf().FindPath(v); |
|
121 if (path_not_found != NULL) { |
|
122 // tell controller that the path was only 'guessed' |
|
123 // treat the path as found if stopped on the first two way signal(s) |
|
124 *path_not_found = !(path_found || Yapf().m_stopped_on_first_two_way_signal); |
|
125 } |
|
126 |
|
127 // if path not found - return INVALID_TRACKDIR |
|
128 Trackdir next_trackdir = INVALID_TRACKDIR; |
|
129 Node* pNode = &Yapf().GetBestNode(); |
|
130 if (pNode != NULL) { |
|
131 // path was found or at least suggested |
|
132 // walk through the path back to the origin |
|
133 Node* pPrev = NULL; |
|
134 while (pNode->m_parent != NULL) { |
|
135 pPrev = pNode; |
|
136 pNode = pNode->m_parent; |
|
137 } |
|
138 // return trackdir from the best origin node (one of start nodes) |
|
139 Node& best_next_node = *pPrev; |
|
140 assert(best_next_node.GetTile() == tile); |
|
141 next_trackdir = best_next_node.GetTrackdir(); |
|
142 } |
|
143 return next_trackdir; |
|
144 } |
|
145 |
|
146 static bool stCheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2) |
|
147 { |
|
148 Tpf pf; |
|
149 return pf.CheckReverseTrain(v, t1, td1, t2, td2); |
|
150 } |
|
151 |
|
152 FORCEINLINE bool CheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2) |
|
153 { |
|
154 // create pathfinder instance |
|
155 // set origin and destination nodes |
|
156 Yapf().SetOrigin(t1, td1, t2, td2, 1, false); |
|
157 Yapf().SetDestination(v); |
|
158 |
|
159 // find the best path |
|
160 bool bFound = Yapf().FindPath(v); |
|
161 |
|
162 if (!bFound) return false; |
|
163 |
|
164 // path was found |
|
165 // walk through the path back to the origin |
|
166 Node* pNode = &Yapf().GetBestNode(); |
|
167 while (pNode->m_parent != NULL) { |
|
168 pNode = pNode->m_parent; |
|
169 } |
|
170 |
|
171 // check if it was reversed origin |
|
172 Node& best_org_node = *pNode; |
|
173 bool reversed = (best_org_node.m_cost != 0); |
|
174 return reversed; |
|
175 } |
|
176 }; |
|
177 |
|
178 template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class TdestinationT, template <class Types> class TfollowT> |
|
179 struct CYapfRail_TypesT |
|
180 { |
|
181 typedef CYapfRail_TypesT<Tpf_, Ttrack_follower, Tnode_list, TdestinationT, TfollowT> Types; |
|
182 |
|
183 typedef Tpf_ Tpf; |
|
184 typedef Ttrack_follower TrackFollower; |
|
185 typedef Tnode_list NodeList; |
|
186 typedef CYapfBaseT<Types> PfBase; |
|
187 typedef TfollowT<Types> PfFollow; |
|
188 typedef CYapfOriginTileTwoWayT<Types> PfOrigin; |
|
189 typedef TdestinationT<Types> PfDestination; |
|
190 typedef CYapfSegmentCostCacheGlobalT<Types> PfCache; |
|
191 typedef CYapfCostRailT<Types> PfCost; |
|
192 }; |
|
193 |
|
194 struct CYapfRail1 : CYapfT<CYapfRail_TypesT<CYapfRail1 , CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {}; |
|
195 struct CYapfRail2 : CYapfT<CYapfRail_TypesT<CYapfRail2 , CFollowTrackRail , CRailNodeListExitDir , CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {}; |
|
196 struct CYapfRail3 : CYapfT<CYapfRail_TypesT<CYapfRail3 , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {}; |
|
197 |
|
198 struct CYapfAnyDepotRail1 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {}; |
|
199 struct CYapfAnyDepotRail2 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRail , CRailNodeListExitDir , CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {}; |
|
200 struct CYapfAnyDepotRail3 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail3, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT , CYapfFollowAnyDepotRailT> > {}; |
|
201 |
|
202 |
|
203 Trackdir YapfChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs, bool *path_not_found) |
|
204 { |
|
205 // default is YAPF type 2 |
|
206 typedef Trackdir (*PfnChooseRailTrack)(Vehicle*, TileIndex, DiagDirection, TrackdirBits, bool*); |
|
207 PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack; |
|
208 |
|
209 // check if non-default YAPF type needed |
|
210 if (_patches.forbid_90_deg) |
|
211 pfnChooseRailTrack = &CYapfRail3::stChooseRailTrack; // Trackdir, forbid 90-deg |
|
212 else if (_patches.yapf.disable_node_optimization) |
|
213 pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack; // Trackdir, allow 90-deg |
|
214 |
|
215 Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, trackdirs, path_not_found); |
|
216 |
|
217 return td_ret; |
|
218 } |
|
219 |
|
220 bool YapfCheckReverseTrain(Vehicle* v) |
|
221 { |
|
222 // tile where the engine is |
|
223 TileIndex tile = v->tile; |
|
224 // tile where we have last wagon |
|
225 Vehicle* last_veh = GetLastVehicleInChain(v); |
|
226 // if we are in tunnel then give up |
|
227 if (v->u.rail.track == 0x40 || last_veh->u.rail.track == 0x40) return false; |
|
228 // get trackdirs of both ends |
|
229 Trackdir td = GetVehicleTrackdir(v); |
|
230 Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh)); |
|
231 |
|
232 |
|
233 typedef bool (*PfnCheckReverseTrain)(Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir); |
|
234 PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain; |
|
235 |
|
236 // check if non-default YAPF type needed |
|
237 if (_patches.forbid_90_deg) |
|
238 pfnCheckReverseTrain = &CYapfRail3::stCheckReverseTrain; // Trackdir, forbid 90-deg |
|
239 else if (_patches.yapf.disable_node_optimization) |
|
240 pfnCheckReverseTrain = &CYapfRail1::stCheckReverseTrain; // Trackdir, allow 90-deg |
|
241 |
|
242 bool reverse = pfnCheckReverseTrain(v, tile, td, last_veh->tile, td_rev); |
|
243 |
|
244 return reverse; |
|
245 } |
|
246 |
|
247 bool YapfFindNearestRailDepotTwoWay(Vehicle *v, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed) |
|
248 { |
|
249 *depot_tile = INVALID_TILE; |
|
250 *reversed = false; |
|
251 |
|
252 Vehicle* last_veh = GetLastVehicleInChain(v); |
|
253 |
|
254 TileIndex tile = v->tile; |
|
255 TileIndex last_tile = last_veh->tile; |
|
256 |
|
257 // their trackdirs |
|
258 Trackdir td = GetVehicleTrackdir(v); |
|
259 Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh)); |
|
260 |
|
261 typedef bool (*PfnFindNearestDepotTwoWay)(Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir, int, int, TileIndex*, bool*); |
|
262 PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay; |
|
263 |
|
264 // check if non-default YAPF type needed |
|
265 if (_patches.forbid_90_deg) |
|
266 pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail3::stFindNearestDepotTwoWay; // Trackdir, forbid 90-deg |
|
267 else if (_patches.yapf.disable_node_optimization) |
|
268 pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay; // Trackdir, allow 90-deg |
|
269 |
|
270 bool ret = pfnFindNearestDepotTwoWay(v, tile, td, last_tile, td_rev, max_distance, reverse_penalty, depot_tile, reversed); |
|
271 return ret; |
|
272 } |
|
273 |
|
274 /** if any track changes, this counter is incremented - that will invalidate segment cost cache */ |
|
275 int CSegmentCostCacheBase::s_rail_change_counter = 0; |
|
276 |
|
277 void YapfNotifyTrackLayoutChange(TileIndex tile, Track track) {CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);} |