Movement는 Game AI에서 가장 기초가 되는 행동이다.
모든 Movement algorithms에서는 own state(현재 위치, 속도), world state(목표 위치, 장애물 등의 외부데이터), geometric output(결과로 갖게되는 이동 방향이나 속도)를 갖는다.
위 그림에서 character가 own state이고 game이 world state, movement request가 geometric output이 되겠다.
1️⃣ Movement 기본
Movement의 종류
movement의 종류는 다음과 같다.
- Kinematic movement: 캐릭터가 어떻게 감속/가속 할 지 고려안하고 방향과 속도만 고려
-> output: Direction and velocity
-> 구현과 연산 쉬움
-> 즉각적인 변화로 부자연스러울 수 있음
- Dynamic movement: 가해지는 힘이나 가속등을 고려한다.
-> output: Acceleration or force
-> 구현과 연산 복잡함
-> 점진적인 변화로 좀 더 현실성 있음
캐릭터를 하나의 점으로
Movement 알고리즘에선 캐릭터를 하나의 점으로 고려하고 구현한다.
충돌판정이나 장애물 회피 등등의 다른 알고리즘은 캐릭터의 size를 고려하지만 movement 그 자체는 그냥 점으로 고려한다.
Static
Orthonormal한 2D 평면에서 알고리즘을 다룰 것이다. z축과 x축을 사용한다.
Orientation은 캐릭터가 바라보는 방향으로, 반시계 방향을 +로 radian을 사용한다.
(이 글에서 다루는 코드는 전부 Pseudo code임)
Kinematics와 Steering 구성
타깃의 위치와 방향을 기준으로 타깃의 속도를 계산함으로써 movement 알고리즘을 구현한다.
- Linear velocity: x, y축에서 캐릭터가 얼마나 빨리 움직이는지 (그냥 속도)
- Angular velocity: 캐릭터의 orientation이 얼마나 빨리 움직이는지
steering의 경우 가속도를 return해야 한다.
update (좌표, 방향 업데이트)
위치와 방향을 업데이트 시킬 때, 움직임을 부드럽게 만들어야 한다.
2️⃣ Kinematic Movement 알고리즘
static data (좌표, 방향)를 사용하여 velocity를 return한다. 가속은 고려하지 않음
위는 velocity의 방향으로 캐릭터의 방위를 바꿔주는 함수이다.
✔️ Seek 알고리즘
kinematic에서 Seek 알고리즘은 캐릭터와 타깃의 static data를 이용해서 속도와 방향을 return한다.
타깃의 위치와 캐릭터의 위치로 속도를 구하고 maxSpeed로 바꾸어준다.
이 정보를 steering 객체에 저장하여 반환한다.
steering 객체의 구조는 다음과 같다.
✔️ Flee 도망 알고리즘
그냥 단순히 캐릭터의 위치에서 타킷의 위치를 빼는 것으로 바꾸어주면 된다.
✔️ Arriving 알고리즘
캐릭터가 타깃지점에 도달했을 때, 캐릭터는 항상 maxSpeed로 움직여서 overshoot한다는 문제가 있다.
이를 해결하기 위해 범위를 제공해서 범위 안에 캐릭터가 들어가면 속도를 줄이도록 한다.
-
radius 변수가 범위이다.
-
timeToTarget = 0.25는 0.25초만에 타깃에 도착하도록 설정한 것이다. 이 변수가 커지면 그만큼 속도는 감소한다.
-
만약 캐릭터가 radius 안에 들어가 있으면 None을 return한다.
-
속도가 너무 빠를 땐 clipping 해준다.
✔️ Wandering 알고리즘
wandering은 maxSpeed로 캐릭터의 방향을 향해 움직인다.
이 알고리즘은 캐릭터의 방향을 바꾸어 준다.
3️⃣ Steering Behaviors
Steering Behaviors는 이전 movement 알고리즘에 속도와 회전을 더함으로써 확장한다.
Steering Behaviors의 variable matching은 각 요소에 대해 개별 매칭 알고리즘을 사용한 다음, 나중에 올바른 방식으로 이들을 결합한다.
이전 kinematic에서는 update에서 velocity가 maxSpeed보다 커지는지 확인하고 clipping하는 작업을 하지 않았는데 해주게 된다.
✔️ Seek 알고리즘
타깃을 향해 가능한 빨리 갈 수 있는 방향을 찾는다.
Flee 알고리즘은 위와 마찬가지로 빼기 방향을 반대로 해서 구현한다.
✔️ Arrive 알고리즘
위와 마찬가지로 overshoot이 발생한다.
이번엔 2개의 범위를 사용한다. 도착을 인정하는 반지름과 감속시키는 반지름이다. 도착 인정 반지름은 속도를 0으로 만든다.
감속시키는 반지름은 거리에따라 목표 속도에 맞춰 속도를 보간한다.
이 처럼 반지름을 2개 선언해두었다.
필기에는 이 시간안에 도착하도록이라 했는데 이것이 아니라 이 시간안에 목표 속도에 도달하는 것이다.
✔️ Align 알고리즘
캐릭터의 방향과 타깃의 방향을 맞추는 알고리즘이다. 위치와 속도는 고려하지 않는다.
방향은 2 radian마다 반복되어서 단순히 캐릭터의 방향에서 타깃의 방향을 빼는 것으론 충분하지 않다.
결과를 범위로 바꿔줘야한다.
Align 클래스
필기한 그림에서는 시계방향으로 각을 표시해두었는데 이거 반시계방향으로 생각하면 코드 이해된다.
✔️ Velocity matching 알고리즘
군집행동 등의 알고리즘을 구현할 때 유용하다.
✔️ Wandering 알고리즘
키네마틱 (kinematic wander)에서는, 매번 실행될 때마다 방황 방향을 무작위 값으로 약간 변화시킴
(캐릭터의 회전이 불규칙함)
캐릭터 주변에 목표가 제한되는 원이 있음
행동이 실행될 때마다, 무작위 값만큼 목표를 원 위에서 약간 이동시킴
이후 캐릭터는 그 목표를 향해 이동함 seek
✔️ Path following 알고리즘
- 현재 위치에서 경로위 가장 가까운 점을 찾고 d 만큼 이동
- 캐릭터의 예측 이동 방향에 점을 찍고 1번 반복
-> 경로가 커브이거나 복잡하다면, 3번 그림처럼 생략되는 문제가 발생할 수 있음
✔️ Collision avoidance 알고리즘
그림에서 저 각도안에 들어온 캐릭터를 회피한다.
만약 각도안에 여러 캐릭터가 있다면?
- 각도안에 있는 모든 캐릭터의 속도와 위치의 평균을 구한다.
- 가까운 캐릭터만 고려하고 나머지는 무시한다.
✔️ Panic
실제로 충돌하지는 않는데 회피 대상으로 인식한다. 즉, 회피하지 않아도 되는데 회피하는 상황을 말한다.
✔️ Evasive action
단순히 경로가 교차하는지만 봐서는 캐릭터들이 충돌할지를 알 수 없다. 대신, 두 캐릭터가 가장 가까워지는 순간을 찾아야 하고, 그 순간의 거리(분리 거리)를 계산하여 충돌 여부를 판단해야 한다.
✔️ Obstacle and wall avoidance 알고리즘
-
움직이는 캐릭터는 자신의 이동 방향으로 하나 이상의 레이(ray) 를 쏨
-
이 레이들이 장애물과 충돌하면, 충돌을 피할 수 있는 목표 지점(target) 이 생성되고
캐릭터는 해당 목표를 향해 기본적인 seek 행동을 수행함 -
일반적으로 레이는 무한하지 않음 (길이가 제한됨)
-
충돌 지점(collision point) 과 법선(normal) 정보를 사용함
avoidDistance는 충돌 거리가 아니라 회피 거리이다.
ray를 쏘는 여러 방법
위 처럼 single ray는 코너 감지를 잘 못한다. 따라서 ray를 여러개 쏘도록 한다.
Central ray with whiskers 방식은 또 좁은 통로에서는 좋지 않다.
parallel 같은 거는 또 위처럼 Corner에 갇히는 문제가 생길 수도 있다.
위처럼 각각에 맞는 ray를 쏘는 방식이 있다.
그래서 여러 ray 방식을 이용하거나 코너 트랩을 회피하는 코드(충돌하면 ray 1개 제거 등)을 작성한다.
