00001 #ifndef DSTAR_H 00002 #define DSTAR_H 00003 #include <star.h> 00004 #include <node_chain.h> 00005 #include <motion_chain.h> 00006 #include <priorityqueue.h> 00007 //#include <occupancy_grid.h> 00008 //#define EDGES 8 00010 00034 class DStar : public Star 00035 { 00036 public: 00037 friend class PriorityQueue; 00038 DStar(OGrid* grid); 00040 bool search(motion_chain & path, motion start, motion goal); 00042 bool research(motion_chain & path, motion start, node_chain& changed_nodes); 00044 00046 void update_nodes(node_chain& changed_nodes); 00048 bool valid(); 00049 #ifdef DOS 00050 void dump(void); 00051 #endif 00052 private: 00053 void Update_Keys(Node*); 00054 void update_succ(int); 00055 void Initialize(); 00056 Priority CalculateKey(Node*); 00057 bool ComputeShortestPath(); 00058 void UpdateVertex(Node*); 00059 Node* MinSucc(Node* s,int& G); 00060 void GetPred(Node* u, Node* child[EDGES+1]); 00061 void GetSucc(Node* u, Node* child[EDGES+1]); 00062 Node* Min(Node* s); 00063 int MinSuccCost(Node* s); 00064 bool GetPath(motion_chain&); 00065 void InitDstar(void); 00066 PriorityQueue U; 00067 int K_m; // movement value {Ref. Sec 4.2 } 00068 Node* start; 00069 Node* goal; 00070 // int minG; 00071 protected: 00072 DStar(void); 00073 }; 00074 00075 #endif
1.3