A * pathing 코드에서 잘못된 검색

Question

A * 경로를 찾기 위해 작성한 일부 C++ 코드가 있지만 이상하게 작동합니다. 여기에 꽤 많은 코드가 있습니다. 그래서 그것을 덩어리로 나누고 내가하고있는 것을 설명하려고 노력할 것입니다. A * pathing이 어떻게 작동하는지 설명하지 않을 것입니다. 나는 당신이 알고리즘을 이미 알고있는 것을 도우려는 것으로 가정한다.

우선, 여기 노드의 시간 값 계산하는 내 함수의 :

int 
calculateH(int cX, int cY, int eX, int eY, int horiCost = 10, int diagCost = 14) { 
int h; 
int xDist = abs(eX - cX); 
int yDist = abs(eY - cY); 

if (xDist > yDist) 
    h = (diagCost * yDist) + (horiCost * (xDist - yDist)); 
else 
    h = (diagCost * xDist) + (horiCost * (yDist - xDist)); 

return h; 
} 

를 내가 여기에 아무 문제가 없습니다 확신 해요; 아주 간단한 물건.

다음 내 노드 클래스. 그리고 저는 알고 있습니다. 변수를 비공개로 만들고 게터를 사용합니다. 방금 테스트 목적으로이 방법을 사용했습니다.

class Node { 
public: 
Node(int x_, int y_, int g_, int h_, int pX_, int pY_, bool list_) { 
    x = x_; 
    y = y_; 
    g = g_; 
    h = h_; 
    pX = pX_; 
    pY = pY_; 
    list = list_; 
}; 
int x, y, g, h, pX, pY; 
bool list; 
}; 

각 노드에는 X 및 Y 변수가 있습니다. 나는 F와 F를 제외한 G와 H 만 저장하고 필요할 때 F를 계산합니다 (코드에서 한 번만). 그런 다음 상위 X 값과 Y 값이 있습니다. List는 부울입니다. fale = 열린 목록, true = 닫힌 목록.

또한 Object 클래스가 있습니다. 여기에서 중요한 변수는 X, Y 및 Passable이며 모두 getter를 통해 액세스합니다.
이제 실제 길 찾기 코드의 시작입니다. 아래 그림과 같이 그것은 방향에 해당하는 숫자의 문자열을 반환
678
432
(501)
그래서 1 수단은 8 개 수단 아래로 바로 이동을 오른쪽으로 이동, 0 수단은 어디 가지 않는다.

string 
findPath(int startX, int startY, int finishX, int finishY) { 
// Check if we're already there. 
if (startX == finishX && startY == finishY) 
    return "0"; 
// Check if the space is occupied. 
for (int k = 0; k < objects.size(); k ++) 
    if ((objects[k] -> getX() == finishX) && 
     (objects[k] -> getY() == finishY) && 
     (!objects[k] -> canPass())) 
     return "0"; 
// The string that contains our path. 
string path = ""; 
// The identifier of the current node. 
int currentNode = 0; 
// The list of nodes. 
vector<Node> nodes; 
// Add the starting node to the closed list. 
nodes.push_back(Node(startX, startY, 0, 
    calculateH(startX, startY, finishX, finishY), 
    startX, startY, true)); 

이제 목적지를 찾을 때까지 반복합니다. sizeLimit는 우리가 영원히 반복하지 않도록하기위한 것입니다 (이 코드를 고칠 수 없다면 문제가 발생합니다. 지금 당장은 필수적입니다). 이 점에서부터 내가 다르게 표시 할 때까지는 ij 루프 안에 있습니다.

다음 부분

int sizeLimit = 0; 
while ((nodes[currentNode].x != finishX) | (nodes[currentNode].y != finishY)) { 

    // Check the surrounding spaces. 
    for (int i = -1; i <= 1; i ++) { 
     for (int j = -1; j <= 1; j ++) { 
      bool isEmpty = true; 
      // Check if there's a wall there. 
      for (int k = 0; k < objects.size(); k ++) { 
       if ((objects[k] -> getX() == (nodes[currentNode].x + i)) && 
        (objects[k] -> getY() == (nodes[currentNode].y + j)) && 
        (!objects[k] -> canPass())) { 
        isEmpty = false; 
       } 
      } 

:

// Check if it's on the closed list. 
      for (int k = 0; k < nodes.size(); k ++) { 
       if ((nodes[k].x == (nodes[currentNode].x + i)) && 
        (nodes[k].y == (nodes[currentNode].y + j)) && 
        (nodes[k].list)) { 
        isEmpty = false; 
       } 
      } 

는에 계속 :

// Check if it's on the open list. 
      for (int k = 0; k < nodes.size(); k ++) { 
       if ((nodes[k].x == (nodes[currentNode].x + i)) && 
        (nodes[k].y == (nodes[currentNode].y + j)) && 
        (!nodes[k].list)) { 
        // Check if the G score is lower from here. 
        if (nodes[currentNode].g + 10 + (abs(i * j) * 4) <= nodes[k].g) { 
         nodes[k].g = nodes[currentNode].g + 10 + (abs(i * j) * 4); 
         nodes[k].pX = nodes[currentNode].x; 
         nodes[k].pY = nodes[currentNode].y; 
        } 
        isEmpty = false; 
       } 
      } 

이것은 IJ 루프의 마지막 부분입니다 :

if (isEmpty) { 
       nodes.push_back(Node(nodes[currentNode].x + i, 
        nodes[currentNode].y + j, 
        nodes[currentNode].g + 10 + (abs(i * j) * 4), 
        calculateH(nodes[currentNode].x + i, nodes[currentNode].y + j, finishX, finishY), 
        nodes[currentNode].x, 
        nodes[currentNode].y, 
        false)); 
      } 
    } 
} 

지금 우리는 노드를 찾을 수 최저 F 점수는 현재의 no로 변경하십시오. de, 닫힌 목록에 추가하십시오. 무한 전지에 대한 보호도 여기에 완료 :

// Set the current node to the one with the lowest F score. 
    int lowestF = (nodes[currentNode].g + nodes[currentNode].h); 
    int lowestFIndex = currentNode; 
    for (int k = 0; k < nodes.size(); k ++) { 
     if (((nodes[k].g + nodes[k].h) <= lowestF) && 
      (!nodes[k].list)) { 
      lowestF = (nodes[k].g + nodes[k].h); 
      lowestFIndex = k; 
     } 
    } 
    currentNode = lowestFIndex; 
    // Change it to the closed list. 
    nodes[currentNode].list = true; 

    sizeLimit ++; 
    if (sizeLimit > 1000) 
     return ""; 
} 

나는 데 문제가 늘 특정 경로를 찾을 수 있다는 것입니다. 경로가 올라가거나 어떤 지점에서 떠난다면 결코 작동하지 않는 것 같습니다. 아래, 왼쪽, 오른쪽 모두 제대로 작동합니다. 어쨌든 대부분의 시간. 나는이 문제의 원인이 무엇인지 전혀 모른다. 어느 시점에서 난 수동으로 내 코드가 문제가 어디에 있는지 보려고했습니다. 놀라운 일은 없었습니다.

그리고 한 가지 더 : 내 중괄호를 계산하는 경우 (처음에는 모든 와우, 내가 생각했던 것보다 더 많은 헌신적 인 노력이 필요함), 마지막에 대괄호가 빠져 있음을 알 수 있습니다. 내 반환 진술서는 말할 것도없고.결국 내가 빠뜨린 길을 만드는 코드 끝에 약간의 코드가 있습니다. 나는 그 부분이 문제가 아니라는 것을 알고있다. 나는 현재 주석 처리했으며, 여전히 같은 방식으로 작동하지 않습니다. 나는 그것이 작동하지 않는 곳을 알려주는 코드를 추가했으며, 해석이 아니라 길 찾기 부분에있다.

죄송합니다. 코드가 너무 복잡하고 비효율적입니다. 저는 C++을 처음 접했으므로 제 기술에 대한 비판적인 조언을 환영합니다.

Answer 1

다음 "currentNode"를 찾을 때 lowestF = (nodes[currentNode].g + nodes[currentNode].h);으로 시작해서는 안되기 때문에 원칙적으로 해당 값이 오픈 - 엔드 노드의 다른 노드보다 낮거나 같기 때문에 시작해야합니다. 세트. std::numeric_limits<int>::max() 또는 매우 큰 숫자로 시작하거나 std::vector 대신 우선 순위 대기열을 사용하여 노드 (예 : std::priority_queue 또는 boost::d_ary_heap_indirect)를 저장하십시오.

나는 이것이 문제라는 것을 확신합니다. 그리고 당신의 경험적 방법은 얻은 실제 경로 거리와 매우 같을 수 있기 때문에 오픈 세트의 노드를 따라 가면 currentNode와 동일한 비용 (g + h)을 갖게됩니다. 이것은 왜 어떤 경로가 탐구되고 다른 경로는 탐험되지 않고 왜 갇혀 있는지 설명합니다.