비디오게임 경로 탐색을 위한 A* 알고리듬의 교묘한 기술

 (timmastny.com)
4P by GN⁺ | ★ favorite | 댓글 1개
  • 8비트 탑다운 Zelda풍 게임에서 몬스터 추적을 구현하려면 단순 직선 이동만으로는 부족해, Dijkstra와 A*를 비교하며 게임용 경로 탐색의 절충점을 찾음
  • 직선 이동은 벽에 막히면 멈추지만 wall-sliding을 붙이면 벽을 따라 움직일 수 있어 조작감은 좋아지고, 몬스터를 지형에 가두는 전략 요소도 만들 수 있음
  • Dijkstra 알고리듬은 최단 경로를 보장하지만 시작 노드 주변을 폭넓게 탐색하므로, 목적지가 매 프레임 바뀌는 게임에서는 필요한 다음 방향보다 많은 계산을 하게 됨
  • A*는 목적지까지의 거리로 탐색 우선순위를 정해 목적지 방향을 먼저 살피고, 벽을 만나면 주변 노드를 조사하면서 이미 본 노드는 재방문하지 않아 우회 경로를 찾을 수 있음
  • 게임 맵에서는 인접 리스트를 미리 만들지 않는 암시적 그래프와 타일 단위 탐색, 반복 깊이 제한 같은 기하 기반 휴리스틱으로 속도와 구현 난도를 조정할 수 있음

게임 맥락과 기본 요구

  • PPU466 기반의 8비트 탑다운 Zelda풍 게임에서 몬스터가 플레이어를 추적해야 했음
    • PPU466은 PICO-8 같은 판타지 콘솔과 비슷하게 8비트 그래픽, 타일당 4색, 고정 배경, 적은 수의 스프라이트 제약을 가짐
  • 목표는 몬스터가 플레이어를 따라오되, 단순히 벽에 막혀 멈추거나 원치 않는 방식으로 갇히지 않게 하는 것임

직선 이동과 wall-sliding

  • 가장 단순한 방식은 몬스터와 플레이어 사이에 직선을 그어 그 방향으로 움직이는 것임
  • 이 방식만 쓰면 몬스터가 벽에 닿는 순간 멈춤
  • wall-sliding을 적용하면 벽에 부딪혔을 때 멈추지 않고 벽을 따라 이동함
    • 플레이어 이동에서는 벽과 모서리 근처 조작을 더 반응성 있게 만드는 기법으로, 거의 모든 게임에서 쓰임
    • Pac-Man 이후 사용되어 왔고, Pac-Man Championship Edition DX+는 플레이어가 wall-slide할 때 스파크 효과를 추가함
  • 직선 이동에 wall-sliding을 붙이면 몬스터를 특정 지형에 가둘 수 있음
    • 일부 게임은 이를 전략 요소로 사용하며, Runescape의 safespotting이 예시임
    • 이 게임에서는 원하는 동작이 아니어서 실제 경로 탐색 알고리듬을 검토함

Dijkstra 알고리듬의 한계

  • Dijkstra 알고리듬은 구현이 직관적이고 최단 경로를 보장함
  • 문제는 필요한 것보다 너무 많은 일을 한다는 점임
    • 시작 노드에서 그래프의 모든 다른 노드까지 최단 경로를 찾음
    • 목적지 노드를 찾으면 멈출 수는 있지만, 특정 목적지 방향으로 탐색을 유도할 방법은 없음
  • 비디오게임에서는 플레이어가 계속 움직이므로 몬스터의 목적지가 매 프레임 변경됨
  • 몬스터에게 필요한 것은 전체 경로보다 지금 어느 방향으로 움직일지에 가까움
  • 맵의 모든 픽셀이나 타일에 대한 최단 경로를 미리 계산할 수는 있지만, 메모리를 많이 사용함
  • 레거시 플랫폼이나 자원이 제한된 플랫폼에서는 Dijkstra가 적합하지 않음

A*가 게임 경로 탐색에 맞는 이유

  • A* Search Algorithm은 시작 노드에서 목적지까지의 거리 정보를 사용해 탐색 우선순위를 정함
  • 첫 단계에서는 목적지까지 직선으로 가려는 방향을 우선 시도함
    • Dijkstra와 달리 필요하지 않으면 반대 방향 탐색에 많은 시간을 쓰지 않음
  • 벽이 경로를 막으면 주변 노드를 조사해 벽을 우회하려고 함
  • Dijkstra처럼 이미 본 노드를 재방문하지 않기 때문에, 되돌아가기가 많이 필요해도 결국 우회 경로를 찾을 수 있음
  • 예시에서 A*를 쓰는 몬스터는 벽 뒤에 갇히지 않음

암시적 그래프 자료구조

  • 교과서식 그래프는 노드 목록과 인접 행렬 또는 인접 리스트로 표현되지만, 게임에서는 인접 노드를 더 유연하게 만들 수 있음
  • 예를 들어 256×240 픽셀 화면에서 각 픽셀 좌표를 하나의 노드로 볼 수 있음
    • 인접 픽셀은 위, 아래, 왼쪽, 오른쪽, 대각선 4개를 포함한 8방향임
    • 상하좌우 이동 가중치는 1, 대각선 이동 가중치는 √2, 즉 약 1.4임
  • 거대한 인접 리스트를 미리 만들지 않고, 실제 방문할 노드에 대해서만 즉석에서 생성할 수 있음
  • 벽 위에 있거나 다른 스프라이트가 차지한 픽셀은 유효한 몬스터 위치가 아니므로 동적으로 인접 리스트에서 제외함
  • 이 방식이면 맵 에디터에서 인접 불가 노드를 수동으로 제외하지 않아도 됨

맵 기하를 반영한 휴리스틱

  • A*의 일부 요소는 맵의 기하 구조에 맞춰 직접 조정할 수 있음

  • 스텝 크기

    • 픽셀을 노드로 쓰는 대신, 2D 타일 기반 게임에서는 타일을 노드로 사용할 수 있음
    • 타일 단위 탐색은 플레이어까지 경로를 찾는 반복 횟수를 크게 줄여 검색을 빠르게 함
    • 이 경우 경로는 정확한 한 프레임 단위 이동 목록이 아니라 몬스터가 가야 할 방향들의 시퀀스에 가까움
    • 몬스터는 보통 프레임당 1타일 속도로 움직이지 않으므로, 타일 기반 경로라도 실제로 필요한 정보는 플레이어에게 도달할 수 있는 방향임
    • 픽셀 기반 경로도 같은 성격을 가지며, 몬스터가 프레임당 1픽셀이나 정수 픽셀 단위로 움직이지 않을 수도 있음

  • 반복 깊이

    • A*에서는 노드가 우선순위 큐에서 나올 때, 그 노드는 지금까지 본 최선 경로의 마지막 단계임
    • 고정된 반복 횟수에서 알고리듬을 멈추면 목적지까지의 최단 경로에 대한 현재까지의 최선 추정 경로를 얻을 수 있음
    • 알고리듬을 끝까지 실행하지 않아도 합리적인 진행 방향을 얻을 수 있음
    • 최대 반복 깊이는 레벨의 기하 구조에 맞게 조정해야 함
    • 깊이가 너무 작으면 몬스터가 여전히 벽 뒤에 갇힐 수 있음
    • 예시에서는 고정 깊이 30타일에서 플레이어 위치에 따라 몬스터가 갇혀 진행하지 못함
    • A*를 매 프레임 다시 계산하기 때문에 루프가 생길 수 있음
      • 벽에 도달한 첫 프레임에는 아래로 가야 한다고 계산함
      • 다음 프레임에는 위로 가야 한다고 계산함
      • 이 반복으로 몬스터가 루프에 갇힘
    • 플레이어가 몬스터의 탐색 범위 안으로 들어오면 올바른 경로를 찾을 수 있음
    • 고정 깊이 1에서는 이 현상이 더 극단적으로 나타나며, 몬스터는 플레이어와의 유클리드 거리가 가장 짧은 픽셀로 계속 돌아감

사전 계산의 절충안

  • 더 정교하게 만들려면 맵의 어떤 위치에서든 A*가 경로를 찾는 데 필요한 최대 깊이를 미리 계산할 수 있음
  • Dijkstra식 전체 경로 사전 계산과 달리 저장해야 하는 것은 그 최대값 하나임
  • 해당 최대 깊이가 주어지면 A*는 실시간으로 유효한 경로를 찾을 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 프로덕션 MMO에서 **A***에 썼던 요령들: 1) 도시 단위, 건물 내 방 사이, 방 내부처럼 계층 그래프를 두면 어느 도시의 어느 건물, 어느 방 안의 점에서 다른 점까지도 밀리초의 일부 시간에 탐색 가능함
    2) 현재 A* 탐색의 메타데이터를 그래프 노드 자체에 저장하면 별도의 연관 배열을 유지하지 않아도 됨
    3) 결과 경로를 그대로 따라가지 말고, 가능할 때 다음 경로 노드로 코너를 잘라 가려는 조향 행동의 입력으로 쓰는 편이 좋음. 다른 캐릭터에게 가는 경로라면 대상 캐릭터가 “빵부스러기”를 떨어뜨리게 해서, 새 위치가 경로의 마지막 노드에서 직선 이동 가능하지 않을 때 경로에 추가하게 함

    • 집 안을 볼 수 있는 도시 건설 게임을 만들고 있는데, 1번을 확장하면 이런 식임
      1. 도로는 자체 그래프를 갖고, 각 건물도 개별 그래프를 가짐. 주소록이 있고, 각 건물은 도로 그래프에 연결되는 진입로 타일을 여기에 저장함
      2. 집 안 경로 탐색은 A*를 쓰며, 더 빠르게 하려고 건물/마당의 각 타일에 대해 8방향 탈출 가중치를 미리 구워 둠
        2b) 이것을 16비트 비트마스크로 압축함. 2비트 조각 8개, 즉 8방향이고 해시 테이블에 저장함
        2c) 각 비트 조각은 네 상태를 가짐: FULL_BLOCK(벽), HARD_BLOCK(어느 방향에서도 타일을 통과 못 하게 하는 큰 물체), SOFT_BLOCK(한쪽 모서리 통과를 막는 작은 물체), NO_BLOCK(빈 타일이나 아주 작은 물체가 있는 타일)
        이렇게 하면 건물 안 유닛이 경로를 찾을 때 모든 타일마다 장애물을 검사할 필요가 없음. 물체가 거대하지 않고 회전 방향상 입구와 출구 모서리를 막지 않으면, 물체가 있는 타일도 통과할 수 있음. 마지막으로 플레이어가 문 배치를 잊었을 때처럼 시뮬레이션이 망가지지 않도록 에이전트가 벽도 통과할 수 있게 함
      3. 에이전트가 서로 다른 그래프 계층을 쉽게 가로지르도록 큐에 저장되는 경유지 시스템을 씀. 운전할 때 먼저 차까지 걸어가라고 지시하는 데도 사용함
      4. 도로 경로 탐색은 다른 방식을 쓰지만, 역시 미리 구운 그래프를 활용해서 매우 빠르게 만듦
        https://store.steampowered.com/app/2287430/Metropolis_1998/
    • 각 경로 노드에서 가장 가까운 장애물까지의 거리도 계산해 경로 노드에 저장하면 좋음
      캐릭터가 이런 “거품” 안에 있는 동안은 월드와의 충돌 검사를 통째로 건너뛸 수 있음
    • “도시 단위, 건물 내 방 사이, 방 내부” 같은 계층 그래프는 손으로 만든 건가? 그래프 분할처럼 작지만 NP-난해한 문제가 반복해서 나오면, 라이브러리를 찾아 배우지 않고 그냥 기성 알고리즘을 던져 넣고 싶어져서 늘 귀찮음
      대학 때는 RTS에서 A*가 왜 그렇게 어려운지 이해하지 못했는데, 유닛들이 서로를 통과하지 않게 하려면 움직이는 모든 것이 다른 모든 유닛을 계속 피해 경로를 다시 찾아야 한다는 설명을 보고 Command & Conquer를 새삼 존경하게 됨
    • 그래프 노드 자체에 현재 A* 탐색 메타데이터를 저장하는 방식은 어떤 상황에는 맞을 수 있지만, 자주 접근하는 데이터와 드문 데이터를 섞고 동시 탐색도 막아 버림
      아주 강한 이유가 없다면 개인적으로는 피하겠음
    • 로봇공학에서 경로 계획을 다루면 이런 개념마다 논문 더미가 있는데, 이걸 “요령”이라고 부르는 걸 보니 꽤 웃김

  • Scala로 만든 Quoridor AI를 빠르게 하려고 빠른 경로 탐색을 많이 고민했고, 배운 요령은 이렇다
    MPAA(다중 경로 적응형 A*)는 장애물이 추가되는 상황에서 같은 영역을 여러 번 다시 탐색해야 할 때 좋음. 이전 탐색 결과를 넣어 경로 탐색을 빠르게 만들 수 있음
    JPS(점프 포인트 탐색)는 고려할 “노드” 수를 크게 줄일 수 있어 이론적으로 매력적이지만, 점프 포인트를 찾는 오버헤드가 커져 실제 속도 향상은 없었음. MPAA와 JPS 아이디어를 결합할 방법이 있을 수도 있지만, 알고리즘을 창의적으로 만지다 보면 사소한 개념적 디테일로 쉽게 발등을 찍게 됨. 예를 들어 >=가 필요할 때 >를 쓰면 특정 상황에서 진짜 최단 경로를 보장하지 못할 수 있음
    열린 노드를 저장할 때 제대로 된 힙 대신, 최대 우선순위 값이 비교적 작은 정수라면 버킷 우선순위 큐도 고려할 만함. 내부 배열을 우선순위로 인덱싱하므로 삽입과 꺼내기가 꽤 빨라짐
    Quoridor는 9x9 격자에서 진행되며, 플레이어가 목표에 얼마나 가까운지와 목표 도달 가능 여부를 판단하려면 반복 경로 탐색이 필수임. 특정 위치에서 가능한 수를 판단하려면 모든 수가 목표 도달을 불가능하게 만들지 않는지 검사해야 함. 몇 달 안에 공개할 계획이고, 최소 3개의 의사결정 “엔진”을 포함할 예정임: mtdf(미니맥스 변형), MCTS(몇 가지 요령을 넣은 병렬 버전), catboost를 섞은 하이브리드

    • 9x9는 아주 작은 격자라서 타일이 81개뿐임. 모든 타일에서 모든 다른 타일까지의 거리를 저장해도 6561바이트면 되고, 일반적인 L1 캐시에 들어감
      이걸 보통의 직선거리 대신 휴리스틱 함수용 조회 테이블로 쓸 수 있다는 점이 좋음. 예를 들어 매 턴 시작 시 이미 놓인 벽을 반영해 Floyd-Warshall 알고리즘으로 이 테이블을 초기화할 수 있음. 비슷한 문제에서 이 기법으로 A*를 꽤 크게 빠르게 만들었고, 매우 단순했음. 다만 MPAA나 JPS 없이 순수 A*였음
    • JPS는 재미있지만, 실제로는 점프 노드 계산 때문에 저자들이 제시한 성능 향상을 해석하기가 어려웠음
      여러 해 전에 PathFinding.js의 JPS 구현에 점프 노드를 찾는 재귀 탐색을 시각화하는 기능을 추가했음. 온라인 데모는 여기 있음: https://qiao.github.io/PathFinding.js/visual/
    • 버킷 큐에 한 표. 몇 주 전에 이 요령을 알게 됐고, 내 사용 사례에서는 A* 실행 시간이 약 60~70% 줄었음

  • 적이 둘 이상이면 플레이어 관점에서 그냥 Dijkstra를 한 번 돌리고, 각 몬스터가 플레이어까지의 최적 경로를 조회하게 하는 편이 유리해질 수 있음
    몬스터 수가 변할 때 계산 비용이 더 예측 가능해짐

  • 마지막 애니메이션의 깊이가 너무 작은 문제는 흥미로운 행동처럼 보임. 몬스터가 “네가 어느 쪽으로 갈지 보려고 기다리는” 것처럼 보임
    한쪽으로 가는 척하다가 방향을 바꾸면 속일 수도 있지 않나? 다행히 인간은 이런 것에 꽤 관대해서, 뭐든 지능이 있는 것처럼 모델링하는 듯함

    • 작성자임: 멋진 아이디어고 생각 못 했음! 현재 구현에서는 그대로 되진 않지만, 작은 수정으로 가능할 듯함
      기본적으로 적이 매 프레임이 아니라 짧은 지연 뒤에만 경로를 갱신하게 하면 됨. 그러면 “관성” 때문에 기존 경로를 따라가고, 플레이어가 속일 수 있게 됨
    • 정확히 이걸 턴 지연과 “냄새 흔적 따라가기”로 구현했는데 꽤 잘 동작함. 가끔 AI가 잠깐 멈춰 자신을 추스른 뒤 플레이어에게 직선으로 달려드는 것처럼 보임

  • 게임 맥락에서 A*의 흥미로운 활용으로, 2000년대 초반 게임의 컴퓨터 상대를 만들어야 했던 프로그래머가 있었음
    게임에서 AI가 가진 선택지를 추상화하고, 그 그래프에서 가장 가까운 거리를 A*로 찾게 했음. 월드 경로 탐색이라는 전통적 용도가 아니라, 컴퓨터가 할 수 있는 선택의 표현 위에서 경로를 찾고 최단 경로가 가능한 최선 전략을 나타내게 했다는 점이 멋졌음

    • 게임 AI에서 더 흔한 접근 중 하나가 GOAP(목표 지향 행동 계획)이고, 본질적으로 같은 개념으로 어떤 행동 집합을 “선택”함. 가능한 선택지를 그래프 탐색, 보통 A*로 찾는 방식임
      0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
      1 - https://web.archive.org/web/20230804100329/https://alumni.me...
      참고 자료도 있음(내 것은 아님): https://github.com/agoose77/goap-resources
    • 방을 가로질러 걷기, 공격/방어/아이템 사용 선택, 어떤 적을 목표로 할지 같은 작업에 비슷한 계획 알고리즘을 쓸 수 있다는 점이 게임 AI에 지능을 부여해 보이게 만드는 일부 이유일 수 있음
      인간은 자신과 다른 인간이 경로 계획, 위험/보상 평가, 6개월 뒤 행사 계획처럼 전혀 다른 활동에도 비슷한 사고 패턴과 비슷한 깊이의 생각을 쓴다고 여기는 듯함. 다양한 “탐색 공간”을 공통 알고리즘에 맞는 그래프로 인코딩할 수 있으면, 플레이 중 몰입 상태에서 AI가 사려 깊고 거의 인격체처럼 보이는 개연성이 생김
    • CodinGame Spring/Fall Challenge에서 이기는 방식도 기본적으로 이렇지만, 한 번에 하나의 경로를 보는 A* 대신 여러 경로를 병렬로 확인하는 빔 탐색을 씀

  • 대학에서 A*를 배우던 때, 동시에 공용 Minecraft 서버에서 그 특이한 문제를 겪었음
    서버가 심하게 버벅여서 추적을 돌려 보니, 좀비들이 큰 울타리로 완전히 막아 둔 마을에 들어가려고 길을 찾는 루프에 빠져 있었음. 당시 구현이 순진해서 절대 포기하지 않았다는 뜻임
    이를 어떻게 고칠지 꽤 자세히 적힌 버그 리포트가 있었던 것으로 기억함

    • Dwarf Fortress에도 비슷한 장기 버그가 있었음. 문이나 해치를 동물이 통과할 수 없게 표시했는데, 길든 떠돌이 동물(대개 고양이)이 지나가고 싶어 하면 반대편으로 가는 경로 찾기를 절대 포기하지 않음
      특히 여러 동물이 모두 통과 불가능한 출입구를 지나가려 할 때 fps에 아주 눈에 띄는 영향을 줄 수 있음. 물론 닫힌 문을 지나가겠다고 매우 집요하게 요구하는 고양이 행동으로 보면 엄청 현실적이라고 할 수도 있음. 문을 열어 주자마자 고양이가 즉시 마음을 바꾸고 지나가는 데 관심을 잃으면 더 현실적이겠지만!
    • 지난 10분 동안 Minecraft의 몹 추적 구현 정보를 찾아봤는데 아무것도 못 찾았음. 아마 몇 가지 매개변수를 붙인 평범한 A*일 것 같음

  • 낯선 지형에서 A*를 쓰는 다중 에이전트 시스템 논문에 관심이 있을 수도 있음: https://www.researchgate.net/publication/333917261_Implement...

  • 이 글과 HN 스레드에 좋은 요령들이 있음. 아직 A*를 많이 쓸 일은 없었지만, 괜찮은 Haskell 라이브러리가 있다는 건 알고 있음: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...

답변달기