转自--->Waiting For You:http://www.waitingfy.com/archives/831
1.介绍:
Figure 1
接上一篇《Cocos2d-x 寻路算法之一 距离优先》,看这个图,我们发现这个寻路算法有点傻,明明终点在右侧却每个方向都找。难道没有其他办法了吗?从现实生活中我们知道东西如果在东边,当然是往东边搜索才是最好的办法。
2.开始动手
Figure 2
计算机中如何表示离目标近呢? 用图来解释就是这样的,目标在右上角,我们往右走,从X轴的角度来说离目标又近了一步,同理往上走是在Y轴上里目标近一步。最好的一步应该是图中-2的点,X轴和Y轴同时离目标近了一步。简单地转换成代码就是下面的这样:
扔到heap的比较条件中我们轻易地就实现了按照离目标距离优先的寻路算法,startPathFinding整个方法都不要改,只需要传进去上面提到的比较方法就行了。
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@
Cell *nowProcessCell; @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@
} @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@
cell->setLastX(nowProcessCell->getX()); @H_403_70@
cell->setLastY(nowProcessCell->getY()); @H_403_70@
cell->setDistance(beforeDistance); @H_403_70@
push_heap(vecCells.begin(),compareMethod); @H_403_70@
{@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@
startPathFinding(comparebyWhichNearerGoalSimpleWay,_playerX,_playerY,_goalX,_goalY);@H_403_70@
//demo@H_403_70@