如何在 C++ 中使用 A* 追溯路径？

Question

几周来我一直在尝试实现 A*，这样敌人就可以在我的游戏中追逐玩家，但我无法让它发挥作用。我整个周末都在研究它，最后我什至把它的大部分内容都删掉了，然后重新写了一遍。我可以画出一条从起点到终点的路径，但我无法追溯回去，就像实际写下路径一样。我正在使用来自 SFML 的 Vector2f（有序的一对浮点数）和 Sprite，但那里的所有代码都非常简单，所以你真的不需要理解它。

编辑：问题出在 Node.cameFrom。出于某种原因，它除了墙壁什么都没有。

这里是Node.h

#ifndef NODE_H
#define NODE_H
#include <SFML/Graphics.hpp>

using namespace sf;

class Node {
    public:
        Vector2f pos;
        // Distance traveled already to reach node
        int level;
        // Level + estimated dist to goal
        int priority;

        Node *cameFrom;

        Node(Vector2f npos, int lv, Vector2f dest, Node *cf=nullptr);

        bool operator == (const Node &nhs) const {
            return nhs.priority == priority;
        }

};

#endif // NODE_H

Node.cpp

#include "Node.h"
#include <SFML/Graphics.hpp>
#include <math.h>
#include <iostream>

using namespace std;
using namespace sf;

int estimatedDist(Vector2f pos, Vector2f dest) {
    return abs(dest.x - pos.x) + abs(dest.y - pos.y);
}

Node::Node(Vector2f npos, int lv, Vector2f dest, Node *cf) {
    cameFrom = cf;
    level = lv;
    pos = npos;
    priority = level + estimatedDist(pos, dest);
}

Enemy.cpp 寻路函数

bool occupies(Vector2f pos, vector<Wall> walls) {
    for (unsigned w = 0; w < walls.size(); w++) {
        if (walls.at(w).collisionBox.getGlobalBounds().contains(pos.x * 32, pos.y * 32)) {
            return true;
        }
    }
    return false;
}

bool nFind(Node n, vector<Node> nodes) {
    for (unsigned i = 0; i < nodes.size(); i++) {
        if (nodes.at(i).pos == n.pos) {
            return true;
        }
    }
    return false;
}

void Enemy::pathFind(Vector2f dest, vector<Wall> walls) {
    char fullMap[32][22];
    vector<Node> openSet;
    vector<Node> closedSet;
    int xStart, yStart;
    for (unsigned y = 0; y < 22; y++) {
        for (unsigned x = 0; x < 32; x++) {
            if (sprite.getGlobalBounds().top >= y * 32 && sprite.getGlobalBounds().top <= (y + 1) * 32) {
                if (sprite.getGlobalBounds().left >= x * 32 && sprite.getGlobalBounds().left <= (x + 1) * 32) {
                    xStart = x;
                    yStart = y;
                }
            } if (occupies(Vector2f(x, y), walls)) {
                fullMap[x][y] = '2';
            } else {
                fullMap[x][y] = ' ';
            }
        }
    }
    fullMap[int(dest.x)][int(dest.y)] = 'D';
    Node *current = new Node(Vector2f(xStart, yStart), 0, dest);
    fullMap[int(current->pos.x)][int(current->pos.y)] = '2';
    openSet.push_back(*current);

    while (openSet.size() > 0) {
        sort(openSet.begin(), openSet.end(), sortByPriority());
        *current = openSet.front();

        if (current->pos == dest) {
            cout << "We gots it ";
            for (unsigned y = 0; y < 22; y++) {
                for (unsigned x = 0; x < 32; x++) {
                    if (occupies(Vector2f(x, y), walls)) {
                        fullMap[x][y] = '2';
                    } else {
                        fullMap[x][y] = ' ';
                    }
                }
            }
            while (current->cameFrom) {
                fullMap[int(current->pos.x)][int(current->pos.y)] = 'P';
                current = current->cameFrom;
                for (unsigned y = 0; y < 22; y++) {
                    for (unsigned x = 0; x < 32; x++) {
                        cout << fullMap[x][y];
                    }
                    cout << endl;
                }
                cout << endl;
            } for (unsigned y = 0; y < 22; y++) {
                for (unsigned x = 0; x < 32; x++) {
                    cout << fullMap[x][y];
                }
                cout << endl;
            }
            cout << endl;
            return;
        }

        openSet.erase(remove(openSet.begin(), openSet.end(), *current), openSet.end());
        closedSet.push_back(*current);
        fullMap[int(current->pos.x)][int(current->pos.y)] = '2';

        vector<Node> neighbors;

        neighbors.push_back(Node(Vector2f(current->pos.x - 1, current->pos.y - 1), current->level + 1, dest));
        neighbors.push_back(Node(Vector2f(current->pos.x, current->pos.y - 1), current->level + 1, dest));
        neighbors.push_back(Node(Vector2f(current->pos.x + 1, current->pos.y - 1), current->level + 1, dest));
        neighbors.push_back(Node(Vector2f(current->pos.x + 1, current->pos.y), current->level + 1, dest));
        neighbors.push_back(Node(Vector2f(current->pos.x + 1, current->pos.y + 1), current->level + 1, dest));
        neighbors.push_back(Node(Vector2f(current->pos.x, current->pos.y + 1), current->level + 1, dest));
        neighbors.push_back(Node(Vector2f(current->pos.x - 1, current->pos.y + 1), current->level + 1, dest));
        neighbors.push_back(Node(Vector2f(current->pos.x - 1, current->pos.y), current->level + 1, dest));

        for (unsigned i = 0; i < neighbors.size(); i++) {
            if (nFind(neighbors.at(i), closedSet) ||
                neighbors.at(i).pos.x > 22 ||
                neighbors.at(i).pos.y > 32 ||
                neighbors.at(i).pos.x < 0 ||
                neighbors.at(i).pos.y < 0 ||
                occupies(neighbors.at(i).pos, walls)) {

                continue;
            } if (!nFind(neighbors.at(i), openSet)) {
                openSet.push_back(neighbors.at(i));
            }
            neighbors.at(i).cameFrom = current;
        }
    }
}

Answer 1

对于每个图块，您需要它的成本（到达那里的成本加上启发式），以及您到达它的相邻图块的标识。

该算法在起点周围有 "balloon" 个点，首先分析最佳点。所以如果路径很简单，气球就会被拉长。如果它是复杂的，气球是圆的，许多路径因为被墙壁和已经访问过的瓷砖包围而被放弃。

Answer 2

MCVE 会帮助我们尝试（见 zett42 评论）。

因此，只要快速浏览一下，我就可以为您提供一些在调试过程中查看的指示，但没有明确的答案。

这些行看起来非常可疑：

Node *current = new Node(Vector2f(xStart, yStart), 0, dest);
// ^ no delete in source, will leak memory

*current = openSet.front();
// will overwrite the heap memory with copy constructor
// but the pointer will remain the same
// so all of your nodes will always have "cameFrom"
// pointing to this same memory.

总的来说这段代码看起来有点复杂。你有固定方形 32x22 方块的游戏吗？为什么 "walls" 向量呢？

我会只维护单个全局瓦片地图作为关卡（但 A* 搜索不应该损坏它，而是创建它自己的副本以供搜索，或者更确切地说是拥有具有到达成本的新地图，即可能会大大简化代码）。

xStart, yStart可以直接计算，不需要每次循环都重复：

xStart = int(sprite.getGlobalBounds().left)>>5;  // left/32
yStart = int(sprite.getGlobalBounds().top)>>5;   // top/32

bool operator == (const Node &nhs) const看起来不健康，但它甚至没有在任何地方使用。

而要查看邻居是否在墙内，您不需要使用 O(N) occupies，只需测试 == '2' 的地图？（我的意思是如果代码是那样设计的，我没有验证如果您立即在代码中更改它是否会按预期工作）。

总体而言，我不喜欢该代码，如果您专注于要处理的数据以及处理方式，并且停止在多个列表中来回移动对象，则可以将其简化为较短的版本。对于 A* IIRC，您应该需要带有 insert_at 的单个排序队列来保持排序，而 map 字段则需要标记哪些方块已被处理。

那些Vector2f位置重要吗，例如：

...
P#D
...

如果玩家"P"站在方格的下部（“#”是墙，"D"是目的地），A*应该找到底部路径，还是只需要"tile" 精度和上面的路径也好吗？

我不清楚你的问题，你是否以子图块的精度工作，如果不是，那么你可以放弃大部分 Vector2f 的东西，只在图块坐标中工作。

以子图块精度，您可能仍然可以丢弃大部分，但如果实际上图块的大小为“32”，而玩家例如只有“3”宽，那么他可以将图块用作某种"area" 并通过不同的线穿过它，避免在上面的示例中到达中间瓷砖的完整中心，节省距离......然后您需要以某种方式计算这些子瓷砖位置以至少获得大致准确 "shortest"路径。

当我在做一个游戏时，我们有节点链表（经典数学图）而不是图块，每个节点都有它的 "area radius"，并且在找到最短的节点到节点路径之后，另一种迭代算法做了很少的循环，从节点位置移动到半径内的某个影子节点位置，但更接近其他两个影子节点。在达到最大迭代次数后，或者阴影位置变化不大（通常最多需要 3-5 次迭代），它停止 "smoothing" 路径并返回它。这样，士兵们运行几乎是直线穿过沙漠，而实际上路点节点就像稀疏的网格，区域半径为 20 米，所以士兵实际上只走了 2-3 个节点，starting/ending 远远离节点中心在节点图中几乎呈锯齿形。

如何在 C++ 中使用 A* 追溯路径？

How do I trace back a path using A* in C++?

c++

a-star

path-finding

sfml