/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */

/** @file yapf_ship.cpp Implementation of YAPF for ships. */

#include "../../stdafx.h"
#include "../../ship.h"
#include "../../vehicle_func.h"

#include "yapf.hpp"
#include "yapf_node_ship.hpp"
#include "yapf_ship_regions.h"
#include "../water_regions.h"

#include "../../safeguards.h"

constexpr int NUMBER_OR_WATER_REGIONS_LOOKAHEAD = 4;
constexpr int MAX_SHIP_PF_NODES = (NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1) * WATER_REGION_NUMBER_OF_TILES * 4; ///< 4 possible exit dirs per tile.

constexpr int SHIP_LOST_PATH_LENGTH = 8; ///< The length of the (aimless) path assigned when a ship is lost.

template <class Types>
class CYapfDestinationTileWaterT {
public:
	typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class).
	typedef typename Types::TrackFollower TrackFollower;
	typedef typename Types::NodeList::Item Node; ///< this will be our node type.
	typedef typename Node::Key Key; ///< key to hash tables.

protected:
	TileIndex dest_tile;
	TrackdirBits dest_trackdirs;
	StationID dest_station;

	bool has_intermediate_dest = false;
	TileIndex intermediate_dest_tile;
	WaterRegionPatchDesc intermediate_dest_region_patch;

public:
	void SetDestination(const Ship *v)
	{
		if (v->current_order.IsType(OT_GOTO_STATION)) {
			this->dest_station = v->current_order.GetDestination().ToStationID();
			this->dest_tile = CalcClosestStationTile(this->dest_station, v->tile, StationType::Dock);
			this->dest_trackdirs = INVALID_TRACKDIR_BIT;
		} else {
			this->dest_station = StationID::Invalid();
			this->dest_tile = v->dest_tile == INVALID_TILE ? TileIndex{} : v->dest_tile;
			this->dest_trackdirs = GetTileTrackStatus(this->dest_tile, TransportType::Water, RoadTramType::Invalid).trackdirs;
		}
	}

	void SetIntermediateDestination(const WaterRegionPatchDesc &water_region_patch)
	{
		this->has_intermediate_dest = true;
		this->intermediate_dest_tile = GetWaterRegionCenterTile(water_region_patch);
		this->intermediate_dest_region_patch = water_region_patch;
	}

protected:
	/** @copydoc CYapfBaseT::Yapf */
	inline Tpf& Yapf()
	{
		return *static_cast<Tpf*>(this);
	}

public:
	/** @copydoc CYapfBaseT::PfDetectDestinationFunc */
	inline bool PfDetectDestination(Node &n)
	{
		return this->PfDetectDestinationTile(n.GetTile(), n.GetTrackdir());
	}

	/** @copydoc CYapfBaseT::PfDetectDestinationTileFunc */
	inline bool PfDetectDestinationTile(TileIndex tile, Trackdir td)
	{
		if (this->has_intermediate_dest) {
			/* GetWaterRegionInfo is much faster than GetWaterRegionPatchInfo so we try that first. */
			if (GetWaterRegionInfo(tile) != this->intermediate_dest_region_patch) return false;
			return GetWaterRegionPatchInfo(tile) == this->intermediate_dest_region_patch;
		}

		if (this->dest_station != StationID::Invalid()) return IsDockingTile(tile) && IsShipDestinationTile(tile, this->dest_station);

		return tile == this->dest_tile && this->dest_trackdirs.Any(TrackdirToTrackdirBits(td));
	}

	/** @copydoc CYapfBaseT::PfCalcEstimateFunc */
	inline bool PfCalcEstimate(Node &n)
	{
		const TileIndex destination_tile = this->has_intermediate_dest ? this->intermediate_dest_tile : this->dest_tile;

		if (this->PfDetectDestination(n)) {
			n.estimate = n.cost;
			return true;
		}

		n.estimate = n.cost + OctileDistanceCost(n.GetTile(), n.GetTrackdir(), destination_tile);
		assert(n.estimate >= n.parent->estimate);
		return true;
	}
};

/** Node Follower module of YAPF for ships */
template <class Types>
class CYapfFollowShipT {
public:
	typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class).
	typedef typename Types::TrackFollower TrackFollower;
	typedef typename Types::NodeList::Item Node; ///< this will be our node type.
	typedef typename Node::Key Key; ///< key to hash tables.

protected:
	/** @copydoc CYapfBaseT::Yapf */
	inline Tpf &Yapf()
	{
		return *static_cast<Tpf*>(this);
	}

	std::vector<WaterRegionDesc> water_region_corridor;

public:
	/** @copydoc CYapfBaseT::PfFollowNodeFunc */
	inline void PfFollowNode(Node &old_node)
	{
		TrackFollower follower{Yapf().GetVehicle()};
		if (follower.Follow(old_node.key.tile, old_node.key.td)) {
			if (this->water_region_corridor.empty()
					|| std::ranges::find(this->water_region_corridor, GetWaterRegionInfo(follower.new_tile)) != this->water_region_corridor.end()) {
				Yapf().AddMultipleNodes(&old_node, follower);
			}
		}
	}

	/**
	 * Restricts the search by creating corridor or water regions through which the ship is allowed to travel.
	 * @param path The path to restrict the search by.
	 */
	inline void RestrictSearch(const std::vector<WaterRegionPatchDesc> &path)
	{
		this->water_region_corridor.clear();
		for (const WaterRegionPatchDesc &path_entry : path) this->water_region_corridor.push_back(path_entry);
	}

	/** @copydoc CYapfBaseT::TransportTypeCharFunc */
	inline char TransportTypeChar() const
	{
		return 'w';
	}

	/**
	 * Returns a random trackdir out of a set of trackdirs.
	 * @param trackdirs The possible track dirs.
	 * @return One of the possible track dirs.
	 */
	static Trackdir GetRandomTrackdir(TrackdirBits trackdirs)
	{
		return trackdirs.GetNthSetBit(RandomRange(trackdirs.Count())).value_or(Trackdir::Invalid);
	}

	/**
	 * Returns a random tile/trackdir that can be reached from the current tile/trackdir, or tile/Track::Invalid if none is available.
	 * @param v The ship to get the direction for.
	 * @param tile The start tile.
	 * @param dir the start direction.
	 * @return The next tile and a direction.
	 */
	static std::pair<TileIndex, Trackdir> GetRandomFollowUpTileTrackdir(const Ship *v, TileIndex tile, Trackdir dir)
	{
		TrackFollower follower{v};
		if (follower.Follow(tile, dir)) {
			TrackdirBits dirs = follower.new_td_bits;
			/* Exclude 90 degree turns unless there are no non-90 turns. */
			dirs.Reset(TrackdirCrossesTrackdirs(dir));
			if (dirs.None()) dirs = follower.new_td_bits;
			return { follower.new_tile, GetRandomTrackdir(dirs) };
		}
		return { follower.new_tile, Trackdir::Invalid };
	}

	/**
	 * Creates a random path, avoids 90 degree turns.
	 * @param v The ship to create the path for.
	 * @param[in,out] path_cache Cache of the path for the ship.
	 * @param path_length The length of the random path to create.
	 * @return The next track direction to take, or \c Trackdir::Invalid when there is no option.
	 */
	static Trackdir CreateRandomPath(const Ship *v, ShipPathCache &path_cache, int path_length)
	{
		std::pair<TileIndex, Trackdir> tile_dir = { v->tile, v->GetVehicleTrackdir()};
		for (int i = 0; i < path_length; ++i) {
			tile_dir = GetRandomFollowUpTileTrackdir(v, tile_dir.first, tile_dir.second);
			if (tile_dir.second == Trackdir::Invalid) break;
			path_cache.push_back(tile_dir.second);
		}

		if (path_cache.empty()) return Trackdir::Invalid;

		/* Reverse the path so we can take from the end. */
		std::reverse(std::begin(path_cache), std::end(path_cache));

		const Trackdir result = path_cache.back().trackdir;
		path_cache.pop_back();
		return result;
	}

	static Trackdir ChooseShipTrack(const Ship *v, TileIndex tile, TrackdirBits forward_dirs, TrackdirBits reverse_dirs,
		bool &path_found, ShipPathCache &path_cache, Trackdir &best_origin_dir)
	{
		const std::vector<WaterRegionPatchDesc> high_level_path = YapfShipFindWaterRegionPath(v, tile, NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1);
		if (high_level_path.empty()) {
			path_found = false;
			/* Make the ship move around aimlessly. This prevents repeated pathfinder calls and clearly indicates that the ship is lost. */
			return CreateRandomPath(v, path_cache, SHIP_LOST_PATH_LENGTH);
		}

		/* Try one time without restricting the search area, which generally results in better and more natural looking paths.
		 * However the pathfinder can hit the node limit in certain situations such as long aqueducts or maze-like terrain.
		 * If that happens we run the pathfinder again, but restricted only to the regions provided by the region pathfinder. */
		for (int attempt = 0; attempt < 2; ++attempt) {
			Tpf pf(MAX_SHIP_PF_NODES);

			/* Set origin and destination nodes */
			pf.SetOrigin(v->tile, forward_dirs | reverse_dirs);
			pf.SetDestination(v);
			const bool is_intermediate_destination = static_cast<int>(high_level_path.size()) >= NUMBER_OR_WATER_REGIONS_LOOKAHEAD + 1;
			if (is_intermediate_destination) pf.SetIntermediateDestination(high_level_path.back());

			/* Restrict the search area to prevent the low level pathfinder from expanding too many nodes. This can happen
			 * when the terrain is very "maze-like" or when the high level path "teleports" via a very long aqueduct. */
			if (attempt > 0) pf.RestrictSearch(high_level_path);

			/* Find best path. */
			path_found = pf.FindPath(v);
			Node *node = pf.GetBestNode();
			if (attempt == 0 && !path_found) continue; // Try again with restricted search area.

			/* Make the ship move around aimlessly. This prevents repeated pathfinder calls and clearly indicates that the ship is lost. */
			if (!path_found) return CreateRandomPath(v, path_cache, SHIP_LOST_PATH_LENGTH);

			/* Return only the path within the current water region if an intermediate destination was returned. If not, cache the entire path
			 * to the final destination tile. The low-level pathfinder might actually prefer a different docking tile in a nearby region. Without
			 * caching the full path the ship can get stuck in a loop. */
			const WaterRegionPatchDesc end_water_patch = GetWaterRegionPatchInfo(node->GetTile());
			assert(GetWaterRegionPatchInfo(tile) == high_level_path.front());
			const WaterRegionPatchDesc start_water_patch = high_level_path.front();
			while (node->parent) {
				const WaterRegionPatchDesc node_water_patch = GetWaterRegionPatchInfo(node->GetTile());

				const bool node_water_patch_on_high_level_path = std::ranges::find(high_level_path, node_water_patch) != high_level_path.end();
				const bool add_full_path = !is_intermediate_destination && node_water_patch != end_water_patch;

				/* The cached path must always lead to a region patch that's on the high level path.
				 * This is what can happen when that's not the case https://github.com/OpenTTD/OpenTTD/issues/12176. */
				if (add_full_path || !node_water_patch_on_high_level_path || node_water_patch == start_water_patch) {
					path_cache.push_back(node->GetTrackdir());
				} else {
					path_cache.clear();
				}
				node = node->parent;
			}
			assert(node->GetTile() == v->tile);

			/* Return Trackdir::Invalid to trigger a ship reversal if that is the best option. */
			best_origin_dir = node->GetTrackdir();
			if (!TrackdirToTrackdirBits(best_origin_dir).Any(forward_dirs)) {
				path_cache.clear();
				return Trackdir::Invalid;
			}

			/* A empty path means we are already at the destination. The pathfinder shouldn't have been called at all.
			 * Return a random reachable trackdir to hopefully nudge the ship out of this strange situation. */
			if (path_cache.empty()) return CreateRandomPath(v, path_cache, 1);

			/* Take out the last trackdir as the result. */
			const Trackdir result = path_cache.back().trackdir;
			path_cache.pop_back();

			/* Clear path cache when in final water region patch. This is to allow ships to spread over different docking tiles dynamically. */
			if (start_water_patch == end_water_patch) path_cache.clear();

			return result;
		}

		NOT_REACHED();
	}

	/**
	 * Check whether a ship should reverse to reach its destination.
	 * Called when leaving depot.
	 * @param v Ship.
	 * @param trackdir [out] the best of all possible reversed trackdirs.
	 * @return true if the reverse direction is better.
	 */
	static bool CheckShipReverse(const Ship *v, Trackdir *trackdir)
	{
		bool path_found = false;
		ShipPathCache dummy_cache;
		Trackdir best_origin_dir = Trackdir::Invalid;

		if (trackdir == nullptr) {
			/* The normal case, typically called when ships leave a dock. */
			const Trackdir reverse_dir = ReverseTrackdir(v->GetVehicleTrackdir());
			const TrackdirBits forward_dirs = TrackdirToTrackdirBits(v->GetVehicleTrackdir());
			const TrackdirBits reverse_dirs = TrackdirToTrackdirBits(reverse_dir);
			(void)ChooseShipTrack(v, v->tile, forward_dirs, reverse_dirs, path_found, dummy_cache, best_origin_dir);
			return path_found && best_origin_dir == reverse_dir;
		} else {
			/* This gets called when a ship suddenly can't move forward, e.g. due to terraforming. */
			const DiagDirection entry = ReverseDiagDir(VehicleExitDir(v->direction, v->state));
			const TrackdirBits reverse_dirs = DiagdirReachesTrackdirs(entry) & GetTileTrackStatus(v->tile, TransportType::Water, RoadTramType::Invalid, entry).trackdirs;
			(void)ChooseShipTrack(v, v->tile, {}, reverse_dirs, path_found, dummy_cache, best_origin_dir);
			*trackdir = path_found && best_origin_dir != Trackdir::Invalid ? best_origin_dir : GetRandomTrackdir(reverse_dirs);
			return true;
		}
	}
};

/** Cost Provider module of YAPF for ships. */
template <class Types>
class CYapfCostShipT {
public:
	typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class).
	typedef typename Types::TrackFollower TrackFollower;
	typedef typename Types::NodeList::Item Node; ///< this will be our node type.
	typedef typename Node::Key Key; ///< key to hash tables.

	/** @copydoc CYapfBaseT::Yapf */
	Tpf &Yapf()
	{
		return *static_cast<Tpf*>(this);
	}

public:
	inline int CurveCost(Trackdir td1, Trackdir td2)
	{
		assert(IsValidTrackdir(td1));
		assert(IsValidTrackdir(td2));

		if (TrackdirCrossesTrackdirs(td1).Test(td2)) {
			/* 90-deg curve penalty. */
			return Yapf().PfGetSettings().ship_curve90_penalty;
		} else if (td2 != NextTrackdir(td1)) {
			/* 45-deg curve penalty. */
			return Yapf().PfGetSettings().ship_curve45_penalty;
		}
		return 0;
	}

	/**
	 * Whether the provided direction is a preferred direction for a given tile. This is used to separate ships travelling in opposite directions.
	 * @param tile Tile of current node.
	 * @param td Trackdir of current node.
	 * @returns true if a preferred direction, false otherwise.
	 */
	inline static bool IsPreferredShipDirection(TileIndex tile, Trackdir td)
	{
		const bool odd_x = TileX(tile) & 1;
		const bool odd_y = TileY(tile) & 1;
		if (td == Trackdir::X_NE) return odd_y;
		if (td == Trackdir::X_SW) return !odd_y;
		if (td == Trackdir::Y_NW) return odd_x;
		if (td == Trackdir::Y_SE) return !odd_x;
		return (odd_x ^ odd_y) ^ TrackdirBits{Trackdir::Right_N, Trackdir::Left_S, Trackdir::Upper_W, Trackdir::Lower_E}.Test(td);
	}

	/** @copydoc CYapfBaseT::PfCalcCostFunc */
	inline bool PfCalcCost(Node &n, const TrackFollower *follower)
	{
		/* Base tile cost depending on distance. */
		int c = IsDiagonalTrackdir(n.GetTrackdir()) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
		/* Additional penalty for curves. */
		c += this->CurveCost(n.parent->GetTrackdir(), n.GetTrackdir());

		if (IsDockingTile(n.GetTile())) {
			/* Check docking tile for occupancy. */
			uint count = std::ranges::count_if(VehiclesOnTile(n.GetTile()), [](const Vehicle *v) {
				/* Ignore other vehicles (aircraft) and ships inside depot. */
				return v->type == VehicleType::Ship && !v->vehstatus.Test(VehState::Hidden);
			});
			c += count * 3 * YAPF_TILE_LENGTH;
		}

		/* Encourage separation between ships traveling in different directions. */
		if (!IsPreferredShipDirection(n.GetTile(), n.GetTrackdir())) c += YAPF_TILE_LENGTH;

		/* Skipped tile cost for aqueducts. */
		c += YAPF_TILE_LENGTH * follower->tiles_skipped;

		/* Ocean/canal speed penalty. */
		const ShipVehicleInfo *svi = ShipVehInfo(Yapf().GetVehicle()->engine_type);
		uint8_t speed_frac = (GetEffectiveWaterClass(n.GetTile()) == WaterClass::Sea) ? svi->ocean_speed_frac : svi->canal_speed_frac;
		if (speed_frac > 0) c += YAPF_TILE_LENGTH * (1 + follower->tiles_skipped) * speed_frac / (256 - speed_frac);

		/* Lock penalty. */
		if (IsTileType(n.GetTile(), TileType::Water) && IsLock(n.GetTile()) && GetLockPart(n.GetTile()) == LockPart::Middle) {
			const uint canal_speed = svi->ApplyWaterClassSpeedFrac(svi->max_speed, false);
			/* Cost is proportional to the vehicle's speed as the vehicle stops in the lock. */
			c += (TILE_HEIGHT * YAPF_TILE_LENGTH * canal_speed) / 128;
		}

		/* Apply it. */
		n.cost = n.parent->cost + c;
		return true;
	}
};

/**
 * Config struct of YAPF for ships.
 * Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
 */
template <class Tpf_>
struct CYapfShip_TypesT {
	typedef CYapfShip_TypesT<Tpf_> Types;         ///< Shortcut for this struct type.
	typedef Tpf_                   Tpf;           ///< Pathfinder type.
	typedef CFollowTrackWater      TrackFollower; ///< Track follower helper class.
	typedef CShipNodeList          NodeList;
	typedef Ship                   VehicleType;

	/** Pathfinder components (modules). */
	typedef CYapfBaseT<Types>                 PfBase;        ///< Base pathfinder class.
	typedef CYapfFollowShipT<Types>           PfFollow;      ///< Node follower.
	typedef CYapfOriginTileT<Types>           PfOrigin;      ///< Origin provider.
	typedef CYapfDestinationTileWaterT<Types> PfDestination; ///< Destination/distance provider.
	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;       ///< Segment cost cache provider.
	typedef CYapfCostShipT<Types>             PfCost;        ///< Cost provider.
};

struct CYapfShip : CYapfT<CYapfShip_TypesT<CYapfShip>> {
	explicit CYapfShip(int max_nodes) { this->max_search_nodes = max_nodes; }
};

Track YapfShipChooseTrack(const Ship *v, TileIndex tile, bool &path_found, ShipPathCache &path_cache)
{
	Trackdir best_origin_dir = Trackdir::Invalid;
	const TrackdirBits origin_dirs = TrackdirToTrackdirBits(v->GetVehicleTrackdir());
	const Trackdir td_ret = CYapfShip::ChooseShipTrack(v, tile, origin_dirs, {}, path_found, path_cache, best_origin_dir);
	return (td_ret != Trackdir::Invalid) ? TrackdirToTrack(td_ret) : Track::Invalid;
}

bool YapfShipCheckReverse(const Ship *v, Trackdir *trackdir)
{
	return CYapfShip::CheckShipReverse(v, trackdir);
}
