A-Star 알고리즘 ( A* )
A-Star 알고리즘은 게임 개발이나 인공지능에서 가장 자주 쓰이는 경로 탐색 알고리즘이다.
유니티의 NavMesh 같은 시스템도 기본적으로 A* 의 원리를 기반으로 만들어졌다.
| 이름 | A-Star ( A* ) 알고리즘 |
| 목적 | 출발지에서 목적지까지 최단 경로를 찾기 |
| 특징 | 현재까지의 거리 + 앞으로의 예측 거리를 동시에 고려 |
| 사용 예시 | 미로 찾기 , 길 찾기 AI , NPC 이동 , RTS 유닛 이동 등 |
| 자료구조 | 우선순위 큐 ( Priority Queue ) 또는 Open / Closed List 사용 |
A* 는 각 노드의 점수를 계산하면서 최적의 경로를 탐색한다.
1. 점수 계산식
각 노드마다 세 가지 값을 계산한다.
f(n) = g(n) + h(n)| g(n) | 시작점에서 현재 노드까지의 실제 비용 ( 실제 이동 거리 ) |
| h(n) | 현재 노드에서 목표까지의 예상 비용 ( 휴리스틱 , Heuristic ) |
| f(n) | 총 비용 ( A* 는 f 가 가장 작은 노드부터 탐색한다 ) |
2. Open / Closed 리스트 구조
| Open List | 아직 탐색하지 않은 노드 목록 |
| Closed List | 이미 탐색을 마친 노드 목록 |
▼ 탐색 과정
- 시작 노드를 Open List 에 추가한다
- Open List 중 f(n) 이 가장 작은 노드를 선택한다
- 그 노드를 확장해서 이웃 노드들의 g , h , f 를 계산한다
- 이미 더 좋은 경로가 있으면 갱신하지 않는다
- 목표 노드에 도달하면 탐색 종료한다
휴리스틱 함수 ( Heuristic )
휴리스틱은 "얼마나 남았을까" 를 예측하는 함수이다.
실제 게임에서는 보통 거리 계산으로 사용한다.
| 종류 | 수식 | 특징 |
| 맨해튼 거리 ( Manhattan ) | ` | x1 - x2 |
| 유클리드 거리 ( Euclidean ) | √((x1 - x2)² + (y1 - y2)²) | 대각선 이동이 가능할 때 |
| 체비쇼프 거리 ( Chebyshev ) | max( | x1 - x2 |
▼격자형 맵 기준 예시 코드
using System.Collections.Generic;
using UnityEngine;
public class AStar
{
public class Node
{
public Vector2Int position;
public float g; // 시작점 → 현재까지의 실제 비용
public float h; // 현재 → 목표까지의 예상 비용
public float f => g + h; // 총 점수
public Node parent;
public Node(Vector2Int pos) { position = pos; }
}
public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal, bool[,] map)
{
List<Node> open = new List<Node>();
HashSet<Vector2Int> closed = new HashSet<Vector2Int>();
Node startNode = new Node(start);
open.Add(startNode);
while (open.Count > 0)
{
// f 값이 가장 작은 노드 선택
open.Sort((a, b) => a.f.CompareTo(b.f));
Node current = open[0];
open.RemoveAt(0);
if (current.position == goal)
return ReconstructPath(current); // 경로 완성
closed.Add(current.position);
// 4방향 탐색 (상하좌우)
Vector2Int[] dirs = {
Vector2Int.up, Vector2Int.down, Vector2Int.left, Vector2Int.right
};
foreach (var dir in dirs)
{
Vector2Int nextPos = current.position + dir;
if (!IsInside(map, nextPos) || !map[nextPos.x, nextPos.y]) continue;
if (closed.Contains(nextPos)) continue;
float g = current.g + 1;
float h = Mathf.Abs(nextPos.x - goal.x) + Mathf.Abs(nextPos.y - goal.y);
Node neighbor = new Node(nextPos) { g = g, h = h, parent = current };
// OpenList에 더 짧은 경로가 있으면 무시
Node existing = open.Find(n => n.position == nextPos);
if (existing == null || g < existing.g)
{
if (existing != null) open.Remove(existing);
open.Add(neighbor);
}
}
}
return null; // 경로 없음
}
private List<Vector2Int> ReconstructPath(Node node)
{
List<Vector2Int> path = new List<Vector2Int>();
while (node != null)
{
path.Add(node.position);
node = node.parent;
}
path.Reverse();
return path;
}
private bool IsInside(bool[,] map, Vector2Int pos)
{
return pos.x >= 0 && pos.y >= 0 && pos.x < map.GetLength(0) && pos.y < map.GetLength(1);
}
}
▼ 예시 코드
using System.Collections.Generic;
using UnityEngine;
namespace PathFind
{
public class Node
{
public bool IsWall { get; set; } = false; // 진행 불가 판정
public bool IsClosed { get; set; } = false; // 닫힌(연산이 종료된)노드인지 판단
public Node Prev { get; set; } // 이전 노드
public int X { get; set; } // X축 좌표
public int Y { get; set; } // Y축 좌표
public int G { get; set; } // 현재까지 이동 거리
public int H { get; set; } // 목적지까지의 직선 거리
public int F { get => G + H; }
}
[System.Serializable] public class Astar
{
// 탐색을 진행할 맵
[field: SerializeField] public Map _map { get; set; }
// 대각선 탐색 여부
[SerializeField] private bool _diagonalPath;
// 대각선 탐색시 충돌되는 벽 우회 여부
[SerializeField] private bool _disableDiagonalObstacle;
// 전체 노드를 관리하는 2차원 배열
private Node[,] NodeArray;
// 탐색 대상/비대상 노드 리스트
private List<Node> OpenNode = new List<Node>();
// 최종적으로 경로로 선정된 노드 리스트
public List<Node> FinalNodeList { get; private set; } = new List<Node>();
// 시작, 대상, 이전 노드 정보
private Node StartNode;
private Node TargetNode;
private Node CurNode;
private void Init(Vector2Int StartPos, Vector2Int TargetPos)
{
// 노드 배열 크기 지정
int sizeX = _map.EndArea.x - _map.StartArea.x + 1;
int sizeY = _map.EndArea.y - _map.StartArea.y + 1;
NodeArray = new Node[sizeX, sizeY];
// 노드 배열만큼 반복
for (int x = 0; x < sizeX; x++)
{
for (int y = 0; y < sizeY; y++)
{
NodeArray[x, y] = new Node();
// 좌표 영역의 감지된 노드 인식
foreach (Collider2D col in Physics2D.OverlapCircleAll(new Vector2(x + _map.StartArea.x, y + _map.StartArea.y), 0.4f))
{
// 감지된 노드의 레이어가 "Wall"이라면
if (col.gameObject.layer == LayerMask.NameToLayer("Wall"))
{
// 벽 여부를 true로
NodeArray[x, y].IsWall = true;
}
}
// 노드에 좌표 주입
NodeArray[x, y].X = x + _map.StartArea.x;
NodeArray[x, y].Y = y + _map.StartArea.y;
}
}
// 출발지점과 도착지점 노드를 각 Start, Target Node로 지정
StartNode = NodeArray[StartPos.x - _map.StartArea.x, StartPos.y - _map.StartArea.y];
TargetNode = NodeArray[TargetPos.x - _map.StartArea.x, TargetPos.y - _map.StartArea.y];
// 시작점을 열린 노드로 미리 추가
OpenNode.Add(StartNode);
}
public void PathFinding(Vector2Int StartPos, Vector2Int TargetPos)
{
// 0. 초기화 -----
Init(StartPos, TargetPos);
while (true)
{
// 열린 노드가 하나도 없으면 종료(경로를 못 찾았을 때)
if(OpenNode.Count <= 0)
{
break;
}
// 오픈 노드 리스트의 첫 번째 노드를 현재 노드로 지정
CurNode = OpenNode[0];
// 1. 노드 교체(이동과정) -----
// 열린 노드 리스트 수만큼 반복
for (int i = 1; i < OpenNode.Count; i++)
{
// 대상 원소와 현재 노드를 비교해서
// 대상 원소의 F가 현재 노드의 F이하이고 목적지까지 직선 거리가 더 가깝다면
if (OpenNode[i].F <= CurNode.F && OpenNode[i].H < CurNode.H)
{
// 현재 노드는 비교했던 노드로 교체
CurNode = OpenNode[i];
}
}
// 현재 노드의 닫힘 여부를 true로 바꾸고 열린 노드 리스트에서 삭제한다.
CurNode.IsClosed = true;
OpenNode.Remove(CurNode);
// Final. 알고리즘 종료 단계 -----
if (CurNode == TargetNode)
{
int TotalLengh = CurNode.G;
Node TargetCurNode = TargetNode;
// 각 노드들에 등록된 이전 노드들을 최종 경로에 추가한다.
// 현재 도착지 노드가 시작점 노드라면 반복 종료
while (TargetCurNode != StartNode)
{
FinalNodeList.Add(TargetCurNode);
TargetCurNode = TargetCurNode.Prev;
}
// 시작점 노드를 최종 경로에 추가하고 순서를 역순으로 바꾼다.
FinalNodeList.Add(StartNode);
FinalNodeList.Reverse();
Debug.Log(TotalLengh);
return;
}
// 2. 주변의 노드를 열린 노드에 추가 -----
// 대각방향 탐색 여부가 true 라면
if (_diagonalPath)
{
// 대각선 노드들 포함
AddOpen(Xdir.Right, Ydir.Up);
AddOpen(Xdir.Left, Ydir.Up);
AddOpen(Xdir.Left, Ydir.Down);
AddOpen(Xdir.Right, Ydir.Down);
}
// 상하좌우 노드 추가
AddOpen(Xdir.Center, Ydir.Up);
AddOpen(Xdir.Right, Ydir.Center);
AddOpen(Xdir.Center, Ydir.Down);
AddOpen(Xdir.Left, Ydir.Center);
}
}
public enum Xdir { Left = -1, Center, Right }
public enum Ydir { Down = -1, Center, Up }
void AddOpen(Xdir x, Ydir y)
{
int X = CurNode.X + (int)x;
int Y = CurNode.Y + (int)y;
// 추가적인 노드가 맵의 범위를 벗어나지 않을 때
if (X >= _map.StartArea.x &&
X < _map.EndArea.x + 1 &&
Y >= _map.StartArea.y &&
Y < _map.EndArea.y + 1
)
{
int CurX = CurNode.X - _map.StartArea.x;
int CurY = CurNode.Y- _map.StartArea.x;
X = CurNode.X + (int)x - _map.StartArea.x;
Y = CurNode.Y + (int)y - _map.StartArea.x;
// 해당 좌표의 노드가 벽이 아니면서 && 닫혀 있지 않다면
if(!NodeArray[X, Y].IsWall &&
!NodeArray[X, Y].IsClosed)
{
// 대각선 허용시
if (_diagonalPath)
{
// 진행 대각선 방향에 인접한 두 노드가 모두 벽일때
if (NodeArray[CurX, Y].IsWall &&
NodeArray[X, CurY].IsWall)
{
// □ □ □ □ □
// □ □ □ □ □
// □ □ ■ □ □
// □ □ ↗ ■ □
// □ □ □ □ □
return; // 함수 중단(추가하지 않는다)
}
}
// 대각선 이동시 모서리를 통과하지 않을거면
if (_disableDiagonalObstacle)
{
if (NodeArray[CurX, Y].IsWall ||
NodeArray[X, CurY].IsWall)
{
// 진행 대각선 방향에 인접한 상하좌우 방향의 노드 중에서 벽이 있으면
// □ □ □ □ □ 예시
// □ □ □ □ □
// □ ↗ ■ □ □
// □ □ □ □ □
// □ □ □ □ □
return;
}
}
// 이웃(주변)노드로 두고
Node NeighborNode = NodeArray[X, Y];
// 노드당 이동 거리는 직선 10, 대각선 14
int MoveCost;
if(CurX == X || CurY == Y)
{
MoveCost = CurNode.G + 10;
}
else
{
MoveCost = CurNode.G + 14;
}
// 이동비용이 주변 노드G보다 작거나 ||
// 오픈 리스트에 주변 노드가 포함되어 있지 않다면
if (MoveCost < NeighborNode.G || !OpenNode.Contains(NeighborNode))
{
// 주변 노드에 G, H 주입하고 이전 노드 변수에 현재 노드를 주입하고
NeighborNode.G = MoveCost;
NeighborNode.H = (Mathf.Abs(NeighborNode.X - TargetNode.X) + Mathf.Abs(NeighborNode.Y - TargetNode.Y)) * 10;
NeighborNode.Prev = CurNode;
// 열린 리스트에 추가
OpenNode.Add(NeighborNode);
}
}
}
}
}
}
▼ 예시 코드
using NUnit.Framework;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Rendering;
class AStarNode
{
public int Index; // 노드 인덱스 , 구별값 ABCD 0123
public Vector2 pos; // 노드 위치
public float G; // 시작점에서 지금 위치까지의 실제 비용
public float H; // 휴리스틱 , 예측 비용
public float F => G + H; // 총 점수 , 가중치
public AStarNode Parent; // 부모 노드 , 경로 복원 용도
// 생성자
public AStarNode(int index, Vector2 pos, float g, float h, AStarNode parent = null)
{
Index = index;
this.pos = pos;
G = g;
H = h;
Parent = parent;
}
// F값 기준으로 정렬을 위한 비교 함수
public int CompareTo(AStarNode other)
{
// F값으로 우선 비교
int fCompare = F.CompareTo(other.F);
if (fCompare != 0)
{
return fCompare;
}
// F값이 같을 경우 인덱스 기준 비교
return Index.CompareTo(other.Index);
}
}
public class AStarExample : MonoBehaviour
{
// 두 좌표 사이의 거리를 휴리스틱으로 사용하기로 함
static float Heuristic(Vector2 a, Vector2 b) => Vector2.Distance(a, b);
private void Start()
{
int n = 4; // 노드 4개 사용
int startIndex = 0; // 시작 위치는 0번 노드 A
int goalIndex = 3; // 종료 위치는 3번 노드 D
// 각각의 노드에 좌표 설정해주기
Vector2[] positions = new Vector2[4]
{
new Vector2(0, 0), //A
new Vector2(2, 0), //B
new Vector2(0, 1), //C
new Vector2(1, 1) //D
};
// 그래프 구성
List<(int to, float cost)>[] graph = new List<(int to, float cost)>[n];
for (int i = 0; i < n; i++)
{
graph[i] = new List<(int to, float cost)>();
}
// 비용 정보 추가
graph[0].Add((1, 5)); // A -> B (1)
graph[1].Add((2, 2)); // B -> C (2)
graph[1].Add((3, 3)); // B -> D (3)
graph[2].Add((3, 5)); // C -> D (5)
// G 점수 배열 초기화
float[] gScore = new float[n];
for (int i = 0; i < n; i++)
{
gScore[i] = float.MaxValue;
}
// 시작 위치
gScore[startIndex] = 0;
// 방문 여부
bool[] closed = new bool[n];
// 오픈 리스트 , 탐색 대상들
var openList = new List<AStarNode>();
// 시작 지점 추가
openList.Add(new AStarNode(startIndex, positions[startIndex], 0,
Heuristic(positions[startIndex], positions[goalIndex])));
// 탐색 루프
while(openList.Count > 0)
{
// F값 기준 정렬
openList.Sort((a, b) => a.CompareTo(b));
// 가장 F가 낮은 노드 찾아오기
var current = openList[0];
// 방문한 노드는 제거
openList.RemoveAt(0);
// 이미 방문한 노드면 패스
if (closed[current.Index])
{
continue;
}
// 방문 처리
closed[current.Index] = true;
// 목표에 도달했으면 경로 복원
if(current.Index == goalIndex)
{
// 경로 저장용 리스트
var path = new List<int>();
var temp = current;
// 부모 따라가면서 역추적
while (temp != null)
{
path.Add(temp.Index);
temp = temp.Parent;
}
// D - C - B - A
// 역순으로 들어갔으니까 뒤집기
path.Reverse();
// A - B - C - D
Debug.Log("A* Path " + string.Join(" -> ", path));
Debug.Log("Distance " + current.G);
break;
}
// 인접 노드 탐색
foreach(var neighbor in graph[current.Index])
{
// 이미 처리한 노드는 패스
if (closed[neighbor.to])
{
continue;
}
// 현재의 G + 이동 비용 계산
float t = current.G + neighbor.cost;
// 더 짧은 경로 발견시 갱신
if(t < gScore[neighbor.to])
{
gScore[neighbor.to] = t;
// H값 게산
float h = Heuristic(positions[neighbor.to], positions[goalIndex]);
// 새로운 노드 추가
openList.Add(new AStarNode(neighbor.to, positions[neighbor.to], t, h, current));
}
}
}
}
}| 장점 | 단점 |
| 항상 최적의 경로를 찾는다 ( 휴리스틱이 올바르다면 ) | 맵이 크면 연산량이 많아진다 |
| 휴리스틱 조정으로 현실적인 경로 표현이 가능하다 | 실시간 게임에서는 속도 조절이 필요하다 |
| 다목적 ( 2D , 3D , 격자형 , 그래프형 등 가능 ) | 복잡한 지형에서는 구현 난이도가 증가한다 |
▼ 게임에서의 활용
| RTS 병사 이동 | 유닛이 장애물을 피해 가장 짧은 길로 이동한다 |
| 좀비 추격 AI | 플레이어의 위치까지 최단 경로를 계산한다 |
| 타워 디펜스 | 적이 최적 경로로 길을 따라 전진한다 |
| 맵 네비게이션 | NevMesh 내부적으로 A* 변형 사용 |
참고 자료
https://qiao.github.io/PathFinding.js/visual/
'📊Algorithm > 탐색' 카테고리의 다른 글
| Dijkstra & A-Star (0) | 2025.11.20 |
|---|---|
| Dijkstra 다익스트라 (0) | 2025.11.20 |
| 너비 우선 탐색 ( BFS ) (0) | 2025.11.14 |
| 깊이 우선 탐색 ( DFS ) (0) | 2025.11.14 |
| 탐색 알고리즘 ( Search Algorithms ) (0) | 2025.11.10 |