Game AI: Decision Making

‍박성령·2025년 4월 15일

목록 보기

8/8

Decision Making

Decision Making은 우리 AI 모델의 중간 요소이다.

Decision Making System은 캐릭터가 갖고 있는 내외부 정보를 input으로 받고 행동을 한다.

외부 정보는 다른 캐릭터의 위치나 레벨의 구조, 스위치가 작동되었는지 여부, 소리가 나는 방향과 같이 외부 환경의 정보를 말한다.

내부 정보는 캐릭터의 체력, 목표, 몇 초 전까지 무엇을하고 있었는지 등에 대한 정보이다.

캐릭터의 외부 상태를 변경할 수 있고 (무기 발사, 방으로 이동 등), 내부 상태에만 영향을 미치는 행동을 변경할 수도 있다. (새로운 목표 설정, 확률 변경 등)

1️⃣ Decision Trees

decision tree는 의사 결정에 사용된다.

tree의 시작점인 root를 가지고 있고 각 지점에서 분기가 나뉜다.
캐릭터가 갖고있는 정보를 기준으로 각 결정을한다.
tree의 laef에선 특정 행동을 한다. 또 여러 leaf에서 같은 행동을 할 수 있다.
Data Type은 다음과 같다.

Boolean
Eunmeration
Numeric value
3D Vector

decision tree는 위와 같이 결정이 일반적으로 매우 단순하다.

Complexity

또 위처럼 tree의 구조이기 때문에 4번의 결정만 하면 서로 다른 16개의 action을 취할 수 있다.

Branching

오른쪽 같은 구조는 잘 사용하지 않는다.
computation 관점으로 봤을 때 어차피 내부에서 if 문을 돌려야하기 때문에 의미가 없다.

Balancing the tree

decision tree는 tree가 balance할 때, 빠르게 동작할 수 있다.

balanced tree를 만들기 위해서 각 브랜치마다 같은 수의 leave들을 갖도록 구현한다.
또 실행하는 데 시간이 많이 걸리는 결정 (예: 가장 가까운 적까지의 거리를 탐색하는 결정)은 정말 필요한 경우에만 수행되어야 한다.
트리를 균형 있게 구성하되, 자주 사용되는 가지는 짧게, 드물게 사용되는 가지는 길게, 그리고 연산 비용이 많이 드는 결정은 뒤쪽에 배치해야 한다.

Random decision trees

Random 행동 선택 요소는 예측 불가능성, 흥미, 다양성을 더해준다.
무작위 숫자를 생성하고, 그 값에 따라 branch를 선택한다.
하지만 이 선택이 매 프레임마다 이루어지면, 캐릭터가 서 있다가 움직이는 등 오락가락하는 모습으로 보일 수 있다. → 연속된 프레임에서는 하나의 결정을 유지해야 합니다.
(게임 AI 만들 때, 결정을 한 뒤 시간이 좀 지나고 나서 바꾸는 느낌인듯 함)

2️⃣ Behavior Trees

Behavior Tree의 핵심은 task이다.

task의 종류는 다음과 같다.

Conditions: 적이 거리내에 있는지 등등의 조건

Actions: 게임의 상태를 변경시킬 수 있는 행동

Composites: Selector와 Sequence

✔️ Selector

Selector는 자식 노드를 왼쪽부터 차례대로 실행하고 자식중에 하나라도 성공하면 성공 상태와 함께 종료하고 그렇지 않으면 다음 자식 노드를 실행한다. 만약 자식 노드 전부 실패하면 실패 상태를 반환한다.

그림처럼 ?로 표시하고 Attack -> Taunt -> Stare 순으로 우선 순위가 매겨져 있다.

이 Selector는 빠른 반응성이 요구될 때 사용되곤 한다.

게임 개발 할 때, 한 공격 실패하면 다른 공격 진행하고 그럴 때 많이 사용했었음

✔️ Sequence

Sequence는 자식중에 하나라도 실패하면 종료한다. 자식 노드가 성공하면 다음 자식 노드를 실행한다.

왼쪽부터 차례대로 task를 수행한다.

단계적인 절차를 구현할 때 적합하다.

한 공격 task를 구성할 때 사용했었음 (콤보 공격 구성)

예제

다음은 AI가 문으로 들어가는 task를 구현한 것이다.

먼저 selector로 왼쪽 sequence를 실행한다. Door open?을 만나고 만약 문이 닫혀있었으면 바로 오른쪽 sequence로 가서 task들을 수행하게 된다.

위처럼 Sequence문의 Condition Task들은 if문 처럼 동작한다.

만약 Sequence가 Selector 안에 있으면 IF-ELSE문의 효과를 얻을 수 있다.

디테일 추가

또 behavior tree에 task를 추가함으로써 디테일을 높일 수 있다.

문을 열 때의 행동들을 추가한 것이다.

문이 먼저 잠겨있었는지 확인하고 문을 열든 부수든 선택한다.

✔️ Non-Deterministic compostion tasks

Decision tree에서 random하게 선택하는 것으로 생각하면 된다.

Selector에서 우선 순위를 매기지않고 random으로 선택하게 할 수도 있으며, Sequence에서 왼쪽에서부터 실행되지 않고 무작위로 실행되게 할 수도 있다.

Non-Deterministic compostion task들은 위처럼 ?앞에 ~ 표시를 하거나 화살표에 ~ 효과를 추가한다.

먼저 ~?에선 문을 부수는 것부터 실행할 수도 있고 오른쪽의 sequence를 수행할 수도 있다.

~sequence의 경우엔 문을 태우기 위해 성냥부터 집을지 기름부터 집을지 상관이 없기 때문에 위처럼 random하게 선택하도록 구현한 것이다.

✔️ Decorator

데코레이터 패턴(Decorator pattern)은 다른 클래스를 감싸서 그 동작을 수정하는 클래스를 말한다.

이 패턴은 하나의 child task만을 가지며, 그 작업의 동작을 어떤 방식으로든 수정하는 작업 유형이다.

위처럼 마름모 형태로 표현한다. 한 class를 감싸고 있으며, 자식 노드가 실패할때까지 반복시키고 있다.

✔️ The parallel task

병렬 작업(Parallel task)은 Sequence task와 비슷한 방식으로 동작한다.

차이점은 작업을 실행하는 방식에 있다. 시퀀스는 작업을 하나씩 실행하는 반면, 병렬 작업은 모든 작업을 동시에 실행한다.
자식 작업 중 하나라도 실패로 종료되면, Parallel은 아직 실행 중인 다른 자식 스레드들을 모두 종료한다.

화살표 3개로 표시된 부분이 병렬작업이다. 각 3명의 병사들이 병렬적으로 수행되는데 한 병사라도 실패하면 종료된다.

병렬 작업(Parallel task)의 또 하나의 일반적인 용도는, 어떤 조건(Condition)이 충족되는지를 지속적으로 확인하면서 특정 행동(Action)을 수행하는 것이다.
위를 보면 UntilFail Decorator를 사용하여 조건 확인을 계속 수행하면서 다른 일도 하고 있다.