Cocos2d-x 寻路算法之一 距离优先

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

1.效果图

寻路这块在游戏中一直很重要，花了点时间研究了下这个问题，主要参考的是《Data Structures For Game Programmers》，其他的算法用普通Console演示就行了，寻路算法还是用一个界面比较好，最近在学Cocos2d-x，就用它了。用到Cocos2d-x中的基本画线段，画矩形就行了，还有简单的sprite拖动。这demo建了一个线条类，继承CCNode，重写draw方法就行了。在draw方法中简单地调用ccDrawColor4F函数来设置颜色，ccDrawLine来画线条，非常容易，cocos2d-x这些函数封装了opengles中的原始函数，使用非常简单。sprite拖动可以参考这篇文章《cocos2d-x Touch 事件应用的一个例子 》

1.小人和红色X都可以用鼠标移动，移到上面的地图上，表示寻路起点和终点。

2.Distance,Simple Heuristic,Complex Heuristic,A Star分别是4种寻路算法，点击程序就会开始演示寻路过程。

3.地图的格子点击会加深颜色，总共4个等级，白，灰，深灰，黑，表示该格子的通过难度，白色是1，灰是2，深灰是3，黑色是不可通过区域。

4.”+++”表示加快演示速度，”—”表示降低演示速度。

2. Breadth – First Search算法

顾名思义，有点像呼吸，一层层地扩展开来，这个时候队列(Queue)，stl中的deque就派上用场了。deque不懂可以参考这篇文章《C++ Queue Example Rearranging RailRoad Cars》

起点在中心，会先访问它的第一个外圈，再是第二个。现在我觉得它更像一颗石头扔在水面上的效果。

下面是伪代码：

BreadthFirst( Node )

Queue.Enqueue( Node )Mark( Node )

While( Queue.IsNotEmpty )

Process( Queue.Front )

For Each Child of Queue.Front

if NotMarked( Child )

Queue.Enqueue( Child )

Mark( Child )

end if

end For

Queue.Dequeue()

End While

End Function

遍历一个树或者图都可以用这个方法。在我们这里遇到了点麻烦，因为我们都知道斜角的距离是根号2的倍数，要比上下左右方向远，因为寻路，很重要的因素的距离的长短。我们需要考虑距离这个因素了。

3.Distance – First Search

起点还在中心，这张图显示了每一格到中心的估算距离。如果依靠距离优先的算法，下图是寻路次序：

所以我们定义了一个方向数组：

const int DIRECTION[8][2]={

{0,1},//north

{1,0},//east

{-1,//west

};

这样通过一个for循环，就可以访问它周围一圈的格子了，而且是按照距离优先了，上下左右优先，斜角次些。

因为是地图，我们这里简单定义了一个2维数组，非常简单用一个vector就可以模拟了，假定读者熟悉stl中的vector和C++中的template，不熟悉可以参考这篇文章《STL Vector》和《C++ 基础之 “模版函数”,”类模版”》

我们还定义了一个Cell类表示每一个格子：它有很多属性，像位置，最短距离到这个Cell的Cell的位置，是否已经处理过，到起点的距离，是否可以通过，还有就是这个Cell的权重，表示经过难度。我们这里使用了一个从cocos2d-x中拷来的宏，这样get和set方法就不用手写了。