A star algorithm not working because of pointer to parent, help fixing it

Question

I have been lately working in an implementation of the a* algorithm and I got a problem.

What happens is that in here:

std::list<Node> openList;
std::list<Node> closedList;

startNode.calc(map, endPos);

openList.push_back(startNode);

while (!openList.empty())
{
    auto min = std::min_element(openList.begin(), openList.end());
    auto current = Node(*min);

    current.calc(map, endPos);

    closedList.push_back(current);
    openList.remove(current);

I'm making current to be equal to the minimal element in openList.

And later in the code

        if (inOpen == openList.end())
        {
            successor.calc(map, endPos);
            successor.parent = &current;

            openList.push_back(successor);
        }

I'm setting the address of current to be successor's parent.

What happens, is that in the next iteration, it seems that current is defined in the same address, successor's parent will be equal to the new current.

What should I use instead of a Node*, because that seems to be what's making my code not work.

Full algorithm code:

bool Solver::aStar()
{

    if ((map.getDangerElement(startPos) == 'X') || map.getDangerElement(endPos) == 'X')
        return false;

    Node startNode(startPos);
    Node goalNode(Vector2(endPos.x - 1, endPos.y - 1));

    std::list<Node> openList;
    std::list<Node> closedList;

    startNode.calc(map, endPos);

    openList.push_back(startNode);

    while (!openList.empty())
    {
        auto current = Node(*std::min_element(openList.begin(), openList.end()));

        current.calc(map, endPos);

        closedList.push_back(current);
        openList.remove(current);

        for (auto& direction : directions)
        {
            Node successor(direction.position + current.position);

            if (map.getDangerElement(successor.position) == 'X' ||
                successor.position.x >= map.getSize() - 1 || successor.position.y >= map.getSize() - 1 ||
                successor.position.x < 0 || successor.position.y < 0 || 
                std::find(closedList.begin(), closedList.end(), successor) != closedList.end())
            {
                continue;
            }

            successor.calc(map, endPos);

            auto inOpen = std::find(openList.begin(), openList.end(), successor);

            if (inOpen == openList.end())
            {
                auto curr = &current;
                successor.parent = curr;
                successor.calc(map, endPos);

                openList.push_back(successor);
            }
            else
            {
                if (successor.G < inOpen->G)
                {
                    auto* curr = &current;
                    successor.parent = curr;
                }
            }
        }

#ifdef DEBUG
        for (auto a : closedList)
        {
            map.setElement(a.position, 'Y');
        }
#endif

        if (current == goalNode) break;
    }


    if (openList.size() == 0)
    {
        std::cout << "There's no solution to this map";
        return false;
    }

    map.display();


    return true;
}

Full code:

Vector2.h

#pragma once

struct Vector2
{
    int x, y;
    Vector2(int, int);
    Vector2();
    Vector2 operator +(const Vector2&);
};

Vector2.cpp

#include "Vector2.h"

Vector2::Vector2(int _x, int _y) : x(_x), y(_y)
{ }

Vector2::Vector2()
{ }

Vector2 Vector2::operator+(const Vector2& other)
{
    Vector2 temp;
    temp.x = this->x + other.x;
    temp.y = this->y + other.y;
    return temp;
}

map.h

#pragma once

#include "vector2.h"

#include <vector>
#include <iostream>
#include <random>
#include <algorithm>

class Map
{
    Vector2 startPos, endPos;
    std::vector<char> data;
    std::vector<char> datad;
    int size;

    void setDangerElement(Vector2 position, char);
    void fillDangerMap();

    Vector2 clamp(int min, int max, Vector2 position) const;

public:
    Map(int size, Vector2 startPosition, Vector2 endPosition);
    Map();

    void setSize(int size);
    void fill(char, char, char, char, char);
    void display();

    char getElement(Vector2 position) const;
    char getDangerElement(Vector2 position) const;
    int  getSize() const;

    void setElement(Vector2 position, char element);
};

std::mt19937& getRandomEngine();

map.cpp

#include "map.h"

Map::Map(int _size, Vector2 _startPos, Vector2 _endPos) : size(_size), startPos(_startPos), endPos(_endPos)
{
    data.resize(size * size);
    datad.resize(size * size);
}

Map::Map()
{ }

Vector2 Map::clamp(int min, int max, Vector2 position) const
{
    if (position.y < 0) position.y = 0;
    if (position.x < 0) position.x = 0;
    if (position.y > size) position.y = size;
    if (position.x > size) position.x = size;

    return position;
}

void Map::fill(char fillStartWith, char fillEndWith, char fillGravWheelWith, char fillAsteroidWith, char fillElseWith)
{
    auto a = (size * size) * 0.1 / 3;
    auto b = (size * size) * 0.3 / 3;

    for(int i = 0; i < size * size; ++i){
        if(i < a)                       data[i] = fillGravWheelWith;
        else if(i < b)                  data[i] = fillAsteroidWith;
        else                            data[i] = fillElseWith;
    }
    std::shuffle(data.begin(), data.end(), getRandomEngine());
    setElement(startPos, fillStartWith);
    setElement(endPos, fillEndWith);
    fillDangerMap();
}

void Map::display()
{
    for(int i = 1; i <= size * size; ++i)
    {
        std::cout << data[i - 1] << " ";
        if (!(i % size))
            std::cout << "\n";
    }
}

void Map::setSize(int _size)
{
    size = _size;
    data.resize(size * size);
}

char Map::getElement(Vector2 position) const
{
    position = clamp(0, size, position);

    position.y *= size;
    return data[position.x + position.y];
}

char Map::getDangerElement(Vector2 position) const
{
    position = clamp(0, size, position);

    position.y *= size;
    return datad[position.x + position.y];
}

void Map::fillDangerMap()
{
    for (int i = 0; i < size * size; ++i) datad[i] = '.';

    for(int y = 0; y < size; ++y){
        for(int x = 0; x < size; ++x){
            Vector2 current(x,y);
            if      (getElement(current) == 'E') setDangerElement(current, 'E');
            else if (getElement(current) == 'S') setDangerElement(current, 'S');
            else if (getElement(current) == 'A') setDangerElement(current, 'X');
            if (getElement(current) == 'G' && x == 0){
                setDangerElement(current, 'X');
                setDangerElement(Vector2(x, y + 1), 'X');
                setDangerElement(Vector2(x, y - 1), 'X');
                setDangerElement(Vector2(x + 1, y + 1), 'X');
                setDangerElement(Vector2(x + 1, y), 'X');
                setDangerElement(Vector2(x + 1, y - 1), 'X');
            }
            else if (getElement(current) == 'G' && y == 0){
                setDangerElement(current, 'X');
                setDangerElement(Vector2(x, y + 1), 'X');
                setDangerElement(Vector2(x - 1, y), 'X');
                setDangerElement(Vector2(x - 1, y + 1), 'X');
                setDangerElement(Vector2(x + 1, y + 1), 'X');
                setDangerElement(Vector2(x + 1, y), 'X');
            }
            else if (getElement(current) == 'G' && x == size - 1){
                setDangerElement(Vector2(x, y), 'X');
                setDangerElement(Vector2(x, y + 1), 'X');
                setDangerElement(Vector2(x, y - 1), 'X');
                setDangerElement(Vector2(x - 1, y), 'X');
                setDangerElement(Vector2(x - 1, y - 1), 'X');
                setDangerElement(Vector2(x - 1, y + 1), 'X');
            }
            else if (getElement(current) == 'G' && y == size - 1){
                setDangerElement(current, 'X');
                setDangerElement(Vector2(x, y - 1), 'X');
                setDangerElement(Vector2(x - 1, y), 'X');
                setDangerElement(Vector2(x - 1, y - 1), 'X');
                setDangerElement(Vector2(x + 1, y), 'X');
                setDangerElement(Vector2(x + 1, y - 1), 'X');
            }
            else if (getElement(current) == 'G'){
                setDangerElement(current, 'X');
                setDangerElement(Vector2(x, y + 1), 'X');
                setDangerElement(Vector2(x, y - 1), 'X');
                setDangerElement(Vector2(x - 1, y), 'X');
                setDangerElement(Vector2(x - 1, y - 1), 'X');
                setDangerElement(Vector2(x - 1, y + 1), 'X');
                setDangerElement(Vector2(x + 1, y + 1), 'X');
                setDangerElement(Vector2(x + 1, y), 'X');
                setDangerElement(Vector2(x + 1, y - 1), 'X');
            }
        }
    }
}

void Map::setElement(Vector2 position, char elem)
{
    position = clamp(0, size, position);
    position.y *= size;
    data[position.x + position. y] = elem;
}

void Map::setDangerElement(Vector2 position, char elem)
{
    position = clamp(0, size, position);

    position.y *= size;
    datad[position.x + position.y] = elem;
}

int Map::getSize() const
{
    return size;
}

std::mt19937& getRandomEngine()
{
    static std::mt19937 randomEngine(std::random_device{}());
    return randomEngine;
}

node.h

#pragma once

#include "map.h"

#include <list>
#include <cmath>

struct Node
{
    Vector2 position;
    int G, H, F;
    Node* parent = nullptr;

    Node();
    Node(const Node& other) = default;
    Node(Vector2 pos);

    void calc(const Map&, const Vector2&);

    bool operator==(const Node&);
    bool operator<(const Node&);
};

node.cpp

#include "node.h"

Node::Node()
{ }

Node::Node(Vector2 pos) : position(pos)
{ }

void Node::calc(const Map& map, const Vector2& endPos)
{
    H = static_cast<int>((abs(static_cast<double>(position.x - endPos.x)) + abs(static_cast<double>(position.y - endPos.y))));
    G = parent ? parent->G + 1 : 1;
    F = G + H;
}

bool Node::operator==(const Node& other)
{
    return (position.x == other.position.x && position.y == other.position.y);
}

bool Node::operator<(const Node& other)
{
    return(F < other.F);
}

solver.h

#pragma once

#include "node.h"

class Solver
{
    Vector2 startPos, endPos;
    Map map;

    std::vector<Node> directions;

public:
    Solver(const int&, const Vector2&, const Vector2&);
    void displayMap();

    bool aStar();
};

solver.cpp

#include "solver.h"

#define DEBUG

Solver::Solver(const int& size, const Vector2& _startPos, const Vector2& _endPos) : startPos(_startPos), endPos(_endPos)
{
    Map temp(size, startPos, endPos);
    map = temp;

    map.fill('S', 'E', 'G', 'A', '.');
    map.display();

    directions.resize(8);

    directions[0] = Node(Vector2 (-1 ,1));
    directions[1] = Node(Vector2(-1, 0));
    directions[2] = Node(Vector2(-1, -1));
    directions[3] = Node(Vector2(0, 1));
    directions[4] = Node(Vector2(0, -1));
    directions[5] = Node(Vector2(1, 1));
    directions[6] = Node(Vector2(1, 0));
    directions[7] = Node(Vector2(1, -1));
}

void Solver::displayMap()
{
    map.display();
}

bool Solver::aStar()
{

    if ((map.getDangerElement(startPos) == 'X') || map.getDangerElement(endPos) == 'X')
        return false;

    Node startNode(startPos);
    Node goalNode(Vector2(endPos.x - 1, endPos.y - 1));

    std::list<Node> openList;
    std::list<Node> closedList;

    startNode.calc(map, endPos);

    openList.push_back(startNode);

    while (!openList.empty())
    {
        auto current = Node(*std::min_element(openList.begin(), openList.end()));

        current.calc(map, endPos);

        closedList.push_back(current);
        openList.remove(current);

        for (auto& direction : directions)
        {
            Node successor(direction.position + current.position);

            if (map.getDangerElement(successor.position) == 'X' ||
                successor.position.x >= map.getSize() - 1 || successor.position.y >= map.getSize() - 1 ||
                successor.position.x < 0 || successor.position.y < 0 || 
                std::find(closedList.begin(), closedList.end(), successor) != closedList.end())
            {
                continue;
            }

            successor.calc(map, endPos);

            auto inOpen = std::find(openList.begin(), openList.end(), successor);

            if (inOpen == openList.end())
            {
                auto curr = &current;
                successor.parent = curr;
                successor.calc(map, endPos);

                openList.push_back(successor);
            }
            else
            {
                if (successor.G < inOpen->G)
                {
                    auto* curr = &current;
                    successor.parent = curr;
                }
            }
        }

#ifdef DEBUG
        for (auto a : closedList)
        {
            map.setElement(a.position, 'Y');
        }
#endif

        if (current == goalNode) break;
    }


    if (openList.size() == 0)
    {
        std::cout << "There's no solution to this map";
        return false;
    }

    map.display();


    return true;
}

source.cpp

#include "solver.h"

int main()
{
    const int SIZE = 20;
    const Vector2 startPos(0, 0);
    const Vector2 endPos(SIZE - 1, SIZE - 1);

    Solver solve(SIZE, startPos, endPos);
    if (solve.aStar()){
        std::cout << "\nMap has been successfully solved.\nMap:\n";
        solve.displayMap();
    }
    else std::cout << "\nThere is no path from the start position to the end position in this map.\n";

    std::cin.get();
    return 0;
}

Thanks!

Answer 1

As the comment suggested, you are storing the address of a local variable inside the container. When that local goes out of scope, your code will exhibit undefined behavior.

Also, the reason why you see the same address being stored is that you are creating a new local instance of current, and by chance, the new local instance has the same address as the old (now destroyed) instance of current.

However, taking a look at the offending function, I see that you are storing current in a std::list. You may have a way of accomplishing what you are seeking with a very minor change.

Since you are doing this in your solver function:

auto current = Node(*std::min_element(openList.begin(), openList.end()));
current.calc(map, endPos);
closedList.push_back(current);  // < -- This could be your lifeline

the last line creates a copy of current, and then places it on the back of a std::list. Why is that promising? It is promising because,

1. You know exactly where the current copy is located (at the back of a std::list) and
2. A pointer to a std::list entry is guaranteed to be valid, in scope, etc. even if the std::list changes size provided that the entry is still in the list.

So given this, the fix to your code should be very simple. Further down in the function you are doing this:

        if (inOpen == openList.end())
        {
            auto curr = &current;
            successor.parent = curr;
            //...

Instead, do this:

        if (inOpen == openList.end())
        {
            auto curr = &closedList.back();  
            successor.parent = curr;
            //...

We are now being returned a reference to the last item that was pushed onto the list, and getting the address of this item.

Now, the caveat is that closedList better not go out of scope, and that item you added to the list doesn't get removed while you are holding the address of the item.

Whether this fixes all your issues, I am not sure. But it is something you should try.

The bottom line is that if you're using a std::list to store objects, getting pointers to those objects in the list is perfectly safe to do as long as

1. The std::list is in scope and
2. The item you have a pointer to is not removed from the std::list.