时间戳

首页 > 解决方案 > A* 算法似乎在循环运行，我做错了什么？

c++ - A* 算法似乎在循环运行，我做错了什么？

问题描述

我已经为我正在制作的游戏编写了星型算法（我第一次使用它），但它无法找到任何超过一格的目标。我使用调试器查看发生了什么，它看起来确实有点像在循环运行。这是我的算法（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 命令缺少 ! 这搞砸了整个事情。

标签： c++a-star

解决方案

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

将其转录成评论。现在，留下评论，一行一行地写下来。

简单地转储一堆不工作的代码并问“我做错了什么”需要有人首先弄清楚你的代码的每一行试图做什么（不假设它正在做一些合理的事情），然后将其映射到实现A* 他们习惯于确定您所做的实际上会导致您所看到的问题。

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

TL; DR 什么“你做错了”是使用低级 C 风格编程编写算法，并且没有连接回算法的正式正确版本，并期望它能够工作。

通常，在编写足够重要的算法以命名时，您将希望能够参考您应该做什么的伪代码描述。简单地编写“做你认为应该做的事情”的代码会使追踪问题变得更加困难。

这可能与您找到的实现此类算法的示例代码不一致；有时这是因为编写示例代码的人已经实现了该算法数十次，有时是因为他们删除了注释（之后，或者在他们编写代码时），或者因为他们有信心（并且足够幸运）去做第一次就对了。

推荐阅读