?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
(svn r28004) -Update from Eints:
[openttd.git] / src / pathfinder / yapf / yapf_costrail.hpp
blobca317f09a76f68e398a9aad8ae737094ab077c7c
1 /* $Id$ */
2
3 /*
4 * This file is part of OpenTTD.
5 * 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.
6 * 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.
7 * 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/>.
8 */
9
10 /** @file yapf_costrail.hpp Cost determination for rails. */
11
12 #ifndef YAPF_COSTRAIL_HPP
13 #define YAPF_COSTRAIL_HPP
14
15 #include "../../pbs.h"
16
17 template <class Types>
18 class CYapfCostRailT : public CYapfCostBase {
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 typedef typename Node::CachedData CachedData;
25
26 protected:
27
28 /* Structure used inside PfCalcCost() to keep basic tile information. */
29 struct TILE {
30 TileIndex tile;
31 Trackdir td;
32 TileType tile_type;
33 RailType rail_type;
34
35 TILE()
36 {
37 tile = INVALID_TILE;
38 td = INVALID_TRACKDIR;
39 tile_type = MP_VOID;
40 rail_type = INVALID_RAILTYPE;
41 }
42
43 TILE(TileIndex tile, Trackdir td)
44 {
45 this->tile = tile;
46 this->td = td;
47 this->tile_type = GetTileType(tile);
48 this->rail_type = GetTileRailType(tile);
49 }
50
51 TILE(const TILE &src)
52 {
53 tile = src.tile;
54 td = src.td;
55 tile_type = src.tile_type;
56 rail_type = src.rail_type;
57 }
58 };
59
60 protected:
61 /**
62 * @note maximum cost doesn't work with caching enabled
63 * @todo fix maximum cost failing with caching (e.g. FS#2900)
64 */
65 int m_max_cost;
66 CBlobT<int> m_sig_look_ahead_costs;
67 bool m_disable_cache;
68
69 public:
70 bool m_stopped_on_first_two_way_signal;
71 protected:
72
73 static const int s_max_segment_cost = 10000;
74
75 CYapfCostRailT() : m_max_cost(0), m_disable_cache(false), m_stopped_on_first_two_way_signal(false)
76 {
77 /* pre-compute look-ahead penalties into array */
78 int p0 = Yapf().PfGetSettings().rail_look_ahead_signal_p0;
79 int p1 = Yapf().PfGetSettings().rail_look_ahead_signal_p1;
80 int p2 = Yapf().PfGetSettings().rail_look_ahead_signal_p2;
81 int *pen = m_sig_look_ahead_costs.GrowSizeNC(Yapf().PfGetSettings().rail_look_ahead_max_signals);
82 for (uint i = 0; i < Yapf().PfGetSettings().rail_look_ahead_max_signals; i++) {
83 pen[i] = p0 + i * (p1 + i * p2);
84 }
85 }
86
87 /** to access inherited path finder */
88 Tpf& Yapf()
89 {
90 return *static_cast<Tpf *>(this);
91 }
92
93 public:
94 inline int SlopeCost(TileIndex tile, Trackdir td)
95 {
96 CPerfStart perf_cost(Yapf().m_perf_slope_cost);
97 if (!stSlopeCost(tile, td)) return 0;
98 return Yapf().PfGetSettings().rail_slope_penalty;
99 }
100
101 inline int CurveCost(Trackdir td1, Trackdir td2)
102 {
103 assert(IsValidTrackdir(td1));
104 assert(IsValidTrackdir(td2));
105 int cost = 0;
106 if (TrackFollower::Allow90degTurns()
107 && ((TrackdirToTrackdirBits(td2) & (TrackdirBits)TrackdirCrossesTrackdirs(td1)) != 0)) {
108 /* 90-deg curve penalty */
109 cost += Yapf().PfGetSettings().rail_curve90_penalty;
110 } else if (td2 != NextTrackdir(td1)) {
111 /* 45-deg curve penalty */
112 cost += Yapf().PfGetSettings().rail_curve45_penalty;
113 }
114 return cost;
115 }
116
117 inline int SwitchCost(TileIndex tile1, TileIndex tile2, DiagDirection exitdir)
118 {
119 if (IsPlainRailTile(tile1) && IsPlainRailTile(tile2)) {
120 bool t1 = KillFirstBit(GetTrackBits(tile1) & DiagdirReachesTracks(ReverseDiagDir(exitdir))) != TRACK_BIT_NONE;
121 bool t2 = KillFirstBit(GetTrackBits(tile2) & DiagdirReachesTracks(exitdir)) != TRACK_BIT_NONE;
122 if (t1 && t2) return Yapf().PfGetSettings().rail_doubleslip_penalty;
123 }
124 return 0;
125 }
126
127 /** Return one tile cost (base cost + level crossing penalty). */
128 inline int OneTileCost(TileIndex &tile, Trackdir trackdir)
129 {
130 int cost = 0;
131 /* set base cost */
132 if (IsDiagonalTrackdir(trackdir)) {
133 cost += YAPF_TILE_LENGTH;
134 switch (GetTileType(tile)) {
135 case MP_ROAD:
136 /* Increase the cost for level crossings */
137 if (IsLevelCrossing(tile)) {
138 cost += Yapf().PfGetSettings().rail_crossing_penalty;
139 }
140 break;
141
142 default:
143 break;
144 }
145 } else {
146 /* non-diagonal trackdir */
147 cost = YAPF_TILE_CORNER_LENGTH;
148 }
149 return cost;
150 }
151
152 /** Check for a reserved station platform. */
153 inline bool IsAnyStationTileReserved(TileIndex tile, Trackdir trackdir, int skipped)
154 {
155 TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(trackdir)));
156 for (; skipped >= 0; skipped--, tile += diff) {
157 if (HasStationReservation(tile)) return true;
158 }
159 return false;
160 }
161
162 /** The cost for reserved tiles, including skipped ones. */
163 inline int ReservationCost(Node &n, TileIndex tile, Trackdir trackdir, int skipped)
164 {
165 if (n.m_num_signals_passed >= m_sig_look_ahead_costs.Size() / 2) return 0;
166 if (!IsPbsSignal(n.m_last_signal_type)) return 0;
167
168 if (IsRailStationTile(tile) && IsAnyStationTileReserved(tile, trackdir, skipped)) {
169 return Yapf().PfGetSettings().rail_pbs_station_penalty * (skipped + 1);
170 } else if (TrackOverlapsTracks(GetReservedTrackbits(tile), TrackdirToTrack(trackdir))) {
171 int cost = Yapf().PfGetSettings().rail_pbs_cross_penalty;
172 if (!IsDiagonalTrackdir(trackdir)) cost = (cost * YAPF_TILE_CORNER_LENGTH) / YAPF_TILE_LENGTH;
173 return cost * (skipped + 1);
174 }
175 return 0;
176 }
177
178 int SignalCost(Node &n, TileIndex tile, Trackdir trackdir)
179 {
180 int cost = 0;
181 /* if there is one-way signal in the opposite direction, then it is not our way */
182 CPerfStart perf_cost(Yapf().m_perf_other_cost);
183 if (IsTileType(tile, MP_RAILWAY)) {
184 bool has_signal_against = HasSignalOnTrackdir(tile, ReverseTrackdir(trackdir));
185 bool has_signal_along = HasSignalOnTrackdir(tile, trackdir);
186 if (has_signal_against && !has_signal_along && IsOnewaySignal(tile, TrackdirToTrack(trackdir))) {
187 /* one-way signal in opposite direction */
188 n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;
189 } else {
190 if (has_signal_along) {
191 SignalState sig_state = GetSignalStateByTrackdir(tile, trackdir);
192 SignalType sig_type = GetSignalType(tile, TrackdirToTrack(trackdir));
193
194 n.m_last_signal_type = sig_type;
195
196 /* cache the look-ahead polynomial constant only if we didn't pass more signals than the look-ahead limit is */
197 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;
198 if (sig_state != SIGNAL_STATE_RED) {
199 /* green signal */
200 n.flags_u.flags_s.m_last_signal_was_red = false;
201 /* negative look-ahead red-signal penalties would cause problems later, so use them as positive penalties for green signal */
202 if (look_ahead_cost < 0) {
203 /* add its negation to the cost */
204 cost -= look_ahead_cost;
205 }
206 } else {
207 /* we have a red signal in our direction
208 * was it first signal which is two-way? */
209 if (!IsPbsSignal(sig_type) && Yapf().TreatFirstRedTwoWaySignalAsEOL() && n.flags_u.flags_s.m_choice_seen && has_signal_against && n.m_num_signals_passed == 0) {
210 /* yes, the first signal is two-way red signal => DEAD END. Prune this branch... */
211 Yapf().PruneIntermediateNodeBranch();
212 n.m_segment->m_end_segment_reason |= ESRB_DEAD_END;
213 Yapf().m_stopped_on_first_two_way_signal = true;
214 return -1;
215 }
216 n.m_last_red_signal_type = sig_type;
217 n.flags_u.flags_s.m_last_signal_was_red = true;
218
219 /* look-ahead signal penalty */
220 if (!IsPbsSignal(sig_type) && look_ahead_cost > 0) {
221 /* add the look ahead penalty only if it is positive */
222 cost += look_ahead_cost;
223 }
224
225 /* special signal penalties */
226 if (n.m_num_signals_passed == 0) {
227 switch (sig_type) {
228 case SIGTYPE_COMBO:
229 case SIGTYPE_EXIT: cost += Yapf().PfGetSettings().rail_firstred_exit_penalty; break; // first signal is red pre-signal-exit
230 case SIGTYPE_NORMAL:
231 case SIGTYPE_ENTRY: cost += Yapf().PfGetSettings().rail_firstred_penalty; break;
232 default: break;
233 }
234 }
235 }
236
237 n.m_num_signals_passed++;
238 n.m_segment->m_last_signal_tile = tile;
239 n.m_segment->m_last_signal_td = trackdir;
240 }
241
242 if (has_signal_against && IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) {
243 cost += n.m_num_signals_passed < Yapf().PfGetSettings().rail_look_ahead_max_signals ? Yapf().PfGetSettings().rail_pbs_signal_back_penalty : 0;
244 }
245 }
246 }
247 return cost;
248 }
249
250 inline int PlatformLengthPenalty(int platform_length)
251 {
252 int cost = 0;
253 const Train *v = Yapf().GetVehicle();
254 assert(v != NULL);
255 assert(v->type == VEH_TRAIN);
256 assert(v->gcache.cached_total_length != 0);
257 int missing_platform_length = CeilDiv(v->gcache.cached_total_length, TILE_SIZE) - platform_length;
258 if (missing_platform_length < 0) {
259 /* apply penalty for longer platform than needed */
260 cost += Yapf().PfGetSettings().rail_longer_platform_penalty + Yapf().PfGetSettings().rail_longer_platform_per_tile_penalty * -missing_platform_length;
261 } else if (missing_platform_length > 0) {
262 /* apply penalty for shorter platform than needed */
263 cost += Yapf().PfGetSettings().rail_shorter_platform_penalty + Yapf().PfGetSettings().rail_shorter_platform_per_tile_penalty * missing_platform_length;
264 }
265 return cost;
266 }
267
268 public:
269 inline void SetMaxCost(int max_cost)
270 {
271 m_max_cost = max_cost;
272 }
273
274 /**
275 * Called by YAPF to calculate the cost from the origin to the given node.
276 * Calculates only the cost of given node, adds it to the parent node cost
277 * and stores the result into Node::m_cost member
278 */
279 inline bool PfCalcCost(Node &n, const TrackFollower *tf)
280 {
281 assert(!n.flags_u.flags_s.m_targed_seen);
282 assert(tf->m_new_tile == n.m_key.m_tile);
283 assert((TrackdirToTrackdirBits(n.m_key.m_td) & tf->m_new_td_bits) != TRACKDIR_BIT_NONE);
284
285 CPerfStart perf_cost(Yapf().m_perf_cost);
286
287 /* Does the node have some parent node? */
288 bool has_parent = (n.m_parent != NULL);
289
290 /* Do we already have a cached segment? */
291 CachedData &segment = *n.m_segment;
292 bool is_cached_segment = (segment.m_cost >= 0);
293
294 int parent_cost = has_parent ? n.m_parent->m_cost : 0;
295
296 /* Each node cost contains 2 or 3 main components:
297 * 1. Transition cost - cost of the move from previous node (tile):
298 * - curve cost (or zero for straight move)
299 * 2. Tile cost:
300 * - base tile cost
301 * - YAPF_TILE_LENGTH for diagonal tiles
302 * - YAPF_TILE_CORNER_LENGTH for non-diagonal tiles
303 * - tile penalties
304 * - tile slope penalty (upward slopes)
305 * - red signal penalty
306 * - level crossing penalty
307 * - speed-limit penalty (bridges)
308 * - station platform penalty
309 * - penalty for reversing in the depot
310 * - etc.
311 * 3. Extra cost (applies to the last node only)
312 * - last red signal penalty
313 * - penalty for too long or too short platform on the destination station
314 */
315 int transition_cost = 0;
316 int extra_cost = 0;
317
318 /* Segment: one or more tiles connected by contiguous tracks of the same type.
319 * Each segment cost includes 'Tile cost' for all its tiles (including the first
320 * and last), and the 'Transition cost' between its tiles. The first transition
321 * cost of segment entry (move from the 'parent' node) is not included!
322 */
323 int segment_entry_cost = 0;
324 int segment_cost = 0;
325
326 const Train *v = Yapf().GetVehicle();
327
328 /* start at n.m_key.m_tile / n.m_key.m_td and walk to the end of segment */
329 TILE cur(n.m_key.m_tile, n.m_key.m_td);
330
331 /* the previous tile will be needed for transition cost calculations */
332 TILE prev = !has_parent ? TILE() : TILE(n.m_parent->GetLastTile(), n.m_parent->GetLastTrackdir());
333
334 EndSegmentReasonBits end_segment_reason = ESRB_NONE;
335
336 TrackFollower tf_local(v, Yapf().GetCompatibleRailTypes(), &Yapf().m_perf_ts_cost);
337
338 if (!has_parent) {
339 /* We will jump to the middle of the cost calculator assuming that segment cache is not used. */
340 assert(!is_cached_segment);
341 /* Skip the first transition cost calculation. */
342 goto no_entry_cost;
343 }
344
345 for (;;) {
346 /* Transition cost (cost of the move from previous tile) */
347 transition_cost = Yapf().CurveCost(prev.td, cur.td);
348 transition_cost += Yapf().SwitchCost(prev.tile, cur.tile, TrackdirToExitdir(prev.td));
349
350 /* First transition cost counts against segment entry cost, other transitions
351 * inside segment will come to segment cost (and will be cached) */
352 if (segment_cost == 0) {
353 /* We just entered the loop. First transition cost goes to segment entry cost)*/
354 segment_entry_cost = transition_cost;
355 transition_cost = 0;
356
357 /* It is the right time now to look if we can reuse the cached segment cost. */
358 if (is_cached_segment) {
359 /* Yes, we already know the segment cost. */
360 segment_cost = segment.m_cost;
361 /* We know also the reason why the segment ends. */
362 end_segment_reason = segment.m_end_segment_reason;
363 /* We will need also some information about the last signal (if it was red). */
364 if (segment.m_last_signal_tile != INVALID_TILE) {
365 assert(HasSignalOnTrackdir(segment.m_last_signal_tile, segment.m_last_signal_td));
366 SignalState sig_state = GetSignalStateByTrackdir(segment.m_last_signal_tile, segment.m_last_signal_td);
367 bool is_red = (sig_state == SIGNAL_STATE_RED);
368 n.flags_u.flags_s.m_last_signal_was_red = is_red;
369 if (is_red) {
370 n.m_last_red_signal_type = GetSignalType(segment.m_last_signal_tile, TrackdirToTrack(segment.m_last_signal_td));
371 }
372 }
373 /* No further calculation needed. */
374 cur = TILE(n.GetLastTile(), n.GetLastTrackdir());
375 break;
376 }
377 } else {
378 /* Other than first transition cost count as the regular segment cost. */
379 segment_cost += transition_cost;
380 }
381
382 no_entry_cost: // jump here at the beginning if the node has no parent (it is the first node)
383
384 /* All other tile costs will be calculated here. */
385 segment_cost += Yapf().OneTileCost(cur.tile, cur.td);
386
387 /* If we skipped some tunnel/bridge/station tiles, add their base cost */
388 segment_cost += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
389
390 /* Slope cost. */
391 segment_cost += Yapf().SlopeCost(cur.tile, cur.td);
392
393 /* Signal cost (routine can modify segment data). */
394 segment_cost += Yapf().SignalCost(n, cur.tile, cur.td);
395
396 /* Reserved tiles. */
397 segment_cost += Yapf().ReservationCost(n, cur.tile, cur.td, tf->m_tiles_skipped);
398
399 end_segment_reason = segment.m_end_segment_reason;
400
401 /* Tests for 'potential target' reasons to close the segment. */
402 if (cur.tile == prev.tile) {
403 /* Penalty for reversing in a depot. */
404 assert(IsRailDepot(cur.tile));
405 segment_cost += Yapf().PfGetSettings().rail_depot_reverse_penalty;
406
407 } else if (IsRailDepotTile(cur.tile)) {
408 /* We will end in this pass (depot is possible target) */
409 end_segment_reason |= ESRB_DEPOT;
410
411 } else if (cur.tile_type == MP_STATION && IsRailWaypoint(cur.tile)) {
412 if (v->current_order.IsType(OT_GOTO_WAYPOINT) &&
413 GetStationIndex(cur.tile) == v->current_order.GetDestination() &&
414 !Waypoint::Get(v->current_order.GetDestination())->IsSingleTile()) {
415 /* This waypoint is our destination; maybe this isn't an unreserved
416 * one, so check that and if so see that as the last signal being
417 * red. This way waypoints near stations should work better. */
418 CFollowTrackRail ft(v);
419 TileIndex t = cur.tile;
420 Trackdir td = cur.td;
421 /* Arbitrary maximum tiles to follow to avoid infinite loops. */
422 uint max_tiles = 20;
423 while (ft.Follow(t, td)) {
424 assert(t != ft.m_new_tile);
425 t = ft.m_new_tile;
426 if (t == cur.tile || --max_tiles == 0) {
427 /* We looped back on ourself or found another loop, bail out. */
428 td = INVALID_TRACKDIR;
429 break;
430 }
431 if (KillFirstBit(ft.m_new_td_bits) != TRACKDIR_BIT_NONE) {
432 /* We encountered a junction; it's going to be too complex to
433 * handle this perfectly, so just bail out. There is no simple
434 * free path, so try the other possibilities. */
435 td = INVALID_TRACKDIR;
436 break;
437 }
438 td = RemoveFirstTrackdir(&ft.m_new_td_bits);
439 /* If this is a safe waiting position we're done searching for it */
440 if (IsSafeWaitingPosition(v, t, td, true, _settings_game.pf.forbid_90_deg)) break;
441 }
442
443 /* In the case this platform is (possibly) occupied we add penalty so the
444 * other platforms of this waypoint are evaluated as well, i.e. we assume
445 * that there is a red signal in the waypoint when it's occupied. */
446 if (td == INVALID_TRACKDIR ||
447 !IsSafeWaitingPosition(v, t, td, true, _settings_game.pf.forbid_90_deg) ||
448 !IsWaitingPositionFree(v, t, td, _settings_game.pf.forbid_90_deg)) {
449 extra_cost += Yapf().PfGetSettings().rail_lastred_penalty;
450 }
451 }
452 /* Waypoint is also a good reason to finish. */
453 end_segment_reason |= ESRB_WAYPOINT;
454
455 } else if (tf->m_is_station) {
456 /* Station penalties. */
457 uint platform_length = tf->m_tiles_skipped + 1;
458 /* We don't know yet if the station is our target or not. Act like
459 * if it is pass-through station (not our destination). */
460 segment_cost += Yapf().PfGetSettings().rail_station_penalty * platform_length;
461 /* We will end in this pass (station is possible target) */
462 end_segment_reason |= ESRB_STATION;
463
464 } else if (TrackFollower::DoTrackMasking() && cur.tile_type == MP_RAILWAY) {
465 /* Searching for a safe tile? */
466 if (HasSignalOnTrackdir(cur.tile, cur.td) && !IsPbsSignal(GetSignalType(cur.tile, TrackdirToTrack(cur.td)))) {
467 end_segment_reason |= ESRB_SAFE_TILE;
468 }
469 }
470
471 /* Apply min/max speed penalties only when inside the look-ahead radius. Otherwise
472 * it would cause desync in MP. */
473 if (n.m_num_signals_passed < m_sig_look_ahead_costs.Size())
474 {
475 int min_speed = 0;
476 int max_speed = tf->GetSpeedLimit(&min_speed);
477 int max_veh_speed = v->GetDisplayMaxSpeed();
478 if (max_speed < max_veh_speed) {
479 extra_cost += YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (4 + tf->m_tiles_skipped) / max_veh_speed;
480 }
481 if (min_speed > max_veh_speed) {
482 extra_cost += YAPF_TILE_LENGTH * (min_speed - max_veh_speed);
483 }
484 }
485
486 /* Finish if we already exceeded the maximum path cost (i.e. when
487 * searching for the nearest depot). */
488 if (m_max_cost > 0 && (parent_cost + segment_entry_cost + segment_cost) > m_max_cost) {
489 end_segment_reason |= ESRB_PATH_TOO_LONG;
490 }
491
492 /* Move to the next tile/trackdir. */
493 tf = &tf_local;
494 tf_local.Init(v, Yapf().GetCompatibleRailTypes(), &Yapf().m_perf_ts_cost);
495
496 if (!tf_local.Follow(cur.tile, cur.td)) {
497 assert(tf_local.m_err != TrackFollower::EC_NONE);
498 /* Can't move to the next tile (EOL?). */
499 if (tf_local.m_err == TrackFollower::EC_RAIL_TYPE) {
500 end_segment_reason |= ESRB_RAIL_TYPE;
501 } else {
502 end_segment_reason |= ESRB_DEAD_END;
503 }
504
505 if (TrackFollower::DoTrackMasking() && !HasOnewaySignalBlockingTrackdir(cur.tile, cur.td)) {
506 end_segment_reason |= ESRB_SAFE_TILE;
507 }
508 break;
509 }
510
511 /* Check if the next tile is not a choice. */
512 if (KillFirstBit(tf_local.m_new_td_bits) != TRACKDIR_BIT_NONE) {
513 /* More than one segment will follow. Close this one. */
514 end_segment_reason |= ESRB_CHOICE_FOLLOWS;
515 break;
516 }
517
518 /* Gather the next tile/trackdir/tile_type/rail_type. */
519 TILE next(tf_local.m_new_tile, (Trackdir)FindFirstBit2x64(tf_local.m_new_td_bits));
520
521 if (TrackFollower::DoTrackMasking() && IsTileType(next.tile, MP_RAILWAY)) {
522 if (HasSignalOnTrackdir(next.tile, next.td) && IsPbsSignal(GetSignalType(next.tile, TrackdirToTrack(next.td)))) {
523 /* Possible safe tile. */
524 end_segment_reason |= ESRB_SAFE_TILE;
525 } else if (HasSignalOnTrackdir(next.tile, ReverseTrackdir(next.td)) && GetSignalType(next.tile, TrackdirToTrack(next.td)) == SIGTYPE_PBS_ONEWAY) {
526 /* Possible safe tile, but not so good as it's the back of a signal... */
527 end_segment_reason |= ESRB_SAFE_TILE | ESRB_DEAD_END;
528 extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty;
529 }
530 }
531
532 /* Check the next tile for the rail type. */
533 if (next.rail_type != cur.rail_type) {
534 /* Segment must consist from the same rail_type tiles. */
535 end_segment_reason |= ESRB_RAIL_TYPE;
536 break;
537 }
538
539 /* Avoid infinite looping. */
540 if (next.tile == n.m_key.m_tile && next.td == n.m_key.m_td) {
541 end_segment_reason |= ESRB_INFINITE_LOOP;
542 break;
543 }
544
545 if (segment_cost > s_max_segment_cost) {
546 /* Potentially in the infinite loop (or only very long segment?). We should
547 * not force it to finish prematurely unless we are on a regular tile. */
548 if (IsTileType(tf->m_new_tile, MP_RAILWAY)) {
549 end_segment_reason |= ESRB_SEGMENT_TOO_LONG;
550 break;
551 }
552 }
553
554 /* Any other reason bit set? */
555 if (end_segment_reason != ESRB_NONE) {
556 break;
557 }
558
559 /* For the next loop set new prev and cur tile info. */
560 prev = cur;
561 cur = next;
562
563 } // for (;;)
564
565 /* Don't consider path any further it if exceeded max_cost. */
566 if (end_segment_reason & ESRB_PATH_TOO_LONG) return false;
567
568 bool target_seen = false;
569 if ((end_segment_reason & ESRB_POSSIBLE_TARGET) != ESRB_NONE) {
570 /* Depot, station or waypoint. */
571 if (Yapf().PfDetectDestination(cur.tile, cur.td)) {
572 /* Destination found. */
573 target_seen = true;
574 }
575 }
576
577 /* Update the segment if needed. */
578 if (!is_cached_segment) {
579 /* Write back the segment information so it can be reused the next time. */
580 segment.m_cost = segment_cost;
581 segment.m_end_segment_reason = end_segment_reason & ESRB_CACHED_MASK;
582 /* Save end of segment back to the node. */
583 n.SetLastTileTrackdir(cur.tile, cur.td);
584 }
585
586 /* Do we have an excuse why not to continue pathfinding in this direction? */
587 if (!target_seen && (end_segment_reason & ESRB_ABORT_PF_MASK) != ESRB_NONE) {
588 /* Reason to not continue. Stop this PF branch. */
589 return false;
590 }
591
592 /* Special costs for the case we have reached our target. */
593 if (target_seen) {
594 n.flags_u.flags_s.m_targed_seen = true;
595 /* Last-red and last-red-exit penalties. */
596 if (n.flags_u.flags_s.m_last_signal_was_red) {
597 if (n.m_last_red_signal_type == SIGTYPE_EXIT) {
598 /* last signal was red pre-signal-exit */
599 extra_cost += Yapf().PfGetSettings().rail_lastred_exit_penalty;
600 } else if (!IsPbsSignal(n.m_last_red_signal_type)) {
601 /* Last signal was red, but not exit or path signal. */
602 extra_cost += Yapf().PfGetSettings().rail_lastred_penalty;
603 }
604 }
605
606 /* Station platform-length penalty. */
607 if ((end_segment_reason & ESRB_STATION) != ESRB_NONE) {
608 const BaseStation *st = BaseStation::GetByTile(n.GetLastTile());
609 assert(st != NULL);
610 uint platform_length = st->GetPlatformLength(n.GetLastTile(), ReverseDiagDir(TrackdirToExitdir(n.GetLastTrackdir())));
611 /* Reduce the extra cost caused by passing-station penalty (each station receives it in the segment cost). */
612 extra_cost -= Yapf().PfGetSettings().rail_station_penalty * platform_length;
613 /* Add penalty for the inappropriate platform length. */
614 extra_cost += PlatformLengthPenalty(platform_length);
615 }
616 }
617
618 /* total node cost */
619 n.m_cost = parent_cost + segment_entry_cost + segment_cost + extra_cost;
620
621 return true;
622 }
623
624 inline bool CanUseGlobalCache(Node &n) const
625 {
626 return !m_disable_cache
627 && (n.m_parent != NULL)
628 && (n.m_parent->m_num_signals_passed >= m_sig_look_ahead_costs.Size());
629 }
630
631 inline void ConnectNodeToCachedData(Node &n, CachedData &ci)
632 {
633 n.m_segment = &ci;
634 if (n.m_segment->m_cost < 0) {
635 n.m_segment->m_last_tile = n.m_key.m_tile;
636 n.m_segment->m_last_td = n.m_key.m_td;
637 }
638 }
639
640 void DisableCache(bool disable)
641 {
642 m_disable_cache = disable;
643 }
644 };
645
646 #endif /* YAPF_COSTRAIL_HPP */
OpenTTD trunk