转自--->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++ 基础之 “模版函数”,”类模版”》
1
2
3
4
5
6
7
8
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
|
#ifndef ARRAY2D_H
#define ARRAY2D_H
#include <vector>
using
namespace
std;
template
<
class
Datatype>
Array2D{
public
:
Array2D(
int
p_width,
p_height):m_array(p_width * p_height),
m_width(p_width),m_height(p_height){
}
Datatype* Get(
p_x,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"> p_y)
const
{
return
m_array[p_y * m_width + p_x];
}
void
Set(
p_y,Datatype* data){
m_array[p_y * m_width + p_x] = data;
}
Size()
{
m_width * m_height;
}
Width()
{
m_width;
}
Height()
{
m_height;
}
private
:
vector<Datatype*> m_array;
m_width;
m_height;
};
#endif
|
我们还定义了一个Cell类表示每一个格子:它有很多属性,像位置,最短距离到这个Cell的Cell的位置,是否已经处理过,到起点的距离,是否可以通过,还有就是这个Cell的权重,表示经过难度。我们这里使用了一个从cocos2d-x中拷来的宏,这样get和set方法就不用手写了。
#define _CELL_H
#define SYNTHESIZE(varType,varName,funName)\
protected
: varType varName;\
:
virtual
varType get##funName(
)
{
varName; }\
virtual
void
set##funName(varType var){ varName = var; }
Cell{
Cell():_marked(
false
),_distance(0),_lastX(-1),_lastY(-1),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">_x(-1),_y(-1),_passable(
true
){
}
SYNTHESIZE(
,_x,X);
//start at left bottom
//start at left bottom
//store the nearest cell's location related this cell
//store the nearest cell's location related this cell
bool
//whether this cell process or not
float
//distance between this cell and start
//whether this call can pass
//just for draw the path finding progress
inline
setWeight(
weight){
if
(weight > 4){
_weight = 1;
}
else
_weight = weight;
setPassable(weight == 4 ?
:
);
}
}
inline
int
getWeight()
{
_weight;}
:
_weight;
//default is 1,4 means this cell is impassable.
//distance have relationship with weight
};
核心算法如下:事先需要了解的知识:因为我们需要按照最短距离优先寻路,所以一个优先队列就需要了,这里简单地使用了heap,对heap不了解的可以看下这篇文章《HeapSort(堆排序 C++) 》,下面还用上了C++中的函数指针,可以参考这篇文章《C++ 函数指针 函数名作为参数 》,为什么要用函数指针呢?看完整个寻路算法系列你就知道了。
语言解释:
先把起点Cell加入到heap中,对这个Cell的周围8个Cell进行处理,主要是更新他们到起点的距离和记录最短距离到这个Cell的Cell的位置。每次找到一个新的Cell,
1.如果还没处理过,标上处理过标志,更新他们到起点的距离和记录最短距离到这个Cell的Cell的位置,再把这个Cell加入到堆中,重新形成一个堆,这样开始很容易得到离起点最近的点。
2.如果处理过,看下新的距离是不是比老的距离短,如果短,更新上面的提到的两点。
不断处理,直到访问了所有的点或者找到终点了。
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef
bool
(*compareTwoCells)(Cell *c1,Cell *c2);
compareTwoCellsByDistance(Cell *c1,Cell *c2){
(c1->getDistance() <= c2->getDistance()){
return
false
;
{
true
;
}
}
HelloWorld::startPathFinding(compareTwoCells compareMethod,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"> 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);
make_heap(vecCells.begin(),vecCells.end(),compareMethod);
startCell->setMarked(
);
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
;
}
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);
beforeDistance = DISTANCE[i] * cell->getWeight() + _m_Map.Get(nowProcessCell->getX(),
nowProcessCell->getY())->getDistance();
//calculate the distance
(cell->getMarked() ==
){
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);
{
// 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(compareTwoCellsByDistance,_playerX,_playerY,_goalX,_goalY);
//demo