[유니티 알고리즘] 슬라이딩 윈도우 알고리즘 활용

 

안녕하세요, 오늘은 슬라이딩 윈도우 알고리즘을
 
게임에서 어떻게 활용하면 좋을지에 대해서 포스팅하고자 합니다.

---

오늘의 키워드

• 슬라이딩 윈도우 알고리즘

---

 

슬라이딩 윈도우 알고리즘

 

슬라이딩 윈도우 알고리즘이란 배열 내에서 연속된 구간의 범위를 순회하는 알고리즘 입니다.
 
위 그림처럼 배열에서 연속된 3개의 구간의 합이 가장 큰 부분을 찾는 과정과 같습니다.
 
윈도우 슬라이딩 알고리즘을 사용해야 하는 이유는 바로 시간 복잡도O(n) 이라는 이점이 있기 때문입니다.
 
만약, 윈도우 슬라이딩 알고리즘을 사용하지 않고 직관적으로 코드를 구현한다면 어떤 코드가 나올까요?
 

int maxSum = 0;

for (int i = 0; i < arr.Length - 2; i++)
{
    int sum = 0;
    for (int j = i; j < i + 3; j++)
    {
        sum += arr[j];
    }
    if (sum > maxSum)
    {
        maxSum = sum;
    }
}

 
이와 같이 반복문을 2번 사용하여 O(3n) 의 시간복잡도가 나오게 구현하고 말 것입니다.
 
윈도우 슬라이딩 알고리즘의 경우, 연속된 구간의 윈도우를 구하고 이를 마치 슬라이딩 하듯이 구현합니다.
 
 

int maxSum = 0;
int sum = 0;

// 첫 번째 윈도우 초기화
for (int i = 0; i < 3; i++)
{
    sum += arr[i];
}
maxSum = sum;

// 윈도우 슬라이딩
for (int i = 1; i <= arr.Length - 3; i++)
{
    sum = sum - arr[i - 1] + arr[i + 2];
    if (sum > maxSum)
    {
        maxSum = sum;
    }
}

 
위 코드와 같이 연속된 구간을 유지한 채 시작 부분을 끝 부분으로 이동시키는 방식입니다.

---

 

이 알고리즘을 게임 개발에서는 어떻게 활용하면 좋을까요?
 
DPS 계산
 
MVP 계산
 
적 AI가 일정 간격 플레이어로 부터 피격 횟수를 이용해서 위험도 계산
 
Combo 판정 등
 
슬라이딩 윈도우 기법을 활용해서 다양한 기능을 구현할 수 있다.
 
게임 외에도 채팅 도배 감지 등에서도 사용할 수 있다.
 
이 중 DPS 계산을 구현해보겠습니다.

---

DPS 계산

미리보기

 
 

public class DPSExample : MonoBehaviour
{
    [SerializeField] private TMP_Text dpsText;
    [SerializeField] private Slider dpsSlider;
    [SerializeField] private Button attackButton;
    [SerializeField] private float damage;
    [SerializeField] private float Window = 1f;
    [SerializeField] private float dpsLerpTime = 0.1f;

    private float _displayDPS = 0f;
    private float _totalDamage = 0;
    private float _maxDps = 0;
    private readonly List<(float time, float damage)> _damages = new();


    private void Start()
    {
        attackButton.OnClickAsObservable().Subscribe(OnDamage).AddTo(this);
    }

    private void Update()
    {
        float now = Time.time;

        float removedDamage = 0;

        _damages.RemoveAll(d =>
        {
            bool isExpired = now - d.time > Window;

            if (isExpired)
            {
                removedDamage += d.damage;
            }

            return isExpired;
        });

        _totalDamage -= removedDamage;
        float dps = _totalDamage / Window;
        if(dps > _maxDps)
        {
            _maxDps = dps;
            dpsSlider.maxValue = _maxDps;
        }
        _displayDPS = Mathf.Lerp(_displayDPS, dps, dpsLerpTime * Time.deltaTime);
        dpsSlider.value = _displayDPS;
        dpsText.text = _displayDPS.ToString("N0");
    }

    public void OnDamage(Unit _)
    {
        float now = Time.time;

        _damages.Add((now, damage));
        _totalDamage += damage;
    }
}

 

 
이게 왜 윈도우 슬라이딩 알고리즘인가 생각할 수 있지만,
 
윈도우의 중심이 배열의 Index가 아닌,
 
Time으로 변경되었을 뿐이다.
 
값을 추가하고 시간을 중심으로 Window를 이용한 이전 값을 삭제하는 방식이다.
 
하지만 위 코드는 약간 단점이 있다.
 
RemoveAll을 사용했기 때문이다.
 
 RemoveAll 함수는 배열 내 모든 요소를 탐색하기 때문에 무조건 최소 시간 복잡도O(N)가 나옵니다.
 
시간 복잡도를 낮추기 위해서는 Queue를 활용하는 것이 좋습니다.
 

    private void Update()
    {
        float now = Time.time;

        while(_damages.Count > 0)
        {
            var oldest = _damages.Peek(); // 가장 오래된 데이터를 가져옴

            if (now - oldest.time > Window)
            {
                _totalDamage -= oldest.damage; // 전체 데미지 감소
                _damages.Dequeue(); // Dequeue로 데이터 제거
            }
            else break;
        }

        float dps = _totalDamage / Window;
        if(dps > _maxDps)
        {
            _maxDps = dps;
            dpsSlider.maxValue = _maxDps;
        }
        _displayDPS = Mathf.Lerp(_displayDPS, dps, dpsLerpTime * Time.deltaTime);
        dpsSlider.value = _displayDPS;
        dpsText.text = _displayDPS.ToString("N0");
    }

 

Queue는 먼저 들어온 값을 먼저 내보내는 FIFO 방식이고, 오래된 순의 데이터를 관리하기 좋습니다.
 
이로 인해 최대 시간복잡도O(N)으로 최적화를 할 수 있습니다.
 

---

이상으로 윈도우 슬라이딩 알고리즘에 대해서 포스팅을 마치겠습니다.