jeudi 14 janvier 2021

Probleme A Star in C++

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