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

前端之家收集整理的这篇文章主要介绍了Cocos2d-x 寻路算法之二 离目的地的距离优先前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

转自--->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@H_403_70@ comparebyWhichNearerGoalSimpleWay(Cell *c1,Cell *c2){@H_403_70@
@H_403_70@ int@H_403_70@ distanceOfC1AndGoal = @H_403_70@ abs@H_403_70@ (g_goalX - c1->getX()) + @H_403_70@ (g_goalY - c1->getY());@H_403_70@
distanceOfC2AndGoal = @H_403_70@ (g_goalX - c2->getX()) + @H_403_70@ (g_goalY - c2->getY());@H_403_70@
@H_403_70@ if@H_403_70@ (distanceOfC1AndGoal <= distanceOfC2AndGoal){@H_403_70@
return@H_403_70@ false@H_403_70@ ;@H_403_70@
@H_403_70@ }@H_403_70@ else@H_403_70@ {@H_403_70@
true@H_403_70@ ;@H_403_70@
}@H_403_70@
}@H_403_70@

扔到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
45
46
47
48
49
typedef@H_403_70@ bool@H_403_70@ (*compareTwoCells)(Cell *c1,Cell *c2); @H_403_70@
void@H_403_70@ HelloWorld::startPathFinding(compareTwoCells compareMethod,@H_403_70@ 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){ @H_403_70@
Cell *startCell = _m_Map.Get(startX,startY); @H_403_70@
vector<Cell*> vecCells; @H_403_70@
vecCells.push_back(startCell); @H_403_70@
make_heap(vecCells.begin(),vecCells.end(),compareMethod); @H_403_70@
startCell->setMarked(@H_403_70@ true@H_403_70@ ); @H_403_70@
Cell *nowProcessCell; @H_403_70@
while@H_403_70@ (vecCells.size() != 0){ @H_403_70@
pop_heap(vecCells.begin(),compareMethod); @H_403_70@
nowProcessCell = vecCells.back(); @H_403_70@
vecCells.pop_back(); @H_403_70@
(nowProcessCell->getX() == _goalX && nowProcessCell->getY() == _goalY){@H_403_70@ //the goal is reach @H_403_70@
return@H_403_70@ ; @H_403_70@
} @H_403_70@
for@H_403_70@ (@H_403_70@ i = 0; i < 8; ++i){ @H_403_70@ //check eight direction @H_403_70@
indexX = nowProcessCell->getX() + DIRECTION[i][0]; @H_403_70@
indexY = nowProcessCell->getY() + DIRECTION[i][1]; @H_403_70@
(indexX >= 0 && indexX < xLineCount && indexY >= 0 && indexY < yLineCount @H_403_70@
&& _m_Map.Get(indexX,indexY)->getPassable() == @H_403_70@ ){@H_403_70@ //check is a OK cell or not @H_403_70@
Cell *cell = _m_Map.Get(indexX,indexY); @H_403_70@
float@H_403_70@ beforeDistance = DISTANCE[i] * cell->getWeight() + _m_Map.Get(nowProcessCell->getX(),@H_403_70@
nowProcessCell->getY())->getDistance();@H_403_70@ //calculate the distance @H_403_70@
(cell->getMarked() == @H_403_70@ false@H_403_70@ ){ @H_403_70@
cell->setMarked(@H_403_70@ ); @H_403_70@
cell->setLastX(nowProcessCell->getX()); @H_403_70@
cell->setLastY(nowProcessCell->getY()); @H_403_70@
cell->setDistance(beforeDistance); @H_403_70@
vecCells.push_back(cell);@H_403_70@ //only push the unmarked cell into the vector @H_403_70@
push_heap(vecCells.begin(),compareMethod); @H_403_70@
@H_523_404@ {@H_403_70@ // if find a lower distance,update it @H_403_70@
(beforeDistance < cell->getDistance()){ @H_403_70@
cell->setDistance(beforeDistance); @H_403_70@
cell->setLastX(nowProcessCell->getX()); @H_403_70@
cell->setLastY(nowProcessCell->getY()); @H_403_70@
403_70@ //distance change,so make heap again @H_403_70@
} @H_403_70@
} @H_403_70@
} @H_403_70@
} @H_403_70@
} @H_403_70@
} @H_403_70@
@H_301_457@ startPathFinding(comparebyWhichNearerGoalSimpleWay,_playerX,_playerY,_goalX,_goalY);@H_403_70@ //demo@H_403_70@

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

Figure 3

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

4.算法改进

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

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

15
distanceBetweenTwoCells(@H_403_70@ 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){@H_403_70@
return@H_403_70@ sqrt@H_403_70@ (@H_403_70@ pow@H_403_70@ (c2X - c1X,2) + @H_403_70@ (c2Y - c1Y,2));@H_403_70@
}@H_403_70@
comparebyWhichNearerGoalPhysicWay(Cell *c1,Cell *c2){@H_403_70@
distanceOfC1AndGoal = distanceBetweenTwoCells((@H_403_70@ )c1->getX(),(@H_403_70@ )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);@H_403_70@
distanceOfC2AndGoal = distanceBetweenTwoCells((@H_403_70@ )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);@H_403_70@
(distanceOfC1AndGoal <= distanceOfC2AndGoal){@H_403_70@
;@H_403_70@
{@H_403_70@
;@H_403_70@
}@H_403_70@
演示了下发现没有什么变化。但我们知道我们变的更好了。

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相关文章