A *星算法帮助C++

Question

我的打开和关闭列表有问题。如果我改变B并移动它不起作用，但是在地图的某些地方，如果我改变了B的位置，那么它将再次起作用。如果任何人都可以帮我解决我出错的地方，我会非常感激。由于

#include <iostream> 
#include <string> 
#include <cmath> 
#include <vector> 
#include <utility> 
#include <algorithm> 
#include <queue> 

using namespace std; 

class CNode 
{ 
public: 

    CNode() : xPos(0), yPos(0), travelCost(0) {} 
    CNode(int x, int y) : xPos(x), yPos(y), travelCost(0) {} 
    CNode(int x, int y, int cost) : xPos(x), yPos(y), travelCost(cost) {} 

    inline CNode& operator=(const CNode& target) 
    { 
     if (*this != target) 
     { 
      xPos = target.xPos; 
      yPos = target.yPos; 
      travelCost = target.travelCost; 
     } 

     return *this; 
    } 

    inline bool operator==(const CNode& target) const 
    { 
     return xPos == target.xPos && yPos == target.yPos; 
    } 

    inline bool operator!=(const CNode& target) const 
    { 
     return !(*this == target); 
    } 

    inline bool operator<(const CNode& target) const 
    { 
     return target.travelCost < travelCost; 
    } 

    int xPos, yPos, travelCost; 
}; 

class CPath 
{ 
public: 

    typedef vector<CNode> nodeList; 

    nodeList Find(const CNode& startNode, const CNode& endNode, int mapArray[][20]) 
    { 
     nodeList finalPath, openList, closedList; 

     finalPath.push_back(startNode); 
     openList.push_back(startNode); 
     closedList.push_back(startNode); 

     while (!openList.empty()) 
     { 
      // Check each node in the open list 
      for (size_t i = 0; i < openList.size(); ++i) 
      { 
       if (openList[i].xPos == endNode.xPos && openList[i].yPos == endNode.yPos) 
        return finalPath; 

       priority_queue<CNode> nodeQueue; 

       // Get surrounding nodes 
       for (int x = -1; x <= 1; ++x) 
       { 
        for (int y = -1; y <= 1; ++y) 
        { 
         const int current_x = openList[i].xPos + x; 
         const int current_y = openList[i].yPos + y; 

         bool alreadyCheckedNode = false; 
         for (size_t i = 0; i < closedList.size(); ++i) 
         { 
          if (current_x == closedList[i].xPos && current_y == closedList[i].yPos) 
          { 
           alreadyCheckedNode = true; 
           break; 
          } 
         } 

         if (alreadyCheckedNode) 
          continue; 

         // Ignore current coordinate and don't go out of array scope 
         if (current_x < 0 || current_x > 20 || current_y < 0 ||current_y > 20 || (openList[i].xPos == current_x && openList[i].yPos == current_y)) 
          continue; 

         // Ignore walls 
         if (mapArray[current_x][current_y] == '#') 
          continue; 

         const int xNodeDifference = abs(current_x - (openList[i].xPos)); 
         const int yNodeDifference = abs(current_y - (openList[i].yPos));    

         // Diagonal? 
         const int direction = xNodeDifference == 1 && yNodeDifference == 1; //? 14 : 10; 

         const int xDistance = abs(current_x - endNode.xPos); 
         const int yDistance = abs(current_y - endNode.yPos); 
         int heuristic = 10 * (xDistance + yDistance); 

         nodeQueue.push(CNode(current_x, current_y, heuristic)); 
        } 
       } 

       if (!nodeQueue.empty()) 
       { 
        // Add the nearest node 
        openList.push_back(nodeQueue.top()); 
        finalPath.push_back(nodeQueue.top()); 

        // Put into closed list 
        while (!nodeQueue.empty()) 
        { 
         closedList.push_back(nodeQueue.top()); 
         nodeQueue.pop(); 
        } 
       } 
      } 
     } 

     return finalPath; 
    } 
}; 

int mapArray[20][20] = 
{ 
    { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }, 
    { '#', 'A', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', 'B', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' }, 
    { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }, 

}; 

int main(int argc, char** argv) 
{ 
    CNode start, end; 

    for (int width = 0; width < 20; ++width) 
    { 
     for (int height = 0; height < 20; ++height) 
     { 
      if (mapArray[width][height] == 'A') 
      { 
       start.xPos = width; 
       start.yPos = height; 
      } 
      else if (mapArray[width][height] == 'B') 
      { 
       end.xPos = width; 
       end.yPos = height; 
      } 
     } 
    } 

    CPath pathFinder; 
    CPath::nodeList n = pathFinder.Find(start, end, mapArray); 

    for (int i = 0; i < n.size(); ++i) 
     if (mapArray[n[i].xPos][n[i].yPos] != 'A' && mapArray[n[i].xPos][n[i].yPos] != 'B') 
      mapArray[n[i].xPos][n[i].yPos] = '*'; 

    for (int height = 0; height < 20; ++height) 
    { 
     for (int width = 0; width < 20; ++width) 
     { 
      if (width % 20 == 0) 
       cout << endl; 

      cout << (char)mapArray[height][width] << " "; 
     } 
    } 

    cin.get(); 

    return 0; 
} 

Answer 1

似乎有是一些事情不对的：

1. 你永远不会从openList流行，这意味着每一次你检查，你已经看过节点，将节点推入已经在openList或closedList中的openList。这增加了很多计算。

2. 当你真的只需要两个队列和列表时，你有许多队列和列表。您需要一个列表（甚至更好，一个映射，以便检查某个节点是否已被扩展）以跟踪哪些节点已被扩展，并且您需要一个优先级队列来从中拉出下一个节点。因此，不必为openList设置一个嵌套for循环，而只需要使用while循环，然后每次从具有最佳启发式值的节点中弹出（例如，您期望让您距离目标最近的那个节点基于你的启发式）。

还有几个细节可以解决最终路径，但我认为只有两个数据结构而不是三个会将您的代码推向正确的方向。