在2D网格上开发A*的Stuck/常规帮助

Question

我想我已经接近完成这个A*的实现了，但是我的思想已经开始变得模糊，我正在寻找关于我应该做些什么来完成它的指针。

我目前的问题是，我通过A*运行的函数仍然停留在相同的节点上，因为在当前节点中永远不会移动到任何其他打开的节点。

下面是我的主函数，请注意，启发式( Node &n1，Node &n2)函数当前设置为总是返回0，因此它当前的工作方式应该更像Dijkstra算法，而不是A*。此外，移动被限制在NESW平面上，没有对角移动，因此distance_between(Node &n1，Node &n2)总是返回1。

void astar(Node start_, Node end_) {

    Node start = start_;
    Node end = end_;

    // compute f,g,h for the start node
    start.g = 0;
    start.h = heuristic(start, end);
    start.f = start.g + start.h;

    // insert start node into the open set
    openNodes.insert(&start);

    // while the set of open nodes is not empty
    while (openNodes.size() > 0) {

        // pick the most promising node to look at next
        Node currentNode;

        cout << "currentNode before: ";
        currentNode.displaylocation();

        // go through all the open nodes and find the one with the smallest 'f' value
        Node* minf = (*openNodes.begin()); // set initial value for minimum f to be the first node in the set of open nodes

        for (auto n : openNodes) {
            if (n->f <= minf->f) {
                minf = n;
            }
        }
        currentNode = *minf; // set the current node to the node that holds the smallest 'f' value

        cout << "currentNode after: ";
        currentNode.displaylocation();

        // if the current node is the end node, then we have found a path
        if (currentNode.type == -3) {
            break;
        }

        // remove the current node from the set of open nodes, and add it to the set of closed nodes
        openNodes.erase(&currentNode);
        closedNodes.insert(&currentNode);

        // go through the currents node's neighbours
        for (auto n : neighbours(currentNode)) {
            cout << "neighbour local: " << n.location.x << "," << n.location.y << "\n";

            if (closedNodes.count(&n) == 0 && n.type != -2) { // if this node is neither closed or a blocker
                int new_g = currentNode.g + distance_between(currentNode, n);

                if (openNodes.count(&n) != 0) { // if we have not seen this node before, add to the open set
                    openNodes.insert(&n);
                }
                else if (new_g >= n.g) { // else if we have seen this node before, and already found a shorter path to it from the starting node

                }
                n.g = new_g;
                n.f = n.g + heuristic(n, end);
                n.parent_ = &currentNode;
            }
        }

        cout << "\n A* run success! \n";
        //break;
    }
}

下面是Node结构和全局变量的减速：

// The size of the grid
#define WIDTH 6
#define HEIGHT 6

// Holds values for x and y locations on the grid
struct Coord {
    int x, y;
};

// holds data for each node required for A*
struct Node {
    int type; // used for defining if this node is a blocker, empty, start or end
    Coord location;
    int g = 0;
    int h = 0;
    int f = g + h;
    Node *parent_; // pointer to this node's parent

    std::string debugmessage;

    void displaylocation() {
        std::cout << "I am the node at: " << location.x << "," << location.y << "\n";
    }
};

// The 2D grid array for A*, requiring a Node struct to store the data of each cell
Node astarArray[WIDTH][HEIGHT];

// Sets for A*
std::set<Node *> openNodes; // contains the nodes that are yet to be considered (if this is empty, then there are no more paths to consider or there is no path)
std::set<Node *> closedNodes; // contains the nodes that have already been considered (if the end node is placed in here, a path has been found)    

// stores the start and end values for A*
Node start_A, end_A;

void astar(Node start_, Node end_);
int distance_between(Node& n1, Node& n2);
int heuristic(Node& n1, Node& n2);
std::list<Node> neighbours(Node& n_);


// returns the distance between two nodes for A*
int distance_between(Node& n1, Node& n2) {
    return 1; // always return 1 as we are working in a grid restricted to NSEW movement
}


int heuristic(Node& n1, Node& n2) {
    return 0; // return 0 to work as a Dijkstra algorithm rather than A*
}


// finds a node's neighbours for A*
std::list<Node> neighbours(Node& n_) {

    std::list<Node> neighbours_;

    int x = n_.location.x;
    int y = n_.location.y;
    // start at the location belonging to 'n_'
    //for (int y = n_.location.y; y < HEIGHT; y++) {
        //for (int x = n_.location.x; x < WIDTH; x++) {

            // east
            if (x < WIDTH - 1) {
                neighbours_.push_back(astarArray[x + 1][y]);
            }
            // west
            if (x > 0) {
                neighbours_.push_back(astarArray[x - 1][y]);
            }
            // south
            if (y < HEIGHT - 1) {
                neighbours_.push_back(astarArray[x][y + 1]);
            }
            // north
            if (y > 0) {
                neighbours_.push_back(astarArray[x][y -1]);
            }
        //}
    //}

    return neighbours_;
}

非常感谢您的阅读和您能给予的任何帮助。我会提供更多的代码，如果需要。

Answer 1

您遇到的主要问题是您正在使用指针(内存地址)来找出节点是否在您的集合中。

currentNode = *minf; // set the current node to the node that holds the smallest 'f' value

然后将minf的内容复制到currentNode。currentNode的地址将与指向minf的指针不同

因为currentNode没有相同的地址，所以openNodes.erase(&currentNode);不会删除minf。

• ，我建议你更多地研究如何实现A*，因为你遗漏了一些步骤。使用网格(pos.x * numCols) + pos.y

中该节点的位置索引，查找该节点的内存地址的优先级queues.

• Instead