文 / 易水寒

　　接两篇文章：《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. }

　　特点：可以找到目标，但搜索Cell太多。

　　3.2 只考虑离目标距离


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

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


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

　　4.A Star动态gif演示图


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

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

　　相关阅读：a寻路算法(for 初学者)

锐亚教育，游戏开发论坛|游戏制作人|游戏策划|游戏开发|独立游戏|游戏产业|游戏研发|游戏运营| unity|unity3d|unity3d官网|unity3d 教程|金融帝国3|8k8k8k|mcafee8.5i|游戏蛮牛|蛮牛 unity|蛮牛