A* Algorithm -4 (완)

이제는 본격적인 A* 에 대해 진행할 예정이다. 

 

이전의 포스트를 올리면서 코드를 분석해보니, 생각보다 이해안되었던 부분들도 하나하나 보면서 이해했다. 

 

void Solve_AStar() {
        //전체 노드 훑으면서 
        for (int x = 0; x < nMapWidth; x++) {
            for (int y = 0; y < nMapHeight; y++) {
                // 초기화 시키기
                nodes[y * nMapWidth + x].bVisited = false;
                nodes[y * nMapWidth + x].fGlobalGoal = INFINITY;
                nodes[y * nMapWidth + x].fLocalGoal = INFINITY;
                nodes[y * nMapWidth + x].parent = nullptr;
            }
        }
        // 두 노드 사이간의 거리 구하기
        auto distance = [](Node * a, Node * b) {
            return sqrtf((a - > _x - b - > _x) * (a - > _x - b - > _x) + (a - > _y - b - > _y) * (a - > _y - b - > _y));
        };

        ...

 

두 노드 사이의 거리를 구할때는 유클리드 거리를 통해서 구할 수 있는데,

 

각 차원의 차를 제곱을 하고, 그 값을 전부 더한 다음. 제곱근을 주해주면 두 노드 사이의 거리를 구할 수 있다.

// 람다 함수로, distance를 캡쳐하고, 똑같이 a,b를 매개변수로 받는다.
// 비용의 추정치를 계산하는 과정
// 두 노드간의 거리를 휴리스틱 값으로 사용.
auto heuristic = [distance](Node * a, Node * b) {
    return distance(a, b);
};

// 현재 노드를 스타트로 정하고, fLocalGoal은 시작노드로부터 현재 노드까지의 최소 비용이고, 
// fGlobal은 목표 노드까지의 예상 비용이다. 
// 그래서 nodeStart의 LocalGoal은 0이고, GlobalGoal은 heuristic(nodeStart, nodeEnd) 가 된다.

Node * nodeCurrent = nodeStart;
nodeStart - > fLocalGoal = 0.0 f;
nodeStart - > fGlobalGoal = heuristic(nodeStart, nodeEnd);

// 끝점에서부터 역으로 올라와야 하니까, LIFO인 list를 선언해서 먼저 시작점을 넣어준다.
list < Node * > listNotTestedNodes;
listNotTestedNodes.push_back(nodeStart);

// list가 비거나, 현재 노드가 끝노드일때까지 반복 탐색
while (!listNotTestedNodes.empty() && nodeCurrent != nodeEnd) {
    // 리스트에 있는 노드들의 fGlobalGoal 비용을 오름차순으로 정렬 (가장 낮은값이 앞에)
    listNotTestedNodes.sort([](const Node * lhs,
        const Node * rhs) {
        return lhs - > fGlobalGoal < rhs - > fGlobalGoal;
    });

    // list가 비거나, 현재 list의 첫번째 노드가 visitied 되어있을 때
    while (!listNotTestedNodes.empty() && listNotTestedNodes.front() - > bVisited) {
        // 비용 탐색 범위에서 제외
        listNotTestedNodes.pop_front();
    }

    // 비어있으면 탈출 = 끝노드 도착
    if (listNotTestedNodes.empty()) {
        break;
    }

    // 현재노드 설정 ( 리스트 맨 앞에 있는 노드)
    nodeCurrent = listNotTestedNodes.front();
    nodeCurrent - > bVisited = true;

    // 현재 노드의 인근 노드들 탐색
    for (auto nodeNeighbour: nodeCurrent - > vecNeighbours) {
        // 아직 방문하지 않았고, 장애물이 아닌 노드일때
        if (!nodeNeighbour - > bVisited && nodeNeighbour - > bObstacle == 0) {
            // 탐색해야 하는 노드 리스트에 추가
            listNotTestedNodes.push_back(nodeNeighbour);
        }
        //  이웃 노드에 도달할 때 목표 비용 =현재 노드의 localGoal + 현재노드와 이웃 노드간의 거리
        float fPossiblyLowerGoal = nodeCurrent - > fLocalGoal + distance(nodeCurrent, nodeNeighbour);

        // 비용이 인근 노드의 localGoal 보다 낮은 경우 ( 나은 경로를 찾은 경우) 
        if (fPossiblyLowerGoal < nodeNeighbour - > fLocalGoal) {
            // 이웃노드의 부모노드 = 현재 노드(가장 비용이 적은 경로)
            nodeNeighbour - > parent = nodeCurrent;
            // 이웃노드의 localGoal = 이웃노드에 도달할 때 목표 비용
            nodeNeighbour - > fLocalGoal = fPossiblyLowerGoal;
            // 이웃노드의 GlobalGoal = localGoal + 끝노드 까지의 Global 비용
            nodeNeighbour - > fGlobalGoal = nodeNeighbour - > fLocalGoal + heuristic(nodeNeighbour, nodeEnd);
        }
    }
}

이렇게 반복적으로, 목적지까지의 거리를 계산하고 끝에 다다르면 멈춰서 다음 값을 대기한다.

 

Visited 된곳은 Cyan 색으로 되어있고(탐색한곳), 최단 경로는 노란색 선으로 이어져서 보여지게 된다.

 

한번에 쭉 생각하려면 너무나도 어렵고 막막한 전개이지만, 차근차근 조금씩 이해해 나가면서 풀어가니 어느정도 가닥은 잡힌 느낌이다. 이해는 했지만 다시 이걸 순수 내 지능으로 풀어내라? 솔직히 못하겠다.

 

그래도 찾아보고, 원하는 기능을 만들 수 있는 해결 능력은 생긴 기분이다. 자만한 걸수도 있지만, 이걸 테스트 하기 위해 다음 프로젝트나 탐구에 적용해보는 연습을 필히! 해봐야겠다. 그때가서 지금의 공부가 어땠는지 부족한게 무엇인지 더 알 수 있을듯 하다.

 

추가적으로) 노드의 길을 만드는 코드부분 중에서

 

if (y > 0 && x > 0)
    // 노드의 맨윗줄과 맨왼쪽줄 제외 = 왼쪽 위 대각선
    nodes[y * nMapWidth + x].vecNeighbours.push_back( & nodes[(y - 1) * nMapWidth + (x - 1)]);
if (y < nMapHeight - 1 && x > 0)
    // 노드의 맨아래줄과 맨왼쪽줄 제외 = 왼쪽 아래 대각선
    nodes[y * nMapWidth + x].vecNeighbours.push_back( & nodes[(y + 1) * nMapWidth + (x - 1)]);
if (y > 0 && x < nMapWidth - 1)
    // 노드의 맨윗줄과 맨오른쪽 제외 = 오른쪽 위 대각선
    nodes[y * nMapWidth + x].vecNeighbours.push_back( & nodes[(y - 1) * nMapWidth + (x + 1)]);
if (y < nMapHeight - 1 && x < nMapWidth - 1)
    // 노드의 맨아래줄과 맨오른쪽 제외 = 오른쪽 아래 대각선
    nodes[y * nMapWidth + x].vecNeighbours.push_back( & nodes[(y + 1) * nMapWidth + (x + 1)]);

이 코드를 추가하면 상하좌우로 연결되어있는 노드들이 대각선으로도 연결되어 8방향으로 연결되어진다.

 

탐색의 계산이 커지고, 비용도 늘겠지만 필요에 따라서 이런식으로 확장성 있게 구현할 수 있다. 

 

대각선으로도 가능하다.