rubidium@9786: /* $Id$ */
rubidium@9786: 
rubidium@9786: /** @file pbs.cpp */
rubidium@9786: #include "stdafx.h"
rubidium@9786: #include "openttd.h"
rubidium@9786: #include "pbs.h"
rubidium@9786: #include "rail_map.h"
rubidium@9786: #include "road_map.h"
rubidium@9786: #include "station_map.h"
rubidium@9786: #include "tunnelbridge_map.h"
rubidium@9787: #include "functions.h"
rubidium@9787: #include "debug.h"
rubidium@9787: #include "direction_func.h"
rubidium@9787: #include "settings_type.h"
rubidium@9798: #include "road_func.h"
rubidium@9798: #include "vehicle_base.h"
rubidium@9814: #include "vehicle_func.h"
rubidium@9798: #include "yapf/follow_track.hpp"
rubidium@9786: 
rubidium@9786: /**
rubidium@9786:  * Get the reserved trackbits for any tile, regardless of type.
rubidium@9786:  * @param t the tile
rubidium@9786:  * @return the reserved trackbits. TRACK_BIT_NONE on nothing reserved or
rubidium@9786:  *     a tile without rail.
rubidium@9786:  */
rubidium@9786: TrackBits GetReservedTrackbits(TileIndex t)
rubidium@9786: {
rubidium@9786: 	switch (GetTileType(t)) {
rubidium@9786: 		case MP_RAILWAY:
rubidium@9786: 			if (IsRailWaypoint(t) || IsRailDepot(t)) return GetRailWaypointReservation(t);
rubidium@9786: 			if (IsPlainRailTile(t)) return GetTrackReservation(t);
rubidium@9786: 			break;
rubidium@9786: 
rubidium@9786: 		case MP_ROAD:
rubidium@9786: 			if (IsLevelCrossing(t)) return GetRailCrossingReservation(t);
rubidium@9786: 			break;
rubidium@9786: 
rubidium@9786: 		case MP_STATION:
rubidium@9786: 			if (IsRailwayStation(t)) return GetRailStationReservation(t);
rubidium@9786: 			break;
rubidium@9786: 
rubidium@9786: 		case MP_TUNNELBRIDGE:
rubidium@9786: 			if (GetTunnelBridgeTransportType(t) == TRANSPORT_RAIL) return GetRailTunnelBridgeReservation(t);
rubidium@9786: 			break;
rubidium@9786: 
rubidium@9786: 		default:
rubidium@9786: 			break;
rubidium@9786: 	}
rubidium@9786: 	return TRACK_BIT_NONE;
rubidium@9786: }
rubidium@9787: 
rubidium@9787: /**
rubidium@9787:  * Set the reservation for a complete station platform.
rubidium@9787:  * @pre IsRailwayStationTile(start)
rubidium@9787:  * @param start starting tile of the platform
rubidium@9787:  * @param dir the direction in which to follow the platform
rubidium@9787:  * @param b the state the reservation should be set to
rubidium@9787:  */
rubidium@9787: void SetRailwayStationPlatformReservation(TileIndex start, DiagDirection dir, bool b)
rubidium@9787: {
rubidium@9787: 	TileIndex     tile = start;
rubidium@9787: 	TileIndexDiff diff = TileOffsByDiagDir(dir);
rubidium@9787: 
rubidium@9787: 	assert(IsRailwayStationTile(start));
rubidium@9787: 	assert(GetRailStationAxis(start) == DiagDirToAxis(dir));
rubidium@9787: 
rubidium@9787: 	do {
rubidium@9787: 		SetRailwayStationReservation(tile, b);
rubidium@9823: 		MarkTileDirtyByTile(tile);
rubidium@9787: 		tile = TILE_ADD(tile, diff);
rubidium@9787: 	} while (IsCompatibleTrainStationTile(tile, start));
rubidium@9787: }
rubidium@9787: 
rubidium@9787: /**
rubidium@9787:  * Try to reserve a specific track on a tile
rubidium@9787:  * @param tile the tile
rubidium@9787:  * @param t the track
rubidium@9787:  * @return true if reservation was successfull, i.e. the track was
rubidium@9787:  *     free and didn't cross any other reserved tracks.
rubidium@9787:  */
rubidium@9787: bool TryReserveRailTrack(TileIndex tile, Track t)
rubidium@9787: {
rubidium@9787: 	assert((GetTileTrackStatus(tile, TRANSPORT_RAIL, 0) & TrackToTrackBits(t)) != 0);
rubidium@9787: 
rubidium@9787: 	if (_settings_client.gui.show_track_reservation) {
smatz@9954: 		/* show the reserved rail if needed */
rubidium@9787: 		MarkTileDirtyByTile(tile);
rubidium@9787: 	}
rubidium@9787: 
rubidium@9787: 	switch (GetTileType(tile)) {
rubidium@9787: 		case MP_RAILWAY:
rubidium@9787: 			if (IsPlainRailTile(tile)) return TryReserveTrack(tile, t);
rubidium@9787: 			if (IsRailWaypoint(tile) || IsRailDepot(tile)) {
rubidium@9787: 				if (!GetDepotWaypointReservation(tile)) {
rubidium@9787: 					SetDepotWaypointReservation(tile, true);
smatz@9954: 					MarkTileDirtyByTile(tile); // some GRFs change their appearance when tile is reserved
rubidium@9787: 					return true;
rubidium@9787: 				}
rubidium@9787: 			}
rubidium@9787: 			break;
rubidium@9787: 
rubidium@9787: 		case MP_ROAD:
rubidium@9787: 			if (IsLevelCrossing(tile) && !GetCrossingReservation(tile)) {
rubidium@9787: 				SetCrossingReservation(tile, true);
rubidium@9824: 				BarCrossing(tile);
smatz@9954: 				MarkTileDirtyByTile(tile); // crossing barred, make tile dirty
rubidium@9787: 				return true;
rubidium@9787: 			}
rubidium@9787: 			break;
rubidium@9787: 
rubidium@9787: 		case MP_STATION:
rubidium@9787: 			if (IsRailwayStation(tile) && !GetRailwayStationReservation(tile)) {
rubidium@9787: 				SetRailwayStationReservation(tile, true);
smatz@9954: 				MarkTileDirtyByTile(tile); // some GRFs need redraw after reserving track
rubidium@9787: 				return true;
rubidium@9787: 			}
rubidium@9787: 			break;
rubidium@9787: 
rubidium@9787: 		case MP_TUNNELBRIDGE:
rubidium@9787: 			if (GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL && !GetRailTunnelBridgeReservation(tile)) {
rubidium@9787: 				SetTunnelBridgeReservation(tile, true);
rubidium@9787: 				return true;
rubidium@9787: 			}
rubidium@9787: 			break;
rubidium@9787: 
rubidium@9787: 		default:
rubidium@9787: 			break;
rubidium@9787: 	}
rubidium@9787: 	return false;
rubidium@9787: }
rubidium@9787: 
rubidium@9787: /**
rubidium@9787:  * Lift the reservation of a specific track on a tile
rubidium@9787:  * @param tile the tile
rubidium@9787:  * @param t the track
rubidium@9787:  */
rubidium@9787:  void UnreserveRailTrack(TileIndex tile, Track t)
rubidium@9787: {
rubidium@9787: 	assert((GetTileTrackStatus(tile, TRANSPORT_RAIL, 0) & TrackToTrackBits(t)) != 0);
rubidium@9787: 
rubidium@9787: 	if (_settings_client.gui.show_track_reservation) {
rubidium@9787: 		MarkTileDirtyByTile(tile);
rubidium@9787: 	}
rubidium@9787: 
rubidium@9787: 	switch (GetTileType(tile)) {
rubidium@9787: 		case MP_RAILWAY:
rubidium@9823: 			if (IsRailWaypoint(tile) || IsRailDepot(tile)) {
rubidium@9823: 				SetDepotWaypointReservation(tile, false);
rubidium@9823: 				MarkTileDirtyByTile(tile);
smatz@9954: 				break;
rubidium@9823: 			}
rubidium@9787: 			if (IsPlainRailTile(tile)) UnreserveTrack(tile, t);
rubidium@9787: 			break;
rubidium@9787: 
rubidium@9787: 		case MP_ROAD:
rubidium@9824: 			if (IsLevelCrossing(tile)) {
rubidium@9824: 				SetCrossingReservation(tile, false);
rubidium@9824: 				UpdateLevelCrossing(tile);
rubidium@9824: 			}
rubidium@9787: 			break;
rubidium@9787: 
rubidium@9787: 		case MP_STATION:
rubidium@9823: 			if (IsRailwayStation(tile)) {
rubidium@9823: 				SetRailwayStationReservation(tile, false);
rubidium@9823: 				MarkTileDirtyByTile(tile);
rubidium@9823: 			}
rubidium@9787: 			break;
rubidium@9787: 
rubidium@9787: 		case MP_TUNNELBRIDGE:
rubidium@9787: 			if (GetTunnelBridgeTransportType(tile) == TRANSPORT_RAIL) SetTunnelBridgeReservation(tile, false);
rubidium@9787: 			break;
rubidium@9787: 
rubidium@9787: 		default:
rubidium@9787: 			break;
rubidium@9787: 	}
rubidium@9787: }
rubidium@9798: 
rubidium@9814: 
rubidium@9814: /** Follow a reservation starting from a specific tile to the end. */
rubidium@9814: static PBSTileInfo FollowReservation(Owner o, RailTypes rts, TileIndex tile, Trackdir trackdir, bool ignore_oneway = false)
rubidium@9814: {
rubidium@9814: 	/* Do not disallow 90 deg turns as the setting might have changed between reserving and now. */
rubidium@9814: 	CFollowTrackRail ft(o, rts);
rubidium@9814: 	while (ft.Follow(tile, trackdir)) {
rubidium@9814: 		TrackdirBits reserved = (TrackdirBits)(ft.m_new_td_bits & (GetReservedTrackbits(ft.m_new_tile) * 0x101));
rubidium@9814: 
rubidium@9814: 		/* No reservation --> path end found */
rubidium@9814: 		if (reserved == TRACKDIR_BIT_NONE) break;
rubidium@9814: 
rubidium@9814: 		/* Can't have more than one reserved trackdir */
rubidium@9814: 		Trackdir new_trackdir = FindFirstTrackdir(reserved);
rubidium@9814: 
rubidium@9814: 		/* One-way signal against us. The reservation can't be ours as it is not
rubidium@9814: 		 * a safe position from our direction and we can never pass the signal. */
rubidium@9814: 		if (!ignore_oneway && HasOnewaySignalBlockingTrackdir(ft.m_new_tile, new_trackdir)) break;
rubidium@9814: 
rubidium@9814: 		tile = ft.m_new_tile;
rubidium@9814: 		trackdir = new_trackdir;
rubidium@9814: 
rubidium@9814: 		/* Depot tile? Can't continue. */
rubidium@9814: 		if (IsRailDepotTile(tile)) break;
rubidium@9814: 		/* Non-pbs signal? Reservation can't continue. */
rubidium@9814: 		if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) break;
rubidium@9814: 	}
rubidium@9814: 
rubidium@9814: 	return PBSTileInfo(tile, trackdir, false);
rubidium@9814: }
rubidium@9814: 
rubidium@10083: /**
rubidium@10083:  * Helper struct for finding the best matching vehicle on a specific track.
rubidium@10083:  */
rubidium@10083: struct FindTrainOnTrackInfo {
rubidium@10083: 	PBSTileInfo res; ///< Information about the track.
rubidium@10083: 	Vehicle *best;   ///< The currently "best" vehicle we have found.
rubidium@10083: 
rubidium@10083: 	/** Init the best location to NULL always! */
rubidium@10083: 	FindTrainOnTrackInfo() : best(NULL) {}
rubidium@10083: };
rubidium@10083: 
rubidium@10083: /** Callback for Has/FindVehicleOnPos to find a train on a specific track. */
frosch@9831: static Vehicle *FindTrainOnTrackEnum(Vehicle *v, void *data)
frosch@9831: {
rubidium@10083: 	FindTrainOnTrackInfo *info = (FindTrainOnTrackInfo *)data;
frosch@9831: 
rubidium@10083: 	if (v->type == VEH_TRAIN && !(v->vehstatus & VS_CRASHED) && HasBit((TrackBits)v->u.rail.track, TrackdirToTrack(info->res.trackdir))) {
rubidium@10083: 		v = v->First();
rubidium@10083: 
rubidium@10083: 		/* ALWAYS return the lowest ID (anti-desync!) */
rubidium@10083: 		if (info->best == NULL || v->index < info->best->index) info->best = v;
rubidium@10083: 		return v;
rubidium@10083: 	}
frosch@9831: 
frosch@9831: 	return NULL;
frosch@9831: }
frosch@9831: 
rubidium@9798: /**
rubidium@9798:  * Follow a train reservation to the last tile.
rubidium@9798:  *
rubidium@9798:  * @param v the vehicle
frosch@9831:  * @param train_on_res Is set to a train we might encounter
rubidium@9798:  * @returns The last tile of the reservation or the current train tile if no reservation present.
rubidium@9798:  */
rubidium@10083: PBSTileInfo FollowTrainReservation(const Vehicle *v, bool *train_on_res)
rubidium@9798: {
rubidium@9798: 	assert(v->type == VEH_TRAIN);
rubidium@9798: 
rubidium@9798: 	TileIndex tile = v->tile;
rubidium@9798: 	Trackdir  trackdir = GetVehicleTrackdir(v);
rubidium@9798: 
rubidium@9798: 	if (IsRailDepotTile(tile) && !GetRailDepotReservation(tile)) return PBSTileInfo(tile, trackdir, false);
rubidium@9798: 
rubidium@10083: 	FindTrainOnTrackInfo ftoti;
rubidium@10083: 	ftoti.res = FollowReservation(v->owner, GetRailTypeInfo(v->u.rail.railtype)->compatible_railtypes, tile, trackdir);
rubidium@10083: 	ftoti.res.okay = IsSafeWaitingPosition(v, ftoti.res.tile, ftoti.res.trackdir, true, _settings_game.pf.forbid_90_deg);
rubidium@10083: 	if (train_on_res != NULL) *train_on_res = HasVehicleOnPos(ftoti.res.tile, &ftoti, FindTrainOnTrackEnum);
rubidium@10083: 	return ftoti.res;
rubidium@9814: }
rubidium@9798: 
rubidium@9814: /**
rubidium@9814:  * Find the train which has reserved a specific path.
rubidium@9814:  *
rubidium@9814:  * @param tile A tile on the path.
rubidium@9814:  * @param track A reserved track on the tile.
rubidium@9814:  * @return The vehicle holding the reservation or NULL if the path is stray.
rubidium@9814:  */
rubidium@9814: Vehicle *GetTrainForReservation(TileIndex tile, Track track)
rubidium@9814: {
rubidium@9814: 	assert(HasReservedTracks(tile, TrackToTrackBits(track)));
rubidium@9814: 	Trackdir  trackdir = TrackToTrackdir(track);
rubidium@9814: 
rubidium@9814: 	RailTypes rts = GetRailTypeInfo(GetTileRailType(tile))->compatible_railtypes;
rubidium@9814: 
rubidium@9814: 	/* Follow the path from tile to both ends, one of the end tiles should
rubidium@9814: 	 * have a train on it. We need FollowReservation to ignore one-way signals
rubidium@9814: 	 * here, as one of the two search directions will be the "wrong" way. */
rubidium@9814: 	for (int i = 0; i < 2; ++i, trackdir = ReverseTrackdir(trackdir)) {
rubidium@10083: 		FindTrainOnTrackInfo ftoti;
rubidium@10083: 		ftoti.res = FollowReservation(GetTileOwner(tile), rts, tile, trackdir, true);
rubidium@9814: 
rubidium@10083: 		FindVehicleOnPos(ftoti.res.tile, &ftoti, FindTrainOnTrackEnum);
rubidium@10083: 		if (ftoti.best != NULL) return ftoti.best;
rubidium@9814: 
rubidium@9814: 		/* Special case for stations: check the whole platform for a vehicle. */
rubidium@10083: 		if (IsRailwayStationTile(ftoti.res.tile)) {
rubidium@10083: 			TileIndexDiff diff = TileOffsByDiagDir(TrackdirToExitdir(ReverseTrackdir(ftoti.res.trackdir)));
rubidium@10083: 			for (TileIndex st_tile = ftoti.res.tile + diff; IsCompatibleTrainStationTile(st_tile, ftoti.res.tile); st_tile += diff) {
rubidium@10083: 				FindVehicleOnPos(st_tile, &ftoti, FindTrainOnTrackEnum);
rubidium@10083: 				if (ftoti.best != NULL) return ftoti.best;
rubidium@9814: 			}
rubidium@9814: 		}
rubidium@9814: 
rubidium@9814: 		/* Special case for bridges/tunnels: check the other end as well. */
rubidium@10083: 		if (IsTileType(ftoti.res.tile, MP_TUNNELBRIDGE)) {
rubidium@10083: 			FindVehicleOnPos(GetOtherTunnelBridgeEnd(ftoti.res.tile), &ftoti, FindTrainOnTrackEnum);
rubidium@10083: 			if (ftoti.best != NULL) return ftoti.best;
rubidium@9814: 		}
rubidium@9798: 	}
rubidium@9798: 
rubidium@9814: 	return NULL;
rubidium@9798: }
rubidium@9798: 
rubidium@9798: /**
rubidium@9798:  * Determine whether a certain track on a tile is a safe position to end a path.
rubidium@9798:  *
rubidium@9798:  * @param v the vehicle to test for
rubidium@9798:  * @param tile The tile
rubidium@9798:  * @param trackdir The trackdir to test
rubidium@9798:  * @param include_line_end Should end-of-line tiles be considered safe?
rubidium@9798:  * @param forbid_90def Don't allow trains to make 90 degree turns
rubidium@9798:  * @return True if it is a safe position
rubidium@9798:  */
rubidium@9798: bool IsSafeWaitingPosition(const Vehicle *v, TileIndex tile, Trackdir trackdir, bool include_line_end, bool forbid_90deg)
rubidium@9798: {
rubidium@9798: 	if (IsRailDepotTile(tile)) return true;
rubidium@9798: 
rubidium@9798: 	if (IsTileType(tile, MP_RAILWAY)) {
rubidium@9798: 		/* For non-pbs signals, stop on the signal tile. */
rubidium@9798: 		if (HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) return true;
rubidium@9798: 	}
rubidium@9798: 
rubidium@9798: 	/* Check next tile. For perfomance reasons, we check for 90 degree turns ourself. */
rubidium@9798: 	CFollowTrackRail ft(v, GetRailTypeInfo(v->u.rail.railtype)->compatible_railtypes);
rubidium@9798: 
rubidium@9798: 	/* End of track? */
rubidium@9798: 	if (!ft.Follow(tile, trackdir)) {
rubidium@9798: 		/* Last tile of a terminus station is a safe position. */
rubidium@9798: 		if (include_line_end) return true;
rubidium@9798: 	}
rubidium@9798: 
rubidium@9798: 	/* Check for reachable tracks. */
rubidium@9798: 	ft.m_new_td_bits &= DiagdirReachesTrackdirs(ft.m_exitdir);
michi_cc@10210: 	if (forbid_90deg) ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(trackdir);
rubidium@9798: 	if (ft.m_new_td_bits == TRACKDIR_BIT_NONE) return include_line_end;
rubidium@9798: 
rubidium@9798: 	if (ft.m_new_td_bits != TRACKDIR_BIT_NONE && KillFirstBit(ft.m_new_td_bits) == TRACKDIR_BIT_NONE) {
rubidium@9798: 		/* PBS signal on next trackdir? Safe position. */
rubidium@9798: 		if (HasPbsSignalOnTrackdir(ft.m_new_tile, FindFirstTrackdir(ft.m_new_td_bits))) return true;
rubidium@9798: 	}
rubidium@9798: 
rubidium@9798: 	return false;
rubidium@9798: }
rubidium@9798: 
rubidium@9798: /**
rubidium@9798:  * Check if a safe position is free.
rubidium@9798:  *
rubidium@9798:  * @param v the vehicle to test for
rubidium@9798:  * @param tile The tile
rubidium@9798:  * @param trackdir The trackdir to test
rubidium@9798:  * @param forbid_90def Don't allow trains to make 90 degree turns
rubidium@9798:  * @return True if the position is free
rubidium@9798:  */
rubidium@9798: bool IsWaitingPositionFree(const Vehicle *v, TileIndex tile, Trackdir trackdir, bool forbid_90deg)
rubidium@9798: {
rubidium@9798: 	Track     track = TrackdirToTrack(trackdir);
rubidium@9798: 	TrackBits reserved = GetReservedTrackbits(tile);
rubidium@9798: 
rubidium@9798: 	/* Tile reserved? Can never be a free waiting position. */
rubidium@9798: 	if (TrackOverlapsTracks(reserved, track)) return false;
rubidium@9798: 
rubidium@9798: 	/* Not reserved and depot or not a pbs signal -> free. */
rubidium@9798: 	if (IsRailDepotTile(tile)) return true;
rubidium@9798: 	if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir) && !IsPbsSignal(GetSignalType(tile, track))) return true;
rubidium@9798: 
rubidium@9798: 	/* Check the next tile, if it's a PBS signal, it has to be free as well. */
rubidium@9798: 	CFollowTrackRail ft(v, GetRailTypeInfo(v->u.rail.railtype)->compatible_railtypes);
rubidium@9798: 
rubidium@9798: 	if (!ft.Follow(tile, trackdir)) return true;
rubidium@9798: 
rubidium@9798: 	/* Check for reachable tracks. */
rubidium@9798: 	ft.m_new_td_bits &= DiagdirReachesTrackdirs(ft.m_exitdir);
rubidium@9798: 	if (forbid_90deg) ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(trackdir);
rubidium@9798: 
rubidium@9798: 	return !HasReservedTracks(ft.m_new_tile, TrackdirBitsToTrackBits(ft.m_new_td_bits));
rubidium@9798: }