TL;DR I have a vector of std::shared_ptr's that I have to run std::push_heap, std::pop_heap, and std::find on. How do I compare the the things the pointers are pointing to rather than the pointers themselves?
Hi, I am trying to implement A* in my game and am having some trouble figuring out how to store all the nodes. Since I can't store a member of the same class in a class I have to use pointers. I can't use raw pointers because I realized that I would end up pointing to locations in a std::vector rather than the values stored in them. I now have decided that I will use std::shared_ptr's. However, I come across the issue in the TL;DR above. The Node object has an overload of the > operator, how can I end up using that. Here is my code; if anyone sees something that can be improved, please do say so.
Node.h
#ifndef NODE_H
#define NODE_H
#include <memory>
#include <SFML/Graphics.hpp>
class Node
{
public:
//Constructors
Node(std::shared_ptr<Node>, const sf::Vector2i&);
Node(const sf::Vector2i&);
//Getters
std::shared_ptr<Node> getParentNodePtr() const;
float getDistanceValue() const;
float getHeuristicValue() const;
float getTotalValue() const;
bool isStartNode() const;
sf::Vector2i getPosition() const;
//Setters
void setDistanceValue(float);
void setHeuristicValue(float);
void setTotalValue(float);
void setIsStartNode(bool);
//Comparison overloads
bool operator() (const Node&, const Node&) const;
bool operator== (const Node&) const;
bool operator< (const Node&) const;
private:
std::shared_ptr<Node> parentNodePtr_;
//Values
sf::Vector2i position_;
float distanceValue_ = 0.0f;
float heuristicValue_ = 0.0f;
float totalValue_ = 0.0f;
bool startNode_ = false;
};
#endif
Node.cpp
#include "Node.h"
Node::Node(std::shared_ptr<Node> parentNodePtr, const sf::Vector2i& position)
:parentNodePtr_(parentNodePtr)
{
position_ = parentNodePtr_->getPosition() + position * 32;
}
Node::Node(const sf::Vector2i& position)
:position_(position)
{}
//Getters
std::shared_ptr<Node> Node::getParentNodePtr() const { return parentNodePtr_; }
float Node::getDistanceValue() const { return distanceValue_; }
float Node::getHeuristicValue() const { return heuristicValue_; }
float Node::getTotalValue() const { return totalValue_; }
bool Node::isStartNode() const { return startNode_; }
sf::Vector2i Node::getPosition() const { return position_; }
//Setters
void Node::setDistanceValue(float distanceValue) { distanceValue_ = distanceValue; }
void Node::setHeuristicValue(float heuristicValue) { heuristicValue_ = heuristicValue; }
void Node::setTotalValue(float totalValue) { totalValue_ = totalValue; }
void Node::setIsStartNode(bool startNode) { startNode_ = startNode; }
//Comparison functor
bool Node::operator() (const Node& lhv, const Node& rhv) const {return lhv.totalValue_ < rhv.totalValue_; /*Backwards because I want a min-heap/min-priority-queue*/ }
bool Node::operator== (const Node& rhv) const {return position_ == rhv.position_; }
bool Node::operator< (const Node& rhv) const { return totalValue_ > rhv.totalValue_; }
Relevant Zombie.cpp
NOTE: sPNodes_ is a std::stack of std::shared_ptr's
Formatting wrong, use pastebin: http://pastebin.com/Z9NxTELV
void Zombie::findPath(std::vector< std::vector<Tile> >* pVTiles)
{
if(targetPosition_ != sf::Vector2i(0.0f, 0.0f))
{
//Initiates lists
std::vector<std::shared_ptr<Node>> openList;
std::vector<std::shared_ptr<Node>> closedList;
std::shared_ptr<Node> currentNode;
bool pathFound = false;
//Initiates the great journey
openList.push_back(std::make_shared<Node>(sf::Vector2i(positionGlobal_.x - fmod(positionGlobal_.x, 32.0f) + 16.0f, positionGlobal_.y - fmod(positionGlobal_.y, 32.0f) + 16.0f)));
openList.back()->setIsStartNode(true);
std::push_heap(openList.begin(), openList.end()); //NEED COMPARISON FOR THE POINTERS HERE
while(!pathFound)
{
//Gets the a pointer to the top item in the openList, then moves it to the closed list
std::pop_heap(openList.begin(), openList.end()); //NEED COMPARISON FOR THE POINTERS HERE
currentNode = openList.back();
closedList.push_back(currentNode);
openList.pop_back();
//Debug info
std::cout << std::endl << "TargetPosition: " << targetPosition_.x / 32 << ", " << targetPosition_.y / 32 << std::endl;
std::cout << "Position: " << currentNode->getPosition().x / 32 << ", " << currentNode->getPosition().y / 32 << std::endl;
std::cout << "Distance from start node: " << currentNode->getDistanceValue() / 32.0f << std::endl;
std::cout << "Heuristic Value: " << currentNode->getHeuristicValue() / 32.0f<< std::endl;
std::cout << "Total: " << currentNode->getTotalValue() / 32.0f << std::endl;
//For the eight neighboring tiles/nodes
for (int i = 0; i < 8; ++i)
{
int xPos;
int yPos;
//xPos
if(i == 0 || i == 4)
xPos = 0;
else if(i > 0 && i < 4)
xPos = 1;
else
xPos = -1;
//yPos
if(i == 2 || i == 6)
yPos = 0;
else if(i < 2 || i > 6)
yPos = 1;
else
yPos = -1;
sf::Vector2i nodePosition = currentNode->getPosition() + sf::Vector2i(xPos * 32, yPos * 32);
//Stop working if the node/tile is a wall or contains a tree
if(pVTiles->at(nodePosition.x / 32).at(nodePosition.y / 32).getType() == "unwalkable" || pVTiles->at(nodePosition.y / 32).at(nodePosition.x / 32).hasItem())
continue;
//Creates a node for the tile
auto node = std::make_shared<Node>(currentNode, sf::Vector2i(xPos, yPos));
//Checks to see if it is the target adds node to stack and breaks if so
if(node->getPosition() == targetPosition_)
{
std::cout << "found target!" << std::endl;
pathFound = true;
sPNodes_.push(node);
break;
}
//If it's not the target
if(!pathFound)
{
float parentDistanceValue = node->getParentNodePtr()->getDistanceValue();
//Distance is 1.4f x 32 if diagonal, 1 x 32 otherwise
if(xPos == yPos)
node->setDistanceValue(parentDistanceValue + 44.8f);
else
node->setDistanceValue(parentDistanceValue + 32.0f);
//Gets the distance to the target(Heuristic) and then gets the total(Distance + Heuristic)
node->setHeuristicValue(sqrt(pow(node->getPosition().x - targetPosition_.x, 2) + pow(node->getPosition().y - targetPosition_.y, 2)));
node->setTotalValue(node->getHeuristicValue() + node->getDistanceValue());
//Makes sure the node is not already in the open or closed list (NEED TO COMPARE VALUE OF WHAT THE POINTERS POINT TO HERE)
if(std::find(openList.begin(), openList.end(), node) == openList.end() && std::find(closedList.begin(), closedList.end(), node) == closedList.end())
{
openList.push_back(node);
std::push_heap(openList.begin(), openList.end()); //NEED COMPARISON HERE
}
}
}
}
//Keeps stacking parent nodes until the start is reached
while(!sPNodes_.top()->isStartNode())
{
std::cout << "stacking backward..." << std::endl;
std::cout << "Position: " << sPNodes_.top()->getPosition().x / 32 << ", " << sPNodes_.top()->getPosition().y / 32 << std::endl;
auto parent = sPNodes_.top()->getParentNodePtr();
sPNodes_.push(parent);
}
}
}
Thanks!
The second form of std::push_heap takes custom comparator as the third parameter, so you can give it the < overload:
struct SPtrNodeLess {
bool operator()(const std::shared_ptr<Node> &first, const std::shared_ptr<Node> &second) const {
return *first < *second;
}
}
std::push_heap(h.begin(), h.end(), SPtrNodeLess())
The std::find_if takes the unary predicate in similar fashion:
struct NodeSPtrEqual {
const Node &n;
NodeSPtrEqual(const Node &n) : n(n) {}
bool operator()(const std::shared_ptr<Node> &n2) {
return n == *n2;
}
}
std::find_if(h.begin(), h.end(), NodeSPtrEqual(node));
Or alternatively you can overload the operator== and use classic std::find:
bool operator==(const Node &n, const std::shared_ptr<Node> &n2) {
return n == *n2;
}
bool operator==(const std::shared_ptr<Node> &n, const Node &n2) {
return *n == n2;
}
std::find(h.begin(), h.end(), node);