# yapf_base.hpp

Go to the documentation of this file.

    00001 /* $Id: yapf_base.hpp 15718 2009-03-15 00:32:18Z rubidium $ */
    00002
    00005 #ifndef  YAPF_BASE_HPP
    00006 #define  YAPF_BASE_HPP
    00007
    00008 #include "../debug.h"
    00009 #include "../settings_type.h"
    00010
    00011 extern int _total_pf_time_us;
    00012
    00042 template <class Types>
    00043 class CYapfBaseT {
    00044 public:
    00045   typedef typename Types::Tpf Tpf;
    00046   typedef typename Types::TrackFollower TrackFollower;
    00047   typedef typename Types::NodeList NodeList;
    00048   typedef typename NodeList::Titem Node;
    00049   typedef typename Node::Key Key;
    00050
    00051
    00052   NodeList             m_nodes;
    00053 protected:
    00054   Node                *m_pBestDestNode;
    00055   Node                *m_pBestIntermediateNode;
    00056   const YAPFSettings  *m_settings;
    00057   int                  m_max_search_nodes;
    00058   const Vehicle       *m_veh;
    00059
    00060   int                  m_stats_cost_calcs;
    00061   int                  m_stats_cache_hits;
    00062
    00063 public:
    00064   CPerformanceTimer    m_perf_cost;
    00065   CPerformanceTimer    m_perf_slope_cost;
    00066   CPerformanceTimer    m_perf_ts_cost;
    00067   CPerformanceTimer    m_perf_other_cost;
    00068
    00069 public:
    00070   int                  m_num_steps;
    00071
    00072 public:
    00074   FORCEINLINE CYapfBaseT()
    00075     : m_pBestDestNode(NULL)
    00076     , m_pBestIntermediateNode(NULL)
    00077     , m_settings(&_settings_game.pf.yapf)
    00078     , m_max_search_nodes(PfGetSettings().max_search_nodes)
    00079     , m_veh(NULL)
    00080     , m_stats_cost_calcs(0)
    00081     , m_stats_cache_hits(0)
    00082     , m_num_steps(0)
    00083   {
    00084   }
    00085
    00087   ~CYapfBaseT() {}
    00088
    00089 protected:
    00091   FORCEINLINE Tpf& Yapf()
    00092   {
    00093     return *static_cast<Tpf*>(this);
    00094   }
    00095
    00096 public:
    00098   FORCEINLINE const YAPFSettings& PfGetSettings() const
    00099   {
    00100     return *m_settings;
    00101   }
    00102
    00110   inline bool FindPath(const Vehicle *v)
    00111   {
    00112     m_veh = v;
    00113
    00114 #ifndef NO_DEBUG_MESSAGES
    00115     CPerformanceTimer perf;
    00116     perf.Start();
    00117 #endif /* !NO_DEBUG_MESSAGES */
    00118
    00119     Yapf().PfSetStartupNodes();
    00120
    00121     while (true) {
    00122       m_num_steps++;
    00123       Node *n = m_nodes.GetBestOpenNode();
    00124       if (n == NULL) {
    00125         break;
    00126       }
    00127
    00128       /* if the best open node was worse than the best path found, we can finish */
    00129       if (m_pBestDestNode != NULL && m_pBestDestNode->GetCost() < n->GetCostEstimate()) {
    00130         break;
    00131       }
    00132
    00133       Yapf().PfFollowNode(*n);
    00134       if (m_max_search_nodes == 0 || m_nodes.ClosedCount() < m_max_search_nodes) {
    00135         m_nodes.PopOpenNode(n->GetKey());
    00136         m_nodes.InsertClosedNode(*n);
    00137       } else {
    00138         m_pBestDestNode = m_pBestIntermediateNode;
    00139         break;
    00140       }
    00141     }
    00142
    00143     bool bDestFound = (m_pBestDestNode != NULL) && (m_pBestDestNode != m_pBestIntermediateNode);
    00144
    00145 #ifndef NO_DEBUG_MESSAGES
    00146     perf.Stop();
    00147     if (_debug_yapf_level >= 2) {
    00148       int t = perf.Get(1000000);
    00149       _total_pf_time_us += t;
    00150
    00151       if (_debug_yapf_level >= 3) {
    00152         UnitID veh_idx = (m_veh != NULL) ? m_veh->unitnumber : 0;
    00153         char ttc = Yapf().TransportTypeChar();
    00154         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);
    00155         int cost = bDestFound ? m_pBestDestNode->m_cost : -1;
    00156         int dist = bDestFound ? m_pBestDestNode->m_estimate - m_pBestDestNode->m_cost : -1;
    00157
    00158         DEBUG(yapf, 3, "[YAPF%c]%c%4d- %d us - %d rounds - %d open - %d closed - CHR %4.1f%% - c%d(sc%d, ts%d, o%d) -- ",
    00159           ttc, bDestFound ? '-' : '!', veh_idx, t, m_num_steps, m_nodes.OpenCount(), m_nodes.ClosedCount(),
    00160           cache_hit_ratio, cost, dist, m_perf_cost.Get(1000000), m_perf_slope_cost.Get(1000000),
    00161           m_perf_ts_cost.Get(1000000), m_perf_other_cost.Get(1000000)
    00162         );
    00163       }
    00164     }
    00165 #endif /* !NO_DEBUG_MESSAGES */
    00166     return bDestFound;
    00167   }
    00168
    00172   FORCEINLINE Node *GetBestNode()
    00173   {
    00174     return (m_pBestDestNode != NULL) ? m_pBestDestNode : m_pBestIntermediateNode;
    00175   }
    00176
    00180   FORCEINLINE Node& CreateNewNode()
    00181   {
    00182     Node& node = *m_nodes.CreateNewNode();
    00183     return node;
    00184   }
    00185
    00187   FORCEINLINE void AddStartupNode(Node& n)
    00188   {
    00189     Yapf().PfNodeCacheFetch(n);
    00190     /* insert the new node only if it is not there */
    00191     if (m_nodes.FindOpenNode(n.m_key) == NULL) {
    00192       m_nodes.InsertOpenNode(n);
    00193     } else {
    00194       /* if we are here, it means that node is already there - how it is possible?
    00195        *   probably the train is in the position that both its ends point to the same tile/exit-dir
    00196        *   very unlikely, but it happened */
    00197     }
    00198   }
    00199
    00201   FORCEINLINE void AddMultipleNodes(Node *parent, const TrackFollower &tf)
    00202   {
    00203     bool is_choice = (KillFirstBit(tf.m_new_td_bits) != TRACKDIR_BIT_NONE);
    00204     for (TrackdirBits rtds = tf.m_new_td_bits; rtds != TRACKDIR_BIT_NONE; rtds = KillFirstBit(rtds)) {
    00205       Trackdir td = (Trackdir)FindFirstBit2x64(rtds);
    00206       Node& n = Yapf().CreateNewNode();
    00207       n.Set(parent, tf.m_new_tile, td, is_choice);
    00208       Yapf().AddNewNode(n, tf);
    00209     }
    00210   }
    00211
    00214   void AddNewNode(Node &n, const TrackFollower &tf)
    00215   {
    00216     /* evaluate the node */
    00217     bool bCached = Yapf().PfNodeCacheFetch(n);
    00218     if (!bCached) {
    00219       m_stats_cost_calcs++;
    00220     } else {
    00221       m_stats_cache_hits++;
    00222     }
    00223
    00224     bool bValid = Yapf().PfCalcCost(n, &tf);
    00225
    00226     if (bCached) {
    00227       Yapf().PfNodeCacheFlush(n);
    00228     }
    00229
    00230     if (bValid) bValid = Yapf().PfCalcEstimate(n);
    00231
    00232     /* have the cost or estimate callbacks marked this node as invalid? */
    00233     if (!bValid) return;
    00234
    00235     /* detect the destination */
    00236     bool bDestination = Yapf().PfDetectDestination(n);
    00237     if (bDestination) {
    00238       if (m_pBestDestNode == NULL || n < *m_pBestDestNode) {
    00239         m_pBestDestNode = &n;
    00240       }
    00241       m_nodes.FoundBestNode(n);
    00242       return;
    00243     }
    00244
    00245     if (m_max_search_nodes > 0 && (m_pBestIntermediateNode == NULL || (m_pBestIntermediateNode->GetCostEstimate() - m_pBestIntermediateNode->GetCost()) > (n.GetCostEstimate() - n.GetCost()))) {
    00246       m_pBestIntermediateNode = &n;
    00247     }
    00248
    00249     /* check new node against open list */
    00250     Node *openNode = m_nodes.FindOpenNode(n.GetKey());
    00251     if (openNode != NULL) {
    00252       /* another node exists with the same key in the open list
    00253        * is it better than new one? */
    00254       if (n.GetCostEstimate() < openNode->GetCostEstimate()) {
    00255         /* update the old node by value from new one */
    00256         m_nodes.PopOpenNode(n.GetKey());
    00257         *openNode = n;
    00258         /* add the updated old node back to open list */
    00259         m_nodes.InsertOpenNode(*openNode);
    00260       }
    00261       return;
    00262     }
    00263
    00264     /* check new node against closed list */
    00265     Node *closedNode = m_nodes.FindClosedNode(n.GetKey());
    00266     if (closedNode != NULL) {
    00267       /* another node exists with the same key in the closed list
    00268        * is it better than new one? */
    00269       int node_est = n.GetCostEstimate();
    00270       int closed_est = closedNode->GetCostEstimate();
    00271       if (node_est < closed_est) {
    00272         /* If this assert occurs, you have probably problem in
    00273          * your Tderived::PfCalcCost() or Tderived::PfCalcEstimate().
    00274          * The problem could be:
    00275          *  - PfCalcEstimate() gives too large numbers
    00276          *  - PfCalcCost() gives too small numbers
    00277          *  - You have used negative cost penalty in some cases (cost bonus) */
    00278         assert(0);
    00279
    00280         return;
    00281       }
    00282       return;
    00283     }
    00284     /* the new node is really new
    00285      * add it to the open list */
    00286     m_nodes.InsertOpenNode(n);
    00287   }
    00288
    00289   const Vehicle * GetVehicle() const
    00290   {
    00291     return m_veh;
    00292   }
    00293
    00294   void DumpBase(DumpTarget &dmp) const
    00295   {
    00296     dmp.WriteStructT("m_nodes", &m_nodes);
    00297     dmp.WriteLine("m_num_steps = %d", m_num_steps);
    00298   }
    00299
    00300   /* methods that should be implemented at derived class Types::Tpf (derived from CYapfBaseT) */
    00301
    00302 #if 0
    00303
    00304   FORCEINLINE void PfSetStartupNodes()
    00305   {
    00306     /* example: */
    00307     Node& n1 = *base::m_nodes.CreateNewNode();
    00308     .
    00309     . // setup node members here
    00310     .
    00311     base::m_nodes.InsertOpenNode(n1);
    00312   }
    00313
    00315   FORCEINLINE void PfFollowNode(Node& org)
    00316   {
    00317     for (each follower of node org) {
    00318       Node& n = *base::m_nodes.CreateNewNode();
    00319       .
    00320       . // setup node members here
    00321       .
    00322       n.m_parent   = &org; // set node's parent to allow back tracking
    00323       AddNewNode(n);
    00324     }
    00325   }
    00326
    00328   FORCEINLINE bool PfCalcCost(Node& n)
    00329   {
    00330     /* evaluate last step cost */
    00331     int cost = ...;
    00332     /* set the node cost as sum of parent's cost and last step cost */
    00333     n.m_cost = n.m_parent->m_cost + cost;
    00334     return true; // true if node is valid follower (i.e. no obstacle was found)
    00335   }
    00336
    00338   FORCEINLINE bool PfCalcEstimate(Node& n)
    00339   {
    00340     /* evaluate the distance to our destination */
    00341     int distance = ...;
    00342     /* set estimate as sum of cost from origin + distance to the target */
    00343     n.m_estimate = n.m_cost + distance;
    00344     return true; // true if node is valid (i.e. not too far away :)
    00345   }
    00346
    00348   FORCEINLINE bool PfDetectDestination(Node& n)
    00349   {
    00350     bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);
    00351     return bDest;
    00352   }
    00353 #endif
    00354 };
    00355
    00356 #endif /* YAPF_BASE_HPP */