Cocos2d-x ??????????A Star

??

??? / ???

?????????Cocos2d-x ?????????? ???????Cocos2d-x ?????????? ??????????

??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.????

1. float distanceBetweenTwoCells(float c1X,float c1Y, float c2X, float c2Y){
   
2. 
   
3.     return sqrt(pow(c2X - c1X,2) + pow(c2Y - c1Y,2));
   
4. }
   
5. bool comparebyDistanceBetweenStartAndGoal(Cell *c1, Cell *c2){
   
6.     float distanceOfC1AndGoal = c1->getDistance() +
   
7.         distanceBetweenTwoCells((float)c1->getX(),(float)c1->getY(),(float)g_goalX,(float) g_goalY);
   
8. 
   
9.     float distanceOfC2AndGoal = c2->getDistance() +
   
10.         distanceBetweenTwoCells((float)c2->getX(),(float)c2->getY(),(float)g_goalX,(float) g_goalY);
    
11.     if(distanceOfC1AndGoal <= distanceOfC2AndGoal){
    
12.         return false;
    
13.     }else{
    
14.         return true;
    
15.     }
    
16. }

复制代码

?????????????????????heap????????startPathFinding????????????startPathFinding???

1. typedef bool (*compareTwoCells)(Cell *c1, Cell *c2);     
   
2. void HelloWorld::startPathFinding(compareTwoCells compareMethod, int startX,int startY,int goalX,int goalY){   
   
3.     Cell *startCell = _m_Map.Get(startX, startY);   
   
4.     vector<Cell*> vecCells;   
   
5.     vecCells.push_back(startCell);   
   
6.     make_heap(vecCells.begin(),vecCells.end(),compareMethod);   
   
7.     startCell->setMarked(true);   
   
8.     Cell *nowProcessCell;   
   
9. 
   
10.     while(vecCells.size() != 0){   
    
11.         pop_heap(vecCells.begin(),vecCells.end(),compareMethod);   
    
12.         nowProcessCell = vecCells.back();   
    
13.         vecCells.pop_back();   
    
14. 
    
15.         if(nowProcessCell->getX() == _goalX && nowProcessCell->getY() == _goalY){//the goal is reach   
    
16.             return;   
    
17.         }   
    
18. 
    
19.         for(int i = 0; i < 8; ++i){ //check eight direction   
    
20. 
    
21.             int indexX = nowProcessCell->getX() + DIRECTION[i][0];   
    
22.             int indexY = nowProcessCell->getY() + DIRECTION[i][1];   
    
23. 
    
24.             if(indexX >= 0 && indexX < xLineCount && indexY >= 0 && indexY < yLineCount   
    
25.                 && _m_Map.Get(indexX,indexY)->getPassable() == true){//check is a OK cell or not   
    
26.                     Cell *cell = _m_Map.Get(indexX,indexY);   
    
27.                     float beforeDistance = DISTANCE[i] * cell->getWeight() + _m_Map.Get(nowProcessCell->getX(),   
    
28.                         nowProcessCell->getY())->getDistance();//calculate the distance   
    
29.                     if(cell->getMarked() == false){     
    
30.                         cell->setMarked(true);   
    
31.                         cell->setLastX(nowProcessCell->getX());   
    
32.                         cell->setLastY(nowProcessCell->getY());   
    
33.                         cell->setDistance(beforeDistance);   
    
34.                         vecCells.push_back(cell);//only push the unmarked cell into the vector   
    
35.                         push_heap(vecCells.begin(),vecCells.end(),compareMethod);   
    
36.                     }else{// if find a lower distance, update it     
    
37.                         if(beforeDistance < cell->getDistance()){   
    
38.                             cell->setDistance(beforeDistance);   
    
39.                             cell->setLastX(nowProcessCell->getX());   
    
40.                             cell->setLastY(nowProcessCell->getY());   
    
41.                             make_heap(vecCells.begin(),vecCells.end(),compareMethod);//distance change,so make heap again   
    
42.                         }   
    
43.                     }   
    
44.             }   
    
45. 
    
46.         }   
    
47.     }   
    
48. }   
    
49. startPathFinding(comparebyDistanceBetweenStartAndGoal,_playerX,_playerY,_goalX,_goalY);//A star path finding demo

复制代码

??????????

??3.???????????

??3.1?????????????Breadth-First

???????????????Cell???

??3.2 ????????

???????Cell??????????????????????

??3.3 A Star ??????????????

????????????????Cell???????????????????????????

??4.A Star??gif???

??????????GIF?????

??PS?Cocos2d-x A Star ????????

???????a????(for ???)