A*算法似乎在兜圈子，我做错了什么

Question

我为我正在制作的游戏编写了一个星形算法(这是我第一次使用它)，但它找不到任何距离一个瓦片以上的目标。我使用调试器来查看发生了什么，它看起来确实有点像在绕圈运行。这是我的算法(sx，sy是起始瓦片坐标，tx，ty是目标坐标。此外，如果你想知道未定义的变量，这个函数也是一个类的一部分)：

void Pathfinder(int sx, int sy, unsigned int tx, unsigned int ty, int map[7][11],std::map<array2,Door*> doors,int dv){
if (!map[ty][tx] == 0){ return;}
Node map_nodes [7][11];
std::vector<Node*> open;
int current_index, x, y, tile;
path.clear();
map_nodes[sy][sx].load(sx,sy,tx,ty,0, true, false,0,0);
Node* current = &map_nodes[sy][sx];
open.push_back(current);
while (open.size() > 0) {
for (int b = 0; b < open.size(); ++b) {
if (b == 0 || open[b]->f < current->f) {
current = open[b];
current_index = b;
}
}
// checks if current is the target
if (current->x == tx && current->y == ty) {
int path_length = current->g + 1;
path.resize(path_length, {0, 0});
for (int p = 0; p < path_length; p++) {
path[p][0] = current->x;
path[p][1] = current->y;
current = &map_nodes[current->y][current->x];
}
return;
}
current->closed = true;
current->open = false;
open.erase(open.begin() + current_index);
for (int k = 0; k < 3; k++) {
for (int u = 0; u < 3; u++) {
if (k != 1 && u != 1) {
x = current->x + u - 1;
y = current->y + k - 1;
if (x >= 0 && y >= 0) {
//checks if it is traversable
if (map_nodes[y][x].closed || (map[y][x] == 0 || (map[y][x] >= dv && doors[{x, y}]->access_level <= acess_level))) {
if (!map_nodes[y][x].open) {
map_nodes[y][x].load(x, y, tx, ty, current->g + 1, true, false, current->x,current->y);
open.push_back(&map_nodes[y][x]);
} else if (current->g < map_nodes[y][x].g) {
map_nodes[y][x].update_f(current->g, current->x,current->y);
}
}
}
}
}
}
}
}

这是节点类：

class Node{
public:
int x = 0, y = 0, f = 0, g = 0, h = 0, px = 0, py = 0;
bool open = false, closed = false;
void load(int xa, int ya, int tx, int ty, unsigned int ga, bool opena, bool closeda, int pxa,int pya){
x = xa;
y = ya;
g = ga;
h = ((tx - x) * (tx - x)) + ((ty - y) * (ty - y));
f = g + h;
open = opena;
closed = closeda;
px = pxa;
py = pya;
}
void update_f(unsigned int ga, int pxa, int pya){
g = ga;
f = g + h;
px = pxa;
py = pya;
}
};

编辑：没关系修复它，有一个if命令缺少一个！把整件事搞砸了。

Answer 1

从一些A*伪代码开始，比如维基百科上的这个。(维基百科是著名算法的伪代码的不错来源，因为有足够多的随机人开车经过并修复最严重的拼写错误)

把它转录成评论。现在，留下评论，一行一行写下来。

简单地丢弃一堆不起作用的代码并问"我做错了什么"需要有人首先弄清楚试图做的每一行代码是什么(而不假设它在做合理的事情)，然后将其映射到他们习惯的a*的实现，确定你正在做的实际导致你看到的问题的事情。

每行旁边都有注释，说明应该做什么，查找bug的问题变得更容易了O(n)；你可以发现一行没有按照评论所说的去做，或者你可以在评论中发现一个错误。

TL；DR"你做错了"是使用低级C风格的编程编写一个算法，而没有连接到算法的正式正确版本，并期望它能工作。

一般来说，当编写足够重要的算法以获得名称时，您希望能够引用回您应该做的事情的伪代码描述。简单地编写"做你认为应该做的事情"的代码会让追踪问题变得越来越困难。

这可能与您发现的实现此类算法的示例代码不一致；有时，这是因为编写示例代码的人已经实现了几十次该算法，其他时候是因为他们删除了注释(无论是在之后，还是在编写代码时)，或者是因为他们有信心(而且足够幸运)第一次就做对了。