在STL Heap和std :: find中比较std :: shared_ptr的值。 （试图实现A *）

Question

TL; DR 我有一个std :: shared_ptr的向量，我必须运行std :: push_heap，std :: pop_heap和std :: find。我如何比较指针指向的内容而不是指针本身？我想在我的游戏中实现A *，并且在计算如何存储所有节点时遇到了一些麻烦。因为我不能在一个类中存储同一个类的成员，所以我必须使用指针。我不能使用原始指针，因为我意识到我最终会指向std :: vector中的位置，而不是存储在它们中的值。我现在已经决定我将使用std :: shared_ptr's。但是，我在上面的TL; DR中遇到了这个问题。 节点对象有一个过载的运算符，我怎么能最终使用它。这是我的代码;如果有人看到可以改进的东西，请说明一下。

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

相关Zombie.cpp

注：sPNodes_是的std ::堆栈的std :: shared_ptr的的

格式错误，使用引擎收录：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);  
    } 
    } 
} 

谢谢！

Answer 1

的std::push_heap第二种形式定制比较器作为第三个参数，所以可以给它<过载：

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()) 

的std::find_if需要以类似的方式与一元谓词：

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

或者，您可以重载operator==并使用经典的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);