[netPanzer-CVS] netpanzer/src/NetPanzer/Classes/AI Astar.cpp As...

[Matthias Braun]

CVSROOT:        /cvsroot/netpanzer
Module name:    netpanzer
Branch:         
Changes by:     Matthias Braun <address@hidden> 03/09/11 10:58:03

Modified files:
        src/NetPanzer/Classes/AI: Astar.cpp Astar.hpp 

Log message:
        converted a PPriorityQueue to a STL priority_queue in Astar class

Patches:
Index: netpanzer/src/NetPanzer/Classes/AI/Astar.cpp
diff -u netpanzer/src/NetPanzer/Classes/AI/Astar.cpp:1.5 
netpanzer/src/NetPanzer/Classes/AI/Astar.cpp:1.6
--- netpanzer/src/NetPanzer/Classes/AI/Astar.cpp:1.5    Wed Sep 10 08:32:53 2003
+++ netpanzer/src/NetPanzer/Classes/AI/Astar.cpp        Thu Sep 11 10:58:03 2003
@@ -16,49 +16,31 @@
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
 #include <config.h>
-#include "Astar.hpp"
 
+#include <functional>
+#include "Astar.hpp"
 #include "Timer.hpp"
 #include "PathingState.hpp"
 
-int compare(void *object1, void *object2 )
- {
-  AstarNode *node1, *node2;
-  node1 = (AstarNode *) object1;                                          
-  node2 = (AstarNode *) object2;
- 
-  if (node1->f > node2->f)
-   return( 1 );
-  else
-   if ( node1->f < node2->f )
-    return( -1 );
-    
-  return( 0 ); 
- } 
-
-
-Astar::Astar( void )
- {
-  node_list = 0;
- }
+Astar::Astar()
+{
+       node_list = 0;
+}
 
 void Astar::initializeAstar( unsigned long node_list_size,
                              unsigned long step_limit,
                                             long heuristic_weight )
- { 
+{ 
   open_set.initialize( getMapXsize(),  getMapYsize() );
   closed_set.initialize( getMapXsize(), getMapYsize() );
   
-  open.initialize( node_list_size + (100) , node_list_size / 10, 0xFFFFFFFF );
-  open.setCompare( compare );
-
   initializeNodeList( node_list_size );
 
   Astar::step_limit = step_limit;
   Astar::heuristic_weight = heuristic_weight;
  
   ini_flag = true; 
- }
+}
 
 void Astar::initializeAstar( unsigned long node_list_size )
  {
@@ -187,7 +169,7 @@
   best_node->f = best_node->g + best_node->h;
   best_node->parent = 0;
   
-  open.push( best_node );
+  open.push(best_node);
   
   open_set.setBit( best_node->map_loc.x, best_node->map_loc.y );  
  
@@ -301,7 +283,8 @@
   
   while( !done && !steps_comp )
    {   
-       best_node = (AstarNode *) open.pop( );
+       best_node = open.top();
+       open.pop();
     
     if ( best_node == 0 )
     {
@@ -356,8 +339,7 @@
                                 if ( start_sampling_flag == true)
                   astar_set_array.setBit( node->map_loc.x, node->map_loc.y );
                                  
-                 open.push( node );
-              
+                 open.push(node);
                  }
              
              } // ** else
@@ -459,7 +441,12 @@
 
   open_set.clear();
   closed_set.clear(); 
-  open.reset();
+  
+  // STL doesn't define a clear for some reason, so we try a workaround with
+  // asignment
+  //open.clear();
+  open = std::priority_queue<AstarNode*, std::vector<AstarNode*>, 
+                             AstarNodePtrCompare>();
 
   resetNodeList();
   ini_flag = true;
Index: netpanzer/src/NetPanzer/Classes/AI/Astar.hpp
diff -u netpanzer/src/NetPanzer/Classes/AI/Astar.hpp:1.4 
netpanzer/src/NetPanzer/Classes/AI/Astar.hpp:1.5
--- netpanzer/src/NetPanzer/Classes/AI/Astar.hpp:1.4    Wed Sep 10 08:32:54 2003
+++ netpanzer/src/NetPanzer/Classes/AI/Astar.hpp        Thu Sep 11 10:58:03 2003
@@ -18,7 +18,8 @@
 #ifndef _ASTAR_HPP
 #define _ASTAR_HPP
 
-#include "PPriorityQueue.hpp"
+#include <queue>
+
 #include "BitArray.hpp"
 #include "MapInterface.hpp"
 #include "UnitID.hpp"
@@ -30,119 +31,131 @@
 enum { _path_result_success, _path_result_goal_unreachable };
 
 class PathRequest
- {
-  public:
-   unsigned short status;
-   unsigned short result_code;
-
-   unsigned short request_type;
-   unsigned short path_type;
-   UnitID         unit_id;
-   iXY       start;
-   iXY       goal;
-   PathList      *path;
- 
-   void set( UnitID &unit_id, 
-             iXY &start, 
-                        iXY &goal, 
-                        unsigned short path_type, 
-                        PathList *path,
-                        unsigned short request_type )
-    {
-        PathRequest::unit_id = unit_id;
-        PathRequest::start = start;
-     PathRequest::goal = goal;
-        PathRequest::path_type = path_type;
-        PathRequest::path = path;       
-     PathRequest::request_type = request_type;
-     PathRequest::status = _slot_status_free;
+{
+public:
+       unsigned short status;
+       unsigned short result_code;
+
+       unsigned short request_type;
+       unsigned short path_type;
+       UnitID         unit_id;
+       iXY       start;
+       iXY       goal;
+       PathList      *path;
+ 
+       void set( UnitID &unit_id, 
+                       iXY &start, 
+                       iXY &goal, 
+                       unsigned short path_type, 
+                       PathList *path,
+                       unsigned short request_type )
+       {
+               PathRequest::unit_id = unit_id;
+               PathRequest::start = start;
+               PathRequest::goal = goal;
+               PathRequest::path_type = path_type;
+               PathRequest::path = path;        
+               PathRequest::request_type = request_type;
+               PathRequest::status = _slot_status_free;
        }
- 
- 
-  void operator=( const PathRequest &rhs )
-   {
-       memmove( this, &rhs, sizeof( PathRequest ) );
-   }
- 
- };
-
+        
+       // XXX this looks strange to me
+#if 0
+       void operator=( const PathRequest &rhs )
+       {
+               memmove( this, &rhs, sizeof( PathRequest ) );
+       }
+#endif
+};
 
 class AstarNode
- {
-  public:
-  iXY map_loc;
-  unsigned long abs_loc;
-  long f;
-  long g; 
-  long h; 
-  AstarNode *parent;
- };
+{
+public:
+       iXY map_loc;
+       unsigned long abs_loc;
+       long f;
+       long g; 
+       long h; 
+       AstarNode *parent;
 
+       bool operator <(const AstarNode& other) const {
+               return other.f < f;
+       }
+};
 
 enum { _path_merge_front, _path_merge_rear };
 
+class AstarNodePtrCompare 
+       : public std::binary_function<const AstarNode*, const AstarNode*, bool>
+{
+public:
+       bool operator()(const AstarNode* node1, const AstarNode* node2) const
+       {
+               return *node1 < *node2;
+       }
+};
+
 class Astar : private MapInterface
- {
-  private:
-   AstarNode *node_list;
+{
+private:
+       AstarNode *node_list;
   
-   unsigned long node_index;
-   unsigned long node_list_size;
+       unsigned long node_index;
+       unsigned long node_list_size;
   
-   AstarNode *getNewNode( void );
-   void releaseNode( AstarNode *node );
-   void resetNodeList( void );  
-   void initializeNodeList( unsigned long initial_size );
+       AstarNode *getNewNode( void );
+       void releaseNode( AstarNode *node );
+       void resetNodeList( void );  
+       void initializeNodeList( unsigned long initial_size );
 
-   AstarNode *free_list_ptr;
-   bool dynamic_node_management_flag;
+       AstarNode *free_list_ptr;
+       bool dynamic_node_management_flag;
   
-  protected:
-   unsigned long mapXYtoAbsloc( iXY map_loc );
+protected:
+       unsigned long mapXYtoAbsloc( iXY map_loc );
    
+       AstarNode current_node;
+       AstarNode goal_node;
+       AstarNode *best_node;
+ 
+       std::priority_queue<AstarNode*, 
+                                               std::vector<AstarNode*>,
+                                               AstarNodePtrCompare> open;
 
-   AstarNode current_node;
-   AstarNode goal_node;
-   AstarNode *best_node;
-  
-   PPriorityQueue open;
-
-   BitArray open_set;
-   BitArray closed_set;
+       BitArray open_set;
+       BitArray closed_set;
 
-   // ** For pathing debugging **
-   BitArray astar_set_array;
-   bool sample_set_array_flag;
-   bool start_sampling_flag;
-   bool debug_mode_flag;        
+       // ** For pathing debugging **
+       BitArray astar_set_array;
+       bool sample_set_array_flag;
+       bool start_sampling_flag;
+       bool debug_mode_flag;    
    
-   unsigned long steps;
-   unsigned long step_limit;
-   unsigned long total_steps;
+       unsigned long steps;
+       unsigned long step_limit;
+       unsigned long total_steps;
   
-   float total_pathing_time;
+       float total_pathing_time;
 
-   long heuristic_weight;                // factor for heuristic   f = g() + w 
* h() 
+       long heuristic_weight;                // factor for heuristic   f = g() 
+ w * h() 
 
-   bool        succ_swap_flag;
-   unsigned short path_type_flag;
-   bool        ini_flag;
+       bool        succ_swap_flag;
+       unsigned short path_type_flag;
+       bool        ini_flag;
   
+       PathRequest *path_request_ptr;
+       unsigned short path_merge_type;
    
-   PathRequest *path_request_ptr;
-   unsigned short path_merge_type;
-   
-   void initializePath( iXY &start, iXY &goal, unsigned short path_type );
-    
-   long heuristic( iXY &pointA, iXY &pointB );
+       void initializePath( iXY &start, iXY &goal, unsigned short path_type );
+       
+       long heuristic( iXY &pointA, iXY &pointB );
  
-   unsigned char generateSucc( unsigned short direction, AstarNode *node, 
AstarNode *succ ); 
-
-   bool process_succ( PathList *path, int *result_code );
-
-  public:
+       unsigned char generateSucc( unsigned short direction, AstarNode *node,
+                                                               AstarNode *succ 
); 
 
-   Astar( void );
+       bool process_succ( PathList *path, int *result_code );
+public:
+   Astar();
   
    void initializeAstar( unsigned long node_list_size,
                          unsigned long step_limit,
@@ -150,20 +163,20 @@
 
    void initializeAstar( unsigned long node_list_size );
 
-   void initializeAstar( void );
+   void initializeAstar();
  
    bool generatePath( PathRequest *path_request, 
                          unsigned short path_merge_type, 
                          bool dynamic_node_managment,
                          int *result_code );
    
-   void cleanUp( void );
+   void cleanUp();
    
    void setDebugMode( bool on_off );
 
-   void sampleSetArrays( void );
+   void sampleSetArrays();
    
-   BitArray * getSampledSetArrays( void );
- };
+   BitArray * getSampledSetArrays();
+};
 
 #endif // ** _ASTAR_HPP