c++ - 为什么A星计算路径每次都和上次不一样

Question

怎么我的A星每次计算出来的路径 都和上次不同的。
起点和 终点都是一样的。

已解决 ...原来是STL的sort 排序出问题了。
不能用类中重载 的 < or () 要在类外写个 函数 并加在sort 参数三中。

 int AStarClass::serachPath(){
    
    //  leftup
    //  left
    //  leftdown
    //  up
    //  down
    //  rightup
    //  right
    //  rightdown
    
    bool findPaht = false;
    
    //  8 direction position
    int dir[8][2] = {
        {-1,-1},
        {-1,0},
        {-1,1},
        {0,-1},
        {0,1},
        {1,-1},
        {1,0},
        {1,1}
    };
    // startPoint add openlist
    _OpenList.push_back(_StartPoint);
    
    unsigned long timer = clock();

    while (!_OpenList.empty()) {
        
        auto CureentNode = *_OpenList.begin();
        
        _OpenList.erase(_OpenList.begin());

        _CloseList.push_back(CureentNode);
        
        if (CureentNode->x == _EndPoint->x
            && CureentNode->y == _EndPoint->y) {
            findPaht = true;
            //  recursion get path
            getPath(CureentNode);
            break;
        }
        
        auto generateNode = this->generateChildNode(*CureentNode, dir);
        int i = 0;
        for (auto &itor:generateNode) {
            int x = itor.x;
            int y = itor.y;
            AStarNode* node = NULL;
            if (_map->getAStarMap(x,y) == 1 || FindVessel(_CloseList, x, y)){
                
            } else if (_map->getAStarMap(x,y) != 1 && FindVessel(_OpenList, x, y) == false && x > -1 && y > -1){
                node = new AStarNode(x,y);
                _OpenList.push_back(node);
                node->setParent(CureentNode);
                
                int G = 0;
                G = getGValues(_StartPoint, node, i);
                int H = manhattan(node->x,node->y,_EndPoint->x,_EndPoint->y);
                
                int F = G + H;
                node->setg(G);
                node->seth(H);
                node->setf(F);
                
            } else if((node = FindVesselGet(_OpenList, x, y)) != NULL){
                int G = getGValues(CureentNode, node, i);
                if (G < node->getg()) {
                    node->setParent(CureentNode);
                    node->setg(G);
                    node->setf(node->geth() + node->getg());
                }
            }
            i++;
        }
        


        std::sort(_OpenList.begin(), _OpenList.end());
        
    }
    
    _Timer = (double)(clock() - timer) / CLOCKS_PER_SEC;
    
    if (!findPaht) {
        std::vector<AStarNode*>().swap(_OpenList);
        std::vector<AStarNode*>().swap(_CloseList);
    }
    
    return findPaht;
    
}
    
std::vector<AStarNode> AStarClass::generateChildNode(AStarNode &node,int dir[8][2]){
    std::vector<AStarNode> list;
    for (int i = 0; i < 8; i++) {
        int x = dir[i][0];
        int y = dir[i][1];
        //  synthetic position
        x += node.x;
        y += node.y;
        if ( x < _map->getAStarMapLine() && y < _map->getAStarMapCol()) {
            list.push_back(AStarNode(x,y));
        }
        
    }
    return list;
}

int AStarClass::getGValues(AStarNode *node0,AStarNode *node1,int i){
    int G = abs(node1->x - node0->x) + abs(node1->y - node0->y);
    if (i == 0 || i == 2 || i == 5 || i == 7) {
        G += 14;
    }else{
        G += 10;
    }
    return G;
}

void AStarClass::getPath(AStarNode *node){
    while(node->getParent()==NULL){
        _ResultList.push_back(node);
        return;
    }
    getPath(node->getParent());
    _ResultList.push_back(node);
}

unsigned int AStarClass::manhattan(int x,int y,int endx,int endy)
{
    return  std::abs( x  - endx )  + std::abs ( y-endy )  * 10;
}

Answer 1

已解決 ...原來是STL的sort 排序出問題了。
不能用類別中重載 的