|
1 /* $Id$ */ |
|
2 |
|
3 #ifndef YAPF_COSTRAIL_HPP |
|
4 #define YAPF_COSTRAIL_HPP |
|
5 |
|
6 |
|
7 template <class Types> |
|
8 class CYapfCostRailT |
|
9 : public CYapfCostBase |
|
10 , public CostRailSettings |
|
11 { |
|
12 public: |
|
13 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) |
|
14 typedef typename Types::TrackFollower TrackFollower; |
|
15 typedef typename Types::NodeList::Titem Node; ///< this will be our node type |
|
16 typedef typename Node::Key Key; ///< key to hash tables |
|
17 typedef typename Node::CachedData CachedData; |
|
18 |
|
19 protected: |
|
20 int m_max_cost; |
|
21 CBlobT<int> m_sig_look_ahead_costs; |
|
22 public: |
|
23 bool m_stopped_on_first_two_way_signal; |
|
24 protected: |
|
25 |
|
26 static const int s_max_segment_cost = 10000; |
|
27 |
|
28 CYapfCostRailT() |
|
29 : m_max_cost(0) |
|
30 , m_stopped_on_first_two_way_signal(false) |
|
31 { |
|
32 // pre-compute look-ahead penalties into array |
|
33 int p0 = Yapf().PfGetSettings().rail_look_ahead_signal_p0; |
|
34 int p1 = Yapf().PfGetSettings().rail_look_ahead_signal_p1; |
|
35 int p2 = Yapf().PfGetSettings().rail_look_ahead_signal_p2; |
|
36 int *pen = m_sig_look_ahead_costs.GrowSizeNC(Yapf().PfGetSettings().rail_look_ahead_max_signals); |
|
37 for (uint i = 0; i < Yapf().PfGetSettings().rail_look_ahead_max_signals; i++) |
|
38 pen[i] = p0 + i * (p1 + i * p2); |
|
39 } |
|
40 |
|
41 /// to access inherited path finder |
|
42 Tpf& Yapf() {return *static_cast<Tpf*>(this);} |
|
43 |
|
44 public: |
|
45 FORCEINLINE int SlopeCost(TileIndex tile, Trackdir td) |
|
46 { |
|
47 CPerfStart perf_cost(Yapf().m_perf_slope_cost); |
|
48 if (!stSlopeCost(tile, td)) return 0; |
|
49 return Yapf().PfGetSettings().rail_slope_penalty; |
|
50 } |
|
51 |
|
52 FORCEINLINE int CurveCost(Trackdir td1, Trackdir td2) |
|
53 { |
|
54 int cost = 0; |
|
55 if (TrackFollower::Allow90degTurns() |
|
56 && ((TrackdirToTrackdirBits(td2) & (TrackdirBits)TrackdirCrossesTrackdirs(td1)) != 0)) { |
|
57 // 90-deg curve penalty |
|
58 cost += Yapf().PfGetSettings().rail_curve90_penalty; |
|
59 } else if (td2 != NextTrackdir(td1)) { |
|
60 // 45-deg curve penalty |
|
61 cost += Yapf().PfGetSettings().rail_curve45_penalty; |
|
62 } |
|
63 return cost; |
|
64 } |
|
65 |
|
66 /** return one tile cost. If tile is a tunnel entry, it is moved to the end of tunnel */ |
|
67 FORCEINLINE int OneTileCost(TileIndex& tile, Trackdir trackdir) |
|
68 { |
|
69 int cost = 0; |
|
70 // set base cost |
|
71 if (IsDiagonalTrackdir(trackdir)) { |
|
72 cost += YAPF_TILE_LENGTH; |
|
73 switch (GetTileType(tile)) { |
|
74 case MP_STREET: |
|
75 /* Increase the cost for level crossings */ |
|
76 if (IsLevelCrossing(tile)) |
|
77 cost += Yapf().PfGetSettings().rail_crossing_penalty; |
|
78 break; |
|
79 |
|
80 case MP_STATION: |
|
81 // penalty for passing station tiles |
|
82 cost += Yapf().PfGetSettings().rail_station_penalty; |
|
83 break; |
|
84 |
|
85 default: |
|
86 break; |
|
87 } |
|
88 } else { |
|
89 // non-diagonal trackdir |
|
90 cost = YAPF_TILE_CORNER_LENGTH; |
|
91 } |
|
92 return cost; |
|
93 } |
|
94 |
|
95 int SignalCost(Node& n, TileIndex tile, Trackdir trackdir) |
|
96 { |
|
97 int cost = 0; |
|
98 // if there is one-way signal in the opposite direction, then it is not our way |
|
99 CPerfStart perf_cost(Yapf().m_perf_other_cost); |
|
100 if (IsTileType(tile, MP_RAILWAY)) { |
|
101 bool has_signal_against = HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir)); |
|
102 bool has_signal_along = HasSignalOnTrackdir(tile, trackdir); |
|
103 if (has_signal_against && !has_signal_along) { |
|
104 // one-way signal in opposite direction |
|
105 n.m_segment->flags_u.flags_s.m_end_of_line = true; |
|
106 } else if (has_signal_along) { |
|
107 SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir); |
|
108 // cache the look-ahead polynomial constant only if we didn't pass more signals than the look-ahead limit is |
|
109 int look_ahead_cost = (n.m_num_signals_passed < m_sig_look_ahead_costs.Size()) ? m_sig_look_ahead_costs.Data()[n.m_num_signals_passed] : 0; |
|
110 if (sig_state != SIGNAL_STATE_RED) { |
|
111 // green signal |
|
112 n.flags_u.flags_s.m_last_signal_was_red = false; |
|
113 // negative look-ahead red-signal penalties would cause problems later, so use them as positive penalties for green signal |
|
114 if (look_ahead_cost < 0) { |
|
115 // add its negation to the cost |
|
116 cost -= look_ahead_cost; |
|
117 } |
|
118 } else { |
|
119 // we have a red signal in our direction |
|
120 // was it first signal which is two-way? |
|
121 if (Yapf().TreatFirstRedTwoWaySignalAsEOL() && n.flags_u.flags_s.m_choice_seen && has_signal_against && n.m_num_signals_passed == 0) { |
|
122 // yes, the first signal is two-way red signal => DEAD END |
|
123 n.m_segment->flags_u.flags_s.m_end_of_line = true; |
|
124 Yapf().m_stopped_on_first_two_way_signal = true; |
|
125 return -1; |
|
126 } |
|
127 SignalType sig_type = GetSignalType(tile); |
|
128 n.m_last_red_signal_type = sig_type; |
|
129 n.flags_u.flags_s.m_last_signal_was_red = true; |
|
130 |
|
131 // look-ahead signal penalty |
|
132 if (look_ahead_cost > 0) { |
|
133 // add the look ahead penalty only if it is positive |
|
134 cost += look_ahead_cost; |
|
135 } |
|
136 |
|
137 // special signal penalties |
|
138 if (n.m_num_signals_passed == 0) { |
|
139 switch (sig_type) { |
|
140 case SIGTYPE_COMBO: |
|
141 case SIGTYPE_EXIT: cost += Yapf().PfGetSettings().rail_firstred_exit_penalty; break; // first signal is red pre-signal-exit |
|
142 case SIGTYPE_NORMAL: |
|
143 case SIGTYPE_ENTRY: cost += Yapf().PfGetSettings().rail_firstred_penalty; break; |
|
144 }; |
|
145 } |
|
146 } |
|
147 n.m_num_signals_passed++; |
|
148 n.m_segment->m_last_signal_tile = tile; |
|
149 n.m_segment->m_last_signal_td = trackdir; |
|
150 } |
|
151 } |
|
152 return cost; |
|
153 } |
|
154 |
|
155 FORCEINLINE int PlatformLengthPenalty(int platform_length) |
|
156 { |
|
157 int cost = 0; |
|
158 const Vehicle* v = Yapf().GetVehicle(); |
|
159 assert(v != NULL); |
|
160 assert(v->type == VEH_Train); |
|
161 assert(v->u.rail.cached_total_length != 0); |
|
162 int needed_platform_length = (v->u.rail.cached_total_length + TILE_SIZE - 1) / TILE_SIZE; |
|
163 if (platform_length > needed_platform_length) { |
|
164 // apply penalty for longer platform than needed |
|
165 cost += Yapf().PfGetSettings().rail_longer_platform_penalty; |
|
166 } else if (needed_platform_length > platform_length) { |
|
167 // apply penalty for shorter platform than needed |
|
168 cost += Yapf().PfGetSettings().rail_shorter_platform_penalty; |
|
169 } |
|
170 return cost; |
|
171 } |
|
172 |
|
173 public: |
|
174 FORCEINLINE void SetMaxCost(int max_cost) {m_max_cost = max_cost;} |
|
175 |
|
176 /** Called by YAPF to calculate the cost from the origin to the given node. |
|
177 * Calculates only the cost of given node, adds it to the parent node cost |
|
178 * and stores the result into Node::m_cost member */ |
|
179 FORCEINLINE bool PfCalcCost(Node& n) |
|
180 { |
|
181 assert(!n.flags_u.flags_s.m_targed_seen); |
|
182 CPerfStart perf_cost(Yapf().m_perf_cost); |
|
183 int parent_cost = (n.m_parent != NULL) ? n.m_parent->m_cost : 0; |
|
184 int first_tile_cost = 0; |
|
185 int segment_cost = 0; |
|
186 int extra_cost = 0; |
|
187 const Vehicle* v = Yapf().GetVehicle(); |
|
188 |
|
189 // start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment |
|
190 TileIndex prev_tile = (n.m_parent != NULL) ? n.m_parent->GetLastTile() : INVALID_TILE; |
|
191 Trackdir prev_trackdir = (n.m_parent != NULL) ? n.m_parent->GetLastTrackdir() : INVALID_TRACKDIR; |
|
192 TileType prev_tile_type = (n.m_parent != NULL) ? GetTileType(n.m_parent->GetLastTile()) : MP_VOID; |
|
193 |
|
194 TileIndex tile = n.m_key.m_tile; |
|
195 Trackdir trackdir = n.m_key.m_td; |
|
196 TileType tile_type = GetTileType(tile); |
|
197 |
|
198 RailType rail_type = GetTileRailType(tile, trackdir); |
|
199 |
|
200 bool target_seen = Yapf().PfDetectDestination(tile, trackdir); |
|
201 |
|
202 while (true) { |
|
203 segment_cost += Yapf().OneTileCost(tile, trackdir); |
|
204 segment_cost += Yapf().CurveCost(prev_trackdir, trackdir); |
|
205 segment_cost += Yapf().SlopeCost(tile, trackdir); |
|
206 segment_cost += Yapf().SignalCost(n, tile, trackdir); |
|
207 if (n.m_segment->flags_u.flags_s.m_end_of_line) { |
|
208 break; |
|
209 } |
|
210 |
|
211 // finish if we have reached the destination |
|
212 if (target_seen) { |
|
213 break; |
|
214 } |
|
215 |
|
216 // finish on first station tile - segment should end here to avoid target skipping |
|
217 // when cached segments are used |
|
218 if (tile_type == MP_STATION && prev_tile_type != MP_STATION) { |
|
219 break; |
|
220 } |
|
221 |
|
222 // finish also on waypoint - same workaround as for first station tile |
|
223 if (tile_type == MP_RAILWAY && IsRailWaypoint(tile)) { |
|
224 break; |
|
225 } |
|
226 |
|
227 // if there are no reachable trackdirs on the next tile, we have end of road |
|
228 TrackFollower F(v, &Yapf().m_perf_ts_cost); |
|
229 if (!F.Follow(tile, trackdir)) { |
|
230 // we can't continue? |
|
231 // n.m_segment->flags_u.flags_s.m_end_of_line = true; |
|
232 break; |
|
233 } |
|
234 |
|
235 // if there are more trackdirs available & reachable, we are at the end of segment |
|
236 if (KillFirstBit2x64(F.m_new_td_bits) != 0) { |
|
237 break; |
|
238 } |
|
239 |
|
240 Trackdir new_td = (Trackdir)FindFirstBit2x64(F.m_new_td_bits); |
|
241 |
|
242 { |
|
243 // end segment if train is about to enter simple loop with no junctions |
|
244 // so next time it should stop on the next if |
|
245 if (segment_cost > s_max_segment_cost && IsTileType(F.m_new_tile, MP_RAILWAY)) |
|
246 break; |
|
247 |
|
248 // stop if train is on simple loop with no junctions |
|
249 if (F.m_new_tile == n.m_key.m_tile && new_td == n.m_key.m_td) |
|
250 return false; |
|
251 } |
|
252 |
|
253 // if tail type changes, finish segment (cached segment can't contain more rail types) |
|
254 { |
|
255 RailType new_rail_type = GetTileRailType(F.m_new_tile, (Trackdir)FindFirstBit2x64(F.m_new_td_bits)); |
|
256 if (new_rail_type != rail_type) { |
|
257 break; |
|
258 } |
|
259 rail_type = new_rail_type; |
|
260 } |
|
261 |
|
262 // move to the next tile |
|
263 prev_tile = tile; |
|
264 prev_trackdir = trackdir; |
|
265 prev_tile_type = tile_type; |
|
266 |
|
267 tile = F.m_new_tile; |
|
268 trackdir = new_td; |
|
269 tile_type = GetTileType(tile); |
|
270 |
|
271 target_seen = Yapf().PfDetectDestination(tile, trackdir); |
|
272 |
|
273 // reversing in depot penalty |
|
274 if (tile == prev_tile) { |
|
275 segment_cost += Yapf().PfGetSettings().rail_depot_reverse_penalty; |
|
276 break; |
|
277 } |
|
278 |
|
279 // if we skipped some tunnel tiles, add their cost |
|
280 segment_cost += YAPF_TILE_LENGTH * F.m_tiles_skipped; |
|
281 |
|
282 // add penalty for skipped station tiles |
|
283 if (F.m_is_station) |
|
284 { |
|
285 if (target_seen) { |
|
286 // it is our destination station |
|
287 uint platform_length = F.m_tiles_skipped + 1; |
|
288 segment_cost += PlatformLengthPenalty(platform_length); |
|
289 } else { |
|
290 // station is not our destination station, apply penalty for skipped platform tiles |
|
291 segment_cost += Yapf().PfGetSettings().rail_station_penalty * F.m_tiles_skipped; |
|
292 } |
|
293 } |
|
294 |
|
295 // add min/max speed penalties |
|
296 int min_speed = 0; |
|
297 int max_speed = F.GetSpeedLimit(&min_speed); |
|
298 if (max_speed < v->max_speed) |
|
299 segment_cost += YAPF_TILE_LENGTH * (v->max_speed - max_speed) / v->max_speed; |
|
300 if (min_speed > v->max_speed) |
|
301 segment_cost += YAPF_TILE_LENGTH * (min_speed - v->max_speed); |
|
302 |
|
303 // finish if we already exceeded the maximum cost |
|
304 if (m_max_cost > 0 && (parent_cost + first_tile_cost + segment_cost) > m_max_cost) { |
|
305 return false; |
|
306 } |
|
307 |
|
308 if (first_tile_cost == 0) { |
|
309 // we just have done first tile |
|
310 first_tile_cost = segment_cost; |
|
311 segment_cost = 0; |
|
312 |
|
313 // look if we can reuse existing (cached) segment cost |
|
314 if (n.m_segment->m_cost >= 0) { |
|
315 // reuse the cached segment cost |
|
316 break; |
|
317 } |
|
318 } |
|
319 // segment cost was not filled yes, we have not cached it yet |
|
320 n.SetLastTileTrackdir(tile, trackdir); |
|
321 |
|
322 } // while (true) |
|
323 |
|
324 if (first_tile_cost == 0) { |
|
325 // we have just finished first tile |
|
326 first_tile_cost = segment_cost; |
|
327 segment_cost = 0; |
|
328 } |
|
329 |
|
330 // do we have cached segment cost? |
|
331 if (n.m_segment->m_cost >= 0) { |
|
332 // reuse the cached segment cost |
|
333 segment_cost = n.m_segment->m_cost; |
|
334 } else { |
|
335 // save segment cost |
|
336 n.m_segment->m_cost = segment_cost; |
|
337 |
|
338 // save end of segment back to the node |
|
339 n.SetLastTileTrackdir(tile, trackdir); |
|
340 } |
|
341 |
|
342 // special costs for the case we have reached our target |
|
343 if (target_seen) { |
|
344 n.flags_u.flags_s.m_targed_seen = true; |
|
345 if (n.flags_u.flags_s.m_last_signal_was_red) { |
|
346 if (n.m_last_red_signal_type == SIGTYPE_EXIT) { |
|
347 // last signal was red pre-signal-exit |
|
348 extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty; |
|
349 } else { |
|
350 // last signal was red, but not exit |
|
351 extra_cost += Yapf().PfGetSettings().rail_lastred_penalty; |
|
352 } |
|
353 } |
|
354 } |
|
355 |
|
356 // total node cost |
|
357 n.m_cost = parent_cost + first_tile_cost + segment_cost + extra_cost; |
|
358 |
|
359 return !n.m_segment->flags_u.flags_s.m_end_of_line; |
|
360 } |
|
361 |
|
362 FORCEINLINE bool CanUseGlobalCache(Node& n) const |
|
363 { |
|
364 return (n.m_parent != NULL) |
|
365 && (n.m_parent->m_num_signals_passed >= m_sig_look_ahead_costs.Size()); |
|
366 } |
|
367 |
|
368 FORCEINLINE void ConnectNodeToCachedData(Node& n, CachedData& ci) |
|
369 { |
|
370 n.m_segment = &ci; |
|
371 if (n.m_segment->m_cost < 0) { |
|
372 n.m_segment->m_last_tile = n.m_key.m_tile; |
|
373 n.m_segment->m_last_td = n.m_key.m_td; |
|
374 } |
|
375 } |
|
376 |
|
377 }; |
|
378 |
|
379 |
|
380 |
|
381 #endif /* YAPF_COSTRAIL_HPP */ |