Boids 알고리즘(군집 이동 알고리즘)

Boids 알고리즘은 크레이그 레이놀즈(Craig Reynolds)에 의해 개발된 인공 생명 프로그램이다.

Boids 규칙

Boids 알고리즘에는 3가지의 규칙이 있고, 이 규칙들이 조화를 이루어 특색있는 움직임을 만들어낸다.

1. Cohesion (응집력)

• 설명
  이웃들의 중간 위치를 찾고 그곳을 향해 이동하는 규칙이다.
  범위 내의 이웃들의 평균 벡터 값을 구하면 이웃들의 중간 위치로 가는 방향이 나온다.

• 코드

private Vector3 CalculateCohesion()
{
    Vector3 cohesionDirection = Vector3.zero;

    if(nearNeighbors.Count > 0)
    {
        for(int i = 0; i < nearNeighbors.Count; ++i)
        {
            cohesionDirection += nearNeighbors[i].transform.position - this.transform.position;
        }
        cohesionDirection /= nearNeighbors.Count;
        cohesionDirection.Normalize();
    }
    return cohesionDirection;
}

• 적용 결과
  

2. Alignment (정렬)

• 설명
  이웃들의 평균 방향으로 이동하는 규칙이다.
  범위 내의 이웃들의 진행 방향 벡터를 더한 후에 평균을 내주면 평균 방향을 구할 수 있다.

• 코드

private Vector3 CalculateAlignment() 
{
    Vector3 alignmentDirection = transform.forward;

    if (nearNeighbors.Count > 0)
    {
        for (int i = 0; i < nearNeighbors.Count; ++i)
        {
            alignmentDirection += nearNeighbors[i].transform.forward;
            //alignmentDirection += nearNeighbors[i].GetComponent<Boid>().velocity;
        }
        alignmentDirection /= nearNeighbors.Count;
        alignmentDirection.Normalize();
    }
    return alignmentDirection;
}

• 적용 결과
  어느 순간 하나가 된다.
  이 문제는 "분리"규칙이 해결해준다.

3. Separation (분리)

• 설명
  이웃들에게서 벗어나는 규칙이다.
  "나(벡터) - 이웃(벡터)"를 계산하면 이웃 위치에서 내 위치로 오는 벡터가 나온다.
  범위 안에 있는 이웃에 대하여 "나(벡터) - 이웃(벡터)"를 계산하고 더해주면 벗어나는 방향을 구할 수 있다.

• 코드

private Vector3 CalculateSeparation()
{
    Vector3 separationDirection = Vector3.zero;

    if(nearNeighbors.Count > 0)
    {
        for(int i = 0; i < nearNeighbors.Count; ++i)
        {
            separationDirection += (this.transform.position - nearNeighbors[i].transform.position); 
        }

        separationDirection.Normalize();
    }

    return separationDirection;
}

• 적용 결과
  깜빡하고 gif 촬영을 하지 않았다..

결과물

3가지의 규칙을 모두 적용하고 이동 범위를 제한하였다.
꽤 물고기 같은 모습을 보여준다.

전체 코드

각 객체에 붙이는 스크립트

using System.Collections;
using System.Collections.Generic;
using Unity.VisualScripting;
using UnityEngine;
using UnityEngine.TestTools;

public class Boid : MonoBehaviour
{
    [Header("Neighbor")]
    List<GameObject> nearNeighbors = new List<GameObject>();

    [Header("MoveInform")]
    [SerializeField] private Vector3 velocity; 

    BoidManager spawner;

    [Header("TEST")]
    [SerializeField] private int neighborCount = 0;

    void Start()
    {
        Init();
    }


    public void Init()
    {
        spawner = BoidManager.Instance;
        velocity = transform.forward * spawner.maxSpeed;


        //start coroutine
    }


    void Update()
    {
        FindNeighbors();

        velocity += CalculateCohesion() * spawner.cohesionWeight;
        velocity += CalculateAlignment() * spawner.alignmentWeight;
        velocity += CalculateSeparation() * spawner.separationWeight;
        LimitMoveRadius();

        if (velocity.magnitude > spawner.maxSpeed) // prevent infinite accelation
            velocity = velocity.normalized * spawner.maxSpeed;

        this.transform.position += velocity * Time.deltaTime; // 가속도
        this.transform.rotation = Quaternion.LookRotation(velocity);
    }

    private void FindNeighbors()
    {
        nearNeighbors.Clear();

        foreach (GameObject neighbor in spawner.Boids) // 전체 이웃 탐색
        {
            if (nearNeighbors.Count >= spawner.maxNeighbors)
                return;
            
            if (neighbor == this.gameObject)
            {
                Debug.Log("Pass, because neighbor is me");
                continue;
            }

            Vector3 diff = neighbor.transform.position - this.transform.position;

            if (diff.sqrMagnitude < spawner.neighborDistance * spawner.neighborDistance) // 범위 내 이웃만 남기기
            {
                nearNeighbors.Add(neighbor);
            }
        }

        neighborCount = nearNeighbors.Count;
        Debug.Log(neighborCount);
    }


    #region Cohesion 계산 메서드
    private Vector3 CalculateCohesion()
    {
        Vector3 cohesionDirection = Vector3.zero;

        if(nearNeighbors.Count > 0)
        {
            for(int i = 0; i < nearNeighbors.Count; ++i)
            {
                cohesionDirection += nearNeighbors[i].transform.position - this.transform.position;
            }
            cohesionDirection /= nearNeighbors.Count;
            cohesionDirection.Normalize();
        }
        return cohesionDirection;
    }
    #endregion


    #region Alignment 계산 메서드
    private Vector3 CalculateAlignment() 
    {
        Vector3 alignmentDirection = transform.forward;

        if (nearNeighbors.Count > 0)
        {
            for (int i = 0; i < nearNeighbors.Count; ++i)
            {
                alignmentDirection += nearNeighbors[i].transform.forward;
                //alignmentDirection += nearNeighbors[i].GetComponent<Boid>().velocity;
            }
            alignmentDirection /= nearNeighbors.Count;
            alignmentDirection.Normalize();
        }
        return alignmentDirection;
    }
    #endregion


    #region Separation 계산 메서드
    private Vector3 CalculateSeparation()
    {
        Vector3 separationDirection = Vector3.zero;

        if(nearNeighbors.Count > 0)
        {
            for(int i = 0; i < nearNeighbors.Count; ++i)
            {
                separationDirection += (this.transform.position - nearNeighbors[i].transform.position);
            }

            separationDirection /= nearNeighbors.Count;
            separationDirection.Normalize();
        }

        return separationDirection;
    }
    #endregion


    private void LimitMoveRadius()
    {
        if (spawner.moveRadiusRange < this.transform.position.magnitude)
        {
            velocity +=
                (this.transform.position - Vector3.zero).normalized *
                (spawner.moveRadiusRange - (this.transform.position - Vector3.zero).magnitude) *
                spawner.boundaryForce *
                Time.deltaTime;
            // 원점->boid 방향 x -(boid가 벗어난 정도) x 힘 x 델타타임
        }
    }
}

객체 생성 스포너

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class BoidManager : MonoBehaviour
{
    public static BoidManager Instance;

    public GameObject prefab;

    [Header("Init")]
    public float InstantiateRadius;
    public int number;

    public List<GameObject> Boids = new List<GameObject>();

    [Header("MoveManage")]
    public float cohesionWeight = 1.0f;     // 3규칙 가중치
    public float alignmentWeight = 1.0f;
    public float separationWeight = 1.0f;
    public float moveRadiusRange = 5.0f;    // 활동 범위 반지름
    public float boundaryForce = 3.5f;      // 범위 내로 돌아가게 하는 힘
    public float maxSpeed = 2.0f;
    public float neighborDistance = 3.0f;   // 이웃 탐색 범위
    public float maxNeighbors = 50;         // 이웃 탐색 수 제한

    private void Awake()
    {
        Instance = this;

        for (int i = 0; i < number; ++i)
        {
            Boids.Add(Instantiate(prefab, this.transform.position + Random.insideUnitSphere * InstantiateRadius, Random.rotation));
        }
    }
}

성능 문제

Boids 알고리즘은 모든 객체가 주변 이웃과의 위치를 계산하다보니 성능면에서 굉장히 좋지 못하다.

내가 따라한 튜토리얼 영상에서는 일단 기능의 완성과 알고리즘 이해가 우선이었기에 수정해줄 부분이 있었다.

개선한 점

• Find
  튜토리얼 영상에서는 이웃을 찾는 것에 Find 함수를 사용하였다. 이는 엄청난 성능 저하를 가져왔다.
  Find 함수의 성능 저하는 말로만 들어봤지 직접 경험한 것은 이것이 처음이었다.
  Find를 사용하지 않고 스포너에서 리스트로 관리하도록 바꾸었다.
• where
  Linq의 where또한
• magnitude
  magnitude는 벡터의 크기(길이)를 반환한다.
  보통 벡터.magnitude < 비교할 길이 이런 식으로 많이 쓰인다.
  하지만 magnitude는 제곱근 연산을 추가로 하기에 성능저하가 어느정도 생긴다는 글을 보았고,
  벡터.sqrMagnitude < 비교할 길이 * 비교할 길이와 같은 형태로 바꿔주었다.

개선할 점

• 코루틴
  지금 매 프레임마다 이웃을 찾아서 근처의 이웃을 찾는데, 이 연산을 코루틴으로 0.1~0.5초 정도로 줄여버릴까 한다.
  이렇게 해도 드라마틱하지 않으면 응집,정렬,분리 함수를 어떻게든 연산을 줄여볼까 생각 중이다.

---

참고

https://youtu.be/_d8M3Y-hiUs?si=GWo-VBTjUwCweOVP
영상을 보고 따라 만들면서 Boids 알고리즘을 쉽게 이해할 수 있었다.

https://en.wikipedia.org/wiki/Boids
위키피디아

https://github.com/BongYunnong/CodingExpress/blob/main/Assets/02.Script/Boids/BoidUnit.cs#L197
코드의 구조를 많이 참고했다.