转自--->Waiting For You:http://www.waitingfy.com/archives/846
1.A Star 寻路算法介绍：
看过之前的两篇文章：《Cocos2d-x 寻路算法之二 离目的地的距离优先》，《Cocos2d-x 寻路算法之一 距离优先》的读者知道，这两种寻路算法都有问题，前一个搜索太广了，资源浪费；后一个还不够聪明，有时候会找不到最佳路线。为什么要先介绍这两种不佳的算法呢？因为A Star 寻路算法就是前面两者的结合。同时考虑离起点的距离和离终点的距离。
Figure 1
究竟是C1还是C2这个格子是最佳路线点呢？因为我们这次离起点的距离和离终点的距离都考虑了，所以C1的价值是1.0 + 1.41 + 4.12 总共 6.53的长度。而C2的价值是 2.0 + 6.32 总共 8.32的长度。显然C1更佳。如果按照我们第一个寻路算法，只考虑离起点距离的话，C2还短些呢！但C2离终点远啊。
2.代码实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
float
distanceBetweenTwoCells(
c1X,
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));
}
bool
comparebyDistanceBetweenStartAndGoal(Cell *c1,Cell *c2){
distanceOfC1AndGoal = c1->getDistance() +
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 = c2->getDistance() +
)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);
if
(distanceOfC1AndGoal <= distanceOfC2AndGoal){
return
false
;
}
else
{
true
;
}
}
|
只要加上这个方法就行了，把这个方法作为heap的比较条件。整个startPathFinding都不需要改，这里再次给出startPathFinding代码：
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
bool
(*compareTwoCells)(Cell *c1,Cell *c2);
void
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; color:gray!important; background:none!important">int
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(
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);
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);
{
// 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(comparebyDistanceBetweenStartAndGoal,_playerX,_playerY,_goalX,_goalY);
//A star path finding demo
