Game AI - Steering Behaviors (3)

2021.08.07 - [Game AI] - Game AI - Steering Behaviors (2)

Game AI - Steering Behaviors (2)

 

Path Following (길 따라가기)

 

이 행동을 이해하기 위해선 우선 매개변수를 사용하는 곡선에 대해 알 필요가 있다.

2021.07.11 - [이론] - 곡선(Curve) & 스플라인(Spline)

곡선(Curve) & 스플라인(Spline)

 

Path Following은 전체 경로를 타겟으로 삼는 steering behavior이다. 이 행동은 다음의 두 가지 스텝으로 이뤄진다

 

1. 경로 상에 가상의 타겟을 설정한다.
2. 가상의 타겟을 대상으로 Seek를 수행한다.

가상의 타겟을 정하기 위해서는 한 점과 가장 가까운 곡선 위의 점을 알아내야 한다. 책에서는 찾아보라고 하고 넘어갔는데 내가 개인적으로 찾은 방법은 아래와 같다.

 

2021.09.04 - [수학] - 한 점과 가장 가까운 곡선 위의 점 구하기

한 점과 가장 가까운 곡선 위의 점 구하기

 

가상의 타겟을 만드는 법도 두 가지 스텝으로 이뤄진다.

 

1. 현재 캐릭터의 위치와 가장 가까운 경로상의 위치를 찾는다.
2. 해당 위치보다 더 멀리있는 경로상의 위치를 가상의 타겟이 있는 위치로 한다.

 

 

 

가상의 타겟을 만들 때 캐릭터의 미래 위치를 이용할 수 있다.

 

1. 가까운 미래의 플레이어 위치를 정한다.
2. 그 위치와 가장 가까운 경로상의 위치를 정한다. 이것을 후보 위치로 정한다.
3. 만약 이전 프레임의 가상의 타겟 위치보다 후보의 위치가 더 멀다면 후보 위치가 새로운 가상의 타겟의 위치가 된다.

 

그러나 이 방법은 코너에서 경로를 이탈할 수 있다. 

 

 

 

가장 가까운 점이 여러개인 경우

가장 가까운 곡선위의 위치가 여러 개일 때 문제가 발생할 수 있는데, 이 경우 원래 위치와 가까운 paramter를 구한다.

 

 

 

Path Following은 경로 위의 가상의 타겟을 만드는 것이 전체 성능에 지배적이다.

 

 

 

Separation (분리)

분리 행동은 군중 시뮬레이션에서 같은 방향으로 움직이는 대상들에게 자주 쓰인다. 만약 방향이 다른 경우 충돌 회피 행동을 사용해야 한다.

 

분리 행동은 다른 대상이 어느 선보다 가까히 오게 된다면 대상으로부터 멀어지는 행동을 하는 것이다. 이때 멀어지려고 하는 힘은 보통 거리의 제곱에 반비례하도록 설정한다.

 

만약 피하려는 대상이 여러명일 경우 모든 steering값을 더한다.

 

만약 객체가 수백 개가 있는 경우 매번 모든 객체를 대상으로 충분히 가까운지 아닌지 판단하는 건 매우 비효율적일 수 있다. 따라서 Multi-resolution map, quad or octree, binary space partition(BST)등을 사용하여 비교할 대상을 적절히 줄여야 한다. 

 

분리 행동의 경우 단독으로 사용되는 일은 거의 없고 다른 행동들과 조합하여 사용한다.

 

 

충돌 회피

 

충돌 회피는 분리와 달리 서로 접근하는 방향에 있는 객체를 피하는 행동이다. 

 

우선 단순한 방법을 생각해보자. 캐릭터 앞에 원뿔모양의 범위를 두고 그 안에 다른 객체가 들어오면 회피한다. 

 

이 경우 캐릭터의 이동방향(Orientation)과 타겟을 향하는 방향(targetDirection)의 각도가 원뿔 각도의 절반보다 큰지를 체크하면 된다. 

 

이때 $threshold = \cos{\theta}$를 미리 구해둔 뒤

DotProduct(orientationVector, targetDirection) > threshold

위 조건을 비교하면 된다. (orientation과 targetDirection의 크기는 1)

 

 

 

그러나 이 방법은 다음과 같은 오류가 있다.

 

 

 

 

위 문제를 해결하기 위해서는 속도를 이용하여 미래에 대상과 가장 가까워졌을 때를 고려하면 된다. 만약 내가 대상과 가장 가까워졌을 때 거리가 일정 반경보다 크다면 굳이 회피할 필요가 없을 것이다.

 

 

참고로 시작할 때 이미 충돌했는지를 체크하면 좋다. 

 

만약 여러 대상이 원뿔 안에 들어온 경우 가장 먼저 만나게 되는 대상을 먼저 회피하는 방법을 선택할 수 있다. 

 

 

 

장애물(벽) 회피

충돌 회피 행동은 피할 대상을 점 혹은 구로 간주한다. 그러나 구나 점이 아닌 장애물들은 어떻게 피해야 할까? 이 경우 보통 raycast를 이용한다. 이를 이용해서 ray가 부딪힌 곳과 장애물의 normalized 된 수선 벡터를 구한 뒤 여기에 avoidDistance만큼을 곱해준 위치에 가상의 타겟을 생성해서 해당 타겟을 항해 가도록(Seek) 만들면 된다.

 

 

그런데 ray를 하나만 쏘는 경우 아래 그림처럼 실제로는 부딪히게 되나 감지하지 못하는 경우가 생길 수 있다.

 

이 경우 여러 개의 ray를 쏘아 해결할 수 있다.

 

그러나 raycast는 꽤 비용이 드는 연산이므로 너무 많은 수의 ray를 쏘면 퍼포먼스의 저하가 발생할 것이다.

 

이런 방법들도 한 가지 문제에 봉착하는데 바로 코너 트랩 문제이다.

 

코너 트랩

 

위 그림과 같은 벽의 모서리가 있다. 그리고 2개의 ray를 쏘는 방법을 사용했다고 하자. 위 캐릭터는 성공적으로 벽을 피할 수 있을까?

 

위 그림에서 캐릭터의 왼쪽 ray가 벽과 충돌하고, 캐릭터는 왼쪽으로 이동하게 된다. 그런데 왼쪽으로 조금 이동하고 나면 다시 오른쪽 ray가 벽과 충돌하게 되고 캐릭터는 오른쪽으로 이동하게 된다. 이렇게 캐릭터는 왼쪽, 오른쪽, 왼쪽, 오른쪽, ... 이렇게 이동하다가 결국 벽에 부딪힐 것이다.

 

만약 두 ray사이의 각도가 충분히 크다면 위와 같은 문제는 발생하지 않겠지만 캐릭터가 좁은 통로를 지나가는데 문제가 생긴다.

 

이 경우 두 ray의 각도를 동적으로 조절하면 어느정도 문제를 해결할 수 있다. 만약 캐릭터가 충돌이 탐지되지 않은 상태라면 각도가 좁아진다. 반면에 충돌을 탐지했다면 점점 각도가 넓어지고 모서리를 피할 수 있게 된다.

 

저자의 말에 따르면 이처럼 적응형으로 각도를 조절하는 짧은 ray 두 개와 보다 긴 중앙 ray를 사용하는 방법이 현재까지는 가장 실용적인 방법이라고 한다.

 

 

 

참고로 가장 이상적인 해결법은 ray가 아니라 플레이어 모양의 객체를 쏘는 것이다. 

 

 

그러나 위와 같은방법은 ray를 쏘는 것보다 훨씬 느리기 때문에 steering behaviour에서 사용하기엔 부적합할 수 있다.

 

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