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 pbs.cpp PBS support routines */
9
10 #include "stdafx.h"
11 #include "viewport_func.h"
12 #include "vehicle_func.h"
13 #include "newgrf_station.h"
14 #include "pathfinder/follow_track.hpp"
15
16 #include "safeguards.h"
17
18 /**
19 * Get the reserved trackbits for any tile, regardless of type.
20 * @param t the tile
21 * @return the reserved trackbits. TRACK_BIT_NONE on nothing reserved or
22 * a tile without rail.
23 */
GetReservedTrackbits(TileIndex t)24 TrackBits GetReservedTrackbits(TileIndex t)
25 {
26 switch (GetTileType(t)) {
27 case MP_RAILWAY:
28 if (IsRailDepot(t)) return GetDepotReservationTrackBits(t);
29 if (IsPlainRail(t)) return GetRailReservationTrackBits(t);
30 break;
31
32 case MP_ROAD:
33 if (IsLevelCrossing(t)) return GetCrossingReservationTrackBits(t);
34 break;
35
36 case MP_STATION:
37 if (HasStationRail(t)) return GetStationReservationTrackBits(t);
38 break;
39
40 case MP_TUNNELBRIDGE:
41 if (GetTunnelBridgeTransportType(t) == TRANSPORT_RAIL) return GetTunnelBridgeReservationTrackBits(t);
42 break;
43
44 default:
45 break;
46 }
47 return TRACK_BIT_NONE;
48 }
49
50 /**
51 * Set the reservation for a complete station platform.
52 * @pre IsRailStationTile(start)
53 * @param start starting tile of the platform
54 * @param dir the direction in which to follow the platform
55 * @param b the state the reservation should be set to
56 */
SetRailStationPlatformReservation(TileIndex start,DiagDirection dir,bool b)57 void SetRailStationPlatformReservation(TileIndex start, DiagDirection dir, bool b)
58 {
59 TileIndex tile = start;
60 TileIndexDiff diff = TileOffsByDiagDir(dir);
61
62 assert(IsRailStationTile(start));
63 assert(GetRailStationAxis(start) == DiagDirToAxis(dir));
64
65 do {
66 SetRailStationReservation(tile, b);
67 MarkTileDirtyByTile(tile);
68 tile = TILE_ADD(tile, diff);
69 } while (IsCompatibleTrainStationTile(tile, start));
70 }
71
72 /**
73 * Try to reserve a specific track on a tile
74 * @param tile the tile
75 * @param t the track
76 * @param trigger_stations whether to call station randomisation trigger
77 * @return \c true if reservation was successful, i.e. the track was
78 * free and didn't cross any other reserved tracks.
79 */
TryReserveRailTrack(TileIndex tile,Track t,bool trigger_stations)80 bool TryReserveRailTrack(TileIndex tile, Track t, bool trigger_stations)
81 {
82 assert(HasTrack(TrackStatusToTrackBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)), t));
83
84 if (_settings_client.gui.show_track_reservation) {
85 /* show the reserved rail if needed */
86 if (IsBridgeTile(tile)) {
87 MarkBridgeDirty(tile);
88 } else {
89 MarkTileDirtyByTile(tile);
90 }
91 }
92
93 switch (GetTileType(tile)) {
94 case MP_RAILWAY:
95 if (IsPlainRail(tile)) return TryReserveTrack(tile, t);
96 if (IsRailDepot(tile)) {
97 if (!HasDepotReservation(tile)) {
98 SetDepotReservation(tile, true);
99 MarkTileDirtyByTile(tile); // some GRFs change their appearance when tile is reserved
100 return true;
101 }
102 }
103 break;
104
105 case MP_ROAD:
106 if (IsLevelCrossing(tile) && !HasCrossingReservation(tile)) {
107 SetCrossingReservation(tile, true);
108 BarCrossing(tile);
109 MarkTileDirtyByTile(tile); // crossing barred, make tile dirty
110 return true;
111 }
112 break;
113
114 case MP_STATION:
115 if (HasStationRail(tile) && !HasStationReservation(tile)) {
116 SetRailStationReservation(tile, true);
117 if (trigger_stations && IsRailStation(tile)) TriggerStationRandomisation(nullptr, tile, SRT_PATH_RESERVATION);
118 MarkTileDirtyByTile(tile); // some GRFs need redraw after reserving track
119 return true;
120 }
121 break;
122
123 case MP_TUNNELBRIDGE:
124 if (GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL && !GetTunnelBridgeReservationTrackBits(tile)) {
125 SetTunnelBridgeReservation(tile, true);
126 return true;
127 }
128 break;
129
130 default:
131 break;
132 }
133 return false;
134 }
135
136 /**
137 * Lift the reservation of a specific track on a tile
138 * @param tile the tile
139 * @param t the track
140 */
UnreserveRailTrack(TileIndex tile,Track t)141 void UnreserveRailTrack(TileIndex tile, Track t)
142 {
143 assert(HasTrack(TrackStatusToTrackBits(GetTileTrackStatus(tile, TRANSPORT_RAIL, 0)), t));
144
145 if (_settings_client.gui.show_track_reservation) {
146 if (IsBridgeTile(tile)) {
147 MarkBridgeDirty(tile);
148 } else {
149 MarkTileDirtyByTile(tile);
150 }
151 }
152
153 switch (GetTileType(tile)) {
154 case MP_RAILWAY:
155 if (IsRailDepot(tile)) {
156 SetDepotReservation(tile, false);
157 MarkTileDirtyByTile(tile);
158 break;
159 }
160 if (IsPlainRail(tile)) UnreserveTrack(tile, t);
161 break;
162
163 case MP_ROAD:
164 if (IsLevelCrossing(tile)) {
165 SetCrossingReservation(tile, false);
166 UpdateLevelCrossing(tile);
167 }
168 break;
169
170 case MP_STATION:
171 if (HasStationRail(tile)) {
172 SetRailStationReservation(tile, false);
173 MarkTileDirtyByTile(tile);
174 }
175 break;
176
177 case MP_TUNNELBRIDGE:
178 if (GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL) SetTunnelBridgeReservation(tile, false);
179 break;
180
181 default:
182 break;
183 }
184 }
185
186
187 /** Follow a reservation starting from a specific tile to the end. */
FollowReservation(Owner o,RailTypes rts,TileIndex tile,Trackdir trackdir,bool ignore_oneway=false)188 static PBSTileInfo FollowReservation(Owner o, RailTypes rts, TileIndex tile, Trackdir trackdir, bool ignore_oneway = false)
189 {
190 TileIndex start_tile = tile;
191 Trackdir start_trackdir = trackdir;
192 bool first_loop = true;
193
194 /* Start track not reserved? This can happen if two trains
195 * are on the same tile. The reservation on the next tile
196 * is not ours in this case, so exit. */
197 if (!HasReservedTracks(tile, TrackToTrackBits(TrackdirToTrack(trackdir)))) return PBSTileInfo(tile, trackdir, false);
198
199 /* Do not disallow 90 deg turns as the setting might have changed between reserving and now. */
200 CFollowTrackRail ft(o, rts);
201 while (ft.Follow(tile, trackdir)) {
202 TrackdirBits reserved = ft.m_new_td_bits & TrackBitsToTrackdirBits(GetReservedTrackbits(ft.m_new_tile));
203
204 /* No reservation --> path end found */
205 if (reserved == TRACKDIR_BIT_NONE) {
206 if (ft.m_is_station) {
207 /* Check skipped station tiles as well, maybe our reservation ends inside the station. */
208 TileIndexDiff diff = TileOffsByDiagDir(ft.m_exitdir);
209 while (ft.m_tiles_skipped-- > 0) {
210 ft.m_new_tile -= diff;
211 if (HasStationReservation(ft.m_new_tile)) {
212 tile = ft.m_new_tile;
213 trackdir = DiagDirToDiagTrackdir(ft.m_exitdir);
214 break;
215 }
216 }
217 }
218 break;
219 }
220
221 /* Can't have more than one reserved trackdir */
222 Trackdir new_trackdir = FindFirstTrackdir(reserved);
223
224 /* One-way signal against us. The reservation can't be ours as it is not
225 * a safe position from our direction and we can never pass the signal. */
226 if (!ignore_oneway && HasOnewaySignalBlockingTrackdir(ft.m_new_tile, new_trackdir)) break;
227
228 tile = ft.m_new_tile;
229 trackdir = new_trackdir;
230
231 if (first_loop) {
232 /* Update the start tile after we followed the track the first
233 * time. This is necessary because the track follower can skip
234 * tiles (in stations for example) which means that we might
235 * never visit our original starting tile again. */
236 start_tile = tile;
237 start_trackdir = trackdir;
238 first_loop = false;
239 } else {
240 /* Loop encountered? */
241 if (tile == start_tile && trackdir == start_trackdir) break;
242 }
243 /* Depot tile? Can't continue. */
244 if (IsRailDepotTile(tile)) break;
245 /* Non-pbs signal? Reservation can't continue. */
246 if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) break;
247 }
248
249 return PBSTileInfo(tile, trackdir, false);
250 }
251
252 /**
253 * Helper struct for finding the best matching vehicle on a specific track.
254 */
255 struct FindTrainOnTrackInfo {
256 PBSTileInfo res; ///< Information about the track.
257 Train *best; ///< The currently "best" vehicle we have found.
258
259 /** Init the best location to nullptr always! */
FindTrainOnTrackInfoFindTrainOnTrackInfo260 FindTrainOnTrackInfo() : best(nullptr) {}
261 };
262
263 /** Callback for Has/FindVehicleOnPos to find a train on a specific track. */
FindTrainOnTrackEnum(Vehicle * v,void * data)264 static Vehicle *FindTrainOnTrackEnum(Vehicle *v, void *data)
265 {
266 FindTrainOnTrackInfo *info = (FindTrainOnTrackInfo *)data;
267
268 if (v->type != VEH_TRAIN || (v->vehstatus & VS_CRASHED)) return nullptr;
269
270 Train *t = Train::From(v);
271 if (t->track == TRACK_BIT_WORMHOLE || HasBit((TrackBits)t->track, TrackdirToTrack(info->res.trackdir))) {
272 t = t->First();
273
274 /* ALWAYS return the lowest ID (anti-desync!) */
275 if (info->best == nullptr || t->index < info->best->index) info->best = t;
276 return t;
277 }
278
279 return nullptr;
280 }
281
282 /**
283 * Follow a train reservation to the last tile.
284 *
285 * @param v the vehicle
286 * @param train_on_res Is set to a train we might encounter
287 * @returns The last tile of the reservation or the current train tile if no reservation present.
288 */
FollowTrainReservation(const Train * v,Vehicle ** train_on_res)289 PBSTileInfo FollowTrainReservation(const Train *v, Vehicle **train_on_res)
290 {
291 assert(v->type == VEH_TRAIN);
292
293 TileIndex tile = v->tile;
294 Trackdir trackdir = v->GetVehicleTrackdir();
295
296 if (IsRailDepotTile(tile) && !GetDepotReservationTrackBits(tile)) return PBSTileInfo(tile, trackdir, false);
297
298 FindTrainOnTrackInfo ftoti;
299 ftoti.res = FollowReservation(v->owner, GetRailTypeInfo(v->railtype)->compatible_railtypes, tile, trackdir);
300 ftoti.res.okay = IsSafeWaitingPosition(v, ftoti.res.tile, ftoti.res.trackdir, true, _settings_game.pf.forbid_90_deg);
301 if (train_on_res != nullptr) {
302 FindVehicleOnPos(ftoti.res.tile, &ftoti, FindTrainOnTrackEnum);
303 if (ftoti.best != nullptr) *train_on_res = ftoti.best->First();
304 if (*train_on_res == nullptr && IsRailStationTile(ftoti.res.tile)) {
305 /* The target tile is a rail station. The track follower
306 * has stopped on the last platform tile where we haven't
307 * found a train. Also check all previous platform tiles
308 * for a possible train. */
309 TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(ftoti.res.trackdir)));
310 for (TileIndex st_tile = ftoti.res.tile + diff; *train_on_res == nullptr && IsCompatibleTrainStationTile(st_tile, ftoti.res.tile); st_tile += diff) {
311 FindVehicleOnPos(st_tile, &ftoti, FindTrainOnTrackEnum);
312 if (ftoti.best != nullptr) *train_on_res = ftoti.best->First();
313 }
314 }
315 if (*train_on_res == nullptr && IsTileType(ftoti.res.tile, MP_TUNNELBRIDGE)) {
316 /* The target tile is a bridge/tunnel, also check the other end tile. */
317 FindVehicleOnPos(GetOtherTunnelBridgeEnd(ftoti.res.tile), &ftoti, FindTrainOnTrackEnum);
318 if (ftoti.best != nullptr) *train_on_res = ftoti.best->First();
319 }
320 }
321 return ftoti.res;
322 }
323
324 /**
325 * Find the train which has reserved a specific path.
326 *
327 * @param tile A tile on the path.
328 * @param track A reserved track on the tile.
329 * @return The vehicle holding the reservation or nullptr if the path is stray.
330 */
GetTrainForReservation(TileIndex tile,Track track)331 Train *GetTrainForReservation(TileIndex tile, Track track)
332 {
333 assert(HasReservedTracks(tile, TrackToTrackBits(track)));
334 Trackdir trackdir = TrackToTrackdir(track);
335
336 RailTypes rts = GetRailTypeInfo(GetTileRailType(tile))->compatible_railtypes;
337
338 /* Follow the path from tile to both ends, one of the end tiles should
339 * have a train on it. We need FollowReservation to ignore one-way signals
340 * here, as one of the two search directions will be the "wrong" way. */
341 for (int i = 0; i < 2; ++i, trackdir = ReverseTrackdir(trackdir)) {
342 /* If the tile has a one-way block signal in the current trackdir, skip the
343 * search in this direction as the reservation can't come from this side.*/
344 if (HasOnewaySignalBlockingTrackdir(tile, ReverseTrackdir(trackdir)) && !HasPbsSignalOnTrackdir(tile, trackdir)) continue;
345
346 FindTrainOnTrackInfo ftoti;
347 ftoti.res = FollowReservation(GetTileOwner(tile), rts, tile, trackdir, true);
348
349 FindVehicleOnPos(ftoti.res.tile, &ftoti, FindTrainOnTrackEnum);
350 if (ftoti.best != nullptr) return ftoti.best;
351
352 /* Special case for stations: check the whole platform for a vehicle. */
353 if (IsRailStationTile(ftoti.res.tile)) {
354 TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(ftoti.res.trackdir)));
355 for (TileIndex st_tile = ftoti.res.tile + diff; IsCompatibleTrainStationTile(st_tile, ftoti.res.tile); st_tile += diff) {
356 FindVehicleOnPos(st_tile, &ftoti, FindTrainOnTrackEnum);
357 if (ftoti.best != nullptr) return ftoti.best;
358 }
359 }
360
361 /* Special case for bridges/tunnels: check the other end as well. */
362 if (IsTileType(ftoti.res.tile, MP_TUNNELBRIDGE)) {
363 FindVehicleOnPos(GetOtherTunnelBridgeEnd(ftoti.res.tile), &ftoti, FindTrainOnTrackEnum);
364 if (ftoti.best != nullptr) return ftoti.best;
365 }
366 }
367
368 return nullptr;
369 }
370
371 /**
372 * Determine whether a certain track on a tile is a safe position to end a path.
373 *
374 * @param v the vehicle to test for
375 * @param tile The tile
376 * @param trackdir The trackdir to test
377 * @param include_line_end Should end-of-line tiles be considered safe?
378 * @param forbid_90deg Don't allow trains to make 90 degree turns
379 * @return True if it is a safe position
380 */
IsSafeWaitingPosition(const Train * v,TileIndex tile,Trackdir trackdir,bool include_line_end,bool forbid_90deg)381 bool IsSafeWaitingPosition(const Train *v, TileIndex tile, Trackdir trackdir, bool include_line_end, bool forbid_90deg)
382 {
383 if (IsRailDepotTile(tile)) return true;
384
385 if (IsTileType(tile, MP_RAILWAY)) {
386 /* For non-pbs signals, stop on the signal tile. */
387 if (HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) return true;
388 }
389
390 /* Check next tile. For performance reasons, we check for 90 degree turns ourself. */
391 CFollowTrackRail ft(v, GetRailTypeInfo(v->railtype)->compatible_railtypes);
392
393 /* End of track? */
394 if (!ft.Follow(tile, trackdir)) {
395 /* Last tile of a terminus station is a safe position. */
396 if (include_line_end) return true;
397 }
398
399 /* Check for reachable tracks. */
400 ft.m_new_td_bits &= DiagdirReachesTrackdirs(ft.m_exitdir);
401 if (Rail90DegTurnDisallowed(GetTileRailType(ft.m_old_tile), GetTileRailType(ft.m_new_tile), forbid_90deg)) ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(trackdir);
402 if (ft.m_new_td_bits == TRACKDIR_BIT_NONE) return include_line_end;
403
404 if (ft.m_new_td_bits != TRACKDIR_BIT_NONE && KillFirstBit(ft.m_new_td_bits) == TRACKDIR_BIT_NONE) {
405 Trackdir td = FindFirstTrackdir(ft.m_new_td_bits);
406 /* PBS signal on next trackdir? Safe position. */
407 if (HasPbsSignalOnTrackdir(ft.m_new_tile, td)) return true;
408 /* One-way PBS signal against us? Safe if end-of-line is allowed. */
409 if (IsTileType(ft.m_new_tile, MP_RAILWAY) && HasSignalOnTrackdir(ft.m_new_tile, ReverseTrackdir(td)) &&
410 GetSignalType(ft.m_new_tile, TrackdirToTrack(td)) == SIGTYPE_PBS_ONEWAY) {
411 return include_line_end;
412 }
413 }
414
415 return false;
416 }
417
418 /**
419 * Check if a safe position is free.
420 *
421 * @param v the vehicle to test for
422 * @param tile The tile
423 * @param trackdir The trackdir to test
424 * @param forbid_90deg Don't allow trains to make 90 degree turns
425 * @return True if the position is free
426 */
IsWaitingPositionFree(const Train * v,TileIndex tile,Trackdir trackdir,bool forbid_90deg)427 bool IsWaitingPositionFree(const Train *v, TileIndex tile, Trackdir trackdir, bool forbid_90deg)
428 {
429 Track track = TrackdirToTrack(trackdir);
430 TrackBits reserved = GetReservedTrackbits(tile);
431
432 /* Tile reserved? Can never be a free waiting position. */
433 if (TrackOverlapsTracks(reserved, track)) return false;
434
435 /* Not reserved and depot or not a pbs signal -> free. */
436 if (IsRailDepotTile(tile)) return true;
437 if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, track))) return true;
438
439 /* Check the next tile, if it's a PBS signal, it has to be free as well. */
440 CFollowTrackRail ft(v, GetRailTypeInfo(v->railtype)->compatible_railtypes);
441
442 if (!ft.Follow(tile, trackdir)) return true;
443
444 /* Check for reachable tracks. */
445 ft.m_new_td_bits &= DiagdirReachesTrackdirs(ft.m_exitdir);
446 if (Rail90DegTurnDisallowed(GetTileRailType(ft.m_old_tile), GetTileRailType(ft.m_new_tile), forbid_90deg)) ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(trackdir);
447
448 return !HasReservedTracks(ft.m_new_tile, TrackdirBitsToTrackBits(ft.m_new_td_bits));
449 }
450