📚 지식 노트

A* 길찾기

적이 벽 뒤의 플레이어에게 오려면 “어느 길로 가야 하나”를 알아야 한다. 목표 쪽으로 곧장 걷다가 벽에 막히면 비켜 가는 식으로는 U자 골목 같은 오목한 지형에 갇힌다. 그래서 게임은 걸을 수 있는 공간을 격자 칸이나 다각형 같은 유한한 조각으로 나누고, 조각을 점(노드), 이웃 관계를 선(간선)으로 본 그래프에서 길을 찾는다. 조각이 유한하니 “다 찾아봤는데 길이 없다”는 판정도 할 수 있다.

가장 단순한 방법은 출발점에서 가까운 칸부터 차례로 전부 넓혀 가는 너비 우선 탐색(BFS)이다. 칸마다 이동 비용이 다르면 우선순위 큐로 비용이 가장 작은 칸부터 꺼내는 다익스트라(Dijkstra)가 된다. 목표에 닿는 순간 그 길이 가장 짧다는 것이 보장되지만, 방향을 가리지 않으니 목표 반대편까지 똑같이 뒤진다.

A*는 꺼낼 칸의 점수에 목표까지 남은 거리의 추정치를 더한다. f = g + h에서 g는 출발점부터 실제로 온 비용, h는 목표까지의 추정(휴리스틱)이다. h가 탐색을 목표 쪽으로 기울여 훨씬 적은 칸만 보고도 같은 길을 찾는다. h를 0으로 두면 다익스트라와 같아진다.

• 허용 가능한 휴리스틱(admissible heuristic): h가 실제 남은 비용보다 크지 않으면 A*는 가장 짧은 길을 찾는다. 4방향 격자의 맨해튼 거리, 자유 이동의 직선 거리가 그렇다.
• 가중 A*: h에 1보다 큰 값을 곱하면 더 빨리 끝나는 대신 최단은 보장하지 않는다. 몬스터가 조금 돌아가도 티가 안 나는 게임에서는 일부러 쓴다.
• 동점 처리: 격자에서는 f가 같은 칸이 무더기로 생긴다. f가 같으면 g가 큰 칸(더 깊이 들어간 칸)을 먼저 꺼내면 같은 점수의 칸을 덜 헤집는다.
• 경로 복원: 칸마다 “어느 칸에서 왔는지”만 적어 두었다가 목표에서 거꾸로 따라가면 길이 된다.

실전에서는 격자 대신 걷는 면을 다각형으로 나눈 내비메시를 쓰고(다음 절), 큰 맵은 방 단위의 거친 그래프로 먼저 찾은 뒤 방 안에서만 자세히 찾는 계층 탐색을 더한다. A*가 게임 밖 로봇 연구에서 나온 내력은 엔진 구조·최적화 노트에 있다.

내비메시와 퍼널 알고리즘

격자 A*가 주는 것은 “어느 칸을 지나는가”까지다. 칸 중심을 따라 걸으면 4방향 격자는 90°, 대각선을 허용해도 45° 단위로만 꺾여 캐릭터가 계단처럼 툭툭 돈다. 3D 맵을 잘게 덮으면 칸이 수만 개가 되어 탐색도 비싸다.

내비게이션 메시(navigation mesh, 내비메시)는 걸을 수 있는 면을 볼록 다각형으로 나눈다. 볼록 다각형 안의 두 점은 언제나 직선으로 이어지므로, 다각형 하나를 “안에서는 어디로든 곧게 갈 수 있는 방”으로 다룰 수 있다. 이웃 다각형이 공유하는 변이 포털(portal)이고, 다각형이 노드, 포털이 간선이 된다. 같은 공간을 칸 수백 개 대신 다각형 수십 개로 나타내니 A*가 훨씬 싸다.

1. 메시 만들기: 공개 라이브러리 Recast는 레벨의 충돌 형상을 복셀로 굽고, 걸을 수 없는 복셀을 걸러 낸 뒤, 남은 영역을 다각형으로 나눈다. 엔진의 내비메시 굽기가 대개 이 흐름이다.
2. 다각형 위 A*: 이웃은 포털을 공유한 다각형, 비용은 보통 포털 중점 사이 거리로 어림한다. 결과는 출발 다각형에서 목표 다각형까지 지나갈 다각형의 줄, 곧 복도다.
3. 퍼널로 실 당기기: 복도 안에서 가장 짧은 직선 경로를 뽑는다. 출발점에서 실을 잡고 포털들을 지나며 팽팽히 당긴다고 보면 된다.
4. 모서리 다듬기: 꼭짓점에서 몸이 한 번에 홱 돌지 않게, 경로를 곡선으로 둥글리거나 회전 속도를 제한한 조향으로 다음 꼭짓점을 따라가게 한다.

퍼널 알고리즘(funnel algorithm, string pulling)은 출발점을 꼭짓점으로 한 깔때기를 포털의 왼쪽 끝과 오른쪽 끝으로 좁혀 간다. 다음 포털의 끝이 깔때기 안쪽이면 그쪽 변을 좁히고, 한쪽 끝이 반대쪽 변을 넘어 깔때기가 뒤집히면 넘어선 쪽이 아니라 반대쪽 변의 끝점을 경로의 꼭짓점으로 확정하고 거기서 깔때기를 새로 연다. 큐 같은 자료구조 없이 루프 하나로 끝나는 단순한 판이 널리 쓰인다.

주의할 점은 캐릭터가 점이 아니라는 것이다. 실을 포털 끝에서 그대로 당기면 몸이 벽 모서리를 긁고 지나간다. 그래서 포털 양 끝을 캐릭터 반지름만큼 안쪽으로 당겨 놓고 퍼널을 돌리거나, 애초에 메시를 반지름만큼 줄여 굽는다. 움직이는 장애물, 경사, 점프 연결 같은 3D 요소는 메시에 따로 표시하거나 아래의 지역 회피가 맡는다.

시야 판정: 부채꼴, 레이캐스트, 인지 게이지

스텔스 게임에서 “적이 나를 봤다”는 눈이 아니라 판정 세 개를 차례로 통과하는 문제다. 싼 판정으로 먼저 거르고, 비싼 판정은 남은 대상에게만 돌린다.

1. 부채꼴: 반경 안인지와 정면에서 시야각의 절반 안인지를 본다. 각도는 역삼각함수 없이 내적으로 비교한다. 두 단위 벡터의 내적은 사잇각의 코사인이므로 dot(정면, 대상 방향) ≥ cos(시야각 / 2)이면 안이다. 거리도 제곱끼리 비교해 제곱근을 피한다. 시야각 90°면 기준값은 cos 45° ≈ 0.707이다.
2. 가림: 부채꼴을 통과한 대상에게만 눈 위치에서 대상까지 레이캐스트(raycast)를 쏴 중간에 벽이 있는지 본다. 몸 중심 한 점만 쏘면 낮은 엄폐물 위로 머리가 보이는데도 가려졌다고 나오므로, 머리·가슴처럼 대표점 몇 곳에 나눠 쏘고 몇 곳이 보였는지를 다음 단계로 넘기기도 한다.
3. 인지 게이지: 보이는 순간 바로 발각시키면 모퉁이에서 옷자락이 한 프레임 스친 것과 정면으로 마주친 것이 같아진다. 그래서 발각은 참·거짓이 아니라 시간에 따라 차오르는 값이다. 거리, 밝기, 자세, 이동 속도를 차오르는 속도에 곱하고, 가려지면 도로 내려가게 한다. 적 머리 위에 차오르는 눈 모양 표시가 이 값을 보여 주는 UI다.

앞의 둘은 기하라 답이 정해져 있고, 게이지는 손맛이라 튜닝으로 정한다. 그래서 게이지 수치는 코드에 박지 말고 데이터로 빼 두는 편이 좋다. 디버그 화면에 “각도 밖인지, 가렸는지, 게이지가 덜 찼는지” 세 값만 띄워도 시야 버그의 원인 대부분이 바로 보인다. 귀로 듣는 판정은 게임 사운드 노트에 있다.

공격 토큰: 몇 명이 동시에 덤비나

적 열 마리에게 둘러싸여도 실제로 달려드는 것은 한두 마리이고 나머지는 주위를 맴돈다. 적이 영리해서가 아니라, 공격하려면 허가를 받아야 하고 그 허가가 몇 장뿐이라서다. 모두가 동시에 때리면 초보자는 배울 틈도 없이 무너진다. 반대로 한 명씩만 덤비게 하는 방식(무협 영화의 장면에서 따온 이름으로 쿵푸 서클, Kung-Fu Circle)은 지루하고 광역기를 쓸 이유를 없앤다.

“동시에 셋까지”처럼 인원으로 세면 적 종류에 따라 압박이 출렁인다. 약한 병사 셋과 거대한 트롤 셋이 같은 “셋”이 되기 때문이다. 그래서 인원 대신 가중치로 센다.

예를 들어 자리 예산이 12일 때 가중치 4인 병사는 셋까지 붙지만, 가중치 8인 트롤은 하나만 붙고 남은 4에 병사 하나가 더 붙는다. 붙은 뒤에도 공격 예산이 남아야 원하는 공격을 쓰고, 모자라면 약한 공격으로 내려가거나 기다린다. 판정은 적 각자가 아니라 중앙 관리자 하나가 쥔다. 적은 자기 자리를 기억하지 않고 매 프레임 다시 묻는다. 그래야 플레이어가 굴러서 반대편으로 빠졌을 때 허가를 회수해 더 가까운 적에게 넘길 수 있다. 한 번 받은 허가를 계속 쥐게 하면 먼저 붙은 몇이 끝까지 독점한다.

• 난이도 손잡이: 적 하나하나의 체력·피해를 다시 맞추지 않고, 예산 두 개만 올리면 더 많이 동시에 덤빈다. DOOM(2016)은 근접·원거리 같은 공격 종류마다 토큰 수를 두고 난이도에 따라 그 수를 바꾼다.
• 가중치는 계단이다: 예산이 12면 가중치 8과 10과 12는 결과가 같다(어느 쪽이든 하나만 들어온다). 가중치를 바꿀 때는 몇 마리가 들어오는지가 바뀌는 경계를 보고 고른다.
• 재는 법: 이 시스템이 막으려는 것은 총 피해량이 아니라 한꺼번에 들어오는 피해다. 효과를 볼 때도 평균이 아니라 짧은 구간의 최대 피해로 재야 한다.

모든 게임이 이렇지는 않다. 여럿에게 둘러싸이면 그대로 동시에 맞는 소울라이크처럼, 압박 자체를 설계 의도로 두는 게임도 있다.

슬롯 시스템과 헝가리안 알고리즘

허가를 받은 적들이 모두 플레이어 한 점을 목표로 달려오면 몸이 겹치고 서로 밀친다. 슬롯(slot) 시스템은 갈 곳 둘레나 그 위에 설 자리를 먼저 놓고, 캐릭터를 그 자리로 보낸다. 근접 적 무리가 몰려오는 게임들이 이 방식을 쓴다고 개발자 글과 발표에서 밝혀 왔다.

• 예약: 플레이어 둘레 원 위에 슬롯을 같은 간격으로 놓고, 적이 빈 슬롯 하나를 예약한다. 예약된 슬롯은 다른 적이 고르지 못한다. 다가온 방향의 슬롯부터 보고, 안 되면 좌우를 번갈아 본다.
• 대기: 슬롯이 다 찼거나 앞 절의 예산이 모자란 적은 바깥 고리에서 기다리다가, 슬롯이 비면 넘겨받는다. 빈 슬롯 앞에 세워 두면 플레이어 옆으로 돌아 들어가는 움직임이 저절로 나온다.
• 끄기: 벽에 막혔거나 플레이어에서 곧게 닿지 않는 슬롯은 잠시 끈다. 벽을 등진 플레이어에게는 그만큼 적게 붙는다.
• 긴 표적: 바리케이드처럼 옆으로 긴 표적은 슬롯을 한 줄로 놓는다. RTS에서는 지도를 나눈 셀 중 사거리 안에 있고 아군이 아직 고르지 않은 셀이 슬롯 노릇을 한다.

포메이션도 슬롯이다. 플레이어가 그은 선 위에 유닛 수만큼 자리를 놓으면 남는 문제는 누가 어느 자리로 가느냐, 곧 매칭이다. 유닛마다 가장 가까운 빈 자리를 차례로 주면 앞 유닛이 좋은 자리를 가져가 뒤 유닛의 길이 엇갈린다. 자리와 유닛을 같은 축으로 정렬해 차례로 맞추면 엇갈림이 크게 준다.

총 이동 거리가 가장 짧은 매칭을 정확히 구하는 것이 헝가리안 알고리즘(Hungarian algorithm)이다. n명과 n자리의 비용 표에서 행과 열마다 최솟값을 빼고, 0인 칸만으로 한 사람에 한 자리씩 고를 수 있을 때까지 표를 고쳐 가는 방법으로, 시간이 O(n³)이다. 유클리드 거리로 총합이 최소인 매칭은 경로가 서로 엇갈리지 않는다(엇갈린 두 쌍은 자리를 바꾸면 삼각부등식 때문에 총합이 줄어든다). 그래서 유닛이 적을 때는 헝가리안으로 정확히 풀고, 많을 때는 정렬로 맞춘 뒤 엇갈린 쌍만 바꿔 주는 식으로 섞어 쓴다.

슬롯은 근접 무리에 맞는 방법이다. 멀리서 쏘는 적이나 수백 유닛을 한꺼번에 옮기는 RTS는 칸마다 갈 방향을 적어 둔 흐름장(flow field)과 아래의 지역 회피를 쓰기도 한다.

Boids: 규칙 세 개로 무리 짓기

몬스터 서른 마리가 몰려와도 서로 밟지 않고, 새 떼와 물고기 떼가 갈라졌다 다시 합친다. 무리 전체를 중앙에서 짜는 코드는 없다. 1987년 SIGGRAPH 논문 Flocks, Herds, and Schools가 제안한 Boids는 개체 하나가 가까운 이웃 몇만 보고 똑같은 규칙 세 개를 돌리게 했고, 무리의 모양은 그 규칙에서 저절로 나온다. 절반이 장애물 왼쪽으로 가도 깨질 코드가 없다.

• 분리(separation): 가까운 이웃에게서 멀어진다. 거리에 반비례하게 세게 밀어야 코앞의 충돌과 먼 이웃이 같은 취급을 받지 않는다.
• 정렬(alignment): 이웃들의 평균 속도에 맞춘다. 같은 방향으로 흐르면 애초에 부딪힐 일이 줄어 분리를 미리 돕는다.
• 응집(cohesion): 이웃들의 평균 위치로 향한다. 무리가 흩어지지 않고 갈라진 무리가 다시 합친다.

여기에 목표로 가는 힘까지 넷을 합쳐야 하는데, 가중치를 곱해 더하기만 하면 서로 반대인 분리와 응집이 지워 버려 가장 급한 충돌 회피가 가장 많이 깎인다. 원 논문은 개체가 한 번에 쓸 수 있는 가속 총량을 정해 두고, 우선순위 순서(충돌 회피가 먼저)로 채우다가 넘치는 요구는 잘라 버리는 우선순위 가속 배분을 썼다. 모바일에서 수천 유닛을 돌린 게임도 같은 구조를 썼다.

• 진짜 비용은 이웃 찾기: 규칙 계산은 벡터 몇 개를 더하는 것이지만, 누가 이웃인지 알려고 모두와 거리를 재면 O(N²)이다. 공간을 이웃 반경 크기의 칸으로 나누면 주변 칸만 보면 된다(엔진 구조·최적화 노트의 공간 격자).
• 물리 충돌만으로는 안 된다: 콜라이더는 닿은 뒤에 밀어내므로 매 프레임 떨림이 생기고, 위치를 강제로 옮겨 정렬이 만든 대형을 깬다. 조향으로 미리 비키고 콜라이더는 뚫린 경우의 얇은 안전망으로 둔다.
• 도착: 목표를 향해 같은 힘으로 가면(seek) 지나쳤다 되돌아오기를 반복한다. 남은 거리에 비례해 감속하는 arrival을 쓴다.

무리 기술이 잘 통하는 곳은 무리가 하나의 대상으로 보이는 곳이다. 몬스터 웨이브, RTS 유닛, 배경 군중이 그렇다. 무리가 크면 개체 하나의 어색한 순간이 묻힌다. 반대로 플레이어가 특정 개체 하나를 계속 지켜보는 장면, 예를 들어 레이싱 게임에서 옆 차와 바퀴를 맞대는 순간에는 그 어색함이 다 보여서 다른 조향 방식으로 바꾼 사례도 있다.

RVO와 ORCA: 부딪힐 속도를 미리 버리기

Boids의 분리는 이웃이 가까워진 뒤에 미는 반응형이다. 같은 방향으로 흐르는 무리 안에서는 상대 속도가 작아 이걸로 충분하지만, 정면으로 마주 오는 상대는 두 속도가 더해져 알아챈 직후 부딪힌다. 그래서 군중 회피는 질문을 바꾼다. “지금 겹쳤나”가 아니라 “이 속도로 계속 가면 몇 초 뒤에 겹치나”다.

• 속도 장애물(velocity obstacle, VO): 상대가 지금 속도로 계속 간다고 할 때, 정해 둔 시간(시간 지평선) 안에 충돌하게 되는 내 속도의 집합이다. 이 집합 밖의 속도를 고르면 그 시간 안에는 부딪히지 않는다.
• RVO(reciprocal velocity obstacle): 상대도 똑같이 비킨다고 보고 책임을 반씩 나눈다. 둘이 조금씩만 틀어 지나가므로 혼자 크게 피하다 생기는 흔들림이 준다.
• ORCA(optimal reciprocal collision avoidance): 이웃마다 “허용되는 속도의 반평면” 하나를 만들고, 모든 반평면을 만족하는 속도 가운데 원하는 속도에 가장 가까운 것을 선형계획으로 고른다. 제약이 이웃마다 하나라 이웃이 많아도 빠르다.

구현을 단순하게 하려면 속도 후보를 원하는 방향 둘레에 여러 개(각도 × 빠르기) 뿌려 놓고, 후보마다 가장 이른 충돌 시각과 방향 틀기·감속 비용을 매겨 가장 싼 것을 고르는 샘플링 방식도 쓴다. Unity의 내비메시 에이전트와 언리얼 엔진의 군중 회피도 이런 속도 기반 회피를 제공한다. 매 프레임 다시 정하지 않고 초당 열 번쯤만 정해도 충분하다.

• 마주 서서 도는 버그: 둘이 거울처럼 마주 보고, 같은 규칙으로, 같은 순간에 마음을 바꾸면 둘 다 같은 쪽으로 비켰다가 같이 되돌아오며 맞물린다. 비킬 쪽을 “세계 기준 빈 쪽” 대신 “내 진행 방향의 오른쪽”처럼 자기 기준으로 정하고, 다시 정하는 박자를 개체마다 어긋내면 성립하지 않는다.
• 나란히 가는 무리: 같은 속도로 붙어 가는 둘은 상대 속도가 0이라 영원히 안 부딪힌다고 계산된다. 줄지어 가는 간격은 가벼운 분리가 맡고, 분리는 회피가 고른 속도에 섞어야 둘 다 산다.
• 지평선 너머는 못 본다: 회피는 몇 초 앞만 본다. ㄷ자 주머니 같은 지형에서는 벽만 피할 뿐 밖으로 돌아 나올 이유를 만들지 못한다. 어느 길로 갈지는 A*가, 그 길 위에서 어떤 속도로 갈지는 회피가 맡는다.

마지막 층은 다시 고르기다. 문이 둘인 방에서 모두가 출발할 때 고른 같은 문으로 몰리면 줄이 생긴다. 경로 비용에 “그 길이 지금 얼마나 붐비나”를 더하면 무리가 두 문을 나눠 쓴다. 다만 순진하게 켜면 두 문 사이를 오가는 핑퐁이 생기므로, 충분히 쌀 때만 갈아타게 하는 히스테리시스와 갈아타기 횟수 제한을 함께 둔다.

스마트 오브젝트: 쓰는 법은 물건에 적는다

생활 시뮬레이션에서 새로 산 물건을 주민이 알아서 가서 쓴다. 주민마다 냉장고 쓰는 법, 침대 쓰는 법이 들어 있다면 물건이 하나 늘 때마다 주민 코드를 고쳐야 한다. 스마트 오브젝트(smart object)는 반대로 한다. 물건이 “나로 무엇을 할 수 있고, 그러면 어떤 욕구가 얼마나 채워지는지”와 쓰는 법을 들고 있고, 주민은 그것을 읽어 실행한다. 심즈(The Sims)가 이 구조로 유명하다.

• 물건 쪽: 설 자리와 바라볼 방향(슬롯), 틀 애니메이션, 차례대로 할 일의 목록, 끝나고 바꿀 욕구 값.
• 주민 쪽: 욕구 값을 보고 물건을 고르고, 슬롯을 예약하고, 걸어가고, 물건의 목록을 한 줄씩 실행하고, 끝나면 예약을 푼다. 주민 코드에는 물건 이름이 나오지 않는다.
• 고르기: 물건마다 채워 줄 수 있는 욕구를 광고하고, 주민은 지금 많이 모자란 욕구를 채워 주면서 가까운 물건에 높은 점수를 준다.

얻는 것은 확장성이다. 게임을 실행하는 중에 새 물건을 놓아도 주민이 그것을 고르고 쓴다. 물건이 자기 상태에 따라 지금 할 수 있는 행동을 정하게 하면(고장 난 샤워기는 “수리하기”만 내놓는 식) 주민 쪽에 모든 경우를 적을 필요가 없다. 대가는 디버깅이다. 이상한 행동의 원인이 주민이 아니라 물건 데이터에 있으니, 어느 물건의 목록이 무엇을 시켰는지 추적할 도구가 필요하다.

엔진마다 “물건에 무엇까지 넣나”가 다르다. 언리얼 엔진의 Smart Objects는 쓰는 차례를 찾기, 예약(claim), 쓰기, 해제로 나누고, 물건에는 슬롯과 태그 같은 데이터를 두며 실제 행동 로직은 쓰는 쪽(에이전트)이 수행한다. 오픈월드 RPG 쪽에서는 비헤이비어 트리의 일부를 물건 쪽에 두고 주민의 트리에 끼워 실행하는 방식도 논문으로 소개됐다. 어느 쪽이든 핵심은 같다. 쓰는 법을 아는 주체를 주민에서 물건으로 옮겨, 물건을 더하고 빼는 것만으로 행동이 늘고 준다.

행동 트리: 우선순위를 나무 모양으로 적는다

적의 판단을 상태 기계(FSM)로 짜면 처음에는 깔끔하다. 순찰, 조사, 교전 셋이면 화살표도 몇 개 안 된다. 그런데 엄폐, 재장전, 도주, 동료 부르기가 붙으면 상태마다 “어떤 일이 생기면 어디로 가나”를 따로 적어야 해서 화살표가 상태 수의 제곱으로 늘고, 같은 조건이 여러 화살표에 복사된다. 하나를 고치다 다른 하나를 빠뜨리기 쉽다.

행동 트리(behavior tree, 비헤이비어 트리)는 전이를 적지 않고 우선순위를 적는다. 매 틱 뿌리에서 출발해 자식을 차례로 방문하고, 방문한 노드는 셋 중 하나를 돌려준다. 끝났으면 성공(success), 할 수 없으면 실패(failure), 아직 하는 중이면 진행 중(running)이다.

• 셀렉터(selector, fallback): 자식을 왼쪽부터 시도해 하나라도 성공하거나 진행 중이면 멈춘다. 왼쪽에 둘수록 급한 일이 된다. “교전할 수 있으면 교전, 아니면 조사, 아니면 순찰”이 셀렉터 하나다.
• 시퀀스(sequence): 자식을 차례로 실행하다 하나라도 실패하면 멈춘다. 조건 몇 개를 앞에 두고 행동을 뒤에 두면 “조건이 다 맞을 때만 한다”가 된다.
• 데코레이터(decorator): 자식 하나의 결과를 바꾼다. 결과 뒤집기, 몇 번 되풀이, 한 번 쓰면 몇 초 쉬기(쿨다운), 몇 초 지나면 실패로 끊기(타임아웃) 같은 것이다.
• 잎: 실제 일은 잎이 한다. “보이나?” 같은 조건은 즉시 성공이나 실패를 돌려주고, “걸어가기” 같은 행동은 도착할 때까지 진행 중을 돌려준다.

노드끼리 직접 값을 주고받지 않는다. 마지막으로 소리가 난 자리, 지금 노리는 대상 같은 값은 블랙보드(blackboard)라는 공용 메모에 적고, 조건과 행동이 거기서 읽는다. 그래서 가지 하나를 떼어 다른 적의 트리에 붙여도 돌아간다. 트리는 같은 모양을 여러 적이 나눠 쓰고, 적마다 다른 것은 블랙보드뿐이다.

• 끼어들기: 매 틱 뿌리부터 다시 보면 조사하러 걷던 중에도 플레이어가 보이는 순간 왼쪽의 교전이 이긴다. 대신 매 틱 모든 조건을 다시 재는 비용이 든다. 언리얼 엔진의 행동 트리는 반대로 진행 중인 잎을 계속 돌리다가, 블랙보드 값이 바뀌면 그 값을 지켜보는 데코레이터가 지금 가지를 끊고(observer aborts) 다시 고르게 한다.
• 끊길 때 정리: 진행 중이던 행동이 끊기면 예약한 엄폐 자리나 공격 토큰을 돌려줘야 한다. 행동마다 시작과 끝 처리를 짝으로 두지 않으면 끊긴 적이 자리를 영영 쥐고 있다.
• 가지를 잠가 두기: 에일리언: 아이솔레이션(2014)의 에일리언은 노드가 백 개가 넘는 트리를 쓰되, 일부 가지를 잠가 두었다가 게임이 진행되며 조건을 채우면 풀었다. 처음에는 단순하던 괴물이 점점 영리해지는 것처럼 보이는 까닭이다.

같은 게임에는 층이 하나 더 있었다. 플레이어 위치를 언제나 아는 감독 AI(director)가 긴장도를 재다가, 가끔 에일리언에게 “대략 이쪽을 뒤져 보라”는 넓은 힌트만 준다. 정확한 위치는 에일리언이 자기 눈과 귀로 찾아야 한다. 긴장이 너무 오래 높으면 감독이 에일리언을 환풍구로 물려 숨 돌릴 틈을 만든다. 전부 아는 쪽과 직접 행동하는 쪽을 나누면, 공정해 보이면서도 속도를 조절할 수 있다.

목표 지향 행동 계획(GOAP): 순서를 AI가 짠다

행동 트리는 디자이너가 순서를 적는다. 반대로 적에게 목표와 쓸 수 있는 행동만 주고 순서는 게임 중에 스스로 찾게 할 수도 있다. 이것이 목표 지향 행동 계획(goal-oriented action planning, GOAP)이다. 바탕은 로봇의 행동 계획에서 나온 STRIPS(엔진 구조·최적화 노트의 게임 기술의 뿌리)다.

• 세계 상태: “무기 장전됨”, “적이 사거리 안”, “엄폐 중” 같은 참·거짓 사실 몇 개로 세상을 줄여 적는다.
• 행동: 행동마다 전제 조건(이게 참이어야 할 수 있다), 효과(하고 나면 이게 참이 된다), 비용을 적는다. 재장전은 전제 “탄약 있음”, 효과 “무기 장전됨”이다.
• 계획: 목표 상태(예: “적 제압됨”)에서 출발해, 아직 참이 아닌 사실을 효과로 만들어 주는 행동을 거꾸로 이어 간다. 이 탐색에 길찾기의 A*를 그대로 쓴다. 노드는 세계 상태, 간선은 행동, 간선 비용은 행동 비용이고, 휴리스틱은 아직 맞지 않은 사실의 개수다.

예를 들어 목표가 “적 제압됨”이면 그 효과를 내는 행동은 “사격”이고, 사격의 전제 “무기 장전됨”이 거짓이면 “재장전”을, 재장전의 전제 “탄약 있음”이 거짓이면 “탄약 줍기”를 앞에 붙인다. 계획은 탄약 줍기 → 재장전 → 사격이다. 바닥에 탄약 대신 수류탄이 있으면 “수류탄 던지기”가 더 싼 길이 되어 계획 자체가 바뀐다. 디자이너가 그 조합을 미리 적지 않아도 된다.

F.E.A.R.(2005)은 이 방식으로 이름을 알렸다. 개발진은 GDC 2006 발표 Three States and a Plan에서 상태 기계에는 상태가 셋(이동, 애니메이션 재생, 스마트 오브젝트 쓰기)뿐이고 무엇을 어떤 순서로 할지는 계획기가 정한다고 설명했다. 같은 행동 목록을 가진 적이라도 놓인 상황이 다르면 다른 순서가 나온다.

• 다시 짜기: 계획을 실행하는 중에 세계가 바뀌면(주우려던 탄약을 플레이어가 먼저 주웠다) 다음 행동의 전제가 깨진다. 행동을 시작할 때마다 전제를 다시 확인하고, 깨졌으면 지금 상태에서 계획을 새로 짠다.
• 비용: 계획 탐색은 행동 트리 한 틱보다 비싸다. 사실과 행동 수를 작게 유지하고, 계획은 목표나 세계가 바뀔 때만 짠다.
• 통제: AI가 순서를 고르니 “여기서는 꼭 이렇게 해 줘”라는 연출을 넣기 어렵다. 그래서 큰 작업을 작은 작업으로 쪼개는 방법을 디자이너가 적어 주는 계층형 작업 네트워크(HTN, hierarchical task network)처럼 통제를 되찾는 변형도 널리 쓴다.

유틸리티 AI: 할 수 있는 일마다 점수를 매긴다

행동 트리의 셀렉터는 “왼쪽부터 되는 것”을 고른다. 그런데 판단이 여러 요인의 저울질이면 순서로는 잘 안 적힌다. 체력이 적으면 회복이 급하지만 탄창이 비었으면 재장전도 급하고, 적이 코앞이면 둘 다 미루고 도망쳐야 한다. 유틸리티 AI(utility AI)는 할 수 있는 행동마다 지금 얼마나 쓸모 있는지 0~1 점수를 매기고 가장 높은 것을 고른다.

1. 고려 항목(consideration): 행동마다 판단에 쓰는 입력 몇 개를 정한다. 회복이면 “체력이 얼마나 모자라나”와 “구급상자가 얼마나 가까운가”다. 입력은 0~1로 맞춘다.
2. 응답 곡선(response curve): 입력을 그대로 쓰지 않고 곡선에 통과시킨다. 체력이 조금 빠졌을 때는 회복할 마음이 거의 없다가 바닥에 가까울수록 급해지게 하려면 제곱 곡선을, 어느 문턱을 넘으면 확 켜지게 하려면 S자 곡선을 쓴다. 손맛은 대부분 이 곡선 모양에서 나온다.
3. 곱하기: 항목 점수를 곱해 행동 점수를 만든다. 하나라도 0이면 그 행동은 0이 되니 “구급상자가 없으면 회복은 아예 안 된다”가 따로 적지 않아도 성립한다.

이 표에서는 재장전이 근소하게 이긴다. 적이 다가와 “안전한 정도”가 떨어지면 재장전 점수가 같이 떨어져 회복이나 도망이 올라온다. 행동 사이의 우선순위를 적은 곳은 어디에도 없고, 상황이 바뀌면 순위가 저절로 바뀐다. 생활 시뮬레이션의 욕구 점수(위의 스마트 오브젝트)도 같은 계산이다.

• 곱셈의 손해: 1보다 작은 수를 많이 곱할수록 작아지므로 고려 항목이 많은 행동이 불리하다. 항목 수에 따라 점수를 보정하거나(곱한 값의 n제곱근, 즉 기하평균을 쓰는 식) 항목 수를 행동끼리 비슷하게 맞춘다.
• 왔다 갔다: 두 행동 점수가 비슷하면 매 틱 1등이 바뀌어 재장전하다 말고 회복하러 갔다 돌아온다. 지금 하는 행동에 작은 가산점(관성)을 주거나, 한 번 고르면 최소 몇 초는 유지한다.
• 뻔함 줄이기: 늘 1등만 고르면 같은 상황에서 같은 행동만 나온다. 1등과 차이가 작은 몇 개 중에서 점수 비례로 뽑으면 덜 기계적이다.
• 디버깅: 왜 그 행동을 골랐는지가 숫자로 남는다. 행동마다 항목 점수를 화면에 띄우는 도구를 먼저 만들어 두면 곡선을 고치기 쉽다.

실제 게임은 셋을 섞는다. 무엇을 할지(목표)는 유틸리티 점수로 고르고, 고른 목표를 어떤 순서로 할지는 행동 트리나 계획기가 맡는 식이다.

흐름장과 영향력 맵: 칸에 답을 적어 둔다

타워디펜스에서는 적 수백 마리가 모두 같은 기지로 간다. 한 마리마다 A*를 돌리면 같은 지도에서 거의 같은 길을 수백 번 찾는다. 질문을 뒤집으면 한 번으로 끝난다. “이 적은 어디로 가야 하나” 대신 “모든 칸에서 목표로 가려면 어느 쪽으로 가야 하나”를 한꺼번에 구해 칸에 적어 두는 것이다.

1. 거리 채우기: 목표 칸을 0으로 두고 너비 우선 탐색(칸마다 비용이 다르면 다익스트라)을 지도 전체에 퍼뜨려 칸마다 목표까지의 비용을 적는다. A*와 달리 멈출 목표가 없으니 휴리스틱이 필요 없다.
2. 화살표 긋기: 칸마다 이웃 중 비용이 가장 작은 칸을 가리키는 방향을 적는다. 이것이 흐름장(flow field, 벡터 필드)이다.
3. 따라가기: 유닛은 자기가 선 칸의 화살표만 읽고 그쪽으로 조향한다. 유닛이 열 마리든 천 마리든 탐색은 한 번이고, 유닛 하나의 비용은 칸 하나 읽기다.

• 다시 계산할 때: 플레이어가 탑을 세워 길을 바꾸면 흐름장을 한 번 다시 만든다. 탑을 세우기 전에 “이걸 세우면 목표로 가는 길이 남나”를 같은 탐색으로 미리 확인해 길을 완전히 막는 배치를 거부할 수도 있다.
• 목표가 여럿: 출발점 여러 칸을 모두 0으로 넣고 퍼뜨리면 칸마다 가장 가까운 목표로 향한다. 식량 창고가 여럿인 일꾼, 출구가 여럿인 대피가 그렇다.
• 대각선과 모서리: 8방향 화살표를 쓰면 움직임이 부드럽지만, 양옆이 벽인 대각선을 허용하면 유닛이 벽 모서리를 파고든다. 대각선은 양옆 두 칸이 모두 열려 있을 때만 허용한다.
• 넓은 지도: 칸이 수백만이면 지도 전체를 매번 채우기 어렵다. 지도를 큰 구역으로 나눠 구역 사이 길은 먼저 거친 그래프에서 찾고, 그 길이 지나는 구역의 흐름장만 만든다. 수백 유닛을 함께 움직이는 RTS가 이런 구역별 흐름장을 썼다.

칸에 숫자를 적어 두는 생각을 길 말고 판단에 쓰면 영향력 맵(influence map)이 된다. 유닛마다 자기 칸에 세력 값을 찍고 거리에 따라 줄어들게 퍼뜨린다. 아군은 양수, 적은 음수로 더하면 큰 양수 지역은 우리 땅, 큰 음수 지역은 적 땅, 0에 가까운 띠가 전선이다.

• 위험 지도: 적 세력만 따로 모은 맵은 “얼마나 위험한가”다. 길찾기 비용에 이 값을 더하면 유닛이 적의 사거리를 돌아서 간다. 체력이 낮은 유닛은 가중치를 키워 더 크게 돌게 한다.
• 자리 고르기: 엄폐하며 쏠 자리, 기지를 지을 자리, 정찰 보낼 곳(오래 안 본 칸의 값이 커지는 맵)을 칸 값으로 고른다. 맵 여러 장에 가중치를 곱해 더하면 판단 하나가 된다.
• 싸게 유지하기: 영향력 맵은 길찾기 격자보다 훨씬 거친 칸으로 충분하고, 매 프레임이 아니라 초당 몇 번만 갱신해도 된다. 스태거 업데이트(엔진 구조·최적화 노트)와 궁합이 좋다.