我的a-star实现中不必要的移动

Question

我用欧几里得启发式算法做了一个a-star实现，它是有效的，但在某些情况下会做不必要的移动。

这是屏幕截图：http://clip2net.com/s/6v2iU4

路径从蓝色的圆圈开始，理论上，它右边的单元格的F(移动成本+启发式成本)较小，因此a-star优先使用它，但它最终不是构建最短路径。

我该如何解决这个问题呢？或者a-star应该以这种方式工作，而我不需要做任何事情？

我的代码：http://pastebin.com/02u33jY6 (h + cpp)

Answer 1

您的算法的问题是，当您的实现在openList中找到目的地时，它会返回路径。

当目的节点在closedList中，而不是在开放列表中时，A*应该终止。

// check if there is dst node on the closed list
for ( unsigned int i = 0; i < closedList.size(); i++ )
{
    if ( closedList.at( i ).getIndex() == dstTileIndex )
    {
        GSPathFinderNode* backtrackNode = &closedList.at( i );
        resultPathNodes->insert( resultPathNodes->begin(), GSCommonMapNode( backtrackNode->getIndex(),
                                                                           backtrackNode->getPosX(),
                                                                           backtrackNode->getPosY() ) );

        while ( 1 )
        {
            for ( unsigned int j = 0; j < closedList.size(); j++ )
            {
                if ( closedList.at( j ).getIndex() == backtrackNode->getParentNodeIndex() )
                {
                    backtrackNode = &closedList.at( j );
                    resultPathNodes->insert( resultPathNodes->begin(), GSCommonMapNode( backtrackNode->getIndex(),
                                                                                       backtrackNode->getPosX(),
                                                                                       backtrackNode->getPosY() ) );

                    if ( backtrackNode->getIndex() == srcTileIndex )
                        return true; // success
                }
            }
        }
    }
}