129 src/pathfinder/yapf/yapf_ship.cpp
View file
Open in desktop
@@ -149,6 +149,50 @@ class CYapfFollowShipT
assert(best_trackdir == td1 || best_trackdir == td2);
return best_trackdir == td2;
}

static bool stFindNearestDepot(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, int max_penalty, TileIndex *depot_tile, bool *reversed)
{
Tpf pf;
bool result = pf.FindNearestDepot(v, tile, td1, td2, max_penalty, depot_tile, reversed);
return result;
}

/**
* Find the best depot for a ship.
* @param v Vehicle
* @param tile Tile of the vehicle.
* @param td1 Trackdir of the vehicle.
* @param td2 reversed Trackdir of the vehicle.
* @param max_cost maximum pathfinder cost.
* @param depot_tile the tile of the depot.
* @param reversed whether the path to depot was found on reversed Trackdir.
*/
inline bool FindNearestDepot(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, int max_cost, TileIndex *depot_tile, bool *reversed)
{
Tpf pf;
/* Set origin. */
pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2));
pf.SetMaxCost(max_cost);

/* find the best path */
bool bFound = pf.FindPath(v);
if (!bFound) return false;

/* some path found
* get found depot tile */
Node *n = pf.GetBestNode();
*depot_tile = n->m_key.m_tile;

/* walk through the path back to the origin */
Node *pNode = n;
while (pNode->m_parent != NULL) {
pNode = pNode->m_parent;
}

/* if the origin node is the ship's Trackdir then we didn't reverse */
*reversed = (pNode->m_key.m_td != td1);
return true;
}
};

/** Cost Provider module of YAPF for ships */
@@ -162,13 +206,22 @@ class CYapfCostShipT
typedef typename Node::Key Key; ///< key to hash tables

protected:
int m_max_cost;

CYapfCostShipT() : m_max_cost(0) {}

/** to access inherited path finder */
Tpf& Yapf()
{
return *static_cast<Tpf *>(this);
}

public:
inline void SetMaxCost(int max_cost)
{
m_max_cost = max_cost;
}

/**
* Called by YAPF to calculate the cost from the origin to the given node.
* Calculates only the cost of given node, adds it to the parent node cost
@@ -192,21 +245,58 @@ class CYapfCostShipT
byte speed_frac = (GetEffectiveWaterClass(n.GetTile()) == WATER_CLASS_SEA) ? svi->ocean_speed_frac : svi->canal_speed_frac;
if (speed_frac > 0) c += YAPF_TILE_LENGTH * (1 + tf->m_tiles_skipped) * speed_frac / (256 - speed_frac);

/* Finish if we already exceeded the maximum path cost (i.e. when
* searching for the nearest depot). */
if (m_max_cost > 0 && (n.m_parent->m_cost + c) > m_max_cost) return false;

/* apply it */
n.m_cost = n.m_parent->m_cost + c;
return true;
}
};

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

/** to access inherited path finder */
Tpf& Yapf()
{
return *static_cast<Tpf *>(this);
}

/** Called by YAPF to detect if node ends in the desired destination */
inline bool PfDetectDestination(Node &n)
{
bool bDest = (IsShipDepotTile(n.m_key.m_tile) && GetShipDepotPart(n.m_key.m_tile) == DEPOT_PART_NORTH) && IsTileOwner(n.m_key.m_tile, Yapf().GetVehicle()->owner);
return bDest;
}

/**
* Called by YAPF to calculate cost estimate. Calculates distance to the destination
* adds it to the actual cost from origin and stores the sum to the Node::m_estimate
*/
inline bool PfCalcEstimate(Node &n)
{
n.m_estimate = n.m_cost;
return true;
}
};

/**
* Config struct of YAPF for ships.
* Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
*/
template <class Tpf_, class Ttrack_follower, class Tnode_list>
template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class CYapfDestinationTileT>
struct CYapfShip_TypesT
{
/** Types - shortcut for this struct type */
typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list> Types;
typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list, CYapfDestinationTileT> Types;

/** Tpf - pathfinder type */
typedef Tpf_ Tpf;
@@ -225,11 +315,15 @@ struct CYapfShip_TypesT
};

/* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater , CShipNodeListTrackDir> > {};
struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1 , CFollowTrackWater , CShipNodeListTrackDir, CYapfDestinationTileT> > {};
/* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , CShipNodeListExitDir > > {};
struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2 , CFollowTrackWater , CShipNodeListExitDir , CYapfDestinationTileT> > {};
/* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3 , CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationTileT> > {};

struct CYapfShipAnyDepot1 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot1, CFollowTrackWater , CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT> > {};
struct CYapfShipAnyDepot2 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot2, CFollowTrackWater , CShipNodeListExitDir , CYapfDestinationAnyDepotShipT> > {};
struct CYapfShipAnyDepot3 : CYapfT<CYapfShip_TypesT<CYapfShipAnyDepot3, CFollowTrackWaterNo90, CShipNodeListTrackDir, CYapfDestinationAnyDepotShipT> > {};

/** Ship controller helper - path finder invoker */
Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
@@ -249,6 +343,31 @@ Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir,
return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
}

FindDepotData YapfShipFindNearestDepot(const Ship *v, int max_penalty)
{
FindDepotData fdd;

Trackdir td = v->GetVehicleTrackdir();
Trackdir td_rev = ReverseTrackdir(td);
TileIndex tile = v->tile;

/* default is YAPF type 2 */
typedef bool(*PfnFindNearestDepot)(const Ship*, TileIndex, Trackdir, Trackdir, int, TileIndex*, bool*);
PfnFindNearestDepot pfnFindNearestDepot = &CYapfShipAnyDepot2::stFindNearestDepot;

/* check if non-default YAPF type should be used */
if (_settings_game.pf.forbid_90_deg) {
pfnFindNearestDepot = &CYapfShipAnyDepot3::stFindNearestDepot; // Trackdir, forbid 90-deg
} else if (_settings_game.pf.yapf.disable_node_optimization) {
pfnFindNearestDepot = &CYapfShipAnyDepot1::stFindNearestDepot; // Trackdir, allow 90-deg
}

bool ret = pfnFindNearestDepot(v, tile, td, td_rev, max_penalty, &fdd.tile, &fdd.reverse);

fdd.best_length = ret ? DistanceManhattan(tile, fdd.tile) : UINT_MAX; // distance manhattan or NOT_FOUND
return fdd;
}

bool YapfShipCheckReverse(const Ship *v)
{
Trackdir td = v->GetVehicleTrackdir();
49 src/ship_cmd.cpp
View file
Open in desktop
@@ -140,7 +140,7 @@ void Ship::GetImage(Direction direction, EngineImageType image_type, VehicleSpri
result->Set(_ship_sprites[spritenum] + direction);
}

static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance)
static FindDepotData FindClosestShipDepot(const Ship *v, uint max_distance)
{
/* Find the closest depot */
const Depot *depot;
@@ -163,7 +163,25 @@ static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance)
}
}

return best_depot;
FindDepotData fdd;
if (best_depot != NULL) {
fdd.best_length = best_dist;
fdd.tile = best_depot->xy;
}
return fdd;
}

static FindDepotData FindClosestReachableShipDepot(const Ship *v, int max_distance)
{
if ((IsShipDepotTile(v->tile) && GetShipDepotPart(v->tile) == DEPOT_PART_NORTH) && IsTileOwner(v->tile, v->owner)) return FindDepotData(v->tile, 0);

switch (_settings_game.pf.pathfinder_for_ships) {
case VPF_OPF : return OPFShipFindNearestDepot(v, max_distance);
case VPF_NPF : return NPFShipFindNearestDepot(v, max_distance);
case VPF_YAPF: return YapfShipFindNearestDepot(v, max_distance);

default: NOT_REACHED();
}
}

static void CheckIfShipNeedsService(Vehicle *v)
@@ -176,24 +194,24 @@ static void CheckIfShipNeedsService(Vehicle *v)

uint max_distance;
switch (_settings_game.pf.pathfinder_for_ships) {
case VPF_OPF: max_distance = 12; break;
case VPF_NPF: max_distance = _settings_game.pf.npf.maximum_go_to_depot_penalty / NPF_TILE_LENGTH; break;
case VPF_YAPF: max_distance = _settings_game.pf.yapf.maximum_go_to_depot_penalty / YAPF_TILE_LENGTH; break;
case VPF_OPF: max_distance = 20; break;
case VPF_NPF: max_distance = _settings_game.pf.npf.maximum_go_to_depot_penalty; break;
case VPF_YAPF: max_distance = _settings_game.pf.yapf.maximum_go_to_depot_penalty; break;
default: NOT_REACHED();
}

const Depot *depot = FindClosestShipDepot(v, max_distance);
const FindDepotData sfdd = FindClosestReachableShipDepot(Ship::From(v), max_distance);

if (depot == NULL) {
if (sfdd.best_length == UINT_MAX) {
if (v->current_order.IsType(OT_GOTO_DEPOT)) {
v->current_order.MakeDummy();
SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);
}
return;
}

v->current_order.MakeGoToDepot(depot->index, ODTFB_SERVICE);
v->SetDestTile(depot->xy);
v->current_order.MakeGoToDepot(GetDepotIndex(sfdd.tile), ODTFB_SERVICE);
v->SetDestTile(sfdd.tile);
SetWindowWidgetDirty(WC_VEHICLE_VIEW, v->index, WID_VV_START_STOP);
}

@@ -774,12 +792,15 @@ CommandCost CmdBuildShip(TileIndex tile, DoCommandFlag flags, const Engine *e, u

bool Ship::FindClosestDepot(TileIndex *location, DestinationID *destination, bool *reverse)
{
const Depot *depot = FindClosestShipDepot(this, 0);

if (depot == NULL) return false;
FindDepotData sfdd = FindClosestReachableShipDepot(this, 0);
if (sfdd.best_length == UINT_MAX) {
sfdd = FindClosestShipDepot(this, 0);
if (sfdd.best_length == UINT_MAX) return false;
}

if (location != NULL) *location = depot->xy;
if (destination != NULL) *destination = depot->index;
if (location != NULL) *location = sfdd.tile;
if (destination != NULL) *destination = GetDepotIndex(sfdd.tile);
if (reverse != NULL) *reverse = sfdd.reverse;

return true;
}