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, );    //寻找相邻点

        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() > );

    if (routeArr->count() <= )

    {

        CCLOG("no path found");

    }

}

int TacticalSecondMatchLayer::findMinFInOpen()

{

    int minId = ;

    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();

        }

    }

    return 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);

    }

    do {

        TacticalSecondMapBlock* _block = (TacticalSecondMapBlock*)allBlockDic->objectForKey(tempBlock->getParentTag());

        if (_block)

        {

            if (tempBlock->getParentTag() == startId)

            {

                tempBlock = NULL;

            }

            else

            {

                routeArr->addObject(_block);

                tempBlock = _block;

            }

        }

        else

        {

            break;

        }

    } while (tempBlock != NULL);

}

巴特西

A*寻路算法的个人理解

最新文章

热门文章