/**

 * Extend a train path as far as possible. Stops on encountering a safe tile,

 * another reservation or a track choice.

 * @return INVALID_TILE indicates that the reservation failed.

 */

static PBSTileInfo ExtendTrainReservation(const Train *v, TrackBits *new_tracks, DiagDirection *enterdir)

{

	PBSTileInfo origin = FollowTrainReservation(v);

	CFollowTrackRail ft(v);

	TileIndex tile = origin.tile;

	Trackdir  cur_td = origin.trackdir;

	while (ft.Follow(tile, cur_td)) {

		if (KillFirstBit(ft.m_new_td_bits) == TRACKDIR_BIT_NONE) {

			/* Possible signal tile. */

			if (HasOnewaySignalBlockingTrackdir(ft.m_new_tile, FindFirstTrackdir(ft.m_new_td_bits))) break;

		}

		if (_settings_game.pf.forbid_90_deg) {

			ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(ft.m_old_td);

			if (ft.m_new_td_bits == TRACKDIR_BIT_NONE) break;

		}

		/* Station, depot or waypoint are a possible target. */

		bool target_seen = ft.m_is_station || (IsTileType(ft.m_new_tile, MP_RAILWAY) && !IsPlainRail(ft.m_new_tile));

		if (target_seen || KillFirstBit(ft.m_new_td_bits) != TRACKDIR_BIT_NONE) {

			/* Choice found or possible target encountered.

			 * On finding a possible target, we need to stop and let the pathfinder handle the

			 * remaining path. This is because we don't know if this target is in one of our

			 * orders, so we might cause pathfinding to fail later on if we find a choice.

			 * This failure would cause a bogous call to TryReserveSafePath which might reserve

			 * a wrong path not leading to our next destination. */

			if (HasReservedTracks(ft.m_new_tile, TrackdirBitsToTrackBits(TrackdirReachesTrackdirs(ft.m_old_td)))) break;

			/* If we did skip some tiles, backtrack to the first skipped tile so the pathfinder

			 * actually starts its search at the first unreserved tile. */

			if (ft.m_tiles_skipped != 0) ft.m_new_tile -= TileOffsByDiagDir(ft.m_exitdir) * ft.m_tiles_skipped;

			/* Choice found, path valid but not okay. Save info about the choice tile as well. */

			if (new_tracks) *new_tracks = TrackdirBitsToTrackBits(ft.m_new_td_bits);

			if (enterdir) *enterdir = ft.m_exitdir;

			return PBSTileInfo(ft.m_new_tile, ft.m_old_td, false);

		}

		tile = ft.m_new_tile;

		cur_td = FindFirstTrackdir(ft.m_new_td_bits);

		if (IsSafeWaitingPosition(v, tile, cur_td, true, _settings_game.pf.forbid_90_deg)) {

			bool wp_free = IsWaitingPositionFree(v, tile, cur_td, _settings_game.pf.forbid_90_deg);

			if (!(wp_free && TryReserveRailTrack(tile, TrackdirToTrack(cur_td)))) break;

			/* Safe position is all good, path valid and okay. */

			return PBSTileInfo(tile, cur_td, true);

		}

		if (!TryReserveRailTrack(tile, TrackdirToTrack(cur_td))) break;

	}

	if (ft.m_err == CFollowTrackRail::EC_OWNER || ft.m_err == CFollowTrackRail::EC_NO_WAY) {

		/* End of line, path valid and okay. */

		return PBSTileInfo(ft.m_old_tile, ft.m_old_td, true);

	}

	/* Sorry, can't reserve path, back out. */

	tile = origin.tile;

	cur_td = origin.trackdir;

	TileIndex stopped = ft.m_old_tile;

	Trackdir  stopped_td = ft.m_old_td;

	while (tile != stopped || cur_td != stopped_td) {

		if (!ft.Follow(tile, cur_td)) break;

		if (_settings_game.pf.forbid_90_deg) {

			ft.m_new_td_bits &= ~TrackdirCrossesTrackdirs(ft.m_old_td);

			assert(ft.m_new_td_bits != TRACKDIR_BIT_NONE);

		}

		assert(KillFirstBit(ft.m_new_td_bits) == TRACKDIR_BIT_NONE);

		tile = ft.m_new_tile;

		cur_td = FindFirstTrackdir(ft.m_new_td_bits);

		UnreserveRailTrack(tile, TrackdirToTrack(cur_td));

	}

	/* Path invalid. */

	return PBSTileInfo();

}

/**

 * Try to reserve any path to a safe tile, ignoring the vehicle's destination.

 * Safe tiles are tiles in front of a signal, depots and station tiles at end of line.

 *

 * @param v The vehicle.

 * @param tile The tile the search should start from.

 * @param td The trackdir the search should start from.

 * @param override_railtype Whether all physically compatible railtypes should be followed.

 * @return True if a path to a safe stopping tile could be reserved.

 */

static bool TryReserveSafeTrack(const Train *v, TileIndex tile, Trackdir td, bool override_tailtype)

{

	switch (_settings_game.pf.pathfinder_for_trains) {

		case VPF_NPF: return NPFTrainFindNearestSafeTile(v, tile, td, override_tailtype);

		case VPF_YAPF: return YapfTrainFindNearestSafeTile(v, tile, td, override_tailtype);

		default: NOT_REACHED();

	}

}

/** This class will save the current order of a vehicle and restore it on destruction. */

class VehicleOrderSaver

{

private:

	Vehicle        *v;

	Order          old_order;

	TileIndex      old_dest_tile;

	StationID      old_last_station_visited;

	VehicleOrderID index;

public:

	VehicleOrderSaver(Vehicle *_v) :

		v(_v),

		old_order(_v->current_order),

		old_dest_tile(_v->dest_tile),

		old_last_station_visited(_v->last_station_visited),

		index(_v->cur_order_index)

	{

	}

	~VehicleOrderSaver()

	{

		this->v->current_order = this->old_order;

		this->v->dest_tile = this->old_dest_tile;

		this->v->last_station_visited = this->old_last_station_visited;

	}

	/**

	 * Set the current vehicle order to the next order in the order list.

	 * @param skip_first Shall the first (i.e. active) order be skipped?

	 * @return True if a suitable next order could be found.

	 */

	bool SwitchToNextOrder(bool skip_first)

	{

		if (this->v->GetNumOrders() == 0) return false;

		if (skip_first) ++this->index;

		int conditional_depth = 0;

		do {

			/* Wrap around. */

			if (this->index >= this->v->GetNumOrders()) this->index = 0;

			Order *order = this->v->GetOrder(this->index);

			assert(order != NULL);

			switch (order->GetType()) {

				case OT_GOTO_DEPOT:

					/* Skip service in depot orders when the train doesn't need service. */

					if ((order->GetDepotOrderType() & ODTFB_SERVICE) && !this->v->NeedsServicing()) break;

				case OT_GOTO_STATION:

				case OT_GOTO_WAYPOINT:

					this->v->current_order = *order;

					UpdateOrderDest(this->v, order);

					return true;

				case OT_CONDITIONAL: {

					if (conditional_depth > this->v->GetNumOrders()) return false;

					VehicleOrderID next = ProcessConditionalOrder(order, this->v);

					if (next != INVALID_VEH_ORDER_ID) {

						conditional_depth++;

						this->index = next;

						/* Don't increment next, so no break here. */

						continue;

					}

					break;

				}

				default:

					break;

			}

			/* Don't increment inside the while because otherwise conditional

			 * orders can lead to an infinite loop. */

			++this->index;

		} while (this->index != this->v->cur_order_index);

		return false;

	}

};

/* choose a track */

static Track ChooseTrainTrack(Train *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool force_res, bool *got_reservation, bool mark_stuck)

{

	Track best_track = INVALID_TRACK;

	bool do_track_reservation = _settings_game.pf.reserve_paths || force_res;

	bool changed_signal = false;

	assert((tracks & ~TRACK_BIT_MASK) == 0);

	if (got_reservation != NULL) *got_reservation = false;

	/* Don't use tracks here as the setting to forbid 90 deg turns might have been switched between reservation and now. */

	TrackBits res_tracks = (TrackBits)(GetReservedTrackbits(tile) & DiagdirReachesTracks(enterdir));

	/* Do we have a suitable reserved track? */

	if (res_tracks != TRACK_BIT_NONE) return FindFirstTrack(res_tracks);

	/* Quick return in case only one possible track is available */

	if (KillFirstBit(tracks) == TRACK_BIT_NONE) {

		Track track = FindFirstTrack(tracks);

		/* We need to check for signals only here, as a junction tile can't have signals. */

		if (track != INVALID_TRACK && HasPbsSignalOnTrackdir(tile, TrackEnterdirToTrackdir(track, enterdir))) {

			do_track_reservation = true;

			changed_signal = true;

			SetSignalStateByTrackdir(tile, TrackEnterdirToTrackdir(track, enterdir), SIGNAL_STATE_GREEN);

		} else if (!do_track_reservation) {

			return track;

		}

		best_track = track;

	}

	PBSTileInfo   res_dest(tile, INVALID_TRACKDIR, false);

	DiagDirection dest_enterdir = enterdir;

	if (do_track_reservation) {

		/* Check if the train needs service here, so it has a chance to always find a depot.

		 * Also check if the current order is a service order so we don't reserve a path to

		 * the destination but instead to the next one if service isn't needed. */

		CheckIfTrainNeedsService(v);

		if (v->current_order.IsType(OT_DUMMY) || v->current_order.IsType(OT_CONDITIONAL) || v->current_order.IsType(OT_GOTO_DEPOT)) ProcessOrders(v);

		res_dest = ExtendTrainReservation(v, &tracks, &dest_enterdir);

		if (res_dest.tile == INVALID_TILE) {

			/* Reservation failed? */

			if (mark_stuck) MarkTrainAsStuck(v);

			if (changed_signal) SetSignalStateByTrackdir(tile, TrackEnterdirToTrackdir(best_track, enterdir), SIGNAL_STATE_RED);

			return FindFirstTrack(tracks);

		}

	}

	/* Save the current train order. The destructor will restore the old order on function exit. */

	VehicleOrderSaver orders(v);

	/* If the current tile is the destination of the current order and

	 * a reservation was requested, advance to the next order.

	 * Don't advance on a depot order as depots are always safe end points

	 * for a path and no look-ahead is necessary. This also avoids a

	 * problem with depot orders not part of the order list when the

	 * order list itself is empty. */

	if (v->current_order.IsType(OT_LEAVESTATION)) {

		orders.SwitchToNextOrder(false);

	} else if (v->current_order.IsType(OT_LOADING) || (!v->current_order.IsType(OT_GOTO_DEPOT) && (

			v->current_order.IsType(OT_GOTO_STATION) ?

			IsRailStationTile(v->tile) && v->current_order.GetDestination() == GetStationIndex(v->tile) :

			v->tile == v->dest_tile))) {

		orders.SwitchToNextOrder(true);

	}

	if (res_dest.tile != INVALID_TILE && !res_dest.okay) {

		/* Pathfinders are able to tell that route was only 'guessed'. */

		bool      path_not_found = false;

		TileIndex new_tile = res_dest.tile;

		Track next_track = DoTrainPathfind(v, new_tile, dest_enterdir, tracks, &path_not_found, do_track_reservation, &res_dest);

		if (new_tile == tile) best_track = next_track;

		/* handle "path not found" state */

		if (path_not_found) {

			/* PF didn't find the route */

			if (!HasBit(v->flags, VRF_NO_PATH_TO_DESTINATION)) {

				/* it is first time the problem occurred, set the "path not found" flag */

				SetBit(v->flags, VRF_NO_PATH_TO_DESTINATION);

				/* and notify user about the event */

				AI::NewEvent(v->owner, new AIEventVehicleLost(v->index));

				if (_settings_client.gui.lost_train_warn && v->owner == _local_company) {

					SetDParam(0, v->index);

					AddVehicleNewsItem(

						STR_NEWS_TRAIN_IS_LOST,

						NS_ADVICE,

						v->index

					);

				}

			}

		} else {

			/* route found, is the train marked with "path not found" flag? */

			if (HasBit(v->flags, VRF_NO_PATH_TO_DESTINATION)) {

				/* clear the flag as the PF's problem was solved */

				ClrBit(v->flags, VRF_NO_PATH_TO_DESTINATION);

				/* can we also delete the "News" item somehow? */

			}

		}

	}

	/* No track reservation requested -> finished. */

	if (!do_track_reservation) return best_track;

	/* A path was found, but could not be reserved. */

	if (res_dest.tile != INVALID_TILE && !res_dest.okay) {

		if (mark_stuck) MarkTrainAsStuck(v);

		FreeTrainTrackReservation(v);

		return best_track;

	}

	/* No possible reservation target found, we are probably lost. */

	if (res_dest.tile == INVALID_TILE) {

		/* Try to find any safe destination. */

		PBSTileInfo origin = FollowTrainReservation(v);

		if (TryReserveSafeTrack(v, origin.tile, origin.trackdir, false)) {

			TrackBits res = GetReservedTrackbits(tile) & DiagdirReachesTracks(enterdir);

			best_track = FindFirstTrack(res);

			TryReserveRailTrack(v->tile, TrackdirToTrack(v->GetVehicleTrackdir()));

			if (got_reservation != NULL) *got_reservation = true;

			if (changed_signal) MarkTileDirtyByTile(tile);

		} else {

			FreeTrainTrackReservation(v);

			if (mark_stuck) MarkTrainAsStuck(v);

		}

		return best_track;

	}

	if (got_reservation != NULL) *got_reservation = true;

	/* Reservation target found and free, check if it is safe. */

	while (!IsSafeWaitingPosition(v, res_dest.tile, res_dest.trackdir, true, _settings_game.pf.forbid_90_deg)) {

		/* Extend reservation until we have found a safe position. */

		DiagDirection exitdir = TrackdirToExitdir(res_dest.trackdir);

		TileIndex     next_tile = TileAddByDiagDir(res_dest.tile, exitdir);

		TrackBits     reachable = TrackdirBitsToTrackBits((TrackdirBits)(GetTileTrackStatus(next_tile, TRANSPORT_RAIL, 0))) & DiagdirReachesTracks(exitdir);

		if (_settings_game.pf.forbid_90_deg) {

			reachable &= ~TrackCrossesTracks(TrackdirToTrack(res_dest.trackdir));

		}

		/* Get next order with destination. */

		if (orders.SwitchToNextOrder(true)) {

			PBSTileInfo cur_dest;

			DoTrainPathfind(v, next_tile, exitdir, reachable, NULL, true, &cur_dest);

			if (cur_dest.tile != INVALID_TILE) {

				res_dest = cur_dest;

				if (res_dest.okay) continue;

				/* Path found, but could not be reserved. */

				FreeTrainTrackReservation(v);

				if (mark_stuck) MarkTrainAsStuck(v);

				if (got_reservation != NULL) *got_reservation = false;

				changed_signal = false;

				break;

			}

		}

		/* No order or no safe position found, try any position. */

		if (!TryReserveSafeTrack(v, res_dest.tile, res_dest.trackdir, true)) {

			FreeTrainTrackReservation(v);

			if (mark_stuck) MarkTrainAsStuck(v);

			if (got_reservation != NULL) *got_reservation = false;

			changed_signal = false;

		}

		break;

	}

	TryReserveRailTrack(v->tile, TrackdirToTrack(v->GetVehicleTrackdir()));

	if (changed_signal) MarkTileDirtyByTile(tile);

	return best_track;

}

/**

 * Try to reserve a path to a safe position.

 *

 * @param v The vehicle

 * @param mark_as_stuck Should the train be marked as stuck on a failed reservation?

 * @param first_tile_okay True if no path should be reserved if the current tile is a safe position.

 * @return True if a path could be reserved.

 */

bool TryPathReserve(Train *v, bool mark_as_stuck, bool first_tile_okay)

{

	assert(v->IsFrontEngine());

	/* We have to handle depots specially as the track follower won't look

	 * at the depot tile itself but starts from the next tile. If we are still

	 * inside the depot, a depot reservation can never be ours. */

	if (v->track == TRACK_BIT_DEPOT) {

		if (HasDepotReservation(v->tile)) {

			if (mark_as_stuck) MarkTrainAsStuck(v);

			return false;

		} else {

			/* Depot not reserved, but the next tile might be. */

			TileIndex next_tile = TileAddByDiagDir(v->tile, GetRailDepotDirection(v->tile));

			if (HasReservedTracks(next_tile, DiagdirReachesTracks(GetRailDepotDirection(v->tile)))) return false;

		}

	}

	Vehicle *other_train = NULL;

	PBSTileInfo origin = FollowTrainReservation(v, &other_train);

	/* The path we are driving on is alread blocked by some other train.

	 * This can only happen in certain situations when mixing path and

	 * block signals or when changing tracks and/or signals.

	 * Exit here as doing any further reservations will probably just

	 * make matters worse. */

	if (other_train != NULL && other_train->index != v->index) {

		if (mark_as_stuck) MarkTrainAsStuck(v);

		return false;

	}

	/* If we have a reserved path and the path ends at a safe tile, we are finished already. */

	if (origin.okay && (v->tile != origin.tile || first_tile_okay)) {

		/* Can't be stuck then. */

		if (HasBit(v->flags, VRF_TRAIN_STUCK)) SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, VVW_WIDGET_START_STOP_VEH);

		ClrBit(v->flags, VRF_TRAIN_STUCK);

		return true;

	}

	/* If we are in a depot, tentativly reserve the depot. */

	if (v->track == TRACK_BIT_DEPOT) {

		SetDepotReservation(v->tile, true);

		if (_settings_client.gui.show_track_reservation) MarkTileDirtyByTile(v->tile);

	}

	DiagDirection exitdir = TrackdirToExitdir(origin.trackdir);

	TileIndex     new_tile = TileAddByDiagDir(origin.tile, exitdir);

	TrackBits     reachable = TrackdirBitsToTrackBits(TrackStatusToTrackdirBits(GetTileTrackStatus(new_tile, TRANSPORT_RAIL, 0)) & DiagdirReachesTrackdirs(exitdir));

	if (_settings_game.pf.forbid_90_deg) reachable &= ~TrackCrossesTracks(TrackdirToTrack(origin.trackdir));

	bool res_made = false;

	ChooseTrainTrack(v, new_tile, exitdir, reachable, true, &res_made, mark_as_stuck);

	if (!res_made) {

		/* Free the depot reservation as well. */

		if (v->track == TRACK_BIT_DEPOT) SetDepotReservation(v->tile, false);

		return false;

	}

	if (HasBit(v->flags, VRF_TRAIN_STUCK)) {

		v->wait_counter = 0;

		SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, VVW_WIDGET_START_STOP_VEH);

	}

	ClrBit(v->flags, VRF_TRAIN_STUCK);

	return true;

}

static bool CheckReverseTrain(const Train *v)

{

	if (_settings_game.difficulty.line_reverse_mode != 0 ||

			v->track == TRACK_BIT_DEPOT || v->track == TRACK_BIT_WORMHOLE ||

			!(v->direction & 1)) {

		return false;

	}

	assert(v->track != TRACK_BIT_NONE);

	switch (_settings_game.pf.pathfinder_for_trains) {

		case VPF_NPF: return NPFTrainCheckReverse(v);

		case VPF_YAPF: return YapfTrainCheckReverse(v);

		default: NOT_REACHED();

	}

}

TileIndex Train::GetOrderStationLocation(StationID station)

{

	if (station == this->last_station_visited) this->last_station_visited = INVALID_STATION;

	const Station *st = Station::Get(station);

	if (!(st->facilities & FACIL_TRAIN)) {

		/* The destination station has no trainstation tiles. */

		this->IncrementOrderIndex();

		return 0;

	}

	return st->xy;

}

void Train::MarkDirty()

{

	Vehicle *v = this;

	do {

		v->UpdateViewport(false, false);

	} while ((v = v->Next()) != NULL);

	/* need to update acceleration and cached values since the goods on the train changed. */

	TrainCargoChanged(this);

	UpdateTrainAcceleration(this);

}

/**

 * This function looks at the vehicle and updates it's speed (cur_speed

 * and subspeed) variables. Furthermore, it returns the distance that

 * the train can drive this tick. This distance is expressed as 256 * n,

 * where n is the number of straight (long) tracks the train can

 * traverse. This means that moving along a straight track costs 256

 * "speed" and a diagonal track costs 192 "speed".

 * @param v The vehicle to update the speed of.

 * @return distance to drive.

 */

static int UpdateTrainSpeed(Train *v)

{

	uint accel;

	if ((v->vehstatus & VS_STOPPED) || HasBit(v->flags, VRF_REVERSING) || HasBit(v->flags, VRF_TRAIN_STUCK)) {

		switch (_settings_game.vehicle.train_acceleration_model) {

			default: NOT_REACHED();

			case TAM_ORIGINAL:  accel = v->acceleration * -4; break;

			case TAM_REALISTIC: accel = GetTrainAcceleration(v, AM_BRAKE); break;

		}

	} else {

		switch (_settings_game.vehicle.train_acceleration_model) {

			default: NOT_REACHED();

			case TAM_ORIGINAL:  accel = v->acceleration * 2; break;

			case TAM_REALISTIC: accel = GetTrainAcceleration(v, AM_ACCEL); break;

		}

	}

	uint spd = v->subspeed + accel;

	v->subspeed = (byte)spd;

	{

		int tempmax = v->max_speed;

		if (v->cur_speed > v->max_speed)

			tempmax = v->cur_speed - (v->cur_speed / 10) - 1;

		v->cur_speed = spd = Clamp(v->cur_speed + ((int)spd >> 8), 0, tempmax);

	}

	/* Scale speed by 3/4. Previously this was only done when the train was

	 * facing diagonally and would apply to however many moves the train made

	 * regardless the of direction actually moved in. Now it is always scaled,

	 * 256 spd is used to go straight and 192 is used to go diagonally

	 * (3/4 of 256). This results in the same effect, but without the error the

	 * previous method caused.

	 *

	 * The scaling is done in this direction and not by multiplying the amount

	 * to be subtracted by 4/3 so that the leftover speed can be saved in a

	 * byte in v->progress.

	 */

	int scaled_spd = spd * 3 >> 2;

	scaled_spd += v->progress;

	v->progress = 0; // set later in TrainLocoHandler or TrainController

	return scaled_spd;

}

static void TrainEnterStation(Train *v, StationID station)

{

	v->last_station_visited = station;

	/* check if a train ever visited this station before */

	Station *st = Station::Get(station);

	if (!(st->had_vehicle_of_type & HVOT_TRAIN)) {

		st->had_vehicle_of_type |= HVOT_TRAIN;

		SetDParam(0, st->index);

		AddVehicleNewsItem(

			STR_NEWS_FIRST_TRAIN_ARRIVAL,

			v->owner == _local_company ? NS_ARRIVAL_COMPANY : NS_ARRIVAL_OTHER,

			v->index,

			st->index

		);

		AI::NewEvent(v->owner, new AIEventStationFirstVehicle(st->index, v->index));

	}

	v->BeginLoading();

	StationAnimationTrigger(st, v->tile, STAT_ANIM_TRAIN_ARRIVES);

}

static byte AfterSetTrainPos(Train *v, bool new_tile)

{

	byte old_z = v->z_pos;

	v->z_pos = GetSlopeZ(v->x_pos, v->y_pos);

	if (new_tile) {

		ClrBit(v->flags, VRF_GOINGUP);

		ClrBit(v->flags, VRF_GOINGDOWN);

		if (v->track == TRACK_BIT_X || v->track == TRACK_BIT_Y) {

			/* Any track that isn't TRACK_BIT_X or TRACK_BIT_Y cannot be sloped.

			 * To check whether the current tile is sloped, and in which

			 * direction it is sloped, we get the 'z' at the center of

			 * the tile (middle_z) and the edge of the tile (old_z),

			 * which we then can compare. */

			static const int HALF_TILE_SIZE = TILE_SIZE / 2;

			static const int INV_TILE_SIZE_MASK = ~(TILE_SIZE - 1);

			byte middle_z = GetSlopeZ((v->x_pos & INV_TILE_SIZE_MASK) | HALF_TILE_SIZE, (v->y_pos & INV_TILE_SIZE_MASK) | HALF_TILE_SIZE);

			if (middle_z != v->z_pos) {

				SetBit(v->flags, (middle_z > old_z) ? VRF_GOINGUP : VRF_GOINGDOWN);

			}

		}

	}

	VehicleMove(v, true);

	return old_z;

}

/* Check if the vehicle is compatible with the specified tile */

static inline bool CheckCompatibleRail(const Train *v, TileIndex tile)

{

	return

		IsTileOwner(tile, v->owner) && (

			!v->IsFrontEngine() ||

			HasBit(v->compatible_railtypes, GetRailType(tile))

		);

}

struct RailtypeSlowdownParams {

	byte small_turn, large_turn;

	byte z_up; // fraction to remove when moving up

	byte z_down; // fraction to remove when moving down

};

static const RailtypeSlowdownParams _railtype_slowdown[] = {

	/* normal accel */

	{256 / 4, 256 / 2, 256 / 4, 2}, ///< normal

	{256 / 4, 256 / 2, 256 / 4, 2}, ///< electrified

	{256 / 4, 256 / 2, 256 / 4, 2}, ///< monorail

	{0,       256 / 2, 256 / 4, 2}, ///< maglev

};

/** Modify the speed of the vehicle due to a change in altitude */

static inline void AffectSpeedByZChange(Train *v, byte old_z)

{

	if (old_z == v->z_pos || _settings_game.vehicle.train_acceleration_model != TAM_ORIGINAL) return;

	const RailtypeSlowdownParams *rsp = &_railtype_slowdown[v->railtype];

	if (old_z < v->z_pos) {

		v->cur_speed -= (v->cur_speed * rsp->z_up >> 8);

	} else {

		uint16 spd = v->cur_speed + rsp->z_down;

		if (spd <= v->max_speed) v->cur_speed = spd;

	}

}

static bool TrainMovedChangeSignals(TileIndex tile, DiagDirection dir)

{

	if (IsTileType(tile, MP_RAILWAY) &&

			GetRailTileType(tile) == RAIL_TILE_SIGNALS) {

		TrackdirBits tracks = TrackBitsToTrackdirBits(GetTrackBits(tile)) & DiagdirReachesTrackdirs(dir);

		Trackdir trackdir = FindFirstTrackdir(tracks);

		if (UpdateSignalsOnSegment(tile,  TrackdirToExitdir(trackdir), GetTileOwner(tile)) == SIGSEG_PBS && HasSignalOnTrackdir(tile, trackdir)) {

			/* A PBS block with a non-PBS signal facing us? */

			if (!IsPbsSignal(GetSignalType(tile, TrackdirToTrack(trackdir)))) return true;

		}

	}

	return false;

}

/**

 * Tries to reserve track under whole train consist

 */

void Train::ReserveTrackUnderConsist() const

{

	for (const Train *u = this; u != NULL; u = u->Next()) {

		switch (u->track) {

			case TRACK_BIT_WORMHOLE:

				TryReserveRailTrack(u->tile, DiagDirToDiagTrack(GetTunnelBridgeDirection(u->tile)));

				break;

			case TRACK_BIT_DEPOT:

				break;

			default:

				TryReserveRailTrack(u->tile, TrackBitsToTrack(u->track));

				break;

		}

	}

}

uint Train::Crash(bool flooded)

{

	uint pass = 0;

	if (this->IsFrontEngine()) {

		pass += 4; // driver

		/* Remove the reserved path in front of the train if it is not stuck.

		 * Also clear all reserved tracks the train is currently on. */

		if (!HasBit(this->flags, VRF_TRAIN_STUCK)) FreeTrainTrackReservation(this);

		for (const Train *v = this; v != NULL; v = v->Next()) {

			ClearPathReservation(v, v->tile, v->GetVehicleTrackdir());

			if (IsTileType(v->tile, MP_TUNNELBRIDGE)) {

				/* ClearPathReservation will not free the wormhole exit

				 * if the train has just entered the wormhole. */

				SetTunnelBridgeReservation(GetOtherTunnelBridgeEnd(v->tile), false);

			}

		}

		/* we may need to update crossing we were approaching,

		* but must be updated after the train has been marked crashed */

		TileIndex crossing = TrainApproachingCrossingTile(this);

		if (crossing != INVALID_TILE) UpdateLevelCrossing(crossing);

	}

	pass += Vehicle::Crash(flooded);

	this->crash_anim_pos = flooded ? 4000 : 1; // max 4440, disappear pretty fast when flooded

	return pass;

}

/**

 * Marks train as crashed and creates an AI event.

 * Doesn't do anything if the train is crashed already.

 * @param v first vehicle of chain

 * @return number of victims (including 2 drivers; zero if train was already crashed)

 */

static uint TrainCrashed(Train *v)

{

	uint num = 0;

	/* do not crash train twice */

	if (!(v->vehstatus & VS_CRASHED)) {

		num = v->Crash();

		AI::NewEvent(v->owner, new AIEventVehicleCrashed(v->index, v->tile, AIEventVehicleCrashed::CRASH_TRAIN));

	}

	/* Try to re-reserve track under already crashed train too.

	 * SetVehicleCrashed() clears the reservation! */

	v->ReserveTrackUnderConsist();

	return num;

}

struct TrainCollideChecker {

	Train *v; ///< vehicle we are testing for collision

	uint num; ///< number of victims if train collided

};

static Vehicle *FindTrainCollideEnum(Vehicle *v, void *data)

{

	TrainCollideChecker *tcc = (TrainCollideChecker*)data;

	/* not a train or in depot */

	if (v->type != VEH_TRAIN || Train::From(v)->track == TRACK_BIT_DEPOT) return NULL;

	/* get first vehicle now to make most usual checks faster */

	Train *coll = Train::From(v)->First();

	/* can't collide with own wagons */

	if (coll == tcc->v) return NULL;

	int x_diff = v->x_pos - tcc->v->x_pos;

	int y_diff = v->y_pos - tcc->v->y_pos;

	/* Do fast calculation to check whether trains are not in close vicinity

	 * and quickly reject trains distant enough for any collision.

	 * Differences are shifted by 7, mapping range [-7 .. 8] into [0 .. 15]

	 * Differences are then ORed and then we check for any higher bits */

	uint hash = (y_diff + 7) | (x_diff + 7);

	if (hash & ~15) return NULL;

	/* Slower check using multiplication */

	if (x_diff * x_diff + y_diff * y_diff > 25) return NULL;