군집 이동(Flocking) 알고리즘: 미니언 무리를 자연스럽게 움직이는 법

왜 단순 추적만으로는 부족할까

여러 미니언이 같은 플레이어를 향해 MoveTowards로 이동하면 한 점에 겹치거나 서로 밀어내며 덜덜 떨기 쉽다. 경로 탐색은 큰 이동 경로를 정하는 데 유용하지만 가까운 개체 사이의 자연스러운 간격까지 해결해 주지는 않는다.

군집 이동은 각 미니언이 주변 이웃의 상태를 보고 조향 벡터를 계산하는 방식이다. 중앙에서 대형을 직접 지정하지 않아도 무리가 하나의 생물처럼 움직이는 모습을 만들 수 있다.

플레이어를 향해 이동하면서 서로 간격을 유지하는 미니언 군집

군집을 만드는 세 가지 규칙

대표적인 Flocking 알고리즘은 다음 세 규칙의 가중 합으로 움직임을 결정한다.

Separation: 너무 가까운 이웃에게서 멀어진다

Separation은 개체가 겹치는 문제를 막는 규칙이다. 가까운 이웃일수록 더 강하게 반대 방향으로 힘을 준다.

S = \sum_{i=1}^{n}\frac{p-p_i}{\max(\lVert p-p_i\rVert^2, \epsilon)}

여기서 $p$ 는 현재 미니언의 위치이고 $p_i$ 는 이웃의 위치다. 거리를 제곱한 값으로 나누면 아주 가까운 이웃을 우선해서 피할 수 있다. 다만 힘이 지나치게 커질 수 있으므로 최종 조향 벡터의 크기는 제한하는 편이 안전하다.

Alignment: 이웃과 비슷한 방향으로 움직인다

Alignment는 주변 미니언의 평균 속도를 따라가게 한다. 이 규칙이 없으면 같은 목표를 향하더라도 개체마다 방향 전환이 제각각이라 무리가 흩어져 보일 수 있다.

A = \frac{1}{n}\sum_{i=1}^{n}v_i - v

$v_i$ 는 이웃의 속도이고 $v$ 는 현재 미니언의 속도다. 평균 속도 자체가 아니라 현재 속도와의 차이를 사용하면 자연스럽게 방향을 맞춘다.

Cohesion: 무리의 중심 쪽으로 모인다

Cohesion은 이웃의 평균 위치를 향하도록 만든다. Separation만 적용하면 미니언이 서로 피하다가 무리가 넓게 퍼질 수 있으므로 두 규칙은 보통 함께 사용한다.

C = \left(\frac{1}{n}\sum_{i=1}^{n}p_i\right)-p

세 힘에 목표 추적 벡터까지 더하면 최종 조향 벡터를 만들 수 있다.

F = w_sS + w_aA + w_cC + w_tT

가중치 $w_s$ , $w_a$ , $w_c$ , $w_t$ 는 게임의 연출에 맞춰 조절한다. 근접 전투 미니언이라면 Separation을 높여 뭉침을 줄이고 날아다니는 적 무리라면 Alignment와 Cohesion을 높여 흐르는 듯한 움직임을 만들 수 있다.

flowchart LR
    N[현재 미니언] --> Q[주변 이웃 검색]
    Q --> S[Separation 계산]
    Q --> A[Alignment 계산]
    Q --> C[Cohesion 계산]
    T[추적 대상] --> G[목표 조향 계산]
    S --> W[가중 합과 크기 제한]
    A --> W
    C --> W
    G --> W
    W --> V[속도와 위치 갱신]

Unity 구현 예제

아래 예제는 평면에서 움직이는 간단한 미니언 컴포넌트다. Physics.OverlapSphereNonAlloc으로 일정 반경 안의 이웃을 찾고 세 조향 규칙과 목표 추적을 합산한다.

using UnityEngine;

public class FlockingMinion : MonoBehaviour
{
    [Header("References")]
    [SerializeField] private Transform target;
    [SerializeField] private LayerMask minionLayer;

    [Header("Movement")]
    [SerializeField] private float maxSpeed = 4f;
    [SerializeField] private float maxSteering = 10f;
    [SerializeField] private float neighborRadius = 3f;

    [Header("Weights")]
    [SerializeField] private float separationWeight = 2.5f;
    [SerializeField] private float alignmentWeight = 1f;
    [SerializeField] private float cohesionWeight = 0.8f;
    [SerializeField] private float targetWeight = 1.5f;

    private readonly Collider[] neighbors = new Collider[32];
    private Vector3 velocity;

    private void Update()
    {
        Vector3 steering = CalculateFlockingForce();
        steering += Seek(target.position) * targetWeight;
        steering = Vector3.ClampMagnitude(steering, maxSteering);

        velocity = Vector3.ClampMagnitude(
            velocity + steering * Time.deltaTime,
            maxSpeed);

        transform.position += velocity * Time.deltaTime;

        if (velocity.sqrMagnitude > 0.001f)
        {
            transform.forward = Vector3.Slerp(
                transform.forward,
                velocity.normalized,
                12f * Time.deltaTime);
        }
    }

    private Vector3 CalculateFlockingForce()
    {
        int count = Physics.OverlapSphereNonAlloc(
            transform.position,
            neighborRadius,
            neighbors,
            minionLayer);

        Vector3 separation = Vector3.zero;
        Vector3 averageVelocity = Vector3.zero;
        Vector3 averagePosition = Vector3.zero;
        int neighborCount = 0;

        for (int i = 0; i < count; i++)
        {
            FlockingMinion other = neighbors[i].GetComponent<FlockingMinion>();
            if (other == null || other == this)
                continue;

            Vector3 offset = transform.position - other.transform.position;
            float distanceSq = offset.sqrMagnitude;

            if (distanceSq > 0.0001f)
                separation += offset / distanceSq;

            averageVelocity += other.velocity;
            averagePosition += other.transform.position;
            neighborCount++;
        }

        if (neighborCount == 0)
            return Vector3.zero;

        averageVelocity /= neighborCount;
        averagePosition /= neighborCount;

        Vector3 alignment = averageVelocity - velocity;
        Vector3 cohesion = averagePosition - transform.position;

        return separation * separationWeight
             + alignment * alignmentWeight
             + cohesion * cohesionWeight;
    }

    private Vector3 Seek(Vector3 destination)
    {
        Vector3 desiredVelocity = destination - transform.position;
        desiredVelocity.y = 0f;

        if (desiredVelocity.sqrMagnitude < 0.001f)
            return -velocity;

        desiredVelocity = desiredVelocity.normalized * maxSpeed;
        return desiredVelocity - velocity;
    }
}

이 스크립트를 사용하는 모든 미니언에는 Collider를 추가하고 전용 레이어를 지정한다. minionLayer에는 그 레이어만 포함해야 이웃 검색 결과에 지형이나 플레이어가 섞이지 않는다.

자연스럽게 보이게 만드는 조정 기준

Flocking은 정답 가중치가 있는 알고리즘이 아니다. 미니언의 역할과 카메라 거리, 이동 공간에 따라 값을 조절해야 한다.

미니언이 겹친다면 separationWeight 또는 neighborRadius를 올린다.
무리가 너무 넓게 퍼진다면 cohesionWeight를 올린다.
방향이 산만하다면 alignmentWeight를 조금 올린다.
목표 주변에서 떨린다면 목표에 가까워질수록 targetWeight를 낮추거나 도착 반경을 둔다.
장애물이 있다면 Flocking과 별도로 회피 조향이나 NavMesh 경로를 결합한다.

장애물을 돌아 목표로 향하면서 군집 형태를 유지하는 미니언들

특히 Separation을 너무 강하게 주면 미니언이 서로 피하는 과정에서 진동할 수 있다. 이를 줄이려면 조향력과 최고 속도를 제한하고 회전에는 Slerp처럼 시간에 따른 보간을 적용한다. 필요하다면 속도 변화량에도 별도의 상한을 둔다.

성능에서 가장 중요한 이웃 검색

군집 이동의 비용은 규칙 계산보다 이웃을 찾는 과정에서 커지는 경우가 많다. 모든 미니언이 다른 모든 미니언을 검사하면 개체 수를 $N$ 이라고 할 때 비용은 대략 $O(N^2)$ 가 된다.

수십 개 수준이라면 간단한 반경 검색만으로도 충분할 수 있다. 수백 개 이상을 다룬다면 다음 방법을 검토한다.

공간 분할을 적용한다

월드를 일정 크기의 셀로 나누고 각 미니언을 현재 셀에 등록한다. 이웃 검색은 자기 셀과 인접 셀만 검사하므로 멀리 떨어진 개체를 불필요하게 확인하지 않는다. 균일 격자, 공간 해시, 쿼드트리 같은 구조가 여기에 해당한다.

매 프레임 모두 계산하지 않는다

모든 미니언이 매 프레임 이웃을 갱신할 필요는 없다. 프레임마다 일부 미니언만 계산하거나 0.1초 간격으로 이웃 정보를 갱신해도, 느리게 움직이는 군집에서는 눈에 띄는 차이가 적다.

할당을 피한다

예제처럼 OverlapSphereNonAlloc을 사용하면 매 프레임 배열을 새로 만들지 않는다. 대규모 군집에서는 GetComponent 호출도 비용이 될 수 있으므로 Collider와 미니언 컴포넌트의 연결 정보를 캐싱하는 방식도 고려할 수 있다.

디버깅할 때 확인할 항목

군집 이동이 이상하면 최종 속도만 보지 말고 각 규칙의 벡터를 따로 그려 보는 것이 좋다. Debug.DrawRay로 Separation, Alignment, Cohesion, 목표 추적 벡터를 다른 색으로 표시하면 어떤 힘이 움직임을 지배하는지 빠르게 확인할 수 있다.

또한 물리 충돌로 미니언을 실제로 밀어낼지 결정해야 한다. Flocking의 Separation은 조향 수준의 간격 유지일 뿐, 빠르게 움직이는 Rigidbody끼리의 관통을 완전히 막아 주지는 않는다. 충돌이 게임 규칙에 중요하다면 Rigidbody와 Collider 설정을 별도로 설계하고 단순한 연출용 무리라면 물리 충돌을 최소화해 계산 비용을 줄이는 편이 낫다.

마무리

Flocking은 개체별로 단순한 지역 규칙만 계산하지만 결과적으로 무리다운 움직임을 만든다. 먼저 Separation과 목표 추적만 적용해 겹침 없는 이동을 만든 뒤 Alignment와 Cohesion을 조금씩 더하는 순서가 조정하기 쉽다.

대규모 전투에서는 Flocking을 경로 탐색의 대체재로 보기보다 NavMesh나 웨이포인트가 정한 큰 방향 위에 얹는 근거리 조향 기법으로 사용하면 안정적인 결과를 얻기 좋다.