C++에서 A *를 사용하여 경로를 어떻게 추적합니까?

Question

나는 몇 주 동안 A *를 구현하여 적이 게임에서 플레이어를 추격 할 수 있도록 노력해 왔으며 제대로 작동하지 않습니다. 나는 주말 내내 그것에 대해 노력해 왔으며, 나는 그것 대부분을 긁어 모으고 그것을 다시 작성하기까지했다. 시작 위치에서 목표까지 경로를 그릴 수는 있지만 실제로 경로를 적는 것처럼 다시 추적 할 수는 없습니다. 저는 Vector2f (float의 순서쌍)와 SFML의 Sprite를 사용하고 있지만 모든 코드는 매우 간단하므로 실제로 이해할 필요는 없습니다.

편집 : 문제는 Node.cameFrom입니다. 웬일인지, 그것은 벽 이외의 어떤 것도 뒤덮지 않는다.

여기

#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 = int(sprite.getGlobalBounds().left)>>5; // left/32 
yStart = int(sprite.getGlobalBounds().top)>>5; // top/32 

bool operator == (const Node &nhs) const는 건강에 해로운 보이지만, 심지어 어디서나 사용할 아니에요 :

xStart, yStart 직접 계산 될 수 있으며, 필요는 매 루프를 반복 없습니다.

이웃이 벽에 있는지 확인하려면 O (N) occupies을 사용할 필요가 없습니다. == '2'에 대한지도를 테스트 하시겠습니까? (코드가 그런 식으로 설계된 것이라면 코드에서 바로 변경하면 코드가 제대로 작동하는지 확인하지 못했습니다).

전체적으로 나는 당신이 처리하고 싶은 데이터와 방법에 초점을 맞추고, 여러 목록을 통해 앞뒤로 움직이는 물체를 멈추게한다면, 그 코드를 더 간결하게 만들 수 있습니다. A * IIRC의 경우 정렬 된 vs 맵 필드를 유지하기 위해 insert_at가있는 단일 정렬 대기열이 필요합니다.이 필드는 이미 처리 된 사각형을 표시합니다.

예를 들어, 중요한 그 Vector2f 위치 위치 :

... 
P#D 
... 

선수 "P"는 정사각형의 아래쪽에 서있는 경우

("#은"벽 "D"가 대상이된다)는 A *가 찾아야한다 하단 경로 또는 "타일"정확도가 필요하고 상단 경로도 좋을까요?

하위 타일 정확도로 작업하든 그렇지 않든간에 질문에 대해 분명하지 않습니다. 그렇지 않다면 그 타일의 대부분을 삭제하고 타일 좌표로만 작업 할 수 있습니다.

하위 타일 정확도를 사용하면 대부분의 경우에도 여전히 드롭 할 수 있지만 실제로 타일 크기가 "32"이고 플레이어 크기가 "3"인 경우 타일을 " 영역 "을 가로 질러 다른 라인으로 이동하여 위의 예제를 피하면서 중간 타일의 전체 중앙으로 가면서 거리를 절약하십시오 ... 그런 다음 서브 타일 위치를 어떻게 든 대략 대략 정확한"최단 "경로를 얻기 위해 계산해야합니다 .

한 게임에서 작업 할 때, 타일 대신에 노드 목록 (고전적인 수학 그래프)을 연결했는데, 각 노드는 "영역 반경"을 가지며 가장 짧은 노드 간 경로가 발견 된 후 반복 알고리즘은 노드 위치에서 반경 내에있는 일부 섀도우 노드 위치로 이동하는 데 약간의 루프를 수행했지만 다른 두 섀도우 노드에 더 가깝습니다. 최대 반복 횟수를 치거나 그림자 위치가 많이 변경되지 않으면 (대개 3 ~ 5 번 반복) 경로를 "부드럽게"중단하고 반환했습니다. 군인들은 거의 직선으로 사막을 가로 질러 달리며, 중간 지점 노드는 20m의 반경을 가진 희미한 그리드와 같았습니다. 그래서 병사는 실제로 2 ~ 3 개의 노드 밖에 가지 않고 노드 센터에서 멀리 떨어지기 시작했습니다. 노드 그래프 자체에서 지그재그 (zig-zag).

Answer 2

, 당신이 점점의 비용 (비용을 필요 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입니다 더하기 휴리스틱), 그리고 당신이 접근 한 이웃 타일의 식별.

알고리즘의 시작점에서 끝 점이 "풍선"으로 나타나고 가장 좋은 점이 먼저 분석됩니다. 따라서 경로가 단순하면 풍선이 매우 길어집니다. 그것이 복잡하다면, 풍선은 둥그스름하고 벽과 이미 방문한 타일로 둘러싸이기 때문에 많은 길은 버려집니다.