0

我对 A* 算法的微弱尝试正在产生不可预测的错误。我的 FindAdjacent() 函数显然是一团糟，当我单步执行它时它实际上不起作用。这是我第一次尝试寻路算法，所以这对我来说是全新的。

当应用程序实际上设法找到目标节点和路径（或者我认为）时，它永远无法设置路径（通过按 Enter 从 main 中调用）。通过查看 SetPath() 函数，我不知道为什么它无法做到这一点。

任何帮助将不胜感激，这是我的代码：

节点类

enum 
{
    NODE_TYPE_NONE  = 0,
    NODE_TYPE_NORMAL,
    NODE_TYPE_SOLID,
    NODE_TYPE_PATH,
    NODE_TYPE_GOAL
};

class Node
{
public:

    Node            ()          : mTypeID(0), mNodeCost(0), mX(0), mY(0), mParent(0){};

public:

    int     mTypeID;
    int     mNodeCost;
    int     mX;
    int     mY;

    Node*   mParent;
};

寻找路径

/**
 *  finds the path between star and goal
 */
void AStarImpl::FindPath()
{
    cout << "Finding Path." << endl;
    GetGoals();

    while (!mGoalFound)
        GetF();
}

 /**
 *  modifies linked list to find adjacent, walkable nodes
 */
void AStarImpl::FindAdjacent(Node* pNode)
{
    for (int i = -1; i <= 1; i++)
    {
        for (int j = -1; j <= 1; j++)
            if (i != 0 && j != 0)
                if (Map::GetInstance()->mMap[pNode->mX+i][pNode->mY+j].mTypeID != NODE_TYPE_SOLID)
                {
                    for (vector<Node*>::iterator iter = mClosedList.begin(); iter != mClosedList.end(); iter++)
                    {
                        if ((*iter)->mX != Map::GetInstance()->mMap[pNode->mX + i][pNode->mY + j].mX && (*iter)->mY != Map::GetInstance()->mMap[pNode->mX + i][pNode->mY + j].mY)
                        {
                            Map::GetInstance()->mMap[pNode->mX+i][pNode->mY+j].mParent = pNode;
                            mOpenList.push_back(&Map::GetInstance()->mMap[pNode->mX+i][pNode->mY+j]);
                        }
                    }
                }
    }

    mClosedList.push_back(pNode);
}

/**
 *  colour the found path
 */
void AStarImpl::SetPath()
{
    vector<Node*>::iterator tParent;
    mGoalNode->mTypeID = NODE_TYPE_PATH;

    Node *tNode = mGoalNode;

    while (tNode->mParent)
    {
        tNode->mTypeID  = NODE_TYPE_PATH;
        tNode           = tNode->mParent;
    }

}

/**
 *  returns a random node
 */
Node* AStarImpl::GetRandomNode()
{
    int tX      = IO::GetInstance()->GetRand(0, MAP_WIDTH - 1);
    int tY      = IO::GetInstance()->GetRand(0, MAP_HEIGHT - 1);

    Node* tNode = &Map::GetInstance()->mMap[tX][tY];

    return tNode;
}

/**
 *  gets the starting and goal nodes, then checks te starting nodes adjacent nodes
 */
void AStarImpl::GetGoals()
{
    //  get the two nodes
    mStartNode  = GetRandomNode();
    mGoalNode   = GetRandomNode();

    mStartNode->mTypeID     = NODE_TYPE_GOAL;
    mGoalNode->mTypeID      = NODE_TYPE_GOAL;

    //  insert start node into the open list
    mOpenList.push_back(mStartNode);

    //  find the starting nodes adjacent ndoes
    FindAdjacent(*mOpenList.begin());

    //  remove starting node from open list
    mOpenList.erase(mOpenList.begin());
}

/**
 *  finds the best f
 */
void AStarImpl::GetF()
{
    int     tF          = 0;
    int     tBestF      = 1000;

    vector<Node*>::const_iterator tIter;
    vector<Node*>::const_iterator tBestNode;

    for (tIter = mOpenList.begin(); tIter != mOpenList.end(); ++tIter)
    {
        tF  =   GetH(*tIter);
        tF  +=  (*tIter)->mNodeCost;

        if (tF < tBestF)
        {
            tBestF = tF;
            tBestNode = tIter;
        }
    }

    if ((*tBestNode) != mGoalNode)
    {
        Node tNode  = **tBestNode;
        mOpenList.erase(tBestNode);
        FindAdjacent(&tNode);
    }
    else
    {
        mClosedList.push_back(mGoalNode);
        mGoalFound = true;
    }
}

/**
 *  returns the heuristic from the given node to goal
 */
int AStarImpl::GetH(Node *pNode)
{
    int H =     (int) fabs((float)pNode->mX - mGoalNode->mX);
        H +=    (int) fabs((float)pNode->mY - mGoalNode->mY);
        H *=    10;

    return H;
}
4

1 回答 1

0

几点建议：

邻接测试

FindAdjacent 中的测试目前只会找到对角线邻居

 if (i != 0 && j != 0)

如果您还想找到您想要使用的左/右/上/下邻居

 if (i != 0 || j != 0)

邻接环

我认为您的代码在 FindAdjacent 中看起来很可疑

for (vector<Node*>::iterator iter = mClosedList.begin(); iter != mClosedList.end(); iter++)

我真的不明白这里的意图。我本来希望 mClosedList 开始为空，所以这个循环永远不会执行，所以不会有任何东西被添加到 mOpenList 中。

我对算法这一部分的期望是让您测试每个邻居是否应该将其添加到打开列表中。

公开名单检查

如果您查看维基百科上的 A* 算法，您会发现您也错过了开始的部分

if neighbor not in openset or tentative_g_score < g_score[neighbor]

在添加之前，您还应该在 FindAdjacent 中检查您的新节点是否已经在 OpenSet 中，如果是，则仅在分数更好时才添加它。

于 2012-06-27T19:09:02.993 回答