[용어] 군중 이동(Flocking/Boids) 알고리즘

1. Flocking(Boids) Algorithm

Flocking Algorithm 또는 Boids Algorithm으로 불리는 이 알고리즘은 복잡한 시스템의 동작을 모방하기 위한 알고리즘으로, 개체 그룹이나 ‘무리’의 움직임을 시뮬레이션하기 위해 개발된 알고리즘이다.

1986년에 컴퓨터 그래픽스 연구자인 크레이그 레이놀즈(Craig Reynolds)가 개발한 알고리즘으로, 새의 무리나 물고기 떼와 같은 집단행동을 시뮬레이션하는 것을 목표로 개발하였다.

Boids는 ‘Bird-oid object’ 그는 각 개체를 ‘Boid’라고 부르는 가상의 새로 표현하였고, 이로부터 Boids라는 이름이 유래되었다.

Flocking의 경우 Flock의 뜻이 무리(떼)를 뜻하며, 결국은 Flocking Algorithm과Boids Algorithm전부 특정 무리의 집단행동을 시뮬레이션하는 같은 알고리즘이다.

이 알고리즘을 통해 특정 무리의 각 개체가 상호 작용하며 자연스러운 동작을 생성하도록 한다.

2. 플로킹 알고리즘의 기본 규칙(Rule)

• 분리(Separation) : 개체는 서로 가까이 다가가지 않도록 한다. Boids들과 충돌하지 않도록 방향을 돌린다.

• 정렬(Alignment) : 개체는 주변 개체들의 방향을 따라 움직인다. Boids들과 같은 방향을 가리키도록 한다.

• 응집(Cohesion) : 개체는 주변 개체들과 함께 떼를 지어 움직이도록 한다. Boids들과 평균 위치로 움직인다.

위의 3가지 규칙을 적용하여 개체들이 움직이는 모습은 집단의 군중 이동을 흉내를 내 자연스러운 모습으로 시뮬레이션이 진행된다.

그 이후에 회피라는 규칙이 추가로 사용되기도 한다.

• 회피(Avoidance) : 개체는 장애물이나 적들에 부딪히지 않도록 방향을 조정한다.

이 규칙을 사용함으로써 개체들은 환경에 존재하는 장애물들을 피하면서 움직일 수 있게 된다.

플로킹 알고리즘을 더욱 복잡한 환경에 적용하려면 이러한 추가적인 규칙 또한 고려해야 한다.

3. 플로킹 알고리즘의 장점

플로킹 알고리즘의 장점으로는 다음과 같은 부분이 있다.

3.1. [ 자연스러운 움직임 ]

플로킹 알고리즘은 개체들이 무리를 이루고, 부딪히지 않으면서도 목표 지점에 도달하는 자연스러운 움직임을 생성한다.

복잡한 움직임을 필요로 하는 게임에서 매우 유용하다.

3.2. [ 유연성 ]

플로킹 알고리즘은 각 개체가 자신의 규칙을 따르므로, 개체 간의 행동이 동적으로 변할 수 있다.

이는 무리의 형태나 움직임을 다양하게 만들 수 있다.

4. 플로킹 알고리즘의 단점

플로킹 알고리즘의 단점으로는 다음과 같은 부분이 있다.

4.1. [ 계산 비용 ]

각 개체가 주변의 다른 개체들과 상호작용을 계산해야 하므로, 개체 수가 많아지면 계산 비용이 많이 증가한다.

따라서 많은 수의 개체를 동시에 시뮬레이션하는 게임에서는 최적화가 필요할 수 있다.

4.2. [ 혼잡한 환경에서의 문제 ]

플로킹 알고리즘은 개체들이 서로 부딪히지 않도록 하는 것이 목표이므로, 혼잡한 환경에서는 개체들이 원활하게 움직이지 못하는 문제가 발생할 수 있다.

5. 플로킹 알고리즘이 적합한 게임

위의 장단점을 고려하면, 플로킹 알고리즘은 주로 큰 개방된 공간에서 다수의 동적 개체들의 움직임을 시뮬레이션하는 게임에 적합하다.

5.1. [ 전략 게임에서의 사용 ]

전략 게임에서는 다수의 유닛을 관리해야 하는 경우가 많다.

이때 플로킹 알고리즘은 유닛들이 자연스럽게 이동하고, 충돌 없이 목표지점까지 도달하는 것을 도와준다.

예를 들자면, 스타크래프트 같은 게임에서 플레이어가 여러 유닛을 선택하고 목표지점을 지정하면, 유닛들은 서로 부딪히지 않으면서도 무리를 이루어 목표지점까지 이동한다.

5.2. [ 생태계 시뮬레이션 ]

게임 내의 동물들이 자연스럽게 행동하는 것을 모델링하는 데 사용된다.

사냥하는 동물들이 무리를 지어 사냥감을 추적하거나, 물고기들이 무리를 지어 움직이는 모습을 플로킹 알고리즘을 통해 구현할 수 있다.

5.3. [ 스포츠 게임 ]

축구 게임에서 선수들이 공을 따라 움직이고, 상대 선수를 피하며 공을 전달하는 모습을 플로킹 알고리즘을 통해 구현할 수도 있다.

5.4. [ 연출 부분 ]

개인적인 생각인데, 밤 필드에서 반딧불을 구현하는 데 써도 좋을 것 같다.

반딧불들이 응집과 분리를 반복하는 과정에서 주인공이나 몬스터라는 특정 오브젝트를 장애물로 인식하여 거리를 두고 피하는 부분에서 활용한다면 아름다운 연출을 할 수 있을 것 같다.

6. 해당 알고리즘의 관련 사용처

다양한 곳에 사용되겠지만, 아래 내용에서도 플로킹 알고리즘이 사용되기도 한다.

6.1. [ 컴퓨터 그래픽 및 애니메이션 ]

플로킹 알고리즘은 비디오 게임, 영화 및 가상 환경에서 사실적인 군중 애니메이션을 시뮬레이션하기 위해 컴퓨터 그래픽에 널리 사용된다.

이는 사람, 동물 또는 차량의 군중을 위한 실제와 같은 움직임을 생성하여 몰입감 있는 경험을 향상하는 데 도움이 된다.

6.2. [ 사회 시뮬레이션 및 행동 연구 ]

혼잡한 공간에서의 보행자 움직임, 공공 행사에서의 군중 역학 및 대피 시나리오와 같은 집단적 인간 행동을 수집하기 위해서 적용되기도 한다.

6.3. [ 무인 항공기(UAV) 조정 ]

UAV 또는 드론 조정에서 중요한 역할을 하기도 한다. 이는 서로 안전한 거리를 유지하고, 충돌을 피하고, 대형으로 비행하는 데 도움이 되며 이는 감시, 검사, 환경 모니터링과 같은 응용 분야에서도 사용된다.