yapf_ship.cpp

Go to the documentation of this file.

/*
 * 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 <http://www.gnu.org/licenses/>.
 */
 
#include "../../stdafx.h"
#include "../../ship.h"
#include "../../industry.h"
#include "../../vehicle_func.h"
 
#include "yapf.hpp"
#include "yapf_node_ship.hpp"
 
#include "../../safeguards.h"
 
template <class Types>
class CYapfDestinationTileWaterT
{
public:
  typedef typename Types::Tpf Tpf;                     
  typedef typename Types::TrackFollower TrackFollower;
  typedef typename Types::NodeList::Titem Node;        
  typedef typename Node::Key Key;                      
 
protected:
  TileIndex    m_destTile;
  TrackdirBits m_destTrackdirs;
  StationID    m_destStation;
 
public:
  void SetDestination(const Ship *v)
  {
    if (v->current_order.IsType(OT_GOTO_STATION)) {
      m_destStation   = v->current_order.GetDestination();
      m_destTile      = CalcClosestStationTile(m_destStation, v->tile, STATION_DOCK);
      m_destTrackdirs = INVALID_TRACKDIR_BIT;
    } else {
      m_destStation   = INVALID_STATION;
      m_destTile      = v->dest_tile;
      m_destTrackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER, 0));
    }
  }
 
protected:
  inline Tpf& Yapf()
  {
    return *static_cast<Tpf*>(this);
  }
 
public:
  inline bool PfDetectDestination(Node& n)
  {
    return PfDetectDestinationTile(n.m_segment_last_tile, n.m_segment_last_td);
  }
 
  inline bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)
  {
    if (m_destStation != INVALID_STATION) {
      return IsDockingTile(tile) && IsShipDestinationTile(tile, m_destStation);
    }
 
    return tile == m_destTile && ((m_destTrackdirs & TrackdirToTrackdirBits(trackdir)) != TRACKDIR_BIT_NONE);
  }
 
  inline bool PfCalcEstimate(Node& n)
  {
    static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};
    static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};
    if (PfDetectDestination(n)) {
      n.m_estimate = n.m_cost;
      return true;
    }
 
    TileIndex tile = n.m_segment_last_tile;
    DiagDirection exitdir = TrackdirToExitdir(n.m_segment_last_td);
    int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];
    int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];
    int x2 = 2 * TileX(m_destTile);
    int y2 = 2 * TileY(m_destTile);
    int dx = abs(x1 - x2);
    int dy = abs(y1 - y2);
    int dmin = std::min(dx, dy);
    int dxy = abs(dx - dy);
    int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);
    n.m_estimate = n.m_cost + d;
    assert(n.m_estimate >= n.m_parent->m_estimate);
    return true;
  }
};
 
 
template <class Types>
class CYapfFollowShipT
{
public:
  typedef typename Types::Tpf Tpf;                     
  typedef typename Types::TrackFollower TrackFollower;
  typedef typename Types::NodeList::Titem Node;        
  typedef typename Node::Key Key;                      
 
protected:
  inline Tpf& Yapf()
  {
    return *static_cast<Tpf *>(this);
  }
 
public:
  inline void PfFollowNode(Node &old_node)
  {
    TrackFollower F(Yapf().GetVehicle());
    if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) {
      Yapf().AddMultipleNodes(&old_node, F);
    }
  }
 
  inline char TransportTypeChar() const
  {
    return 'w';
  }
 
  static Trackdir ChooseShipTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
  {
    /* handle special case - when next tile is destination tile */
    if (tile == v->dest_tile) {
      /* convert tracks to trackdirs */
      TrackdirBits trackdirs = TrackBitsToTrackdirBits(tracks);
      /* limit to trackdirs reachable from enterdir */
      trackdirs &= DiagdirReachesTrackdirs(enterdir);
 
      /* use vehicle's current direction if that's possible, otherwise use first usable one. */
      Trackdir veh_dir = v->GetVehicleTrackdir();
      return (HasTrackdir(trackdirs, veh_dir)) ? veh_dir : (Trackdir)FindFirstBit2x64(trackdirs);
    }
 
    /* move back to the old tile/trackdir (where ship is coming from) */
    TileIndex src_tile = TileAddByDiagDir(tile, ReverseDiagDir(enterdir));
    Trackdir trackdir = v->GetVehicleTrackdir();
    assert(IsValidTrackdir(trackdir));
 
    /* convert origin trackdir to TrackdirBits */
    TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);
 
    /* create pathfinder instance */
    Tpf pf;
    /* set origin and destination nodes */
    pf.SetOrigin(src_tile, trackdirs);
    pf.SetDestination(v);
    /* find best path */
    path_found = pf.FindPath(v);
 
    Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"
 
    Node *pNode = pf.GetBestNode();
    if (pNode != nullptr) {
      uint steps = 0;
      for (Node *n = pNode; n->m_parent != nullptr; n = n->m_parent) steps++;
      uint skip = 0;
      if (path_found) skip = YAPF_SHIP_PATH_CACHE_LENGTH / 2;
 
      /* walk through the path back to the origin */
      Node *pPrevNode = nullptr;
      while (pNode->m_parent != nullptr) {
        steps--;
        /* Skip tiles at end of path near destination. */
        if (skip > 0) skip--;
        if (skip == 0 && steps > 0 && steps < YAPF_SHIP_PATH_CACHE_LENGTH) {
          path_cache.push_front(pNode->GetTrackdir());
        }
        pPrevNode = pNode;
        pNode = pNode->m_parent;
      }
      /* return trackdir from the best next node (direct child of origin) */
      Node &best_next_node = *pPrevNode;
      assert(best_next_node.GetTile() == tile);
      next_trackdir = best_next_node.GetTrackdir();
      /* remove last element for the special case when tile == dest_tile */
      if (path_found && !path_cache.empty()) path_cache.pop_back();
    }
    return next_trackdir;
  }
 
  static bool CheckShipReverse(const Ship *v, TileIndex tile, Trackdir td1, Trackdir td2, Trackdir *trackdir)
  {
    /* create pathfinder instance */
    Tpf pf;
    /* set origin and destination nodes */
    if (trackdir == nullptr) {
      pf.SetOrigin(tile, TrackdirToTrackdirBits(td1) | TrackdirToTrackdirBits(td2));
    } else {
      DiagDirection entry = ReverseDiagDir(VehicleExitDir(v->direction, v->state));
      TrackdirBits rtds = DiagdirReachesTrackdirs(entry) & TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_WATER, 0, entry));
      pf.SetOrigin(tile, rtds);
    }
    pf.SetDestination(v);
    /* find best path */
    if (!pf.FindPath(v)) return false;
 
    Node *pNode = pf.GetBestNode();
    if (pNode == nullptr) return false;
 
    /* path was found
     * walk through the path back to the origin */
    while (pNode->m_parent != nullptr) {
      pNode = pNode->m_parent;
    }
 
    Trackdir best_trackdir = pNode->GetTrackdir();
    if (trackdir != nullptr) {
      *trackdir = best_trackdir;
    } else {
      assert(best_trackdir == td1 || best_trackdir == td2);
    }
    return best_trackdir != td1;
  }
};
 
template <class Types>
class CYapfCostShipT
{
public:
  typedef typename Types::Tpf Tpf;              
  typedef typename Types::TrackFollower TrackFollower;
  typedef typename Types::NodeList::Titem Node; 
  typedef typename Node::Key Key;               
 
protected:
  Tpf& Yapf()
  {
    return *static_cast<Tpf *>(this);
  }
 
public:
  inline int CurveCost(Trackdir td1, Trackdir td2)
  {
    assert(IsValidTrackdir(td1));
    assert(IsValidTrackdir(td2));
 
    if (HasTrackdir(TrackdirCrossesTrackdirs(td1), 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;
  }
 
  static Vehicle *CountShipProc(Vehicle *v, void *data)
  {
    uint *count = (uint *)data;
    /* Ignore other vehicles (aircraft) and ships inside depot. */
    if (v->type == VEH_SHIP && (v->vehstatus & VS_HIDDEN) == 0) (*count)++;
 
    return nullptr;
  }
 
  inline bool PfCalcCost(Node &n, const TrackFollower *tf)
  {
    /* base tile cost depending on distance */
    int c = IsDiagonalTrackdir(n.GetTrackdir()) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
    /* additional penalty for curves */
    c += CurveCost(n.m_parent->GetTrackdir(), n.GetTrackdir());
 
    if (IsDockingTile(n.GetTile())) {
      /* Check docking tile for occupancy */
      uint count = 0;
      HasVehicleOnPos(n.GetTile(), &count, &CountShipProc);
      c += count * 3 * YAPF_TILE_LENGTH;
    }
 
    /* Skipped tile cost for aqueducts. */
    c += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
 
    /* Ocean/canal speed penalty. */
    const ShipVehicleInfo *svi = ShipVehInfo(Yapf().GetVehicle()->engine_type);
    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);
 
    /* apply it */
    n.m_cost = n.m_parent->m_cost + c;
    return true;
  }
};
 
template <class Tpf_, class Ttrack_follower, class Tnode_list>
struct CYapfShip_TypesT
{
  typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;
 
  typedef Tpf_                              Tpf;
  typedef Ttrack_follower                   TrackFollower;
  typedef Tnode_list                        NodeList;
  typedef Ship                              VehicleType;
  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
};
 
/* YAPF type 1 - uses TileIndex/Trackdir as Node key */
struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};
/* YAPF type 2 - uses TileIndex/DiagDirection as Node key */
struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};
 
Track YapfShipChooseTrack(const Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool &path_found, ShipPathCache &path_cache)
{
  /* default is YAPF type 2 */
  typedef Trackdir (*PfnChooseShipTrack)(const Ship*, TileIndex, DiagDirection, TrackBits, bool &path_found, ShipPathCache &path_cache);
  PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir
 
  /* check if non-default YAPF type needed */
  if (_settings_game.pf.yapf.disable_node_optimization) {
    pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir
  }
 
  Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks, path_found, path_cache);
  return (td_ret != INVALID_TRACKDIR) ? TrackdirToTrack(td_ret) : INVALID_TRACK;
}
 
bool YapfShipCheckReverse(const Ship *v, Trackdir *trackdir)
{
  Trackdir td = v->GetVehicleTrackdir();
  Trackdir td_rev = ReverseTrackdir(td);
  TileIndex tile = v->tile;
 
  typedef bool (*PfnCheckReverseShip)(const Ship*, TileIndex, Trackdir, Trackdir, Trackdir*);
  PfnCheckReverseShip pfnCheckReverseShip = CYapfShip2::CheckShipReverse; // default: ExitDir
 
  /* check if non-default YAPF type needed */
  if (_settings_game.pf.yapf.disable_node_optimization) {
    pfnCheckReverseShip = &CYapfShip1::CheckShipReverse; // Trackdir
  }
 
  bool reverse = pfnCheckReverseShip(v, tile, td, td_rev, trackdir);
 
  return reverse;
}