Звезда непредсказуемых ошибок

Question

Моя слабая попытка использования алгоритма A* приводит к непредсказуемым ошибкам. Моя функция FindAdjacent() явно беспорядок, и она на самом деле не работает, когда я прохожу через нее. Я впервые пробую алгоритм поиска пути, так что для меня это все ново.

Когда приложению действительно удается найти целевые узлы и путь (или я так думаю), оно никогда не сможет установить путь (вызывается из main с помощью нажатия enter). Я не знаю, почему он не может сделать это, глядя на функцию 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;
}

Answer 1

Несколько предложений:

Тест на аджансность

Тест в 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, прежде чем добавить его, и если он есть, то добавьте его, только если оценка лучше.