AI 스케줄링

AI Scheduling

---

 

게임이 균등한 프레임을 뽑기 위해서는 다양한 작업들이 제한된 시간 내에 수행되어야 한다.

AI역시 마찬가지인데, 이를 제한된 시간 내에 처리하기 위해서는 다음의 3가지 요소가 필요하다.

 

1. AI 작업들에 적절한 시간을 분배하는 것
2. AI 작업을 여러 프레임에 걸쳐서 수행할 수 있는 알고리즘
3. AI 작업간에 우선순위

 

 

Frequency

작업을 스케줄링하는 가장 간단한 방법 중 하나는 빈도(frequency)를 이용하는 것이다. 

 

스케줄러는 매 프레임마다 어떤 작업을 수행할 것인지를 결정한다. 이때 작업들은 각자 frequency를 가지고 있으며 스케줄러는 이 값을 이용하여 작업을 수행한다. 가령 어떤 작업의 frequency가 5프레임이라면, 스케줄러는 해당 작업을 5프레임마다 한 번 수행한다. 이는 모듈러 연산등을 통해 수행될 수 있다.

 

이런 방법은 뭉침(clumping) 현상이 발생할 수 있는데, 가령 작업 A,B,C의 빈도가 각각 2,3,6프레임당 한 번이라고 해보자.

 

 

그렇다면 위와 같이 특정 프레임에 작업이 몰리게 된다.

 

이를 완화하기 위해서는 작업의 빈도가 서로소가 되는 것이 좋다.

 

 

Phase

 

작업의 빈도를 서로소로 설정하는 것은 뭉침을 완화해줄 수 있지만 완전히 해결은 할 수 없다. 여기에 Phase라는 개념을 더해주면 뭉침을 더 완화할 수 있다. 

 

Phase는 일종의 offset으로 빈도가 실행되는 시점을 offset만큼 늦춘다. 

 

void update()
{
    ++_frame;
    
    //... 
    
    foreach(auto task : tasks)
    {
        if((_frame + task.phase) % task.frequecny)
            task.Run();
    }
}

 

이러면 모든 작업의 빈도가 같아도 균등하게 작업을 배분할 수 있다.

 

만약 모든 작업의 빈도가 같다면, 따로 phase를 더하는 것 보다 프레임별로 array를 할당하여 하나씩 집어 넣는 것이 훨씬 빠를 것이다.

 

그렇다면 좋은 phase 값은 어떻게 찾아야 할까? 좋은 phase값이란 각 프레임에 수행되는 작업의 갯수의 분포가 적고 최대와 최소값이 평균에 가까운 것이다. 이를 통계적으로 찾아야 하지만 쉽지 않은 일이다.

 

이를 찾는 다른 방법은 wright'method이다. 이 방법에서는 우선 일정 프레임 길이 내에서 모든 작업들을 dry하게 수행하여 각 프레임별로 몇 개의 작업을 수행했는지 계산한다. 그 다음에 가장 적은 작업이 수행된 프레임으로 phase를 맞춰줄 수 있다. 이 때, dry-run을 수행할 프레임의 길이는 모든 작업들의 최소공배수가 되는게 이상적이다. 만약 그렇지 않다면 뭉침 현상이 존재할 수 있다.

 

 

로드(load) 밸런싱 스케줄러

로드 밸런싱 스케줄러는 자신에게 주어진 시간이 얼마인지 알고 이를 분배하는 스케줄러이다. 스케줄러는 남은 시간을 작업들에 적당히 분배해서 준다. 그 후에는 작업들이 알아서 잘 해줄것이라 믿는다. 따라서 작업들이 주어진 시간안에 잘 동작하도록 구현하는 것이 중요하다.

 

 

계층적(hierachical) 스케줄링

계층적 스케줄링 시스템에서, 한 스케줄링 시스템은 다른 스케줄링 시스템에 의해서 실행이 가능하다. 즉, 스케줄링 시스템을 하나의 AI작업처럼 취급하여 시간을 분배해주면, 다시 시간을 분배받은 스케줄링 시스템이 하위 작업에 시간을 분배한다. 

 

만약 캐릭터가 수행해야 하는 여러 AI작업 (이동,길찾기,전략 등)이 업데이트 되어야 한다면, 이를 하나의 계층적 스케줄링 시스템으로 구성하여 하위 AI 작업들이 골고루 실행되도록 할 수 있다.

 

 

우선순위 스케줄링

작업(혹은 하위 스케줄링 시스템)마다 우선순위를 두어서, 우선순위만큼 시간을 할당해주는 것. 그러나 이렇게 되면 OS의 스케줄링과 비슷한 우선순위 관련 문제를 갖는다. (기아상태 등) 이를 해결해주는 알고리즘을 OS를 참고하여 구현할 수 있겠지만, 게임의 스케줄러에서 그정도까지 하는 경우는 드물다.

 

 

기타

• 빈도의 개념이 없이 우선순위 만으로 작업을 분배해줄 수 있다.
• 실행되는 작업 자체가 자신이 필요한 시간을 요청하는 방법도 가능하다. 이 경우, 요청한 작업 시간이 남은 시간보다 길다면 다음 프레임에 실행시킨다.