목표지향 행동 - 3

2022.11.24 - [Game AI] - 목표 지향 행동 - 2

목표 지향 행동 - 2

 

 

목표 지향 계획 

---

계획의 필요성

이전에 다룬 로직에서는 해결이 불가능한 상황이 있다. 다음 예시를 보자

 

목표 : 체력 회복 = 4
목표 : 적 죽이기 = 3
행동 : 화염구 (적 죽이기 - 2) MP - 30
행동 : 회복 (체력 회복 - 2) MP - 20
행동 : 대회복 (체력 회복 - 4) MP -30

 

만약 지금 캐릭터의 MP가 50이라면, 가장 최선의 선택은 '회복'을 한 다음 '화염구'를 사용하는 것이다. 그러나 기존 로직으로는 '대회복'을 선택해야 한다. '대회복'을 사용하고 나면 MP가 모자라 어떤 행동도 할 수 없다. 이러한 상황에서는 로직에 계획이 추가될 필요가 있는 것이다.

 

 

 

 

 

GOAP

목표지향계획 (GOAP, Goal-Oriented Action Planning)은 기본적으로 할 수 있는 모든 선택의 Sequence를 고려한다. 

(학술적인 GOAP에 대한 많은 연구가 있지만 게임에서는 구현을 어렵게 하는 몇몇 제약들을 제거해도 잘 굴러가는 AI를 만들 수 있다.) 

 

이렇게 모든 경우를 고려하면 연산이 많이 필요하므로 불필요한 연산을 줄이기 위한 휴리스틱이 필요하다.

 

예를 들어, '불만족 지수가 증가하는 방향의 계획은 고려하지 않는다.'와 같은 휴리스틱은 꽤 합리적이면서 알고리즘의 연산 속도를 높여준다. 그러나 최적의 해를 계산하지 못한다는 단점이 있다. (ex. '이력서 작성하기'는 지금 당장의 만족도는 떨어지지만 미래를 본다면 좋은 선택)

 

이렇게 휴리스틱을 사용하여 계획을 수립하는 것은 A*알고리즘과 동일하다. 여러 A* 알고리즘 중 GOAP에 특히 유용한 녀석이 있는데 바로 IDA*(Iterative deepening A*)이다. 

 

IDA* (Iterative Deepening A*) : 인접 노드 리스트를 저장하지 않는 대신 cut-off를 사용한다. 비용이 cut-off 미만인 구간에서는 기초적인 A*알고리즘을 사용한다. 노드의 비용이 cut-off를 넘어가면 더 이상 해당 노드는 탐색하지 않는다. cut-off 이내에 경로를 찾았으면 return, 아니라면 cut-off 값을 증가시킨다. 인접 노드 리스트를 저장하지 않아 메모리를 절약할 수 있다는 장점이 있지만, 중복 계산이 많아 느리다.

 

 

 

---

 

 

Smelly GOB

---

Smelly GOB(Goal Oriented Behavior, 목표지향행동)는 사물이 캐릭터에게 행동의 선택지를 제공하는 형태이다. 이런걸 냄새(Smell)이라고 표현한 듯. 

 

예를 들면 조리도구는 '나는 음식을 제공할 수 있다.'의 냄새를, 침대는 '나는 휴식을 제공할 수 있다.'의 냄새를 풍긴다. 배가 고프거나 휴식이 필요한 캐릭터들은 이런 냄새를 따라가게 된다.

 

이런 접근법은 복잡한 길찾기를 줄여줄 수 있다. 

 

냄새는 source로 부터 퍼진다. 코너를 이동할 때는 시간이 더 걸리며, 벽을 관통할 수 없다. 냄새가 퍼지는 경로는 미리 계산해 놓을 수도 있다. 냄새의 세기는 source에서 멀어질 수록 점점 떨어진다. 이제 캐릭터는 냄새의 세기가 점점 강해지는 방향으로 이동하면 된다. 그러면 길찾기 알고리즘을 수행할 필요가 없다!

 

냄새의 세기는 source마다 달라질 수 있다. 예를 들어, 날음식은 옅은 냄새를 풍기고 잘 요리된 음식은 짙은 냄새를 풍길 수 있다.

 

참고로 이런 방식은 심즈에서도 사용된 접근법이라 한다.

 

 

 

 

행동 혼합하기

몇몇 행동은 수행하는데 여러 단계가 필요하다.

 

예를 들어, 조리도구는 요리 재료 없이 음식을 제공할 수 없다. 이런 문제는 냄새를 세분화 하거나 캐릭터의 상태에 따라 냄새를 풍길지 말지 정하여 해결할 수 있다.

 

 

냄새를 세분화 하기

냄새를 세분화 하는 방법에서 조리도구는 '나는 음식을 제공할 수 있다.'라는 냄새 대신에 '나는 날음식을 요리할 수 있어.'라는 냄새를 풍긴다. 이렇게 되면 캐릭터가 자신의 욕구를 해소해 줄 냄새를 따라가는 것이 복잡해진다는 단점이 있다. 동시에 다양한 행동을 지원하고 쉽게 확장할 수 있다는 장점이 있다.

 

캐릭터 상태에 따라 정하기

조리도구는 캐릭터가 요리 재료를 가지고 있을 때만 '나는 음식을 제공할 수 있다.'라는 냄새를 풍긴다. 이런 접근법은 매우 유연하고 세워야하는 계획의 양을 크게 줄여준다. 반면에 큰 단점도 있는데, 냄새가 캐릭터의 상태에 의존하게 된다는 것이다. 만약 캐릭터의 갯수가 많아지고 시뮬레이션 속도도 빨라진다면 문제가 된다.

 

 

---

참고 : Ian Millington, AI for GAMES 3rd edition, CRC press, [Chapter 5.7]