如何在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 pathfind功能

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

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瓷砖的游戏吗？为什么“墙”的矢量呢？

我只会维护一个单一的全局瓷砖地图作为关卡（但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的单个排序队列来保持它与地图字段的排序，以标记哪些方块已经被处理。

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

... 
P#D 
... 

如果球员 “P” 矗立在广场的下部（ “＃” 是墙， “d” 为目标），如果A *找到底部的路径，或者你只需​​要“瓦”的准确性，上部路径也会好呢？

我不明白你的问题，无论你是否使用子拼贴精度，如果不是，那么你可以放弃大部分Vector2f的东西，只能在拼贴坐标中工作。

使用子拼图的精度，你仍然可以放弃大部分的精度，但是如果实际上拼图具有“32”大小，而玩家例如只有“3”宽，那么他可以使用拼图作为某种“区域“并且通过不同的线移动穿过它，避免在上面的示例中去到中间区块的全部中心，节省距离...然后，您需要以某种方式计算这些子区块位置以获得至少大致准确的”最短“路径。

当我在一个游戏上工作时，我们链接了节点列表（经典数学图）而不是瓦片，每个节点都有它的“区域半径”，并且在找到最短的节点到节点路径之后，另一个迭代算法没有几个循环从节点位置移动到半径内的阴影节点位置，但更接近其他两个阴影节点。在达到最大迭代次数后，或者阴影位置变化不大（通常最多需要3-5次迭代），它会停止“平滑”路径并将其返回。这样，士兵几乎直线穿过沙漠，而实际上路点节点就像半径20米的稀疏网格，所以士兵实际上只有2-3个节点，远离节点中心的开始/结束时间差不多节点图本身中的锯齿形。

Answer 2

每瓦，你需要它的成本（到达那里的成本加上启发式）以及您到达它的邻近区块的标识。

该算法具有点圆起点的“气球”，最好的一点是首先分析。所以如果路径很简单，气球就非常细长。如果它很复杂，气球是圆的，许多路径被抛弃，因为墙壁和已经访问过的瓷砖被卷入。