6°

A*寻路算法的个人理解

A*寻路算法是一个求两点之间的最短路径的方法

算法详情如下:

准备工作:

两个容器:   open容器和close容器

价值估算公式:    F = G + H

G:从起点移动到指定方格的移动代价;

(在实际运算时,对于G的计算在算法一开始是比较好理解的,因为你一开始获取的当前点就是起点,直接计算当前点到你相邻点的“距离”,这个距离没有特别的限制,你可以定为1,也可以定为两个点之间的H:实际距离;计算到后面,当前点不在是起点了,要计算G也很简单,直接用当前点的G值加上当前点到相邻点的“距离”即可)

H:从指定的方格移动到终点的估算成本;

(这是一个估算的距离,实际上我们并不能知道实际距离是多少,因为我们并不知道我们在前进的时候会遇到哪些阻碍物,所以可以大概的猜一个值,一般都是用这个点到终点的直线距离来代替;需要注意的是,H值和G值的差异不要太大,虽然都可以得到路径,但是差异大的话可能得到的不是最优解。比如你的G值设相邻点距离为1,H值为两个点的实际距离,这样就可能得到不是最优解的解,最好H也是以1位单位加起来的距离)

 

算法开始运行:

1.把起点加入open容器中。

2.重复如下过程:

  • 遍历 open 容器 ,查找 F 值最小的节点,把它作为当前要处理的节点。
  • 把这个节点加入 close 容器中。
  • 从 open 容器中移除这个节点。
  • 判断当前点是否是终点,如果是,找出路径;如果不是,执行下一步。
  • 找出当前点的相邻点,对每个相邻点做如下处理:
    • 如果它是不可抵达的或者它在 close 容器中,忽略它。否则,做如下操作。
    • 如果它不在 open 容器中,把它加入 open 容器,并且把当前方格设置为它的父亲,计算并记录该方格的 F ,G 和 H 值。
    • 如果它已经在 open 容器 中,检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好,用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样,把它的父亲设置为当前方格,并重新计算它的 G 和 F 值。如果你的 open 容器是按 F 值排序的话,改变后你可能需要重新排序。
  • 停止,当 open 容器为空时,结束循环。(如果循环结束还没找到路径。说明该终点无法到达)

3.保存路径。从终点开始,每个方格沿着父节点移动直至起点,这就是你的路径。

注意:可能有人会以为 close 容器中的点就是路径,其实两个容器和路径没有关系。我们在算法运行中,会给每个节点设置父节点,这个是我们寻找路径的依据;当找到终点时,我们从终点开始,根据其父节点一步一步寻找,直到找到起点,那么寻找出的这条路径就是我们需要的最短路径。

以下是我在项目中写的一个A*寻路算法的代码(cocos2d-x,容器都是CCDictionary):

void TacticalSecondMatchLayer::startFindWay(int startId, int endId)
{
    routeArr->removeAllObjects();  //用来保存路径的
    openDic->removeAllObjects();
    closeDic->removeAllObjects();
    TacticalSecondMapBlock* startBlock = (TacticalSecondMapBlock*)allBlockDic->objectForKey(startId);
    if (startBlock)
    {
        openDic->setObject(startBlock, startId);
    }
    do 
    {
        int currentTag = findMinFInOpen();   //寻找open容器中F值最小的点
        TacticalSecondMapBlock* currentBlock = (TacticalSecondMapBlock*)allBlockDic->objectForKey(currentTag);
        closeDic->setObject(currentBlock, currentTag);
        openDic->removeObjectForKey(currentTag);
        if (currentTag == endId)
        {
            constructPathFromStep(currentBlock, startId);
            clearBlockParent();
            CCLOG("find way OK");
            break;
        }
        findAdjoinBlock(currentTag, 1);    //寻找相邻点
        CCDictElement* el = NULL;
        CCDICT_FOREACH(adjoinDic, el)
        {
            CCInteger* adjoinPos = (CCInteger*)el->getObject();
            //判断是否存在closeDic中
            if (closeDic->objectForKey(adjoinPos->getValue()))
            {
                continue;
            }
            //判断是否存在openDic中
            if (openDic->objectForKey(adjoinPos->getValue()))
            {
                TacticalSecondMapBlock* tempBlock = (TacticalSecondMapBlock*)openDic->objectForKey(adjoinPos->getValue());
                if (tempBlock)
                {
                    if (currentBlock->getBlockG() + AdjoinDistance < tempBlock->getBlockG())
                    {
                        tempBlock->setBlockG(currentBlock->getBlockG() + AdjoinDistance);
                        tempBlock->setParentTag(currentTag);
                    }
                }
            }
            else
            {
                TacticalSecondMapBlock* tempBlock = (TacticalSecondMapBlock*)allBlockDic->objectForKey(adjoinPos->getValue());
                if (tempBlock)
                {
            //这些判断条件总的来说就是这个点是可以通过的
if ((tempBlock->getBlockType() == Block_PassType && (tempBlock->getBlockVo()->getBlockType() == Event_Type_NULL || tempBlock->getBlockVo()->getBlockType() == Event_Type_StartPoint)) || adjoinPos->getValue() == endId) { tempBlock->setParentTag(currentTag); tempBlock->setBlockG(currentBlock->getBlockG() + AdjoinDistance); tempBlock->setBlockH(computeHScore(adjoinPos->getValue(), endId)); openDic->setObject(tempBlock, adjoinPos->getValue()); } } } } } while (openDic->count() > 0);
</span><span style="color: #0000ff;">if</span> (routeArr-&gt;count() &lt;= <span style="color: #800080;">0</span><span style="color: #000000;">)
{
    CCLOG(</span><span style="color: #800000;">"</span><span style="color: #800000;">no path found</span><span style="color: #800000;">"</span><span style="color: #000000;">);
}

}

int TacticalSecondMatchLayer::findMinFInOpen()
{
    int minId = 0;
    TacticalSecondMapBlock* minBlock = NULL;
    CCDictElement* el = NULL;
    CCDICT_FOREACH(openDic, el)
    {
        TacticalSecondMapBlock* _block = (TacticalSecondMapBlock*)el->getObject();
        if (minBlock)
        {
            if (minBlock->getBlockF() > _block->getBlockF())
            {
                minBlock = _block;
                minId = el->getIntKey();
            }
        }
        else
        {
            minBlock = _block;
            minId = el->getIntKey();
        }
    }
</span><span style="color: #0000ff;">return</span><span style="color: #000000;"> minId;

}

int TacticalSecondMatchLayer::computeHScore(int startId, int endId)
{
    return sqrt((posArr[endId].x - posArr[startId].x)*(posArr[endId].x - posArr[startId].x) + (posArr[endId].y - posArr[startId].y) * (posArr[endId].y - posArr[startId].y));
}
//寻找路径
void TacticalSecondMatchLayer::constructPathFromStep(TacticalSecondMapBlock* block, int startId)
{
    TacticalSecondMapBlock* tempBlock = block;
    if (tempBlock->getBlockType() == Block_PassType && (tempBlock->getBlockVo()->getBlockType() == Event_Type_NULL || tempBlock->getBlockVo()->getBlockType() == Event_Type_StartPoint))
    {
        routeArr->addObject(tempBlock);
    }
</span><span style="color: #0000ff;">do</span><span style="color: #000000;"> {
    TacticalSecondMapBlock</span>* _block = (TacticalSecondMapBlock*)allBlockDic-&gt;objectForKey(tempBlock-&gt;<span style="color: #000000;">getParentTag());
    </span><span style="color: #0000ff;">if</span><span style="color: #000000;"> (_block)
    {
        </span><span style="color: #0000ff;">if</span> (tempBlock-&gt;getParentTag() ==<span style="color: #000000;"> startId)
        {
            tempBlock </span>=<span style="color: #000000;"> NULL;
        }
        </span><span style="color: #0000ff;">else</span><span style="color: #000000;">
        {
            routeArr</span>-&gt;<span style="color: #000000;">addObject(_block);
            tempBlock </span>=<span style="color: #000000;"> _block;
        }
    }
    </span><span style="color: #0000ff;">else</span><span style="color: #000000;">
    {
        </span><span style="color: #0000ff;">break</span><span style="color: #000000;">;
    }
} </span><span style="color: #0000ff;">while</span> (tempBlock !=<span style="color: #000000;"> NULL);

}

本文转载自博客园,原文链接:https://www.cnblogs.com/liylove/p/12188082.html

全部评论: 0

    我有话说: