00001 /***************************************************************************************************/ 00002 /***************************************************************************************************/ 00008 /***************************************************************************************************/ 00009 /***************************************************************************************************/ 00010 #ifndef A_STAR_H 00011 #define A_STAR_H 00012 00013 00014 /*------------------------------------ Prototypes ---------------------------------------------*/ 00015 class cA_Star_Node; 00016 class cList_A_Star_Nodes; 00017 class cA_Star_Priority_List; 00018 class cA_Star_Search; 00019 00020 //#define DEBUG_A_STAR // si défini, l'algo envoie vers std::cout de infos sur sa progression 00021 /*------------------------------------ Includes ---------------------------------------------*/ 00022 #include <vector> 00023 #include <assert.h> 00024 #include <list> 00025 00026 #include "geo_utils.h" 00027 00028 00029 00030 /*------------------------------------- Classes ---------------------------------------------*/ 00031 00032 00033 /*************************************************************************************************/ 00035 /*************************************************************************************************/ 00036 class cList_A_Star_Nodes : public std::list<cA_Star_Node*> 00037 { 00038 public : 00040 bool Contain( cA_Star_Node* node); 00041 }; 00042 00043 00044 /*************************************************************************************************/ 00046 00048 class cA_Star_Node 00049 { 00050 public: 00052 cA_Star_Node() 00053 { 00054 Path_Parent=NULL; 00055 Cost_From_Start=0; 00056 Estimated_Cost_To_Goal=0; 00057 }; 00058 00059 cA_Star_Node * Path_Parent; 00060 float Cost_From_Start; 00061 float Estimated_Cost_To_Goal; 00062 cPoint2D Position; 00063 00065 inline float Get_Cost() 00066 { 00067 return Cost_From_Start + Estimated_Cost_To_Goal; 00068 } 00069 00071 virtual float Get_Cost( cA_Star_Node * destination) =0; 00073 virtual float Get_Estimated_Cost( cA_Star_Node * destination) =0; 00075 virtual void Get_List_Neighbors( cList_A_Star_Nodes & voisinage ) =0 ; 00076 }; 00077 00078 00079 00080 00081 /*************************************************************************************************/ 00083 /*************************************************************************************************/ 00084 class cA_Star_Priority_List : public std::list<cA_Star_Node*> 00085 { 00086 public: 00088 void Add(cA_Star_Node* new_node); 00090 bool Contain( cA_Star_Node* node); 00091 }; 00092 00093 00094 00095 /*************************************************************************************************/ 00097 00099 class cA_Star_Search 00100 { 00101 public: 00103 00107 bool Find_Path( cA_Star_Node* start , cA_Star_Node* goal , cList_A_Star_Nodes & chemin ); 00108 private: 00110 00113 void Construct_Path( cA_Star_Node* destination , cList_A_Star_Nodes & chemin ); 00114 }; 00115 00116 #endif