玩家需要走的寻路路径，Qt中的c++

Question

我正在尝试实现A*算法，以找到到达目的地的最快路径。当目的地离玩家不远时，我可以找到路径。但是当我站在离球员很远的位置时，就会冻住了。有人能帮我解决这个问题吗？反正也找不到。

int Controller::findPathfindingNodes(int xdes, int ydes)
{
    std::vector<std::shared_ptr<Tile>> tiles = model->getAllLimitTiles(); //all the tiles where we can move
    std::shared_ptr<Protagonist> prota = model->getAllProtagonist(); //get data from protagonist
    int currentX = prota->getXPos(); //get xpos of prota
    int currentY = prota->getYPos(); //get ypos of prota

    openList.clear();
    closedList.clear();
    mylist.clear();

    //return 50;
    std::shared_ptr<Tile> endPoint = model->getCoordinate(QPointF(xdes,ydes));
    std::shared_ptr<Tile> startPoint = model->getCoordinate(QPointF(currentX,currentY));
    int sumtotal = abs((currentX - xdes) + (currentY - ydes));

    //we insert our start position, we have no parrent yet
    PathFinding* start = new PathFinding(startPoint,currentX, currentY, 0, sumtotal,nullptr);
    //this value we insert in our openList
    openList.insert(start->getXCoord() + (model->getCols()+1)*start->getYCoord(), start);

    bool pathFound = false;
    int i = 0;
    int pathcost;
    //do whil path is found
    while(!pathFound){
        QHashIterator<int, PathFinding*> iterator(openList);
        PathFinding* parent;
        iterator.next();
        parent = iterator.value();
        //we take the next tile, and we take the one with the lowest value
        while(iterator.hasNext()){
            iterator.next();
            //checking lowest f value
            if((iterator.value()->getGcost() + iterator.value()->getHcost()) < (parent->getGcost() + parent->getHcost())){
                parent = iterator.value();
            }
        }
        //here we check if we are at the destionation. if we are we return our pathcost.
        if(atDestionation(parent,endPoint)){
            pathFound = true;
            while(parent->hasParent()){
                 mylist.append(parent);
                 parent = parent->getParent();
            }

            //we calculate what the pathcost is and return it
            pathcost = calculatePathCost(mylist);
            return pathcost;
        }else{
            int parent_x = parent->getXCoord();
            int parent_y = parent->getYCoord();
            i++;
            clearLists(parent);
            filllists(parent,endPoint);
        }
     }
}

要将节点的值放在打开和关闭的列表中，我需要这样做：

void Controller::filllists(PathFinding *parent,std::shared_ptr<Tile> endPoint)
{

    int xPosNode = parent->getXPos();
    int yPosNode = parent->getYPos();
    //while found location
    for(int x = -1; x < 2; x++) {
        for(int y = -1; y <2; y++) {
            int p_x = xPosNode + x;
            int p_y = yPosNode + y;
             // Is this coordinate within the world?
             if(p_x >= 0 && p_x < model->getCols() && p_y >= 0 && p_y < model->getRows()) {
                 //we check if the tile exist (if it's no infinity tile)
                 if(model->tileExist(QPointF(p_x,p_y))){
                     // Already in open list > Check if current node is a better parent
                     if((!openList.value(p_x))+ (model->getCols() + 1)*(p_y)){
                         // Not in open and not in closed list > Possible candidate
                         if((!closedList.value(p_x))+ (model->getCols() + 1)*(p_y)){
                             int h_value = calculateHvalue(parent->getXCoord(),parent->getYCoord(),endPoint->getXPos(),endPoint->getYPos());
                             //int g_value = parent->getGcost() + calculateTileCost(parent->getXCoord(),parent->getYCoord(),p_x,p_y);
                             int g_value = calculateGvalue(parent, p_x,  p_y);
                             std::shared_ptr<Tile> tile = model->getCoordinate(QPointF(p_x,p_y));
                             PathFinding* move = new PathFinding(tile,p_x, p_y, g_value, h_value, parent);
                             int number = move->getXCoord() + (model->getCols()+1)*move->getYCoord();
                             openList.insert(move->getXCoord() + (model->getCols()+1)*move->getYCoord(), move);
                         }
                     }
                 }
            }
        }
    }
}

我的头文件看起来如下：

class Controller : public QObject
{
    Q_OBJECT
public:
    Controller(std::shared_ptr<Model> &modelPtr,std::shared_ptr<View> &viewPtr);
   // void checkTile(QString position,PathFinding *parent, std::shared_ptr<Tile> endPoint, int pos);
    void checkAboveTile(PathFinding *parent, std::shared_ptr<Tile> endPoint, int pos);
    void checkBelowTile(PathFinding *parent, std::shared_ptr<Tile> endPoint, int pos);
    void checkLeftTile(PathFinding *parent,  std::shared_ptr<Tile> endPoint, int pos);
    void checkRightTile(PathFinding *parent, std::shared_ptr<Tile> endPoint, int pos);
    bool atDestionation(PathFinding *parent, std::shared_ptr<Tile> endPoint);
    float calculateTileCost(int xposnew,int yposnew, int xpos, int ypos);
    int calculateHvalue(int p_x,int p_y, int des_x, int des_y);
    int calculateGvalue(PathFinding *parent, int x, int y);
    void filllists(PathFinding *parent, std::shared_ptr<Tile> endPoint);

    //QPair<QList<QPointF>, float> generatePath(Tile* endPoint);
    //Openlist contains the nodes to be examined
    QHash <int, PathFinding *> openList;
    //ClosedList has the nodes that are already examined
    QHash <int, PathFinding *> closedList;
    QList<QPointF> pathlist;
    void clearLists(PathFinding *parent);
    QList<PathFinding*> mylist;
    int calculatePathCost(QList<PathFinding*> mylist);
    int findPathfindingNodes(int xdes, int ydes);

private:
    std::shared_ptr<Model> model;
    std::shared_ptr<View> view;
    int heurCost;
signals:
    void atDestination(int xPos,int yPos);
    void gotoview(int xPos,int yPos);
public slots :
    void goToDestination(int xDestination, int yDestination);


};

#endif // CONTROLLER_H

当我试图输出所走过的路径时，我可以看到，它有时会在我的列表中放置相同的位置。

X1 value : 2 Y1 value : 3 
X1 value : 1 Y1 value : 3 
X1 value : 0 Y1 value : 3 
X1 value : 1 Y1 value : 3 
X1 value : 1 Y1 value : 3 
X1 value : 2 Y1 value : 3 
X1 value : 2 Y1 value : 4 
X1 value : 3 Y1 value : 4 
X1 value : 3 Y1 value : 4 
X1 value : 3 Y1 value : 5 
X1 value : 2 Y1 value : 6 
X1 value : 2 Y1 value : 6 
X1 value : 1 Y1 value : 6 
X1 value : 0 Y1 value : 6 
X1 value : 0 Y1 value : 7 
X1 value : 0 Y1 value : 6 
X1 value : 0 Y1 value : 5 

这就是玩家走路的方式，可以看出他有时会再次使用相同的父母。

Answer 1

1. 我看不到您将访问过的节点从开放列表移动到封闭列表的任何位置。 这将解释多次访问同一个地方的原因。
2. if((!openList.value(p_x)) + (model->getCols() + 1)*(p_y))很可能是真的。 (向(model->getCols() + 1)*p_y添加0或1可能不是零。) 我相信你是指if(!openList.value(p_x + (model->getCols() + 1)*p_y))。 (已关闭的列表也有相同的问题) 这也会导致多次访问，因为您在打开的列表中多次插入相同的节点。

我建议将指数计算抽象出来：

int index(shared_ptr<Model> model, int x, int y)
{
    return x * (model->getCols() + 1)* y;
}

并使用它来代替容易出错的代码再现，例如。

openList.insert(index(model, start->getXCoord(), start->getYCoord()), start);
// ...
if(!openList.value(index(model, p_x, p_y)))

在此过程中添加跟踪输出也是个好主意。