Game AI - Combining Steering Behaviors (1)

2021.10.03 - [Game AI] - Game AI - Steering Behaviors (3)

Game AI - Steering Behaviors (3)

---

Blending 과 Arbitration

Steering behavior들을 조합하는 데에는 크게 두 가지 방법이 있다.

 

혼합(Blending)은 조향 동작(Steering Behavior)들의 결과에 가중치(Weight)나 우선순위를 적용하여 그 결과들을 조합하는 방식이다. 이 자체로도 복잡한 동작을 할 수 있지만 캐릭터가 이동할 때 제약이 많은 경우 문제가 발생할 수 있다. 이러한 가중치나 속성은 시간이 지나면서 변화할 수 있으며 사용하지 않는 조향 동작의 가중치는 0으로 둘 수 있다.

 

중재(Arbitration)는 하나 이상의 조향 동작을 선택하여 캐릭터를 조종한다. 반환 값이 꼭 어떤 조향 동작의 반환 값일 필요는 없으며 혼합에 사용되는 가중치들의 집합을 반환할 수도 있다.

 

블랜딩과 중재는 상호 베타적인 관계가 아니며 이 둘을 같이 사용하는 것이 이상적이다.

 

---

 

Weighted Blending

가중치를 이용한 혼합은 조향 동작을 조합하는 가장 단순한 방법이다. 예를 들어 다음과 같은 동작이 있다.

동작1) 어떤 목적지를 향해 같이 이동하는 군중이지만, 서로 일정 거리를 떨어져서 이동한다.

위 동작의 경우 무리의 무게중심을 타겟으로 하는 도착(Arrive)동작과 분리(Separation) 동작을 조합하면 된다. 

 

---

구현

 각 조향동작의 반환 값(예를 들면 Vector3)에 가중치를 곱하여 더하면 된다. 단, 이때 반환 값이 미리 설정해둔 최대 가속도 등을 넘지 않도록 맞춰준다.

 

 Blending에서 각각의 가중치들은 매우 중요한 역할을 하며, 따라서 이런 가중치들의 값을 정하는 일이 매우 중요하다. 이런 가중치들은 유전 알고리즘이나 신경망 알고리즘을 통해 정해질 수 있다. 그러나 저자의 말에 따르면 이런 알고리즘등을 이용한 연구들이 진행됐음에도 고무적인 결과는 없었고 직접 실험하며 수치를 조절하는 것이 가장 그럴듯 했다고 한다. (참고로 책은 2019년 2월에 최종 업데이트된 버전)

 

---

 

Flocking과 Swarming

출처 : http://www.red3d.com/cwr/boids/

 

boids라고도 알려져 있는 동작이다.

 

Flocking은 3가지의 steering behaviors로 이뤄져 있다.

 

1. Separation : 다른 boid와 너무 가깝지 않도록 이동
2. Align/Velocity Matching : 무리 전체와 속도 및 방향을 일치시킴
3. Cohesion : 무리의 무게중심으로 이동

이때 각각의 가중치는 sepration > cohesion >= alignment 정도로 설정하면 자연스럽다. (셋 다 같아도 나쁘지 않다.)

 

대부분의 구현에서는 멀리 있는 boids는 무시하고 인근의 boids만 신경을 쓴다. 즉, Separation은 인근의 boids만 피하며 Velocity Matching과 Cohesion은 인근의 boids로 결과를 구한다. 

 

인접의 기준은 보통 단순하게 원 영역으로 정한다. 참고로 boids의 고안자인 Reynolds는 원 영역에서 진행방향 쪽으로 일정 각도를 잘라낸 영역을 이웃 영역으로 제안했다.

출처 : http://www.red3d.com/cwr/boids/

 

---

문제점

이런 조향 동작들을 혼합할 때 여러가지 문제가 있는데 보통 디버깅이 힘든 경우가 많다. 따라서 적어도 input과 output을 시각화 할 수 있도록 해두는 것이 중요하다.

 

 

평형(Equilibria)

 

혼합 동작의 경우 두 동작이 서로 충돌한다면 문제가 발생한다. 이 경우 캐릭터가 아무것도 안 하고 가만히 있을 수 있다. 이런 경우를 평형상태에 빠졌다고 한다.

 

예를 들어, 타겟을 향해 나아가지만 적은 피해서 가는 행동이 있다. 이때 타겟을 향해 가는 output과 적을 피하려는 output의 크기가 같고 방향이 반대라면 캐릭터는 움직이지 못할 것이다.

 

Unstable Equilibria

 

그러나 위와 같은 상황은 부동 소수점 연산의 오차정도만 발생해도 쉽게 평형상태가 붕괴되고 캐릭터가 움직일 수 있다. 이런 경우를 불안정한 평형(Unstable Equilibria)이라고 한다. 

 

Stable Equilibria

그러나 위와 같은 상황은 어떨까? 캐릭터가 조금 움직인다 하더라도 여전히 평형상태에 빠져있게 된다. 이런 경우를 안정된 평형상태(Stable Equilibria)라고 하고 캐릭터가 평형상태에 머무르게 되는 영역을 끌림 영역(basin of attraction) 이라고 한다. 불안정한 평형의 경우 끌림 영역의 크기가 0이다.

 

끌림 영역은 위치뿐 아니라 특정 방향을 바라보는 것이나 특정 방향으로 이동하는 것도 포함한다. 

 

 

근시(Nearsightedness)

 

조향 동작은 당장의 주위 환경만 고려하여 결정을 내리며 큰 그림은 보지 못한다. 따라서 아래와 같은 문제가 발생할 수 있다.

 

 

위와 같은 경우는 Pathfinding 알고리즘과 통합하여 해결할 수 있다.

 

---

Priorities

우선순위 기반의 시스템에서는 동작들이 그룹을 이룬다. 그 뒤 각각의 그룹들은 우선순위에 따라 정렬된다. 조향 시스템은 정렬된 순서를 따라 각각의 그룹을 순회한다. 만약 현재 조회 중인 그룹의 결과값이 매우 작은 경우에 이 결과를 무시한 뒤 다음 그룹을 조회한다.

 

예를 들어 어떤 타겟을 쫓는 그룹은 다음 두 그룹으로 구성된다.

1. 충돌 회피 동작 그룹
2. 타겟을 쫓는 동작 그룹

 

만약 충돌 회피 동작 그룹에서 결과 값이 나온다면 충돌을 회피한다. 그러나 주변에 장애물이 없어 충돌 회피 동작의 결과값이 매우 작다면 타겟을 쫓는 동작의 결과를 수행한다.

 

 

평형 상태 회피

 

만약 Wander같은 동작을 우선순위가 낮은 그룹으로 추가한다면 앞서 언급한 평형 상태를 빠져나올 수 있다. 이 방법은 불안정 평형 상태에서는 잘 먹히지만 끌림 영역이 큰 안정 평형 상태에서는 여전히 동작하지 않을 수 있다. 

 

 

동적 우선순위

 

그룹의 우선순위를 동적으로 정해서 쓸 수 있지만 실제적으로 효용은 크지 않다. 

---

Cooperative Arbitration

위에서 언급한 혼합 기반의 동작들은 구현하기 쉽고 각각의 동작들이 독립적으로 작동할 수 있다는 큰 장점이 있지만 반대로 평형 상태나 환경 문제 같은 큰 약점도 있다. 그래서 요즘 트렌드는 서로 다른 동작들이 서로 협동하도록 하는 것이다. 

 

위와 같은 상황에서 독립된 동작들을 혼합하는 방식은 벽을 피하기 위해 A와 같은 결과를 내놓을 것이다. 캐릭터는 결국 타겟을 쫓아갈 수 있지만 벽에 근접한 순간 속도가 크게 감소하게 되어 타겟을 쫓아가는데 더 오랜 시간이 걸리게 된다.

보다 합리적인 방법은 벽을 피하기 위해 B방향으로 움직이는 것이다. 그렇다면 캐릭터는 속도를 크게 줄이지 않고 타겟을 쫓아갈 수 있다. B와 같은 결과를 내기 위해서는 벽을 피하기 위한 동작이 전체 맥락을 파악할 줄 알아야 한다(context sensitive). 따라서 동작들을 하나의 블록으로 두고 조립하는 방식은 더 이상 사용할 수 없다. 

 

많은 협력 중재(Cooperative Arbitration) 방식이 결정 트리(Decision Tree) 기반으로 구현되며 각 조향 동작이 하나의 트리 노드로 구현된다. 그러나 이 방법은 올바로 구현하기가 까다롭다.

덜 흔한 방법으로는 blackboard architecture가 있는데. 이 방법의 경우 각각의 동작이 다른 동작들이 무엇을 하는지 blackboard에서 읽을 수 있다는 원리로 설계된다.

 

참고로 협력 중재 방식을 구현하는 이렇다 할 기준은 아직 없다고 한다. (대부분 결정 트리를 쓰지만)

---

다음에는 결정 트리를 사용하지 않고 협력 중재를 구현하는 방법 중 하나인 steering pipeline에 대해서 다룸.

 

참고 : Ian Millington, AI for GAMES 3rd edition, CRC press, [95~108p]