I just started to learn c++ at university, I have to create a pacman in c++.
I wanted to integrate the algorithm of A. Star, I tried ^^, I think I have included it well however when the distance of the target is greater than 4, he sends me the list but not with the lowest distance, I think there’s a problem with my neighbor system, but I don't know where it comes from, do you have any idea?
To proceed I looked for how the algorithm works(video, lessons) , then on the wikipedia page it has a "pseudo code" which is in algorithm
My function for find path:
void finPath(CMat &Mat, Node depart, Node target){
queue<Node> closeList;
vector<Node> vCloseList;
priority_queue<Node,vector<Node>, Comparator> openList;
vector<Node> vOpenList;
openList.push(depart);
vOpenList.push_back(depart);
while(!openList.empty()){
Node u = openList.top();
removesame(openList, vOpenList);
openList.pop();
if((u.x == target.x) && (u.y == target.y)){
//RECONSTRUC PATH
for(unsigned i(0); i<closeList.size();++i){
cout <<closeList.front().x<< " - "<<closeList.front().y<<endl;
closeList.pop();
}
displayMat(Mat);
break;
}
for(unsigned i(0); i<4; ++i){
Node v = getParent(u,i);
if (!(isInList(v,vCloseList) || isInListAndCout(v, vOpenList))){
v.cout = u.cout +1;
v.heristict = v.cout + manathan(v,target);
openList.push(v);
vOpenList.push_back(v);
}
}
closeList.push(u);
vCloseList.push_back(u);
}
}
Function for get neighbour to current Node
Node getParent(Node initial, unsigned i){
Node neighbour = {initial.x,initial.y,initial.cout,0};
/** 0 = UP 1 = RIGHT 2 = DOWN 3 = LEFT **/
if(i == 0){
if(neighbour.x-1 == 0)return neighbour;
neighbour.x -= 1;
}else if(i == 1){
if(neighbour.y+1 == 10)return neighbour;
neighbour.y += 1;
}
else if(i == 2){
if(neighbour.x+1 == 10)return neighbour;
neighbour.x += 1;
}
else if(i == 3){
if(neighbour.y-1 == 0)return neighbour;
neighbour.y -= 1;
}
neighbour.cout =initial.cout+1;
return neighbour;
}
And
struct Node{
unsigned x,y;
unsigned cout,heristict;
};
struct Comparator{
int operator()(const Node &n1, const Node &n2 )const{
if(n1.heristict < n2.heristict)return 1;
else if(n1.heristict == n2.heristict) return 0;
else return -1;
}
};
Thanks for reading
if I use start point {2,2} and target point {4,4} Pathfinding to {2,2} at {4,4}
And now if I use same start point and i define target {5,5} PathFinding {2,2} at {5,5} , Error :/
Aucun commentaire:
Enregistrer un commentaire