A* Pathfinding and Plenty of Pointer Problems?

Question

I know that A* algorithm implementation problems are relatively common on stackoverflow (I've been through a lot of other postings). I have been trying for the past couple of days to implement a simple C++ A* system. I am only allowing movement in four directions (no diagonal checking), so this should be an especially simple task (this is also why I only have a heuristic as my cost). Also, I have stepped through the code and, for all starting positions, an object is able to successfully find a valid path to the target. The issue, however, is that I am unable to step back through the parent pointers and store the path / movement sequence. I am using references, so I am not quite sure why there is an issue with the pointer assignments. I ran through what I "think" the code is doing on paper for a few, short example paths and I do not understand what I am doing incorrectly. Looping through the parent pointers, which should eventually get to NULL infinitely prints the posY of the target.

Here is my header file:

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

And, here's my implementation:

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

By inspection, closed and open contain the correct results. So, I'm sure that I am doing something really silly with my pointers. Any help would be very much appreciated. :)

Answer 1

The problem is that you created an instance on the stack in PathSearch() and passed its address to NodeSuccessors().

It's not about your question exactly, but your algorithm has a performance issue. Priority queue is an excellent choice since a priority queue has O(1) in finding the node with the lowest score and O(log(n)) in inserting a node. However, your algorithm has O(n) in finding a node in open and closed. The performance will be much better if you also maintain the order of nodes so that you can find a node in O(log(n)).

---

I don't remember exactly but this is a brief structure I used.

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;

• Insertion : O(log(n))
  • Insert a node to open_set
  • Insert the returned iterator to open_map
• Finding the lowest score node : O(log(n))
  • Pop the first node from open_set
  • Pop the corresponding status from open_map
• Updating - If the neighbor is in open_map, : O(log(n))
  • Pop the node from open_set using the iterator in open_map
  • Update the cost
  • Insert to open_set
  • Update the open_map to point the reinserted iterator

A huge amount of elements are dynamically allocated when you insert or delete. Adopting a pool allocator for containers might help.

Answer 2

Others already mentioned the likely problem but I'll explain in more detail.

When you create objects on the stack (by not using new) and putting them in containers you are creating copies of the original objects you made. So any pointers you had to the original will keep pointing to the original which is destroyed at some point and will not point to the copy in the container. Also it is not really save to take the address of an object in a container as some containers can shift the objects around when elements are added or removed.

There are two approaches to solving this.

1. don't use pointers but use index values, like the position in a vector or some key value with a container like std::map.
2. Allocate all objects with new and store the pointers in the containers. (Might give some memory management headaches.)

BTW references are basically pointers and have the same issues.