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"
#include "../../misc/dbg_helpers.h"
#include "yapf_type.hpp"
 
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::Item Node; 
  typedef typename Node::Key Key; 
 
  NodeList nodes; 
 
protected:
  Node *best_dest_node = nullptr; 
  Node *best_intermediate_node = nullptr; 
  const YAPFSettings *settings; 
  int max_search_nodes; 
  const VehicleType *vehicle = nullptr; 
 
  int stats_cost_calcs = 0; 
  int stats_cache_hits = 0; 
 
public:
  int num_steps = 0; 
 
public:
  inline CYapfBaseT() : settings(&_settings_game.pf.yapf), max_search_nodes(PfGetSettings().max_search_nodes) {}
 
  ~CYapfBaseT() {}
 
protected:
  inline Tpf &Yapf()
  {
    return *static_cast<Tpf *>(this);
  }
 
public:
  inline const YAPFSettings &PfGetSettings() const
  {
    return *this->settings;
  }
 
  inline bool FindPath(const VehicleType *v)
  {
    this->vehicle = v;
 
    Yapf().PfSetStartupNodes();
 
    for (;;) {
      this->num_steps++;
      Node *best_open_node = this->nodes.GetBestOpenNode();
      if (best_open_node == nullptr) break;
 
      if (Yapf().PfDetectDestination(*best_open_node)) {
        this->best_dest_node = best_open_node;
        break;
      }
 
      Yapf().PfFollowNode(*best_open_node);
      if (this->max_search_nodes != 0 && this->nodes.ClosedCount() >= this->max_search_nodes) break;
 
      this->nodes.PopOpenNode(best_open_node->GetKey());
      this->nodes.InsertClosedNode(*best_open_node);
    }
 
    const bool destination_found = (this->best_dest_node != nullptr);
 
    if (_debug_yapf_level >= 3) {
      const UnitID veh_idx = (this->vehicle != nullptr) ? this->vehicle->unitnumber : 0;
      const char ttc = Yapf().TransportTypeChar();
      const float cache_hit_ratio = (this->stats_cache_hits == 0) ? 0.0f : ((float)this->stats_cache_hits / (float)(this->stats_cache_hits + this->stats_cost_calcs) * 100.0f);
      const int cost = destination_found ? this->best_dest_node->cost : -1;
      const int dist = destination_found ? this->best_dest_node->estimate - this->best_dest_node->cost : -1;
 
      Debug(yapf, 3, "[YAPF{}]{}{:4d} - {} rounds - {} open - {} closed - CHR {:4.1f}% - C {} D {}",
        ttc, destination_found ? '-' : '!', veh_idx, this->num_steps, this->nodes.OpenCount(), this->nodes.ClosedCount(), cache_hit_ratio, cost, dist
      );
    }
 
    return destination_found;
  }
 
  inline Node *GetBestNode()
  {
    return (this->best_dest_node != nullptr) ? this->best_dest_node : this->best_intermediate_node;
  }
 
  inline Node &CreateNewNode()
  {
    Node &node = this->nodes.CreateNewNode();
    return node;
  }
 
  inline void AddStartupNode(Node &n)
  {
    Yapf().PfNodeCacheFetch(n);
    /* insert the new node only if it is not there */
    if (this->nodes.FindOpenNode(n.key) == nullptr) {
      this->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.new_td_bits) != TRACKDIR_BIT_NONE);
    for (TrackdirBits rtds = tf.new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
      Trackdir td = (Trackdir)FindFirstBit(rtds);
      Node &n = Yapf().CreateNewNode();
      n.Set(parent, tf.new_tile, td, is_choice);
      Yapf().AddNewNode(n, tf);
    }
  }
 
  void PruneIntermediateNodeBranch(Node *n)
  {
    bool intermediate_on_branch = false;
    while (n != nullptr && (n->segment->end_segment_reason & ESRB_CHOICE_FOLLOWS) == 0) {
      if (n == Yapf().best_intermediate_node) intermediate_on_branch = true;
      n = n->parent;
    }
    if (intermediate_on_branch) Yapf().best_intermediate_node = n;
  }
 
  void AddNewNode(Node &n, const TrackFollower &tf)
  {
    /* evaluate the node */
    bool cached = Yapf().PfNodeCacheFetch(n);
    if (!cached) {
      this->stats_cost_calcs++;
    } else {
      this->stats_cache_hits++;
    }
 
    bool valid = Yapf().PfCalcCost(n, &tf);
 
    if (valid) valid = Yapf().PfCalcEstimate(n);
 
    /* have the cost or estimate callbacks marked this node as invalid? */
    if (!valid) 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 = this->max_search_nodes > 0 && (this->best_intermediate_node == nullptr || (this->best_intermediate_node->GetCostEstimate() - this->best_intermediate_node->GetCost()) > (n.GetCostEstimate() - n.GetCost()));
 
    /* check new node against open list */
    Node *open_node = this->nodes.FindOpenNode(n.GetKey());
    if (open_node != nullptr) {
      /* another node exists with the same key in the open list
       * is it better than new one? */
      if (n.GetCostEstimate() < open_node->GetCostEstimate()) {
        /* update the old node by value from new one */
        this->nodes.PopOpenNode(n.GetKey());
        *open_node = n;
        /* add the updated old node back to open list */
        this->nodes.InsertOpenNode(*open_node);
        if (set_intermediate) this->best_intermediate_node = open_node;
      }
      return;
    }
 
    /* check new node against closed list */
    Node *closed_node = this->nodes.FindClosedNode(n.GetKey());
    if (closed_node != 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 = closed_node->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 */
    this->nodes.InsertOpenNode(n);
    if (set_intermediate) this->best_intermediate_node = &n;
  }
 
  const VehicleType * GetVehicle() const
  {
    return this->vehicle;
  }
 
  void DumpBase(DumpTarget &dmp) const
  {
    dmp.WriteStructT("nodes", &this->nodes);
    dmp.WriteValue("num_steps", this->num_steps);
  }
};
 
#endif /* YAPF_BASE_HPP */