A* Поиск пути и множество проблем с указателями?
Я знаю, что проблемы реализации алгоритма A* относительно распространены в stackru (я прошел через множество других публикаций). Последние пару дней я пытался реализовать простую систему C++ A*. Я разрешаю движение только в четырех направлениях (без проверки диагонали), так что это должно быть особенно простой задачей (поэтому у меня только эвристика в качестве моей стоимости). Кроме того, я прошел через код, и для всех начальных позиций объект может успешно найти правильный путь к цели. Проблема, однако, заключается в том, что я не могу вернуться назад через родительские указатели и сохранить последовательность пути / движения. Я использую ссылки, поэтому я не совсем уверен, почему существует проблема с назначением указателя. Я пробежал то, что "думаю", код делает на бумаге, для нескольких коротких примеров, и я не понимаю, что я делаю неправильно. Цикл по родительским указателям, который должен в конечном итоге получить значение NULL, бесконечно печатает позицию цели.
Вот мой заголовочный файл:
//to access a priority queue's underlying container, you must extend functionality
template <class T, class S, class C>
S& Container(std::priority_queue<T, S, C>& q) {
struct HackedQueue : private std::priority_queue<T, S, C> {
static S& Container(std::priority_queue<T, S, C>& q) {
return q.*&HackedQueue::c;
}
};
return HackedQueue::Container(q);
}
//different enough from a "Grid" to be a new object
typedef struct Node{
int cost, posX, posY;
Node* parent;
Node(int cost = 0, int posX = 0, int posY = 0, Node* parent = 0) : cost(cost), posX(posX), posY(posY), parent(parent) {}
//overloading operators will make the cpp file easier to read
bool operator==(const Node& rhs){
return (posX == rhs.posX && posY == rhs.posY);
}
bool operator<(const Node& rhs){
return (posX == rhs.posX && posY == rhs.posY && cost < rhs.cost);
}
} Node;
typedef struct NodeCompare{
//compare n1 against a node n2
bool operator()(const Node& n1, const Node& n2){
//if n2 has a lower cost, it has a higher priority
return n2.cost < n1.cost;
}
} NodeCompare;
//a list is essentially a linked list, a vector is a robust array; if you do not need random access, lists are faster than vectors
//we need random access for the priority queue, because it will constantly be resorted
bool PathSearch(std::list<Node>& path, const World& World, const WorldObj& obj, const Node& target); //path is our output list
void NodeSuccessors(std::priority_queue<Node, std::vector<Node>, NodeCompare>& open, std::list<Node>& closed, Node& parentNode, const World& World, const Node& target);
int Heuristic(int posX, int posY, const Node& target);
}
И вот моя реализация:
bool PathSearch(std::list<Node>& path, const World& World, const WorldObj& obj, const Node& target){
std::priority_queue<Node, std::vector<Node>, NodeCompare> open;
std::list<Node> closed;
//put our starting position into our queue of nodes to inspect
Node start(Heuristic(obj.GetposX(), obj.GetposY(), target), obj.GetposX(), obj.GetposY());
open.push(start);
while(!open.empty()){
Node bestNode = open.top(); //has the lowest score by definition
open.pop();
if(bestNode == target){ //made it to the target
Node* ptrNode = &bestNode;
while(ptrNode){ //this is where we would reconstruct the path
std::cout<<ptrNode->posY<<std::endl;
ptrNode = ptrNode->parent;
}
return 1;
}
NodeSuccessors(open, closed, bestNode, World, target); //look at the Node's neighbors
closed.push_back(bestNode);
}
return 0; //no path found
}
//check for towers and check for boundaries; if they exist, skip the creation of that node
//pathfinding works for up, down, left, right, but not diagonal movement
void NodeSuccessors(std::priority_queue<Node, std::vector<Node>, NodeCompare>& open, std::list<Node>& closed, Node& parentNode, const World& World, const Node& target){
std::vector<Node>& openVec = Container(open);
int offsetX, offsetY;
bool skip;
for(int i = 0; i < 4; ++i){
offsetX = 0; offsetY = 0;
skip = 0;
if(i == 0) offsetY = -30; //up
else if(i == 1) offsetY = 30; //down
else if(i == 2) offsetX = -30; //left
else if(i == 3) offsetX = 30; //right
//add check for out of boundaries or in an occupied space
Node newNode(parentNode.cost + Heuristic((parentNode.posX + offsetX), (parentNode.posY + offsetY), target), parentNode.posX + offsetX, parentNode.posY + offsetY, &parentNode);
//if the Node already exists on open or closed with a lower score, we can skip to the next neighbor
//if the Node already exists on open or closed with a higher score, then we need to remove it
//the erasing is somewhat expensive, but simplifies the implementation
for(std::list<Node>::iterator itr = closed.begin(); itr != closed.end(); ++itr){
if(*itr < newNode){
skip = 1;
break;
}
else if(*itr == newNode){
closed.erase(itr);
break;
}
}
if(skip) continue;
for(std::vector<Node>::iterator itr = openVec.begin(); itr != openVec.end(); ++itr){
if(*itr < newNode){
skip = 1;
break;
}
else if(*itr == newNode){
openVec.erase(itr);
break;
}
}
if(skip) continue;
open.push(newNode);
}
}
int Heuristic(int posX, int posY, const Node& target){
return abs(posX - target.posX) + abs(posY - target.posY);
}
При осмотре закрытые и открытые содержат правильные результаты. Итак, я уверен, что я делаю что-то действительно глупое с моими указателями. Любая помощь будет очень высоко ценится.:)
2 ответа
Проблема в том, что вы создали экземпляр в стеке в PathSearch() и передал свой адрес NodeSuccessors(),
Речь идет не о вашем вопросе, но ваш алгоритм имеет проблемы с производительностью. Приоритетная очередь является отличным выбором, поскольку приоритетная очередь имеет O(1) при поиске узла с наименьшей оценкой и O(log (n)) при вставке узла. Тем не менее, ваш алгоритм имеет O(n) в поиске узла в открытом и закрытом. Производительность будет намного лучше, если вы также будете поддерживать порядок узлов, чтобы вы могли найти узел в O(log (n)).
Я точно не помню, но это краткая структура, которую я использовал.
struct status {}; // represents the position, less-than comparable
struct node {
status s;
cost g;
cost h;
status parent;
cost score() const { return g + h; }
};
struct node_comparator {
bool operator(const node& x, const node& y) const { return x.score() < y.score(); }
};
typedef std::multiset<node, node_comparator> open_set;
// should be multiset since two or more nodes can have the same score
typedef std::map<Status, typename open_set::iterator> open_map;
- Вставка: O(log(n))
- Вставить узел в open_set
- Вставьте возвращенный итератор в open_map
- Нахождение узла с наименьшей оценкой: O(log(n))
- Поп первый узел из open_set
- Получить соответствующий статус из open_map
- Обновление - если сосед находится в open_map,: O(log(n))
- Получить узел из open_set с помощью итератора в open_map
- Обновите стоимость
- Вставить в open_set
- Обновите open_map, чтобы он указывал на повторно вставленный итератор
Огромное количество элементов динамически выделяется при вставке или удалении. Принятие распределителя пулов для контейнеров может помочь.
Другие уже упоминали вероятную проблему, но я объясню более подробно.
Когда вы создаете объекты в стеке (не используя new) и помещаете их в контейнеры, вы создаете копии оригинальных созданных вами объектов. Таким образом, любые указатели на оригинал будут указывать на оригинал, который в какой-то момент будет уничтожен, и не будут указывать на копию в контейнере. Кроме того, не реально сохранить адрес объекта в контейнере, так как некоторые контейнеры могут перемещать объекты при добавлении или удалении элементов.
Есть два подхода к решению этой проблемы.
- не используйте указатели, но используйте значения индекса, такие как позиция в векторе или некоторое ключевое значение с контейнером, таким как std::map.
- Выделите все объекты новыми и сохраните указатели в контейнерах. (Могло бы вызвать некоторые головные боли при управлении памятью.)
Кстати, ссылки в основном указатели и имеют те же проблемы.