Solving 8-Puzzle in C++ with A* results in endless loop

Question

I'm currently trying to solve the 8-Puzzle with the A* search algorithm, but my program gets stuck in an endless loop.

My main searching loop is:

std::vector<Field> Search::AStar(Field &start, Field &goal){
std::cout << "Calculating..." << std::endl;

std::unordered_map<Field, Field> explored;
std::vector<Field> searched;

if (Puzzle::finished(start))
    return MakePath(start, start);

std::priority_queue<Field, std::vector<Field>, std::greater<Field>> frontier;
frontier.push(start);

Field current;
Field child;

size_t i = 0;
while (!frontier.empty())
{
    current = frontier.top();
    frontier.pop();

    if (++i > 500)
    {
        std::cout << "Iteration Error" << std::endl;
        return searched;
    }

    searched.push_back(current);

    for (Direction d : Puzzle::Actions(current))
    {
        child = Puzzle::Action(d, current);

        if (Puzzle::finished(child))
        {
            std::cout << "Found goal!" << std::endl;
            return MakePath(explored[child], start);
        }

        child.CostG = current.CostG + 1; // Make a step

        if (!isIn(child, explored) || child.CostG < explored[child].CostG)
        {
            child.CostH = Puzzle::Heuristic(child, goal); // Calculate Heuristic
            child.CostF = child.CostG + child.CostH; // Calculate final costs

            frontier.push(child);
            explored[child] = child;
            explored[child].setParent(&explored[current]);
        }
    }
}

std::cout << "Error: frontier Empty" << std::endl;

return searched;
}

The vector "searched" is just so that I can see what A* does, and I will delete it as soon as the algorithm works.

The CostG stands for the number of steps done until this point, the CostH are the estimated minimum (heuristic) costs to the "goal" and the CostF are those two combined.

The index of the Field::Boxes vector is the number of the field, and every element contains the position.

My Heuristic function looks like this:

    inline int Heuristic(Field &goal)
{
    size_t d = 0;

    for (size_t i = 0; i < Boxes.size(); i++)
    {
        d += (std::abs(static_cast<int>(Boxes[i].x) - static_cast<int>(goal.Boxes[i].x))
            + std::abs(static_cast<int>(Boxes[i].y) - static_cast<int>(goal.Boxes[i].y)));
    }

    return d;
}

For better readability and stuff, the code also is on Github. However, to execute it, you need SFML in your Visual Studio include direction.

Every help is appreciated!

Edit 1: You now no longer need SFML to executed & debug the program! I commited the changes to github, the link is the same.

Answer 1

The problem is that although you remove the current node from your frontier, you never added it to the explored set, i.e. you never close it. The following code should work. My revisions closely follow Wikipedia's A* Pseudocode.

I also recommend you test your algorithm with the trivial heuristic (the one that returns zero for all values) on a simple puzzle to verify that your algorithm is implemented correctly. (See this answer for a brief explanation of this technique.)

while (!frontier.empty())
{
    current = frontier.top();
    frontier.pop();

    if (++i > 500)
    {
        std::cout << "Iteration Error" << std::endl;
        return searched;
    }

    // Check for goal here
    if (Puzzle::finished(current)
    {
        std::cout << "Found goal!" << std::endl;
        return MakePath(explored[current], start);
    }

    explored[current] = current; //close the current node
    searched.push_back(current);

    for (Direction d : Puzzle::Actions(current))
    {
        child = Puzzle::Action(d, current);

        if (isIn(child,explored)) 
        {
            continue; //ignore the neighbor which is already evaluated
        }

        child.CostG = current.CostG + 1; // Make a step

        if (!isIn(child, frontier)) //discovered a new node
        {
            frontier.push(child);
        } 
        else if (child.CostG >= explored[child].CostG)
        {
            continue; //this is not a better path
        {

        //the path is best until now. Record it!
        child.CostH = Puzzle::Heuristic(child, goal); // Calculate Heuristic
        child.CostF = child.CostG + child.CostH; // Calculate final costs

        //frontier.push(child); moved up to earlier point in code
        explored[child] = child;
        explored[child].setParent(&explored[current]);

    }
}