Boids(Flocking) 알고리즘을 만들어 보면서 정리한 글입니다.
공부하면서 정리한 글이기에 잘못된 점이 있을 수 있습니다.
이 점 참고 부탁드리며 오류를 발견하셨다면 편하게 댓글로 공유해 주세요!!
1. Description
Boids(Flocking) 알고리즘이란
새들이 떼를 지어 다니는 행동에 대한 시뮬레이션(군집 이동 알고리즘) 알고리즘입니다.
Boids에 적용되는 가장 기본적인 규칙은 아래와 같습니다.
- Separation(분리)
- Alignment(정렬)
- Cohension(응집력)
군집 이동을 할 객체는
각 규칙을 통해 나아가야 할 방향을 구하고 구한 방향을 모두 더해 객체를 그 방향으로 이동시켜야 합니다.
여기서 규칙에 가중치를 두어 어떤 규칙에 좀 더 초점을 맞출지 처리도 가능합니다.
이 알고리즘의 문제점은 매 프레임마다 객체들이 나아가야 할 방향을 정하다 보니 사용자가 군집 이동을 예측하기가 어렵다는 점입니다.
이제 규칙들에 대해서 하나씩 살펴보겠습니다
여기서 이웃이란 위의 예시 이미지에서 원 안에 들어온 객체들을 뜻합니다.
그러므로 원 바깥의 객체(파란색에 있는 객체)는 이웃이 아니게 됩니다.
1-1. Separation
Separation(분리)는 자기 주변의 객체들이 붐비는 것을 피하기 위해 근처 이웃들에서 벗어나는 규칙입니다.
밑에서도 설명하겠지만 규칙을 어떻게 적용하는지는 정해진 것이 없는 것으로 보여 구현에 따라 피할 방향이 달라지는 것 같습니다.
1-2. Alignment
Alignment(정렬)은 이웃 객체들의 평균 방향으로 이동하는 규칙입니다.
예시 이미지를 보면 이웃 객체들이 11~12시 사이 방향으로 이동하고 있기 때문에 자기 자신(초록색) 또한 평균 방향으로 변경되어 이동하게 됩니다.
1-3. Cohesion
Coehsion(응집력)은 모든 이웃 사이의 중간점(Average Position)을 찾고 중간점을 향해 이동하는 규칙입니다.
이웃들이 계속 바뀌게 되면서 중간점 또한 계속 변하다 보니 이때 방향이 갑작스럽게 변화할 수 있습니다.
2. Coding(C#)
2-1. Separation
Separation(분리)는 자기 주변의 객체들이 붐비는 것을 피하기 위해 근처 이웃들에서 벗어나는 규칙입니다.
Separation(분리)는 Separation만의 이웃 탐지 범위가 존재해야 합니다.
이유는 Separation 탐지 범위가 이웃 탐지 범위보다 커지면 모든 이웃을 피하려고 하는데요.
그래서 Separation용 탐지 범위 변수를 세팅해서 서로 다른 탐지 범위를 가지도록 처리해야 합니다.
이웃들을 피할 방향을 구하는 방법이 정해진 게 있는지 찾아보았는데 정해진 게 없고 구현을 어떻게 하냐에 따라 다른 것 같습니다.
그래서 이 글에서는 간단하게 “이웃 -> 나”로 향하는 벡터들의 합을 나아갈 방향으로 처리했습니다.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using System.Collections.Generic;
using UnityEngine;
public class SeparationRule : IBoidsRule
{
public Vector3 GetDirection(Transform agent, List<Transform> neighbor)
{
if (agent == null || neighbor == null || neighbor.Count == 0)
return Vector3.zero;
Vector3 dir = Vector3.zero;
foreach (var ne in neighbor)
{
dir += agent.position - ne.transform.position;
}
return dir.normalized;
}
}
2-2. Alignment
Alignment(정렬)의 규칙을 다시 살펴보면 Alignment(정렬)은 이웃 객체들의 평균 방향으로 이동하는 규칙입니다.
그렇기 때문에 이웃 객체들의 진행 방향벡터를 모두 더한 뒤 객체 개수로 나누면 이웃들의 평균 방향을 구할 수 있습니다.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using System.Collections.Generic;
using UnityEngine;
public class AlignmentRule : IBoidsRule
{
public Vector3 GetDirection(Transform agent, List<Transform> neighbor)
{
if (agent == null)
return Vector3.zero;
// 이웃이 없다면, 전방으로 진행
if (neighbor == null || neighbor.Count == 0)
return agent.forward;
Vector3 neighborDir = Vector3.zero;
foreach (var ne in neighbor)
{
neighborDir += ne.transform.forward;
}
return (neighborDir /= neighbor.Count).normalized;
}
}
2-3. Cohesion
Coehsion(응집력)은 모든 이웃 사이의 중간점(Average Position)을 찾고 중간점을 향해 이동하는 규칙입니다.
그러므로, 이웃들의 중간점을 찾아서 본인(agent) 기준으로 중간점을 향하는 벡터를 구해주면 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using System.Collections.Generic;
using UnityEngine;
public class CohesionRule : IBoidsRule
{
public Vector3 GetDirection(Transform agent, List<Transform> neighbor)
{
if (agent == null || neighbor == null || neighbor.Count == 0)
return Vector3.zero;
Vector3 averagePos = Vector3.zero;
foreach (var ne in neighbor)
{
averagePos += ne.position;
}
averagePos /= neighbor.Count;
return (averagePos - agent.transform.position).normalized;
}
}
2-4. boids generator
2-1 ~ 2-3까지 규칙들을 통해 얻은 Direction Vector를 모두 더해 객체가 나아가야 할 Direction을 정해줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void Update()
{
foreach (var agent in _boidAgents)
{
Vector3 dir = _cohesionRule.GetDirection(
agent,
GetNeighbor(agent, _detectRange)
);
dir += _alignmentRule.GetDirection(
agent,
GetNeighbor(agent, _detectRange)
);
dir += _separtionRule.GetDirection(
agent,
GetNeighbor(agent, _separationRange)
);
dir.Normalize();
}
}
구한 Direction을 객체에 바로 적용해 줍니다.
1
2
3
4
5
6
7
8
9
10
private void Update()
{
foreach (var agent in _boidAgents)
{
// 위 코드 생략...
agent.transform.position += dir * _speed * Time.deltaTime;
agent.transform.rotation = Quaternion.LookRotation(dir);
}
}
모두 적용하면 아래와 같이 재생이 되는데 보면 객체가 부르르르 떨리는 것을 볼 수 있습니다.
구한 방향을 바로 봄으로써 생기는 문제
객체가 매 프레임마다 구해진 방향을 바로 보기 때문에 떨리는 것으로 보이는데요
Vector3.Lerp를 이용해 조금씩 그 방향으로 이동하게 처리하면 해결됩니다.
1
dir = Vector3.Lerp(agent.transform.forward, dir, Time.deltaTime);
전체 코드는 아래와 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
using System.Collections.Generic;
using UnityEngine;
public class BoidsGenerator : MonoBehaviour
{
[System.Serializable]
struct SpawnArea
{
public float _min, _max;
}
[Header("Boids")]
[SerializeField]
Transform _boids;
[SerializeField]
float _speed = 5f;
[SerializeField]
LayerMask _boidsLayer;
[Header("Range")]
[SerializeField, Range(0, 100f)]
float _detectRange = 10f;
[SerializeField, Range(0, 100f)]
float _separationRange = 5f;
[Header("Spawn")]
[SerializeField, Range(1, 1000)]
int _spawnCount;
[SerializeField]
SpawnArea _spawnAreaPosX;
[SerializeField]
SpawnArea _spawnAreaPosY;
[SerializeField]
SpawnArea _spawnAreaPosZ;
List<Transform> _boidAgents = new();
AlignmentRule _alignmentRule = new();
CohesionRule _cohesionRule = new();
SeparationRule _separtionRule = new();
private void Awake()
{
SpawnBoids();
}
void SpawnBoids()
{
for (int i = 0; i < _spawnCount; i++)
{
Vector3 spawnPos = new Vector3(
Random.Range(_spawnAreaPosX._min, _spawnAreaPosX._max),
Random.Range(_spawnAreaPosY._min, _spawnAreaPosY._max),
Random.Range(_spawnAreaPosZ._min, _spawnAreaPosZ._max));
_boidAgents.Add(Instantiate(_boids,spawnPos,Quaternion.identity));
}
}
private void Update()
{
foreach (var agent in _boidAgents)
{
Vector3 dir = _cohesionRule.GetDirection(
agent,
GetNeighbor(agent, _detectRange)
);
dir += _alignmentRule.GetDirection(
agent,
GetNeighbor(agent, _detectRange)
);
dir += _separtionRule.GetDirection(
agent,
GetNeighbor(agent, _separationRange)
);
dir = Vector3.Lerp(agent.transform.forward, dir, Time.deltaTime);
dir.Normalize();
agent.transform.position += dir * _speed * Time.deltaTime;
agent.transform.rotation = Quaternion.LookRotation(dir);
}
}
List<Transform> GetNeighbor(Transform agent, float range)
{
var overlaps = Physics.OverlapSphere(agent.position, range, _boidsLayer);
if(overlaps.Length == 0)
return null;
List<Transform> tf = new List<Transform>(overlaps.Length);
for (int i = 0; i < overlaps.Length; i++)
{
if (overlaps[i].transform == agent)
continue;
tf.Add(overlaps[i].transform);
}
return tf;
}
}
3. 결과
매 프레임마다 각 객체들이 나아가야 할 방향을 정해주다 보니 프레임이 많이 떨어지는 것 같아서
프레임 상승을 위해선 연산 처리를 간소화하는 처리가 필요할 듯합니다.
참고 자료