20231221 55일차 A* Algorithm2

A*알고리즘을 이해하기 위해서는 Dijkstra 알고리즘을 이해해야 한다.

 

일반적으로, Dijkstra알고리즘은 A*알고리즘의 하위호환이라고 이해하면 될 것이다.

 

 

Dijkstra 알고리즘

 

간선간 연결되어있는 노드들을 예시로 들어보자.

 

 

이제 각 거리간 시간이 걸리는 정도를 계산하고 넣어보자.

 

 

이제 여기에서 전방위 순환을 하면서 가장 가까운 거리를 찾는 것 이다.

 

위와 같은 방식을 비슷하게 사용하나,

더 효율적인 방법으로 A*알고리즘 이 있다.

 

근처 Node를 순환하면서 필요한 인접Node만 탐색하는 방식으로. 전체순환을 할 필요가 없어 더 효율적이다.

 

각 계산수식을 살펴보자.

 

float AStar::GetDiagonalManhattanDistance(int start, int end)
{
    Vector3 startPos = nodes[start]->GetGlobalPosition();
    Vector3 endPos = nodes[end]->GetGlobalPosition();

    Vector3 temp = endPos - startPos;

    float x = abs(temp.x);
    float z = abs(temp.z);

    float minSize = min(x, z);
    float maxSize = max(x, z);

    return (maxSize - minSize) + sqrt(minSize * minSize * 2);
}

 

Astar 알고리즘에서 사용하는, G와 H를 계산하는데 사용하는 맨하탄 거리값을 구하는데 사용되는 함수들이다.

 

시작점과 종료점의 Vector를 확인하고,해당 좌표값대로, 직선거리, 대각선거리를 포함한 가중치를 계산한다.

 

void AStar::Extend(int center, int end)
{
    for (Node::Edge* edge : nodes[center]->edges)
    {
        int index = edge->index;

        if (nodes[index]->state == Node::CLOSED)
            continue;
        if (nodes[index]->state == Node::OBSTACLE)
            continue;

        float G = nodes[center]->g + edge->cost;
        float H = GetDiagonalManhattanDistance(index, end);
        float F = G + H;

        if (nodes[index]->state == Node::OPEN)
        {
            if (F < nodes[index]->f)
            {
                nodes[index]->g = G;
                nodes[index]->f = F;
                nodes[index]->via = center;
            }
        }
        else if (nodes[index]->state == Node::NONE)
        {
            nodes[index]->g = G;
            nodes[index]->h = H;
            nodes[index]->f = F;
            nodes[index]->via = center;
            nodes[index]->state = Node::OPEN;

            //openNodes.push_back(index);
            heap->Insert(nodes[index]);
        }
    }
}

 

인접한 Node의 F G A 를 확인하고, 해당 값대로 순차이동 Vector에 넣어주는 함수이다.

 

int AStar::FindCloseNode(Vector3 pos)
{
    float minDist = FLT_MAX;
    int index = -1;

    FOR(nodes.size())
    {
        if (nodes[i]->state == Node::OBSTACLE)
            continue;

        float distance = MATH->Distance(pos, nodes[i]->GetGlobalPosition());

        if (minDist > distance)
        {
            minDist = distance;
            index = i;
        }
    }

    return index;
}

void AStar::GetPath(IN int start, IN int end, OUT vector<Vector3>& path)
{
    Reset();
    path.clear();

    //1. 시작노드 초기화하고 오픈노드에 추가
    float G = 0;
    float H = GetDiagonalManhattanDistance(start, end);

    nodes[start]->f = G + H;
    nodes[start]->g = G;
    nodes[start]->h = H;
    nodes[start]->via = start;
    nodes[start]->state = Node::OPEN;

    //openNodes.push_back(start);
    heap->Insert(nodes[start]);

    while (nodes[end]->state != Node::CLOSED)
    {
        //길이 막힌 상황
        //if (openNodes.empty())
        if (heap->Empty())
            return;

        //2. 오픈노드 중에서 효율이 가장 좋은 노드 찾기
        int curIndex = GetMinNode();
        //3. 찾은 노드와 연결된 노드의 정보를 갱신 후 오픈노드에 추가하고
        //확장이 끝난 노드는 닫기
        Extend(curIndex, end);
        nodes[curIndex]->state = Node::CLOSED;
    }

    //5. BackTracking
    int curIndex = end;

    while (curIndex != start)
    {
        nodes[curIndex]->state = Node::USING;
        path.push_back(nodes[curIndex]->GetGlobalPosition());
        curIndex = nodes[curIndex]->via;
    }
    //시작노드 추가하기
    //path.push_back(nodes[start]->GetGlobalPosition());
}

각각 지정된 position을 확인하고, 해당되는 index에 대해 이동이 불가능한 곳 인지, 아니라면, 거리값을 확인하여. 인접 index중 가까운 index를 반환하는 함수와,

 

이동경로를 계산하는 함수로, 가장 효율이 좋은 노드를 찾아 반환한다.