c++ - 比较 STL 堆中 std::shared_ptr 的值和 std::find。 (尝试实现 A*)

Question

长话短说 我有一个 std::shared_ptr vector ，我必须在上面运行 std::push_heap、std::pop_heap 和 std::find。我如何比较指针指向的事物而不是指针本身？

---

您好，我正在尝试在我的游戏中实现 A*，但在弄清楚如何存储所有节点时遇到了一些问题。因为我不能在一个类中存储同一个类的成员，所以我必须使用指针。我不能使用原始指针，因为我意识到我最终会指向 std::vector 中的位置，而不是存储在其中的值。我现在决定使用 std::shared_ptr。但是，我在上面的 TL;DR 中遇到了这个问题。 Node 对象重载了 > 运算符，我如何才能最终使用它。这是我的代码；如果有人看到可以改进的地方，请说出来。

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::shared_ptr 的 std::stack

格式错误，使用 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);    
    }
    }
}

谢谢!

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