A* 寻路和大量指针问题？

Question

我知道 A* 算法实现问题在 stackoverflow 上相对常见（我已经浏览过很多其他帖子）。过去几天我一直在尝试实现一个简单的 C++ A* 系统。我只允许在四个方向上移动（没有对角线检查），所以这应该是一个特别简单的任务（这也是为什么我只使用启发式作为我的成本）。另外，我已经逐步完成了代码，对于所有起始位置，对象都能够成功找到到达目标的有效路径。然而，问题是我无法通过父指针后退并存储路径/移动序列。我正在使用引用，所以我不太确定为什么指针分配存在问题。我通过一些简短的示例路径浏览了我“认为”代码在纸上所做的事情，但我不明白我做错了什么。循环遍历父指针，最终应为 NULL，无限打印目标的 posY。

这是我的头文件：

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

通过检查，关闭和打开包含正确的结果。所以，我确信我用我的指针做了一些非常愚蠢的事情。任何帮助将非常感激。 :)

Answer 1

问题是您在 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_map 中的迭代器从 open_set 中弹出节点
  • 更新费用
  • 插入到 open_set
  • 更新 open_map 以指向重新插入的迭代器

插入或删除时会动态分配大量元素。采用容器池分配器可能会有所帮助。

Answer 2

其他人已经提到了可能的问题，但我将更详细地解释。

当您在堆栈上创建对象（不使用 new）并将它们放入容器中时，您正在创建所创建的原始对象的副本。因此，指向原始文件的任何指针都将继续指向原始文件，而原始文件在某个时刻会被销毁，而不会指向容器中的副本。此外，获取容器中对象的地址并不真正节省，因为某些容器可以在添加或删除元素时移动对象。

有两种方法可以解决这个问题。

1. 不要使用指针，而使用索引值，例如向量中的位置或带有 std::map 等容器的某些键值。
2. 用 new 分配所有对象并将指针存储在容器中。 （可能会给内存管理带来一些麻烦。）

顺便说一句，引用基本上是指针，并且具有相同的问题。