Cocos2d-x 寻路算法解析(三):A Star

发表于2016-01-27
评论0 1.5k浏览
       1.A Star 寻路算法介绍:
       看过前面两篇文章的读者知道,这两种寻路算法都有问题,前一个搜索太广了,资源浪费;后一个还不够聪明,有时候会找不到最佳路线。因为A Star 寻路算法就是前面两者的结合。同时考虑离起点的距离和离终点的距离。


  究竟是C1还是C2这个格子是最佳路线点呢?因为我们这次离起点的距离和离终点的距离都考虑了,所以C1的价值是1.0 + 1.41 + 4.12 总共 6.53的长度。而C2的价值是 2.0 + 6.32 总共 8.32的长度。显然C1更佳。如果按照我们第一个寻路算法,只考虑离起点距离的话,C2还短些呢!但C2离终点远啊。

  2.代码实现
float distanceBetweenTwoCells(float c1X,float c1Y, float c2X, float c2Y){
return sqrt(pow(c2X - c1X,2) + pow(c2Y - c1Y,2));
}
bool comparebyDistanceBetweenStartAndGoal(Cell *c1, Cell *c2){
float distanceOfC1AndGoal = c1->getDistance() + 
distanceBetweenTwoCells((float)c1->getX(),(float)c1->getY(),(float)g_goalX,(float) g_goalY);
float distanceOfC2AndGoal = c2->getDistance() + 
distanceBetweenTwoCells((float)c2->getX(),(float)c2->getY(),(float)g_goalX,(float) g_goalY);
if(distanceOfC1AndGoal <= distanceOfC2AndGoal){
return false;
}else{
return true;
}
}
       
       只要加上这个方法就行了,把这个方法作为heap的比较条件。整个startPathFinding都不需要改,这里再次给出startPathFinding代码:
typedef bool (*compareTwoCells)(Cell *c1, Cell *c2);     
void HelloWorld::startPathFinding(compareTwoCells compareMethod, int startX,int startY,int goalX,int goalY){    
    Cell *startCell = _m_Map.Get(startX, startY);    
    vector<Cell*> vecCells;    
    vecCells.push_back(startCell);    
    make_heap(vecCells.begin(),vecCells.end(),compareMethod);    
    startCell->setMarked(true);    
    Cell *nowProcessCell;    
 
    while(vecCells.size() != 0){    
        pop_heap(vecCells.begin(),vecCells.end(),compareMethod);    
        nowProcessCell = vecCells.back();    
        vecCells.pop_back();    
 
        if(nowProcessCell->getX() == _goalX && nowProcessCell->getY() == _goalY){//the goal is reach    
            return;    
        }    
 
        for(int i = 0; i < 8; ++i){ //check eight direction    
 
            int indexX = nowProcessCell->getX() + DIRECTION[i][0];    
            int indexY = nowProcessCell->getY() + DIRECTION[i][1];    
 
            if(indexX >= 0 && indexX < xLineCount && indexY >= 0 && indexY < yLineCount    
                && _m_Map.Get(indexX,indexY)->getPassable() == true){//check is a OK cell or not    
                    Cell *cell = _m_Map.Get(indexX,indexY);    
                    float beforeDistance = DISTANCE[i] * cell->getWeight() + _m_Map.Get(nowProcessCell->getX(),    
                        nowProcessCell->getY())->getDistance();//calculate the distance    
                    if(cell->getMarked() == false){     
                        cell->setMarked(true);    
                        cell->setLastX(nowProcessCell->getX());    
                        cell->setLastY(nowProcessCell->getY());    
                        cell->setDistance(beforeDistance);    
                        vecCells.push_back(cell);//only push the unmarked cell into the vector    
                        push_heap(vecCells.begin(),vecCells.end(),compareMethod);    
                    }else{// if find a lower distance, update it     
                        if(beforeDistance < cell->getDistance()){    
                            cell->setDistance(beforeDistance);    
                            cell->setLastX(nowProcessCell->getX());    
                            cell->setLastY(nowProcessCell->getY());    
                            make_heap(vecCells.begin(),vecCells.end(),compareMethod);//distance change,so make heap again    
                        }    
                    }    
            }    
 
        }    
    }    
}    
startPathFinding(comparebyDistanceBetweenStartAndGoal,_playerX,_playerY,_goalX,_goalY);//A star path finding demo
函数指针太酷了!

  3.三种寻路算法的图片比较

  3.1只考虑距离起点的距离,采用Breadth-First


  特点:可以找到目标,但搜索Cell太多。

  3.2 只考虑离目标距离


  特点:搜索Cell大多情况会相对少些,但不一定能找到最短路线。

  3.3 A Star ,同时考虑到起点和终点的距离

Cocos2d-x 寻路算法解析(三):A Star


  特点:能找到最短路线,搜索的Cell比第一种要少,看最后的搜索方式,也有第二种搜索的智慧。

  4.A Star动态gif演示图

Cocos2d-x 寻路算法解析(三):A Star


  不知道为什么我对GIF这么热衷。

  PS:Cocos2d-x A Star 源码下载见原文。

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引