由于指向父级的指针，星型算法无法正常工作，请帮助修复它

Question

我最近一直致力于 a* 算法的实现，但遇到了一个问题。

这里发生了什么：

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);

我正在使当前等于 openList 中的最小元素。

稍后在代码中

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

            openList.push_back(successor);
        }

我正在将当前的地址设置为继任者的父级。

发生了什么，在下一次迭代中，current 似乎定义在同一地址中，successor 的父级将等于新的 current。

我应该使用什么来代替 Node*，因为这似乎是我的代码无法运行的原因。

完整算法代码：

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;
}

完整代码：

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;
}

谢谢！

Answer 1

正如评论所建议的那样，您正在将局部变量的地址存储在容器内。当该本地超出范围时，您的代码将表现出未定义的行为。

此外，您看到存储相同地址的原因是您正在创建 current 的新本地实例，碰巧新本地实例与旧地址（现在已销毁) current.

实例

但是，查看违规函数，我发现您将 current 存储在 std::list 中。您可能有办法通过非常小的更改来完成您正在寻求的目标。

由于您在 solver 函数中执行此操作：

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

最后一行创建一个current的副本，然后把它放在std::list的后面。为什么这是有希望的？这是有前途的，因为，

您确切知道 current 副本的位置（在 std::list) 和
指向std::list条目的指针保证有效，在范围等。即使 std::list 更改大小，前提是该条目仍在列表中。

鉴于此，对您的代码的修复应该非常简单。在您执行此操作的函数中进一步向下：

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

相反，这样做：

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

我们现在正在返回对推送到列表中的最后一个项目的引用，并获取该项目的地址。

现在，需要注意的是 closedList 最好不要超出范围，并且当您持有该项目的地址时，您添加到列表中的项目不会被删除。

我不确定这是否能解决您的所有问题。但这是你应该尝试的事情。

最重要的是，如果您使用 std::list 来存储对象，只要

获取指向列表中这些对象的指针就绝对安全

std::list 在范围内并且
您有指向的项目未从 std::list 中删除。

由于指向父级的指针，星型算法无法正常工作，请帮助修复它

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

c++

algorithm

a-star