这是AStar.h头文件

#include #include//双端队列 #include #define STEP 10//单位长度 #define STEP_DIAGONAL 14//单位对角线长度 class Node{ private: int x; int y; int g;//沿着生成的路径，从开始节点到指定区域的移动消耗（可以沿对角线走） int h;//估算从指定区域格子到目的地格子的移动消耗（只准横着走，竖着走） int f;//F=G+H Node *father; public: static deque open, closed; Node(); Node(int x, int y); void setX(int x); void setY(int y); void setG(int g); void setH(Node &goal); void setF(); void setFather(int x, int y); void setFather(Node &father); void setFather(Node *father); int getX(); int getY(); int getG(); int getH(); int getF(); Node* getFather(); static void addBarrier(int x, int y); static void addBarrier(Node barrier); Node operator=(const Node&); bool operator==(const Node&); Node createSunNode(int direction, Node goal); static void addToOpen(Node node); static void addToOpenWithOpenNotHave(Node node);//已经确认不在open表中 static void addToClosed(Node node); static bool isInOpen(Node node); static bool isInClosed(Node node); void printNode(); };

这是AStar.cpp文件：

#include #include #include #include #include #include"AStar.h" const int LEFT = 0; const int LEFT_UP = 1; const int UP = 2; const int UP_RIGHT = 3; const int RIGHT = 4; const int RIGHT_DOWN = 5; const int DOWN = 6; const int LEFT_DOWN = 7; using namespace std; Node::Node() :x(0), y(0), g(0), h(0), f(0) { } Node::Node(int x, int y) : x(x), y(y), g(0), h(0), f(0) { } void Node::setX(int x) { this->x = x; } void Node::setY(int y) { this->y = y; } void Node::setG(int g) { this->g = g; } void Node::setH(Node &goal) { this->h = abs(goal.x - this->x) + abs(goal.y-this->y);//横坐标差的绝对值+纵坐标差的绝对值 } void Node::setF() { this->f = this->g + this->h; } void Node::setFather(int x, int y) { this->father->x = x; this->father->y = y; } void Node::setFather(Node &father) { this->father->x = father.x; this->father->y = father.y; this->father->g = father.g; this->father->h = father.h; this->father->f = father.f; } void Node::setFather(Node *father) { this->father->x = father->x; this->father->y = father->y; this->father->g = father->g; this->father->h = father->h; this->father->f = father->f; } int Node::getX() { return x; } int Node::getY() { return y; } int Node::getG() { return g; } int Node::getH() { return h; } int Node::getF() { return f; } Node* Node::getFather() { return father; } void Node::addBarrier(int x, int y) { Node node(x,y); closed.push_back(node); } void Node::addBarrier(Node barrier) { closed.push_back(barrier); } Node Node::operator=(const Node& nodeOrigin) { this->x = nodeOrigin.x; this->y = nodeOrigin.y; this->g = nodeOrigin.g; this->h = nodeOrigin.h; this->f = nodeOrigin.f; this->setFather(nodeOrigin.father); return *this; } bool Node::operator==(const Node& node) { return this->x==node.x&&this->y==node.y; } Node Node::createSunNode(int direction, Node goal) { Node sun = *this;//C++在this对象指针前面加*表示对象。 // switch (direction) { case LEFT: sun.setX(sun.getX() - 1); break; case LEFT_UP: sun.setX(sun.getX() - 1); sun.setY(sun.getY() - 1); break; case UP: sun.setY(sun.getY() - 1); sun.setG(sun.getG()+STEP); break; case UP_RIGHT: sun.setX(sun.getX() + 1); sun.setY(sun.getY() - 1); break; case RIGHT: sun.setX(sun.getX() + 1); break; case RIGHT_DOWN: sun.setX(sun.getX() + 1); sun.setY(sun.getY() + 1); break; case DOWN: sun.setY(sun.getY() + 1); break; case LEFT_DOWN: sun.setX(sun.getX() - 1); sun.setY(sun.getY() + 1); break; default: break; } if (direction%2==0) { //上下左右直走,STEP sun.setG(sun.getG()+STEP); } else { //对角线,STEP_DIAGONAL sun.setG(sun.getG()+STEP_DIAGONAL); } sun.setH(goal); sun.setF(); // return sun; } void Node::addToOpen(Node node) { if (isInClosed(node)) { return; } //检查是否在open bool isInOpen = false; deque::iterator iter;//iter是Node*类型 for (iter = open.begin(); iter != open.end();iter++) { if (*iter==node) { isInOpen = true; break; } } if (isInOpen) { //是否G成本更低 if (node.getG()<(iter->getG())) { //是，改变在open表中的这个node节点的父节点 iter->setFather(node.getFather()); //重新根据F值排序 Node temp = *iter; open.erase(iter); //iter不能再用了，因为删除操作使iter失效了 addToOpenWithOpenNotHave(temp); } else { //否，do nothing } } else { addToOpenWithOpenNotHave(node); } } //已经确认要添加的node不在open表中 void Node::addToOpenWithOpenNotHave(Node node) { //不在open表中，加入open（open表按F值从大到小排列） if (open.size()>0) { for (int i = open.size() - 1; i >= 0; i--) { if (open[i].getF() >= node.getF()) { //这里可能有问题 open.insert(open.begin() + i, node); break; } else { if (i == 0) { open.push_front(node); } } } } else { open.push_back(node); } } void Node::addToClosed(Node node) { closed.push_back(node); } bool Node::isInOpen(Node node) { bool isInOpen = false; deque::iterator iter;//iter是Node*类型 for (iter = open.begin(); iter != open.end(); iter++) { if (*iter == node) { isInOpen = true; break; } } return isInOpen; } bool Node::isInClosed(Node node) { bool result = false; for (int i = 0; i < closed.size(); i++) { if (closed[i] == node) { return true; } } return result; } void Node::printNode() { cout << "x = "<x<#include"AStar.h" #include using namespace std; int main() { Node original(1,2); Node goal(5,2); Node::addToClosed(goal); Node::addToOpenWithOpenNotHave(original); Node::addBarrier(3,1); Node::addBarrier(3,2); Node::addBarrier(3,3); Node lastOne = Node::open.back(); if (lastOne==goal) { cout << "success" << endl; lastOne.printNode(); } Node::closed.push_back(lastOne); Node::open.pop_back(); //生成并添加子节点 for (int i = 0; i < 8;i++) { Node sun = lastOne.createSunNode(i, goal); Node::addToOpen(sun); } return 0; }