Astar 알고리즘은 길찾기에 사용되는 대표적인 알고리즘 입니다.

추격자나 몬스터의 인공지능을 구현할 때 단순히 따라오도록 한다면 벽에 부딪히거나 뚫고 가거나 누가봐도 어색하게 갈 것 입니다. 그래서 원하는 장소까지 자연스럽게 이동시키도록 만드는 것이 중요합니다.

물론 Unity에서 NavMesh를 사용해 간편하게 적용이 가능하지만 완전하진 않습니다.

A* 알고리즘은 상당히 유명해 이미 구현되어 있는 코드가 많이 있습니다.
구글에 검색하면 바로 나오는 공유된 코드가 있습니다.
링크 들어가셔서 참고하시면 됩니다.

Aron Granberg - A* Pathfinding Project

1. 📖 A* 알고리즘

A* 알고리즘은 다음과 같은 구성요소로 되어있습니다.

G: 시작점에서 현재 노드까지의 거리
H: 현재 노드에서 목적지까지의 예상 거리 (휴리스틱)
F = G + H : 총 예상거리

2. 📖 다익스트라(Dijkstra) vs A*

길찾기 알고리즘의 대표적인 주자 다익스트라 알고리즘과 어떤 차이가 있을까요?

	A* 알고리즘	다익스트라 알고리즘
탐색 방향	목표 지점 방향	전 방향
사용하는 값	G + H	G
속도	빠름	느림(전방향 탐색)

2-1. 🔖 다익스트라(Dijkstra)

다익스트라의 경우 전 방향을 모두 살펴본 후에 가장 단거리를 찾는 방식으로
전부 탐색해서 가장 짧은 길을 찾는 것이 이 알고리즘의 핵심입니다.

목적지가 멀리 있든 가깝든 동일한 방식으로 탐색하기 때문에 속도가 느립니다.

이러한 특성으로 게임보다는 네비게이션에서 사용하면 가장 좋은 길찾기 알고리즘입니다.

2-2. 🔖 A*

다익스트라의 경우 모든 방향을 계산하여 단거리를 제시하지만
Astar의 경유 목적지가 정해져 있으면 그 방향만 생각합니다.

목적지가 저기니까 그쪽 방향부터 우선적으로 탐색하는 방식인거죠

여기서 H(휴리스틱)을 이용해서 목표에 가까운 쪽을 먼저 탐색하도록 만드느 것 입니다.

3. 📖 휴리스틱

그럼 휴리스틱은 무엇일까요?

현재 노드에서 목표 지점까지의 예상 거리를 말합니다.
A*는 이 H를 참고해서 목표 지점에 가까운 노드부터 우선적으로 탐색합니다.

여기서 중요한 건 장애물이 있는 경우 무시하고 계산합니다.

휴리스틱은 본질적으로 목표까지 얼마나 되는지를 대충 예측하는 함수기 때문에
장애물까지 고려하면 계산이 너무 복잡해지고, 빠른 탐색이 되질 않습니다.

장애물은 A* 알고리즘에서 따로 처리합니다.

3-1. ✔️ 맨하튼 거리

휴리스틱 계산의 경우 여러가지 계산 방법이 있습니다.

맨하튼 거리의 경우 상하좌우만 이동 가능한 격자에서 사용하는 방식입니다.

맨하튼 거리 계산 방식
H = |x1 - x2| + |y1 - y2|

예를 들어 (0,0) → (4,2) 라면

|0 - 4| + |0 - 2| = 4 + 2 = 6

H는 6이 되는겁니다.

int H (Vector2Int a, Vector2Int b) 
{
    return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}

대각선 이동 불가능한 경우에 빠르게 연산이 필요한 경우에 사용합니다.

그래서 2D 게임이나 턴제 RPG 등에서 많이 사용하는 계산 방식입니다.

3-2. ✔️유클리디안 거리

유클리디안 거리는 피타고라스의 정리를 기반으로 실제 물리적인 거리를 측정합니다.

H = √[(x1 - x2)² + (y1 - y2)²]

예를 들어 (0,0) → (4,2) 라면

√[(4)^2 + (2)^2] = √(16 + 4) = √20 ≈ 4.47

H는 약 4.47이 됩니다.

float H (Vector2 a, Vector2 b) 
{
    return Vector2.Distance(a, b);
    // Mathf.Sqrt(Mathf.Pow(a.x - b.x, 2) + Mathf.Pow(a.y - b.y, 2));
}

대각선 포함한 자유 이동에서 사용합니다.