스타크래프트로 배우는 길찾기 알고리즘 (BFS, 다익스트라, A*)

그 유명한 7인 입구막기

스타크래프트를 하다보면 느끼는데 컴퓨터들을 상대로 입구막기를 하면 메딕같은 것들은 공격대상에서 우선 순위를 안놓아서 그런지 위 짤처럼 버벅거린다.

“저 메딕부터 치면 길 뚫리잖슴”

하지만 컴퓨터는 그렇게 생각하지 않는다. 컴퓨터(상대)가 받은 명령어는 “저 메딕을 공격하라”가 아니라 “저 지점으로 이동하라” 이다. 그래서 컴퓨터에게 메딕은 **공격 대상이 아니라 ‘입구 쪽에 있는 장애물’**로 인식된다.

스타크래프트의 유닛 이동 알고리즘은 유명한 A*알고리즘이 사용되는데 해당 알고리즘의 역할은 오직

‘적을 제거하는 것’이 아니라 ‘장애물을 피해 목적지로 가는 것’

즉, A*는 “이걸 제거해서 지나갈까?”라는 선택지를 보다 “어떻게 피해 가지?"라는 생각만 함

경로 탐색

우리는 길을 찾을 때 핸드폰으로 네이버, 카카오 지도 어플로 계산된 시간+피곤함 수치까지 따진 후 어떤 경로로 갈지 판단하지만 컴퓨터적으로는 다르다.

계산, 선택까지 모두 해야하는데, 이 때 판단하는 것이

“이 칸에서 저 칸으로 이동하는 비용은 얼마지?”
“이 선택이 목적지에 얼마나 가까워지는가?”

컴퓨터는 길을 찍어보는 것이 아니라 모든 선택지에 점수를 매기고 비교한다.

그리고 이 점수 계산 규칙의 집합이 바로 경로 탐색 알고리즘(Pathfinding)

경로 탐색 알고리즘

BFS (너비 우선 탐색 — Breadth First Search)

출처: https://developer-mac.tistory.com/64

개념

BFS는 가장 가까운 것부터 한 단계씩 퍼트려가며 탐색한다.

여기서 단계란, 시작 지점으로부터의 이동 횟수(거리) 를 의미한다.

예를 들어 최단 경로의 길이가 3이라면, BFS는 1단계 → 2단계 → 3단계 순서로 탐색을 진행한다.

그래서 모든 이동 비용이 동일한 그래프/격자에서는 BFS가 최단 경로를 보장한다.

왜 이런 방식이 유용할까?

• 비용이 없는 상황에서 최단 거리를 구하고 싶을 때
• 격자 기반 맵에서 이동 횟수만 필요할 때 BFS는 거리 = 이동 횟수 로 보는 가장 단순한 방법이다.

특징

// 1. 큐(Queue) 생성: 들어온 순서대로 처리 (FIFO)
Queue<Point> queue = new LinkedList<>();
queue.add(start);
visited[start.x][start.y] = true; // 시작점 방문 처리
 
while (!queue.isEmpty()) {
    Point cur = queue.poll(); // 가장 먼저 들어온 노드 꺼내기
    
    // 2. 상하좌우 등 인접한 노드 탐색
    for (Point next : cur.adjacent()) {
        // 방문하지 않은 곳만 큐에 넣음 (무한 루프 방지)
        if (!visited[next.x][next.y]) {
            visited[next.x][next.y] = true;
            queue.add(next);
        }
    }
}

현재 위치에서 갈 수 있는 인접 노드를 차례로 넓혀가는 것

한 줄 요약

BFS는 “거리 = 이동 횟수”라고 정하면 가장 먼저 도착하는 경로를 찾음

다익스트라 알고리즘 (Dijkstra’s Algorithm)

BFS는 비용이 동일할 때 최단 경로를 찾지만, 이 각박한 세상에선 모든 이동의 비용이 같지 않다. 예를 들어:

• 평지 이동 = 비용 1
• 산길 이동 = 비용 3
• 강 건너기 = 비용 5

이런 경우엔 BFS로는 정확한 최단 경로를 찾을 수가 없음

$\rarr$ 이런 상황을 해결하기 위해 나온 알고리즘이 다익스트라 알고리즘이다!

개념

누적 비용이 가장 작은 경로부터 먼저 확장

다익스트라는 우선순위 큐(PriorityQueue)를 사용해서 지금까지 탐색된 경로 중 누적 비용이 가장 작은 노드를 먼저 처리한다.

다익스트라의 동작 원리(한 번 선택된 노드는 다시는 더 짧아질 수 없다는 가정을 기반으로 동작)

1. 시작 정점 A의 비용을 0으로 설정하고, 나머지는 무한대로 초기화

2. 아직 방문하지 않은 정점 중, 누적 비용이 가장 작은 정점을 선택

3. 해당 정점을 기준으로 인접한 정점들의 비용을 갱신

4. 선택된 정점은 “이미 방문” 상태가 되며, 이 시점에서 그 비용은 최단 거리로 확정

5. 모든 정점이 처리될 때까지 2부터 반복

특징

// 1. 우선순위 큐 생성: 비용이 가장 낮은 노드를 우선적으로 꺼냄 (오름차순)
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
 
// 시작점 초기화
dist[start] = 0;
pq.add(new Node(start, 0));
 
while (!pq.isEmpty()) {
    Node cur = pq.poll();
    
    // (중요) 지금 꺼낸 경로가 이미 알고 있는 거리보다 길다면 스킵 (최적화)
    if (cur.cost > dist[cur.idx]) continue;
 
    for (Edge e : cur.edges) {
        int nextCost = cur.cost + e.weight;
        
        // 2. 현재 노드를 거쳐서 가는 것이 더 빠르다면 갱신
        if (nextCost < dist[e.to]) {
            dist[e.to] = nextCost;
            // 갱신된 경로를 큐에 추가
            pq.add(new Node(e.to, nextCost));
        }
    }
}

한 줄 요약

노드마다 최단 거리를 기록해 두고, 가장 비용이 작은 경로를 우선적으로 선택하며 최단 경로를 찾아가는 방법

A* (A-Star)

개념

다익스트라는 비용만 고려하고 목적지가 어디인지 전혀 고려하지 않음

하지만 게임같이 실시간 경로 선택이 필요할 때는 “목적지 방향을 아는 경로 선택”이 훨씬 빠름

여기에 딱인게 A*알고리즘임

F = G + H A 의 핵심*

• G: 지금까지 실제로 온 비용

• H: 목적지까지 남은 비용을 추정한 값 (휴리스틱)

• F: 총 점수

“지금까지 쌓인 비용 + 앞으로 남은 예상 비용” 을 합산해서 가장 낮은 경로를 먼저 탐색

잠시만 🤔 맨 처음엔 길을 어떻게 찾기 시작하지?

출발지에서 마법처럼 목적지까지의 전체 경로를 한 번에 스캔하는 게 아님 A*는 두 개의 장부(Open List, Closed List)를 들고 다니며 발밑부터 탐색함

1. 내 바로 주변(이웃한 칸)을 스캔해서 탐색 후보(Open List) 에 적어둠
2. 후보들 중 $F$값(총 점수)이 가장 낮은, 즉 '제일 합당해 보이는' 칸으로 한 걸음 이동함
3. 이동한 칸을 방문 완료(Closed List) 처리하고, 다시 그 주변을 스캔해 후보에 넣음
4. 만약 가다가 벽에 막혀 $F$값이 너무 높아지면? 장부에 적어둔 다른 차선책 타일들 중 점수가 낮은 곳으로 다시 돌아가서 탐색을 이어감

H (휴리스틱)란

• H는 남은 거리의 추정값

중요한 점은 맵의 이동 규칙에 따라 이 **'추정 공식'**을 다르게 적용해야 한다는 것

대표적인 휴리스틱

출처: velog - @calico 맨해튼 거리 |x1 - x2| + |y1 - y2|

• 상하좌우로만 이동 가능한 격자(Grid) 환경에서 사용
• 루트($\sqrt{}$) 계산이 없어 컴퓨터 연산이 아주 빠름

격자를 따라 이동할 때의 거리

유클리드 거리 sqrt((x1 - x2)^2 + (y1 - y2)^2)

• 두 점 사이를 직선으로 연결했을 때의 실제 최단 거리
• 피타고라스 정리를 기반으로 한 거리 계산 방식

공간상에서의 직선 거리 (공중 유닛에게 적용하면 매우 좋음)

특징

// 1. 우선순위 큐 기준: F값 (G + H)이 가장 작은 노드 순서
// G: 실제 비용, H: 예상 비용
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.g + n.h));
pq.add(start);
 
while (!pq.isEmpty()) {
    Node cur = pq.poll(); // F값이 가장 낮은(가장 유망한) 노드 꺼내기
    
    if (cur.equals(goal)) break; // 목적지 도착!
 
    for (Node next : cur.neighbors()) {
        // G: 시작점부터 현재까지 이동 비용 + 다음 칸 이동 비용
        int g = cur.g + moveCost(cur, next);
        // H: 다음 칸부터 목적지까지의 '추정' 거리 (휴리스틱)
        int h = heuristic(next, goal);
        
        // F = G + H 를 품은 노드를 큐에 추가
        pq.add(new Node(next, g, h));
    }
}

• PriorityQueue 정렬 기준이 g + h
• h는 남은 거리의 추정값

한눈에 비교

• BFS는 단순하고 확실하다
• 다익스트라는 정확하지만 느리다
• A*는 빠르고 정확하지만, 좋은 휴리스틱 함수(추정법)가 필요하다

번외

미네랄 뚫기

아니 어떻게 뚫음? A* 별거없네 ㅋㅋㅋㅋ

스타 고인물 기술로 막혀있는 입구도 뚫을 수 있다...

1. 평소의 이동 (Move 명령)

• 상황: SCV에게 땅을 클릭해서 이동하라고 함
• A* 알고리즘 판단: 다음으로 갈 타일(Node)을 검사 isValidNode?
• 드라군이 서 있는 타일을 **'장애물'**로 인식
• 결과: 해당 타일의 이동 비용을 **무한대($\infty$)**로 처리하거나 아예 갈 수 없는 곳으로 제외

2. 미네랄 클릭 (Gather 명령) -> 버그 발생 원리 🐛

• 상황: SCV에게 미네랄을 캐라고 명령함. (이때 게임 엔진은 '채취 모드'로 전환, 미네랄 시야 있어야 하는 조건)
• 왜 이렇게 만들었나?: 미네랄 근처에서 일꾼끼리 서로 길을 막는걸 방지하기 위해, **'채취 중일 때는 유닛끼리 충돌하지 않는다'**는 예외 규칙이 있음
• 판단 변화:
  • 목적지가 '자원'이면, **이동 가능한 타일의 조건isWalkable**을 일시적으로 바꿈
  • "유닛이 있어도 그냥 뚫고 지나가도 됨 (Cost = 1)"
  • 결과: 드라군이 있는 타일이 장애물이 아니라 **'평범한 길'**로 인식되어벌임
  • A*는 당연히 직선거리가 가장 $F$값(비용)이 낮으므로, 드라군을 관통하는 놀라운 최단 경로를 내놓음

많이 알려진 일꾼 입구 뚫기인데, 사실 개발자가 의도한 A* 알고리즘의 허점(예외 처리)을 파고든 **'알고리즘 해킹'**이라 볼 수 있다.