yapf_base.hpp

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/>.
 */
 
#ifndef YAPF_BASE_HPP
#define YAPF_BASE_HPP
 
#include "../../debug.h"
#include "../../settings_type.h"
 
template <class Types>
class CYapfBaseT {
public:
  typedef typename Types::Tpf Tpf;           
  typedef typename Types::TrackFollower TrackFollower;
  typedef typename Types::NodeList NodeList; 
  typedef typename Types::VehicleType VehicleType; 
  typedef typename NodeList::Titem Node;     
  typedef typename Node::Key Key;            
 
 
  NodeList             m_nodes;              
protected:
  Node                *m_pBestDestNode;      
  Node                *m_pBestIntermediateNode; 
  const YAPFSettings  *m_settings;           
  int                  m_max_search_nodes;   
  const VehicleType   *m_veh;                
 
  int                  m_stats_cost_calcs;   
  int                  m_stats_cache_hits;   
 
public:
  int                  m_num_steps;          
 
public:
  inline CYapfBaseT()
    : m_pBestDestNode(nullptr)
    , m_pBestIntermediateNode(nullptr)
    , m_settings(&_settings_game.pf.yapf)
    , m_max_search_nodes(PfGetSettings().max_search_nodes)
    , m_veh(nullptr)
    , m_stats_cost_calcs(0)
    , m_stats_cache_hits(0)
    , m_num_steps(0)
  {
  }
 
  ~CYapfBaseT() {}
 
protected:
  inline Tpf &Yapf()
  {
    return *static_cast<Tpf *>(this);
  }
 
public:
  inline const YAPFSettings &PfGetSettings() const
  {
    return *m_settings;
  }
 
  inline bool FindPath(const VehicleType *v)
  {
    m_veh = v;
 
    Yapf().PfSetStartupNodes();
 
    for (;;) {
      m_num_steps++;
      Node *best_open_node = m_nodes.GetBestOpenNode();
      if (best_open_node == nullptr) break;
 
      if (Yapf().PfDetectDestination(*best_open_node)) {
        m_pBestDestNode = best_open_node;
        break;
      }
 
      Yapf().PfFollowNode(*best_open_node);
      if (m_max_search_nodes != 0 && m_nodes.ClosedCount() >= m_max_search_nodes) break;
 
      m_nodes.PopOpenNode(best_open_node->GetKey());
      m_nodes.InsertClosedNode(*best_open_node);
    }
 
    const bool destination_found = (m_pBestDestNode != nullptr);
 
    if (_debug_yapf_level >= 3) {
      const UnitID veh_idx = (m_veh != nullptr) ? m_veh->unitnumber : 0;
      const char ttc = Yapf().TransportTypeChar();
      const float cache_hit_ratio = (m_stats_cache_hits == 0) ? 0.0f : ((float)m_stats_cache_hits / (float)(m_stats_cache_hits + m_stats_cost_calcs) * 100.0f);
      const int cost = destination_found ? m_pBestDestNode->m_cost : -1;
      const int dist = destination_found ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;
 
      Debug(yapf, 3, "[YAPF{}]{}{:4d} - {} rounds - {} open - {} closed - CHR {:4.1f}% - C {} D {}",
        ttc, destination_found ? '-' : '!', veh_idx, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(), cache_hit_ratio, cost, dist
      );
    }
 
    return destination_found;
  }
 
  inline Node *GetBestNode()
  {
    return (m_pBestDestNode != nullptr) ? m_pBestDestNode : m_pBestIntermediateNode;
  }
 
  inline Node &CreateNewNode()
  {
    Node &node = *m_nodes.CreateNewNode();
    return node;
  }
 
  inline void AddStartupNode(Node &n)
  {
    Yapf().PfNodeCacheFetch(n);
    /* insert the new node only if it is not there */
    if (m_nodes.FindOpenNode(n.m_key) == nullptr) {
      m_nodes.InsertOpenNode(n);
    } else {
      /* if we are here, it means that node is already there - how it is possible?
       *   probably the train is in the position that both its ends point to the same tile/exit-dir
       *   very unlikely, but it happened */
    }
  }
 
  inline void AddMultipleNodes(Node *parent, const TrackFollower &tf)
  {
    bool is_choice = (KillFirstBit(tf.m_new_td_bits) != TRACKDIR_BIT_NONE);
    for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
      Trackdir td = (Trackdir)FindFirstBit(rtds);
      Node &n = Yapf().CreateNewNode();
      n.Set(parent, tf.m_new_tile, td, is_choice);
      Yapf().AddNewNode(n, tf);
    }
  }
 
  void PruneIntermediateNodeBranch(Node *n)
  {
    bool intermediate_on_branch = false;
    while (n != nullptr && (n->m_segment->m_end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) {
      if (n == Yapf().m_pBestIntermediateNode) intermediate_on_branch = true;
      n = n->m_parent;
    }
    if (intermediate_on_branch) Yapf().m_pBestIntermediateNode = n;
  }
 
  void AddNewNode(Node &n, const TrackFollower &tf)
  {
    /* evaluate the node */
    bool bCached = Yapf().PfNodeCacheFetch(n);
    if (!bCached) {
      m_stats_cost_calcs++;
    } else {
      m_stats_cache_hits++;
    }
 
    bool bValid = Yapf().PfCalcCost(n, &tf);
 
    if (bValid) bValid = Yapf().PfCalcEstimate(n);
 
    /* have the cost or estimate callbacks marked this node as invalid? */
    if (!bValid) return;
 
    /* The new node can be set as the best intermediate node only once we're
     * certain it will be finalized by being inserted into the open list. */
    bool set_intermediate = m_max_search_nodes > 0 && (m_pBestIntermediateNode == nullptr || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()));
 
    /* check new node against open list */
    Node *openNode = m_nodes.FindOpenNode(n.GetKey());
    if (openNode != nullptr) {
      /* another node exists with the same key in the open list
       * is it better than new one? */
      if (n.GetCostEstimate() < openNode->GetCostEstimate()) {
        /* update the old node by value from new one */
        m_nodes.PopOpenNode(n.GetKey());
        *openNode = n;
        /* add the updated old node back to open list */
        m_nodes.InsertOpenNode(*openNode);
        if (set_intermediate) m_pBestIntermediateNode = openNode;
      }
      return;
    }
 
    /* check new node against closed list */
    Node *closedNode = m_nodes.FindClosedNode(n.GetKey());
    if (closedNode != nullptr) {
      /* another node exists with the same key in the closed list
       * is it better than new one? */
      int node_est = n.GetCostEstimate();
      int closed_est = closedNode->GetCostEstimate();
      if (node_est < closed_est) {
        /* If this assert occurs, you have probably problem in
         * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
         * The problem could be:
         *  - PfCalcEstimate() gives too large numbers
         *  - PfCalcCost() gives too small numbers
         *  - You have used negative cost penalty in some cases (cost bonus) */
        NOT_REACHED();
      }
      return;
    }
    /* the new node is really new
     * add it to the open list */
    m_nodes.InsertOpenNode(n);
    if (set_intermediate) m_pBestIntermediateNode = &n;
  }
 
  const VehicleType * GetVehicle() const
  {
    return m_veh;
  }
 
  void DumpBase(DumpTarget &dmp) const
  {
    dmp.WriteStructT("m_nodes", &m_nodes);
    dmp.WriteValue("m_num_steps", m_num_steps);
  }
};
 
#endif /* YAPF_BASE_HPP */