Cocos2d-x 寻路算法之二 离目的地的距离优先

概述转自--->Waiting For You：http://www.waitingfy.com/archives/831 1.介绍：   Figure 1   接上一篇《Cocos2d-x 寻路算法之一 距离优先》，看这个图，我们发现这个寻路算法有点傻，明明终点在右侧却每个方向都找。难道没有其他办法了吗？从现实生活中我们知道东西如果在东边，当然是往东边搜索才是最好的办法。     2.开始动手  

转自--->Waiting For You：http://www.waitingfy.com/archives/831

1.介绍：

figure 1

接上一篇《Cocos2d-x 寻路算法之一 距离优先》，看这个图，我们发现这个寻路算法有点傻，明明终点在右侧却每个方向都找。难道没有其他办法了吗？从现实生活中我们知道东西如果在东边，当然是往东边搜索才是最好的办法。

2.开始动手

figure 2

计算机中如何表示离目标近呢？ 用图来解释就是这样的，目标在右上角，我们往右走，从X轴的角度来说离目标又近了一步，同理往上走是在Y轴上里目标近一步。最好的一步应该是图中-2的点，X轴和Y轴同时离目标近了一步。简单地转换成代码就是下面的这样：

?

1 2 3 4 5 6 7 8 9

bool comparebyWhichNearerGoalSimpleWay(Cell *c1,Cell *c2){ int distanceOfC1AndGoal = abs (g_goalX - c1->getX()) + (g_goalY - c1->getY()); distanceOfC2AndGoal = (g_goalX - c2->getX()) + (g_goalY - c2->getY()); if (distanceOfC1AndGoal <= distanceOfC2AndGoal){ return false ; @H_404_112@ } else { true ; } }

扔到heap的比较条件中我们轻易地就实现了按照离目标距离优先的寻路算法，startPathFinding整个方法都不要改，只需要传进去上面提到的比较方法就行了。

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 @H_419_221@ 45 46 47 48 49 typedef bool (*compareTwoCells)(Cell *c1,Cell *c2); voID HelloWorld::startPathFinding(compareTwoCells compareMethod, startX,monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important"> startY,monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important"> goalX,monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important"> goalY){ Cell *startCell = _m_Map.Get(startX,startY); vector<Cell*> vecCells; vecCells.push_back(startCell); @H_404_112@ make_heap(vecCells.begin(),vecCells.end(),compareMethod); startCell->setMarked( true ); Cell *NowProcessCell; while (vecCells.size() != 0){ pop_heap(vecCells.begin(),compareMethod); NowProcessCell = vecCells.back(); vecCells.pop_back(); (NowProcessCell->getX() == _goalX && NowProcessCell->getY() == _goalY){ //the goal is reach return ; } for ( i = 0; i < 8; ++i){ //check eight direction indexX = NowProcessCell->getX() + DIRECTION[i][0]; indexY = NowProcessCell->getY() + DIRECTION[i][1]; (indexX >= 0 && indexX < xlineCount && indexY >= 0 && indexY < ylineCount && _m_Map.Get(indexX,indexY)->getpassable() == ){ //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 (cell->getMarked() == false ){ cell->setMarked( ); 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(),compareMethod); @H_387_404@ { // if find a lower distance,update it (beforedistance < cell->getdistance()){ cell->setdistance(beforedistance); cell->setLastX(NowProcessCell->getX()); cell->setLastY(NowProcessCell->getY()); //distance change,so make heap again } } } } } } startPathFinding(comparebyWhichNearerGoalSimpleWay,_playerX,_playerY,_goalX,_goalY); //demo

3.离目的地的距离优先效果图：

figure 3

我们惊奇地发现似乎我们成功了，就用了9步就找到了目的地！

4.算法改进

从图2中我们用的是X轴和Y轴上的相对距离，并不是真正的物理距离，意识到这个问题我们马上修改了比较函数。物理距离当然容易算了，公式如下：

换成C++函数就是下面的样子：

15 distanceBetweenTwoCells( c1X,monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important"> c1Y,monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important"> c2X,monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important"> c2Y){ return sqrt ( pow (c2X - c1X,2) + (c2Y - c1Y,2)); } @H_404_112@ comparebyWhichNearerGoalPhysicWay(Cell *c1,Cell *c2){ distanceOfC1AndGoal = distanceBetweenTwoCells(( )c1->getX(),( )c1->getY(),monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important">)g_goalX,monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important">) g_goalY); distanceOfC2AndGoal = distanceBetweenTwoCells(( )c2->getX(),monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important">)c2->getY(),monospace!important; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; wIDth:auto!important; min-height:inherit!important; background:none!important">) g_goalY); (distanceOfC1AndGoal <= distanceOfC2AndGoal){ ; { ; } 演示了下发现没有什么变化。但我们知道我们变的更好了。

5.该算法存在的问题

1.很容易想到的一个问题是，它没有考虑权重！如果目标在右侧，而右侧是一条非常难走的路，那么这个算法将毫无顾虑地走过去，丝毫不考虑就在不远处有条非常轻松的路。下面这个图就可以说明这个问题。

2.还有个问题，即使没有权重Cell的存在，只有可通过和不可通过Cell的存在，这个算法也有问题，我们可以人为地制造一个陷阱，虽然目标在起点的下方，但是上面有条更近的路，这个算法应该会愚蠢地在往下找吧，这个就跟人一样，有时候目光短浅。下图是演示结果。

对比之前的算法发现其实上面的这条路更好的，虽然它查询了大量的Cell才发现这点(人家很努力的好不好)。

看看还有什么更好的办法没有？期待下篇的寻路算法吧。

6.项目下载

(请用7z解压，开发工具vs2010)

http://www.waitingfy.com/?attachment_id=828

http://www.waitingfy.com/?p=831

A*算法应用可以看下这篇文章《贪吃蛇 AI 的实现 snake AI》

总结

以上是内存溢出为你收集整理的Cocos2d-x 寻路算法之二 离目的地的距离优先全部内容，希望文章能够帮你解决Cocos2d-x 寻路算法之二 离目的地的距离优先所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/web/1060990.html