길찾기 알고리즘과 최적화

Unity를 활용하여 AI나 자동으로 길을 찾는 기능을 구현할 경우, 3D는 Nav Mesh Component를 활용하면 된다. 직접 구현하는 것보단 해당 Component를 쓰는 것이 웬만해선 훨씬 빠르고 최적화가 잘 되어있다.

 

다만 2D를 개발하는 경우 해당 Component를 사용할 수 없어 길 찾기 알고리즘을 직접 개발해야 한다. 이에 길 찾기 알고리즘에 대해 알아보고 최적화하는 과정을 작성하고자 한다.

 

구현한 알고리즘의 코드는 깃허브에서 확인할 수 있다.

https://github.com/woghrk12/AStarAlgorithm.git

GitHub - woghrk12/AStarAlgorithm

 

A* 알고리즘

A* 알고리즘이란 $1:N$의 최단 경로를 찾는 알고리즘인 Dijkstra 알고리즘을 확장하여 만들어진 $1:1$ 경로 탐색 알고리즘이다.

 

현재 상태의 비용과 다음 상태로 이동할 때의 예상 비용이 최소가 되는 지점을 우선적으로 탐색하는 알고리즘으로, 다음 상태로 이동할 때의 비용인 $h(x)$ (휴리스틱 함수)에 따라 성능이 달라진다.

 

만약 $h(x)$가 admissible, 즉 목적지까지 남은 거리를 과대평가하지 않는다면 최단 경로가 보장된다.

 

다음 노드 선정을 위한 기본 식은 다음과 같다.

$$f(x) = g(x) + h(x)$$

$g(x)$는 출발 노드에서 해당 노드까지 사용한 최소 비용을, $h(x)$는 현재 노드에서 목표 노드까지의 예상 이동 비용 (Heuristic), $f(x)$는 $g(x)$와 $h(x)$를 더한 총 비용으로 Heuristic cost function이다. $f(x) =g(x)$일 경우 Dijkstra 알고리즘과 동일하다.

 

수행 순서는 다음과 같다.

1. $f(x)$를 오름차순 우선순위 큐에 노드로 삽입
2. 우선순위 큐에서 최우선 노드를 Pop
3. 해당 노드에서 이동할 수 있는 노드를 탐색
4. 이동 가능한 노드들의 $f(x)$ 계산
5. 해당 노드들을 우선순위 큐에 삽입
6. 목표 노드에 도달할 때 까지 반복

PQ.push(start_node, g(start_node) + h(start_node))

while PQ is not empty
	node = PQ.pop()
	if node == target_node
		break
	for next_node in (next_node_begin ... next_node_end)
		PQ.push(next_node, g(node) + cost + h(next_node)

print target_node_list

A* 알고리즘 구현 및 최적화

길 찾기 알고리즘을 구현하기 전에 캐릭터가 이동할 수 있는 영역을 Collider 컴포넌트로 설정했고 격자 형태로 이동할 수 있는 지점을 노드(Node)라고 지칭하겠다.

콜라이더를 사용하여 맵에 이동할 수 있는 영역 설정

맵에 이동할 수 없는 영역에 생성된 빨간 오브젝트

 

1. 거리 계산

각 노드의 좌표는 float 타입이 아닌 int 타입으로 계산했다. int 타입의 계산 속도가 훨씬 빠르며, float 타입으로 계산할 경우 부동소숫점 계산으로 인해 정확도가 매우 떨어져 같은 값이 다르다는 결과를 출력할 수 있기 때문이다.

private void CalculateTest()
{
    long startTime, endTime;

    int intSum = 0;
    float floatSum = 0.0f;

    startTime = System.DateTime.UtcNow.Ticks;
    for (int i = 0; i < 100000000; i++)
    {
        intSum += 1;
    }
    endTime = System.DateTime.UtcNow.Ticks;

    Debug.Log($"Calculating time of int data type : {endTime - startTime}");

    startTime = System.DateTime.UtcNow.Ticks;
    for (int i = 0; i < 100000000; i++)
    {
        floatSum += 1f;
    }
    endTime = System.DateTime.UtcNow.Ticks;

    Debug.Log($"Calculating time of float data type : {endTime - startTime}");
}

int 타입과 float 타입의 1억번 계산의 속도 비교

 

루트 연산과 제곱 연산의 비용은 매우 크기 때문에 다른 방식으로 거리를 계산했다.

private int CalculateDistance(Vector2Int a, Vector2Int b)
{
    int dx = a.x > b.x ? a.x - b.x : b.x - a.x;
    int dy = a.y > b.y ? a.y - b.y : b.y - a.y;
    int e1 = dx > dy ? dx - dy : dy - dx;
    int e2 = dx < dy ? dx : dy;

    return e1 * 10 + e2 * 14;
}

 

2. 힙 데이터 구조

가장 작은 F값을 가진 노드를 탐색하기 위한 알고리즘으로 힙 정렬 알고리즘을 사용했다. 다만 힙 정렬을 위한 트리 구조가 기형적인 모습을 갖게 될 경우 선형 구조가 되어 버블 정렬과 같은 속도를 갖을 수 있다.

기형적인 모습의 힙 데이터 구조. 선형 자료 구조와 차이점이 없다.

 

이를 방지하기 위해 힙 데이터 구조를 완전 이진 트리로 구현했으며 이를 위한 Add, Pop 함수는 다음과 같다.

 

1) Add : 힙 데이터 구조에 원소를 추가할 때는 완전 이진 트리의 마지막 위치에 삽입한 후 해당 위치로부터 루트 노드까지 버블 정렬을 통해 노드의 위치를 찾아간다.

노드를 추가할 때는 완전 이진 트리의 마지막 위치에 삽입한다.

해당 노드부터 루트 노드까지 버블 스왑을 통해 정렬한다.

 

2) Pop : 가장 작은 F 값을 갖고 있는 루트 노드와 힙 데이터 구조의 가장 마지막 노드를 스왑한 후 마지막 노드를 반환할 값으로 제거한다. 이후 루트 노드를 자식 노드와 비교하며 위치를 찾아준다.

루트 노드와 마지막 노드를 스왑한다.

마지막 노드를 제거하고 반환한다.

루트 노드를 자식 노드와 비교하며 올바른 위치를 찾아준다.

 

3. Region

길 찾기 알고리즘의 대표 예시가 스타크래프트이다. 스타크래프트의 맵을 확인해보면 여러 Region으로 나뉘어져있는 것을 알 수 있다.

스타크래프트의 나뉘어진 Region들

 

전체 맵을 작은 단위의 Region으로 나누어 분할 정복 기법을 적용한 것이다. A* 알고리즘을 두 단계로 나누어 진행하여 탐색하는 노드의 갯수를 현저히 줄일 수 있다.

 

1) Region을 나누지 않았을 경우

Region을 나누지 않은 A* 알고리즘의 길 찾기 결과

경로의 길이와 방문한 노드의 수

 

2) Region을 나눴을 경우

Region을 나눈 A* 알고리즘의 길 찾기 결과

경로의 길이와 방문한 노드의 수

 

결과로 출력된 경로는 거의 비슷하나 방문한 노드의 수가 약 20%로 줄었다.

 

초록색 : 기본 A*, 파란색 : Region을 나눈 A*

경로의 길이와 방문한 노드의 수

다른 위치에서 경로를 탐색해도 약 23%로 줄었다. 거리가 멀어질수록 Region을 나눈 A* 알고리즘이 불필요한 노드의 탐색을 방지하기 때문에 훨씬 빠르다.