I'm writing an A* algorithm for Rush Hour (game) in order to learn the basics. For that I wrote a class named Board, which instances also act as the 'nodes' for the A* search.
For the algorithm to work, I generate (generate_moves()) the possible moves as new Board's and add them to the original board as children (std::priority_queue named children).
For some reason, the moment I decide to obtain a Boardfrom mystd::priority_queue childrencontainer withtop(), the pointer it has towards its parent (Board* parent), which is assigned previously during generation, turns into a pointer towards itself.
generate_moves() function:"for each possible move do"
...
Board newBoard = Board();
...
newBoard.parent = this; // I understand 'this' to always point towards the function caller.
children.push(newBoard); // Priority queue of the current board
...
The following images display the debugging process in the a_star() function (which takes the calling Board as root) after a single node expansion from root, while grabbing the very first 'child':
before top()
As you see, every element inside the open priority queue has the root parent, whose own parent is 'nullptr' (this is correct, root node has no parent).
custom score-comparing class Compare for the priority queues
As you can see, everything is messed up already. From the very first comparison, the parent'parent pointer on every child now goes towards itself, instead of nullptr.
after top() (Board currNode)
After the priority queue exits top(), The node is now messed up, having a self-referencing parent.
after top() (priority_queue open)
The same goes for every Board inside the open priority queue, having a self-referencing parent.
I've been dabbling around this issue for a long time now. Any help would be deeply appreciated. If you require any additional context please let me know.
I've tried:
priority_queue with my own type, but I end up dealing with the issues of 'const'-required values, for which I end up creating what's basically the same class.Board&) to normal values (Board), as the issue seems to be happening during comparison. Didn't change a thing.EDIT: Here's my attempt at a "minimal reproducible example". Not sure if consistent due to use of rand() to simplify some functions but it showcases the exact same issue:
#pragma once
#include <iostream>
#include <bitset>
#include <vector>
#include <queue>
#include <stdexcept>
using namespace std;
class SimplifiedBoard {
public:
bitset<36> board;
class Compare {
public:
bool operator() (SimplifiedBoard& a, SimplifiedBoard& b) {
return (a.fscore < b.fscore);
}
};
int fscore;
priority_queue<SimplifiedBoard, vector<SimplifiedBoard>, Compare> children;
SimplifiedBoard* parent;
SimplifiedBoard() {
fscore = 0;
parent = nullptr;
}
// Move generator
void generateMoves() {
int arbitraryChildren = 5;
for (int i = 0; i < arbitraryChildren; i++) {
SimplifiedBoard newBoard = SimplifiedBoard();
newBoard.fscore = (int)rand() / 100;
// Assign parent to child
newBoard.parent = this;
// Add new child
children.push(newBoard);
}
}
// A*
vector<SimplifiedBoard> aStar(SimplifiedBoard& start) {
priority_queue<SimplifiedBoard, vector<SimplifiedBoard>, Compare> open = {};
vector<SimplifiedBoard> closed = {};
start.fscore = 0;
start.parent = nullptr;
open.push(start);
// Loop
while (!open.empty()) {
// ***BUG HAPPENS here (2nd cycle, after root node has been expanded and closed)****
SimplifiedBoard currNode = open.top(); open.pop();
if (currNode.parent != nullptr &&
currNode.parent->parent != nullptr &&
currNode.parent == currNode.parent->parent) {
cout << "Self-referential bug!" << endl;
}
// *** Here, in 2nd cycle, currNode.parent suddenly references a node which references itself ***
// Child generation. f,g,h scores and 'parent' assigned inside function
currNode.generateMoves();
// For each child check OPEN/CLOSE and and see if I add to OPEN
auto childrenCopy = currNode.children;
for (int i = 0; i < (int)currNode.children.size(); i++) {
bool isWorse = false;
SimplifiedBoard currChildNode = childrenCopy.top(); childrenCopy.pop();
// Victory?
if (currChildNode.isVictory()) {
closed.push_back(currChildNode);
// Path reconstruction
vector<SimplifiedBoard> path = {};
SimplifiedBoard currPathNode = currChildNode;
// Ciclo child->parent
while (currPathNode.parent != nullptr) {
path.push_back(currPathNode);
currPathNode = *currPathNode.parent;
}
// Insert root
path.push_back(currPathNode);
// Return path
return path;
}
// OPEN
auto openCopy = open;
for (int j = 0; j < (int)open.size(); j++) {
SimplifiedBoard currOpenNode = openCopy.top(); openCopy.pop();
if (currChildNode.fscore <= currOpenNode.fscore) {
isWorse = true; break;
}
}
if (isWorse) { continue; }
// CLOSED
for (int j = 0; j < (int)closed.size(); j++) {
;
if (currChildNode.fscore <= closed[j].fscore) {
isWorse = true; break;
}
}
if (isWorse) { continue; }
//
open.push(currChildNode);
}
// Close the node
closed.push_back(currNode);
}
// return empty if can't find goal
return vector<SimplifiedBoard>();
}
// Check victory
bool isVictory() {
if ((int)rand() % 50 == 5) { return true; }
else { return false; }
}
};
int main() {
// Debug_example
srand((int)time(NULL));
SimplifiedBoard b = SimplifiedBoard();
cout << "If it gets stuck the bug is happening:" << endl;
vector<SimplifiedBoard> res = b.aStar(b);
for (int i = 0; i < (int)res.size(); i++) {
cout << res[i].fscore << endl;
}
}
Before getting into what's going on, let's simplify your example. In its current form, your question is only applicable to others doing an A*-search, but the problem has nothing to do with searching. Generalizing and simplifying makes the question applicable to a wider audience.
One simplification, that I would expect a question to incorporate, involves realizing that the problem occurs when a node is added to open. So there is no need to test if a node should be added; it must be added to reproduce the bug, so add it. This greatly simplifies the code. Not only is the chunk of code testing close/open/victory eliminated, but also supporting code like isVictory() is eliminated. As a corollary, the score (and randomness) can be eliminated – let the priority queue think all nodes are equivalent. (I suppose you could replace the priority queue with a vector at this point, but I'll hold off on that.) Simplify, compile, run, and verify the bug still manifests!
There are other simplifications that I think also should have been incorporated into the question's code, but their impact is smaller. (Some are minor enough that I did not bother with them.) There are also some simplifications that I would not expect from someone who does not know the answer. These are helpful, though, so I've incorporated them in the code below. Perhaps the most notable of these simplifications is that I don't store children in the node. To reproduce the bug, it is enough to have a node point to its parent; going from parent to child is not necessary. This makes it reasonable to inline generateMoves(), a function that helped obscure the situation.
To further clarify the situation, I've added some diagnostic output at key locations. (Knowing which locations are key is easier when you know the answer. Still, knowing which locations are potentially key is a useful debugging skill.)
#include <iostream>
#include <queue>
using namespace std; // <-- Not recommended, but I'll leave it alone
class SimplifiedBoard {
public:
bool operator< (const SimplifiedBoard&) const {
return false;
}
SimplifiedBoard* parent;
SimplifiedBoard(SimplifiedBoard* parent = nullptr) : parent(parent) {}
// Return true on success, false on the bug.
bool aStar(SimplifiedBoard& start) {
// Initial setup
priority_queue<SimplifiedBoard> open = {};
open.push(start);
// Loop (with an arbitrary cap)
while (!open.empty() && open.size() < 50) {
// Remove the top of the priority queue.
SimplifiedBoard currNode = open.top(); open.pop();
std::cout << "Address of currNode: " << &currNode << "\n";
// ***BUG seen here****
if (currNode.parent != nullptr &&
currNode.parent == currNode.parent->parent) {
std::cout << "Address of parent: " << currNode.parent << "\n";
return false;
}
// Add a child to OPEN.
open.push(SimplifiedBoard(&currNode));
}
return true;
}
};
int main() {
SimplifiedBoard b;
if (b.aStar(b))
cout << "Success!\n";
else
cout << "Self-referential bug!\n";
}
Here is the output:
Address of currNode: 0x7fff3a547408
Address of currNode: 0x7fff3a547408
Address of parent: 0x7fff3a547408
Self-referential bug!
Notice the first two lines of output. Even though currNode is a new object each iteration, its address remains the same. While this is not guaranteed, it is typical. This is ingredient one.
The second ingredient is the construction of child nodes. What is assigned as the parent of these nodes? If you work through the question's code, you should see that the parent of the children is currNode (the *this for the call to generateMoves()). In the simplified version, this is easier to see, with the expression SimplifiedBoard(&currNode). So every child node has its parent set to currNode. While this is a different object each iteration, we just saw that its address does not change. Every child is given the same address for its parent. Looking familiar?
I should note that the parent pointer becomes a dangling pointer at the end of the current iteration of the loop. That means the behavior of your code is undefined, so your results are not guaranteed. However, your results are typical.
Now to wrap up what happens, think about what happens to currNode in the second iteration. The top node of the priority queue is copied into currNode. In the first iteration, its parent pointer is null, but in the second iteration, its parent pointer is &currNode. This is the loop you see. The parent of currnode is currNode, as demonstrated in the third line of output. Once you realize this, you can simplify your test for the bug. Instead of going to currNode.parent->parent, you could simply check currNode.parent == &currNode and skip the null check.
So it's not so much that "the pointer it has towards its parent [...] turns into a pointer towards itself", but that the node is copied to where the parent pointer points. It's not this->parent that changes, but this.
So what can you do about this? The basic problem is that you create short-lived copies, when you need long-lived objects. A solution is to not create the copies.
Rather than creating new objects, your aStar function could use pointers to the existing objects. If object lifetime is a concern, you could use std::shared_ptr, but given the context, raw (non-owning) pointers are probably sufficient. Just be sure that all children are created before obtaining any of their addresses. Adding and removing elements from a container sometimes (depending on the container) invalidates pointers to other elements of that container.
I'll add emphasis on "your aStar function". The open and closed containers are what should store pointers instead of objects. What you do with the data members of SimplifiedBoard is a separate concern. And, yes, when you stop making copies, you will need to go back to storing children in the parent. This is a promising sign.
Here is an example of using pointers. This code does not exhibit the self-referential bug (but I left in the diagnostics).
#include <iostream>
#include <vector>
struct Node {
Node* parent = nullptr;
std::vector<Node> children; // <-- Not necessarily pointers
void generateMoves() {
// Only one child in this example
children.emplace_back(this);
// If not on a recent enough compiler version and C++20:
// children.emplace_back(Node{.parent = this, .children = {}});
}
};
// Return true on success, false on the bug.
bool aStar(Node& start) {
std::vector<Node*> open{&start}; // <-- Pointers
// Loop (with an arbitrary cap)
while (open.size() < 50) {
Node* currNode = open.back();
std::cout << "Address in currNode: " << currNode << "\n";
// ***BUG was seen here****
if (currNode->parent == currNode) {
std::cout << "Address of parent: " << currNode->parent << "\n";
return false;
}
// Add a child to OPEN.
currNode->generateMoves();
open.emplace_back(&currNode->children[0]);
}
return true;
}
int main() {
Node b;
if (aStar(b))
std::cout << "Success!\n";
else
std::cout << "Self-referential bug!\n";
}