Алгоритм звезды не работает из-за указателя на родителя, помогает его исправление

-1

Я недавно работал над реализацией алгоритма 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); 
     }

Я устанавливаю адрес тока, чтобы быть родителем преемника.

Что происходит, так это то, что на следующей итерации кажется, что ток определен в том же адресе, родитель-преемник будет равен новому току.

Что следует использовать вместо узла *, потому что это похоже на то, что делает мой код неработоспособным.

Полный код алгоритма:

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

Спасибо!

источник

2015-06-23 Levon

Вы храните адрес временной переменной стека в структуру данных, которая будет сохраняться после уничтожения этой переменной стека, что приведет к неопределенному поведению. – paddy

По возможности вы должны разработать новую функциональность в изоляции. В этом случае вы могли бы построить и протестировать свой A * решатель с очень простым эвристическим деревом и расстоянием; связывая его так сильно, что вы хотите искать в определенном пространстве, вы сделали сложную задачу для отладки всей программы. – Beta

Как указано в комментарии, вы храните адрес локальной переменной внутри контейнера. Когда этот локаль выходит из сферы действия, ваш код будет демонстрировать неопределенное поведение.

Кроме того, причина, по которой вы видите тот же адрес, который хранится, заключается в том, что вы создаете новый локальный экземпляр 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

последняя строка создает копию текущего, а затем помещает его на задней части 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.

источник

2015-06-24 01:04:52 PaulMcKenzie

Спасибо! это исправило это! Что делать, если я хочу изменить на std :: set, потому что std :: list не так хорош, как std :: set в памяти? – Levon

Это должно быть нормально, если набор не выходит за пределы области видимости и что элемент в наборе не был удален. – PaulMcKenzie

О, спасибо. А также, знаете ли вы, почему на моей карте координаты, равные размеру, являются непригодными для жизни, я не знаю почему, но я, по-видимому, игнорирую эти позиции, может быть, вы поймете, почему. Благодарю. – Levon

Алгоритм звезды не работает из-за указателя на родителя, помогает его исправление

ответ

Смежные вопросы