■ A* 알고리즘
“BFS에서 발전한 알고리즘이 다익스트라라면, 다익스트라에서 한 단계 더 발전한 것이 바로 A 알고리즘이다.”
다익스트라와 동작 방식은 비슷하지만, 목표 노드(n)까지의 거리 측정값인 휴리스틱(Heuristic)을 추가로 사용한다.
각 타일에는 다음과 같은 정보가 저장된다.
| 이름 | 설명 |
| g(n) | 현재 노드까지의 누적 비용. 가중치가 없다면 상하좌우 이동은 10(또는 1), 대각선 이동은 14(또는 1.4)로 계산한다. |
| h(n) | 목표 지점까지의 예상 비용(휴리스틱). 맨해튼 거리 방식이나 정수 근사 휴리스틱(10/14)을 사용해 계산한다. |
| f(n) | g(n) + h(n). A* 알고리즘에서 우선순위를 결정할 때 사용하는 총 비용. |
다익스트라에서는 우선순위 큐의 기준이 g(n) 값(누적 비용)이지만, A*에서는 f(n) 값을 기준으로 한다.
- 열린 목록에 있는 노드들 중, f(n)값이 가장 낮은 노드의 인접 노드를 탐색한다.
- 비용이 확정된 노드는 닫힘 목록(closed list)에 추가하여 더 이상 탐색하지 않는다.
▼ 경로 복원과 대각선 이동 검사에 대해선 다음 내용 참고.
[C#, Unity, 최단경로(PathFinding)] TileMap 너비우선탐색(BFS) 알고리즘
■ 개요우리가 흔히 알고 있는 그래프 탐색 알고리즘에는 깊이우선탐색(DFS), 너비우선탐색(BFS), 다익스트라(Dijkstra) 알고리즘 등이 있다. 그렇다면 이런 그래프 탐색 알고리즘이 "2차원 배열의 타
hate-errorlog.tistory.com
■ 휴리스틱에 대하여
A*에서 휴리스틱은 목표 지점까지의 “예상 비용”을 계산하는데 이 계산 방식에는 크게 2가지가 있다.
1. 맨해튼 거리
뉴욕의 도시 맨해튼의 구조를 보면, 격자 형태로 그 사이사이에 건물들이 배치되어 있고 이 건물을 뚫고 이동하는건 불가능하다.
왼쪽 아래 점을 시작점, 우측 상단 점을 도착점이라 한다면, 이 둘의 최단거리(유클리드 거리)는 초록색 선이다.
하지만 상하좌우로만 이동 가능하니, 파란선이 최단 경로라고 생각할 수 있지만 초록, 파랑, 빨강의 선 길이는 모두 같다.
- 결국, 시작점과 목표점 간에 상하좌우로 각각 몇 칸 이동해야 하는지만 계산하면 되며, 이 값은 다음과 같이 구할 수 있다.
h(n) = |x_2 - x_1| + |y_2 - y_1|
▶ 대각선 이동 시의 맨해튼 거리
A* 알고리즘이 최단 경로를 보장하기 위해선, 휴리스틱 함수가 다음 조건을 만족해야 한다.
- 과소 추정(admissible) → 휴리스틱 값은 실제 최단 거리보다 절대 크면 안됨.
- 일관성(consistent) → 현재 노드에서 인접 노드로 한 번 이동할 때, 휴리스틱이 너무 큰 변화 없이 일정해야 함.
그런데 대각선 이동이 가능한 경우, 맨해튼 거리는 실제 거리보다 너무 크거나, 방향에 따라 들쭉날쭉하게 차이가 나기 때문에 위와 같은 조건을 만족하지 못한다.
2. 정수 기반 휴리스틱 (Diagonal Distance)
대각선 이동이 가능한 경우에는 대각선 이동 비용을 정수로 근사하는 방식을 사용한다.
h(n) = 14 * min(dx, dy) + 10 * (|dx- dy|)
- 여기서 dx = |x2 - x1|(가로 거리)를 의미하고, dy = |y2 - y1|(세로 거리)를 의미한다.
예를 들어, (x1,y1) → (x2, y2)로 가려면 다음과 같은 방식을 생각할 수 있다.
1.가능한 한 많이 대각선으로 이동한다.
x와 y 방향 모두 거리가 남아 있을 때는 대각선으로 한 번에 움직이는 것이 가장 효율적이다. 따라서 이를 min(dx,dy)번으로 처리한다.
2.그 다음 직선으로 마무리.
x또는 y중 하나는 거리를 다 채웠지만, 다른 한 쪽은 아직 남아있다. 이 남은 부분(|dx-dy|)을 상하좌우 직선 이동으로 마무리한다.
■ A* 구현
1. NodeData.cs
public class NodeData : IComparable<NodeData>
{
public float G;
public float H;
public (int, int) Pos;
public float TotalWeight => G + H;
public NodeData((int, int) pos, float g, float h)
{
Pos = pos;
G = g;
H = h;
}
public int CompareTo(NodeData other)
{
var compare = TotalWeight.CompareTo(other.TotalWeight);
if (compare == 0)
{
compare = Pos.CompareTo(other.Pos);
}
return compare;
}
}
각 노드(타일)에 대해 경로 탐색에 필요한 추가 정보를 저장하기 위해 NodeData 클래스를 정의하였다.
- A 알고리즘에서 우선순위는 f(n) = g(n) + h(n)으로 결정되므로, 이를 기준으로 정렬되도록 CompareTo 메서드를 오버라이딩하였다.
- f(n)이 동일할 경우, 비교 일관성을 유지하기 위해 노드의 위치값(Pos)을 추가 기준으로 사용한다.
2. 필요 변수 선언
public List<(int, int)> AStar_PathFinding(Tile[,] tile, (int, int) start, (int, int) end)
{
var height = tile.GetLength(0);
var width = tile.GetLength(1);
var openSet = new PriorityQueue<NodeData, float>();
var openSetDic = new Dictionary<(int, int), NodeData>();
var closeSet = new bool[height, width];
var parent = new (int, int)[height, width];
// 첫 노드는 바로 close 처리 되기 때문에 OpenSetDic에 들어갈 필요 없음
openSet.Enqueue(new NodeData(start, 0, 0), 0);
}
A 알고리즘에 필요한 핵심 자료구조는 아래와 같다.
| openSet(우선순위 큐) | 탐색할 노드가 저장되는 큐. f(n)을 우선순위 값으로 가진다. |
| openSetDic(딕셔너리) | 우선순위 큐에는 인덱스로 접근할 수 없기 때문에, 특정 위치의 노드가 열린 목록에 존재하는지 빠르게 확인하기 위해 사용된다. |
| closeSet(bool[,]) | 이미 탐색을 완료한 노드를 기록하여 중복 탐색을 방지한다. |
| parent(int[,]) | 각 노드가 어떤 노드를 통해 탐색되었는지(부모 노드의 위치)를 저장한다. |
우선순위 큐는 인덱스를 통한 직접 접근이 불가능하므로, 열린 목록의 특정 노드 존재 여부를 빠르게 확인할 수 있도록 openSetDic을 함께 사용한다.
3. 인접 노드 탐색
while (openSet.Count > 0)
{
if (openSet.TryDequeue(out var curNode, out var f) == false) return null;
if (curNode.Pos == end) return PathUtils.FindShortPath(parent, start, end);
closeSet[curNode.Pos.Item1, curNode.Pos.Item2] = true;
var current = -1;
foreach (var dir in PathUtils.SearchDir)
{
current++;
var xPos = curNode.Pos.Item2 + dir.x;
var yPos = curNode.Pos.Item1 + dir.y;
if(xPos < 0 || xPos >= width || yPos < 0 || yPos >= height) continue;
if(closeSet[yPos, xPos] == true || tile[yPos, xPos].Weight == (int)EBiome.WALL)
continue;
// 대각선 이동이 가능한지 확인
if (current >= 4 && PathUtils.IsDiagonalBlocked(tile, curNode.Pos, (dir.y, dir.x))
== true)
{
continue;
}
}
}
큐에서 요소를 꺼낸 뒤 도착 노드라면 경로를 반환한다. 이후 방문 처리를 하고 인접 노드에 대해 8방향 탐색을 진행한다.
- 좌표가 맵 범위를 벗어나거나, 이미 방문한 노드이거나, 이동이 불가능한(벽) 노드라면 건너뛴다.
4. 인접한 노드가 이미 “열린 목록”에 존재한다면?
while (openSet.Count > 0)
{
//
// 생략...
//
foreach (var dir in PathUtils.SearchDir)
{
//
// 생략...
//
// 이미 열린 목록에 노드가 존재한다면
// 상하좌우 4방향만 이동 가능하고, 모든 가중치가 동일하다면, 이미 열린 목록을 확인할 필요는 없음.
if (openSetDic.TryGetValue((yPos, xPos), out var neighbor) == true)
{
// 현재 노드에서 이웃한 노드로 갈 때의 g(n)값 계산
var neighborWeight = tile[yPos, xPos].Weight;
var g = current < 4
? curNode.G + neighborWeight
: curNode.G + neighborWeight * 1.4f;
// 현재 -> 이웃 노드로 갈 때의 g(n)값이 이웃 노드의 g(n)값보다 작다면 갱신
if (g < neighbor.G)
{
neighbor.G = g;
parent[neighbor.Pos.Item1, neighbor.Pos.Item2] = curNode.Pos;
// 갱신된 이웃 노드를 다시 열린 목록에 추가
openSet.Enqueue(neighbor, neighbor.TotalWeight);
// 갱신했으므로, 이후의 과정은 하지 않아도 됨.
continue;
}
}
}
}모든 가중치가 동일하고 대각선 이동이 불가능한 맵이라면 이 과정은 생략할 수 있다. 하지만 가중치가 다르거나 대각선 이동이 가능한 맵이라면, 이웃 노드에 대한 경로 갱신 검사가 반드시 필요하다.
노드 P에서 A, B, C가 탐색되었고, 그중 C가 다음 탐색 노드로 선택되었다고 하자. 이때 A,B는 C의 인접한 노드이자, 이미 열린 목록에 등록된 상태이다.
A*는 항상 현재 노드에서 이웃 노드로 가는 경로가 더 짧을 경우 그 경로로 갱신해준다. 따라서 현재 노드(C)를 통해 이웃 노드로 갈 때의 g(n)값이, 기존 이웃 노드의 g(n)값보다 작다면 갱신해주어야 한다.
- 예를 들어, B노드의 누적 이동 비용을 g(y), C노드에서 B노드로 가는 누적 이동 비용을 g(x) + cost 라 해보자.
- g(x) + cost < g(y) 라면, 기존 경로보다 C를 거쳐서 B로 갈 때의 경로가 더 짧다는 의미이므로, B의 g값과 부모를 갱신한다.
var neighborWeight = tile[yPos, xPos].Weight;
var g = current < 4
? curNode.G + neighborWeight
: curNode.G + neighborWeight * 1.4f;
따라서, 현재 노드C의 g(n)에 B로 이동할 때의 가중치를 더한다. 이 때 current가 4 이상이라면 이웃 노드는 대각선에 위치하므로 1.4를 곱해준다.
// 만약, 이웃노드->현재노드로 올 때의 값이, 이웃 노드의 g(n)보다 작다면 부모 및 g(n)값 갱신
if (g < neighbor.G)
{
neighbor.G = g;
parent[neighbor.Pos.Item1, neighbor.Pos.Item2] = curNode.Pos;
// 갱신된 이웃 노드를 다시 열린 목록에 추가
openSet.Enqueue(neighbor, neighbor.TotalWeight);
// 갱신했으므로, 이후의 과정은 하지 않아도 됨.
continue;
}
새로 계산한 g(n) 값이 이웃 노드인 B의 g(n)보다 더 작다면, 더 나은 경로를 찾은 것이므로 B의 부모 노드를 C로 바꾸고 g(n)을 갱신한다.
- 이후 B를 다시 열린 목록에 추가하여 다른 경로 탐색이 가능하도록 한다.
정리하자면 열린 목록에 있는 이웃 노드들 중, 현재 노드를 거쳐서 해당 이웃 노드로 가는 비용이 더 저렴한지를 비교한다.
만약 더 저렴하다면, 해당 이웃 노드의 g값과 부모 노드 정보를 갱신하여, 나중에 백트래킹 할 때 더 나은 경로가 역추적될 수 있도록 한다.
5. 인접한 노드가 “열린 목록”에 존재하지 않는다면
// 이웃 노드 탐색(대각 이동이라면, 기존 가중치 값에 1.4를 곱함)
var weight = current < 4
? tile[yPos, xPos].Weight
: tile[yPos, xPos].Weight * 1.4f;
var h = CalculateHeuristic((yPos, xPos), end);
var newNode = new NodeData((yPos, xPos), weight, h);
// 부모 노드 갱신
parent[yPos, xPos] = curNode.Pos;
if (openSetDic.TryAdd((yPos, xPos), newNode) == true)
{
openSet.Enqueue(newNode, newNode.TotalWeight);
};
인접한 노드가 아직 열린 목록에 없을 경우, g(n)과 h(n)을 계산한 뒤 NodeData를 생성하고, 부모 노드를 설정한다.
- 이후 해당 노드를 openSet과 openSetDic에 추가하여 이후 탐색 대상이 될 수 있도록 한다.
6. 휴리스틱 계산
private float CalculateHeuristic((int, int) start, (int, int) end)
{
var dx = Mathf.Abs(start.Item2 - end.Item2);
var dy = Mathf.Abs(start.Item1 - end.Item1);
var dir1 = 1f;
var dir2 = 1.414f;
return dir1 * (dx + dy) + (dir2 - 2 * dir1) * Mathf.Min(dx, dy);
}
휴리스틱 계산은 대각선 이동이 가능한 그리드 환경이므로, 정수 기반 대각선 거리 휴리스틱 (Octile Distance)공식을 사용하였다.
- 전체 거리의 직선 기반 총합을 계산한다 : dir1 * (dx + dy)
- 모든 이동을 직선( ↑,↓,←,→)으로만 했을 때의 비용.
- 대각선 한 번이 직선 두 번보다 얼마나 더 저렴한지 계산한다 : dir2 - 2 * dir (대각선 이동이 제공하는 "절약 비용"을 의미)
- 절약 가능한 대각선 이동 횟수를 곱해준다 : *Mathf.Min(dx, dy) / 최대한 대각선으로 이동할 수 있는 횟수
- 1번과 3번 결과를 합산하여 휴리스틱 값을 계산한다.
■ 최종 결과 및 전체 코드
public class AStar
{
public List<(int, int)> AStar_PathFinding(Tile[,] tile, (int, int) start, (int, int) end)
{
PrefCheck.StartPrefCheck();
var height = tile.GetLength(0);
var width = tile.GetLength(1);
var openSet = new PriorityQueue<NodeData, float>();
var openSetDic = new Dictionary<(int, int), NodeData>();
var closeSet = new bool[height, width];
var parent = new (int, int)[height, width];
// 첫 노드는 바로 close 처리 되기 때문에 OpenSetDic에 들어갈 필요 없음
openSet.Enqueue(new NodeData(start, 0, 0), 0);
while (openSet.Count > 0)
{
if (openSet.TryDequeue(out var curNode, out var f) == false)
{
return null;
}
if (curNode.Pos == end)
{
return PathUtils.FindShortPath(parent, start, end);
}
closeSet[curNode.Pos.Item1, curNode.Pos.Item2] = true;
var current = -1;
foreach (var dir in PathUtils.SearchDir)
{
current++;
var xPos = curNode.Pos.Item2 + dir.x;
var yPos = curNode.Pos.Item1 + dir.y;
if (xPos < 0 || xPos >= width || yPos < 0 || yPos >= height) continue;
if (closeSet[yPos, xPos] == true || tile[yPos, xPos].Weight == (int)EBiome.WALL) continue;
// 대각선 이동이 가능한지 확인
if (current >= 4 && PathUtils.IsDiagonalBlocked(tile, curNode.Pos, (dir.y, dir.x)) == true)
{
continue;
}
// 이미 열린 목록에 노드가 존재한다면
// 상하좌우 4방향만 이동 가능하고, 모든 가중치가 동일하다면, 이미 열린 목록을 확인할 필요는 없음.
if (openSetDic.TryGetValue((yPos, xPos), out var neighbor) == true)
{
// 현재 노드에서 이웃한 노드로 갈 때의 g(n)값 계산
var neighborWeight = tile[yPos, xPos].Weight;
var g = current < 4
? curNode.G + neighborWeight
: curNode.G + neighborWeight * 1.4f;
// 현재 -> 이웃 노드로 갈 때의 g(n)값이 이웃 노드의 g(n)값보다 작다면 갱신
if (g < neighbor.G)
{
neighbor.G = g;
parent[neighbor.Pos.Item1, neighbor.Pos.Item2] = curNode.Pos;
// 갱신된 이웃 노드를 다시 열린 목록에 추가
openSet.Enqueue(neighbor, neighbor.TotalWeight);
// 갱신했으므로, 이후의 과정은 하지 않아도 됨.
continue;
}
}
// 이웃 노드 탐색(대각 이동이라면, 기존 가중치 값에 1.4를 곱함)
var weight = current < 4
? tile[yPos, xPos].Weight
: tile[yPos, xPos].Weight * 1.4f;
var h = CalculateHeuristic((yPos, xPos), end);
var newNode = new NodeData((yPos, xPos), weight, h);
// 부모 노드 갱신
parent[yPos, xPos] = curNode.Pos;
if (openSetDic.TryAdd((yPos, xPos), newNode) == true)
{
openSet.Enqueue(newNode, newNode.TotalWeight);
};
}
}
return null;
}
// 대각선 이동이 가능하므로, 맨허튼 거리 대신 대각선 이동의 정수 근사 휴리스틱 (10/14 방식) 사용.
private float CalculateHeuristic((int, int) start, (int, int) end)
{
var dx = Mathf.Abs(start.Item2 - end.Item2);
var dy = Mathf.Abs(start.Item1 - end.Item1);
var dir1 = 1f;
var dir2 = 1.414f;
return dir1 * (dx + dy) + (dir2 - 2 * dir1) * Mathf.Min(dx, dy);
}
}[AStar.cs]
public static class PathUtils
{
public static readonly Vector2Int[] SearchDir = new[]
{
new Vector2Int(0, -1), new Vector2Int(0, 1),
new Vector2Int(-1, 0), new Vector2Int(1, 0),
new Vector2Int(-1, -1), new Vector2Int(-1, 1),
new Vector2Int(1, -1), new Vector2Int(1, 1)
};
public static List<(int, int)> FindShortPath((int, int)[,] parent, (int, int) start,
(int, int) end)
{
var result = new List<(int, int)>();
var current = end;
while (current != start)
{
result.Add(current);
current = parent[current.Item1, current.Item2];
}
result.Add(start);
result.Reverse();
return result;
}
public static bool IsDiagonalBlocked(Tile[,] tile, (int y, int x) curNode, (int y, int x) moveDir)
{
var xPos = curNode.x + moveDir.x;
var yPos = curNode.y + moveDir.y;
if (xPos < 0 || xPos >= tile.GetLength(1) || yPos < 0 || yPos >= tile.GetLength(0))
return true;
return tile[yPos, curNode.x].Weight == (int)EBiome.WALL &&
tile[curNode.y, xPos].Weight == (int)EBiome.WALL;
}
}
[PathUtills.cs]
public class Tile
{
public int Weight { get; private set; }
public Material Mat { get; private set; }
private readonly Color _originColor;
public Tile(GameObject obj, int weight)
{
Mat = obj.GetComponent<Renderer>().material;
_originColor = Mat.color;
Weight = weight;
}
public void ResetColor()
{
Mat.color = _originColor;
}
}
[Tile.cs]
'Unity,C# > 알고리즘' 카테고리의 다른 글
| [정렬 알고리즘, C#] 선택 정렬(Selection Sort) (0) | 2025.06.17 |
|---|---|
| [정렬 알고리즘, C#] 버블 정렬(Bubble Sort) (1) | 2025.06.17 |
| [C#, Unity, 최단경로(PathFinding)] TileMap 다익스트라(Dijkstra) 알고리즘 (0) | 2025.04.10 |
| [C#, Algorithm] Dynamic Programming(동적 계획법) (0) | 2025.04.10 |
| [C#, Algorithm] 그라디(탐욕, 욕심쟁이) 알고리즘 (2) | 2025.04.10 |