카테고리 없음
Boid 알고리즘 구현연습
park-gom
2024. 9. 9. 22:51
몹 700마리가 넘어가자 프레임이 60까지 떨어젔다
연산을 단순화 하기 위해 이번에는 Boid 알고리즘을 찾아보기로했다
먼저 Boid 알고리즘의 구현이다
using UnityEngine;
using System.Collections.Generic;
public class Boid : MonoBehaviour
{
public float speed = 2f; // 이동 속도
public float neighborRadius = 5f; // 이웃을 찾는 반경
public float separationDistance = 2f; // 너무 가까이 붙지 않기 위한 최소 거리
private Vector2 velocity; // 현재 이동 방향 및 속도
// Boid의 초기화
void Start()
{
// 랜덤한 초기 속도
velocity = Random.insideUnitCircle.normalized * speed;
}
// Update는 매 프레임 호출됩니다.
void Update()
{
List<Boid> neighbors = GetNeighbors();
Vector2 separation = CalculateSeparation(neighbors);
Vector2 alignment = CalculateAlignment(neighbors);
Vector2 cohesion = CalculateCohesion(neighbors);
// Boid의 최종 이동 방향 계산
Vector2 force = separation + alignment + cohesion;
velocity += force * Time.deltaTime;
velocity = velocity.normalized * speed;
// Boid의 위치 업데이트
transform.position += (Vector3)velocity * Time.deltaTime;
// Boid의 회전 (이동 방향에 따른 회전)
float angle = Mathf.Atan2(velocity.y, velocity.x) * Mathf.Rad2Deg;
transform.rotation = Quaternion.Euler(0, 0, angle);
}
// 이웃 Boid들을 찾는 함수
private List<Boid> GetNeighbors()
{
List<Boid> neighbors = new List<Boid>();
Boid[] allBoids = FindObjectsOfType<Boid>();
foreach (Boid boid in allBoids)
{
if (boid != this)
{
float distance = Vector2.Distance(transform.position, boid.transform.position);
if (distance < neighborRadius)
{
neighbors.Add(boid);
}
}
}
return neighbors;
}
// Separation: 가까운 이웃들과 거리를 유지하려는 힘
private Vector2 CalculateSeparation(List<Boid> neighbors)
{
Vector2 force = Vector2.zero;
foreach (Boid neighbor in neighbors)
{
float distance = Vector2.Distance(transform.position, neighbor.transform.position);
if (distance < separationDistance)
{
Vector2 direction = (Vector2)transform.position - (Vector2)neighbor.transform.position;
force += direction.normalized / distance;
}
}
return force;
}
// Alignment: 이웃들과 방향을 맞추려는 힘
private Vector2 CalculateAlignment(List<Boid> neighbors)
{
Vector2 averageVelocity = Vector2.zero;
foreach (Boid neighbor in neighbors)
{
averageVelocity += neighbor.velocity;
}
if (neighbors.Count > 0)
{
averageVelocity /= neighbors.Count;
return (averageVelocity - velocity).normalized;
}
return Vector2.zero;
}
// Cohesion: 이웃들과 함께 모이려는 힘
private Vector2 CalculateCohesion(List<Boid> neighbors)
{
Vector2 centerOfMass = Vector2.zero;
foreach (Boid neighbor in neighbors)
{
centerOfMass += (Vector2)neighbor.transform.position;
}
if (neighbors.Count > 0)
{
centerOfMass /= neighbors.Count;
return (centerOfMass - (Vector2)transform.position).normalized;
}
return Vector2.zero;
}
}기본적인 boid알고리즘이다. 적당한 오브젝트를 생성해서 스크립트를 삽입하면 잘 작동하는것도 확인할 수 있다.
이걸 몹에 그대로 적용시켜봤더니
150마리정도에서 60프레임이 나왔다, 기존 물리엔진보다 더 성능이 떨어지는것이다. 뭔가 잘못됬다
사실 boid함수의 모든 기능이 필요한건 아니다. 위 코드에서는 군집의 방향을 스스로 결정( CalculateAlignment )하고 군집의 이탈을 방지하기 위한 함수( CalculateCohesion )가 있지만, 뱀서라이크에서는 적절한 간격을 유지하면서 플레이어라는 명확한 목표가있다.
그래서 과감하게 두 함수는 쓰지않기로 했다. 대신 플레이어를 쫒아가는 함수를 추가했다.
private Vector2 CalculatePlayerAttraction()
{
if (player != null)
{
Vector2 playerPosition = player.transform.position;
Vector2 directionToPlayer = (playerPosition - (Vector2)transform.position).normalized;
return directionToPlayer * playerAttractionStrength;
}
return Vector2.zero;
}하지만 성능적으로 큰 차이는 보이지 않았다
뭔가 획기적인 성능 개선안이 필요했다 먼저 코드상으로 보이는 문제점은 다음과같다.
문제점1) Update는 매 프레임 호출됩니다.
굳이 매프레임마다 체크할 필요가있을까?
문제점2) 매 프레임마다 씬상의 모든 오브젝트를 검증하고, 이를 새로운 리스트에 넣는다.
새로운 리스트를 만드는것이 아니라 몬스터 리스트를 따로 저장하고 그걸 읽기만하는게 어떨까
Boid[] allBoids = FindObjectsOfType<Boid>();
문제점3) 플레이어에 도달한뒤에 방향전환이 너무느리다
이건 힘에관한 설정 때문일것이다. transporm.Translate로 수정해보자
velocity += force * Time.deltaTime;
velocity = velocity.normalized * speed;
//문제점4) 모든 오브젝트를 검증한다
//쿼드트리나, 그리드기반 분할을 이용해서 검증 대상을 한정해보자
using System.Collections.Generic;
using UnityEngine;
public class Enemy : MonoBehaviour
{
Rigidbody2D target;
public float speed = 2f; // 이동 속도
public float neighborRadius = 0.3f; // 이웃을 찾는 반경
public float separationDistance = 0.3f; // 너무 가까이 붙지 않기 위한 최소 거리
public float playerAttractionStrength = 2f; // 플레이어를 향한 힘의 크기
private Vector2 velocity; // 현재 이동 방향 및 속도
private GameObject player; // 플레이어 객체를 참조
private float updateRate = 0.3f; // 0.2초에 한 번씩만 업데이트
private float timer;
Vector2 separation;
Vector2 playerAttraction;
List<Enemy> neighbors = new List<Enemy>();
List<Enemy> neighbors2 = new List<Enemy>();
SpriteRenderer spriter;
private void Awake()
{
spriter = GetComponent<SpriteRenderer>();
}
private void Start()
{
velocity = Vector2.zero;
player = GameManager.instance.player.gameObject;
}
private void FixedUpdate()
{
if (!isLive)
return;
timer += Time.deltaTime;
if (timer >= updateRate)
{
neighbors.Clear();
neighbors = GetNeighbors();
separation = CalculateSeparation(neighbors);
playerAttraction = CalculatePlayerAttraction();
timer = 0f;
}
// Boid의 최종 이동 방향 계산
Vector2 force = playerAttraction + separation * 0.5f; // + cohesion +alignment
Vector2 direction = force.normalized;
transform.Translate(direction * speed * Time.deltaTime, Space.World);
}
private void LateUpdate()
{
spriter.flipX = target.position.x < transform.position.x;
}
// 플레이어를 향한 Attraction 계산
private Vector2 CalculatePlayerAttraction()
{
if (player != null)
{
Vector2 playerPosition = player.transform.position;
Vector2 directionToPlayer = (playerPosition - (Vector2)transform.position).normalized;
return directionToPlayer * playerAttractionStrength;
}
return Vector2.zero;
}
// 이웃 Boid들을 찾는 함수
private List<Enemy> GetNeighbors()
{
neighbors2.Clear();
neighbors2 = new List<Enemy>();
foreach (Enemy boid in GameManager.instance.enemies)
{
if (boid != this)
{
float distance = Vector2.Distance(transform.position, boid.transform.position);
if (distance < neighborRadius)
{
neighbors2.Add(boid);
}
}
}
return neighbors2;
}
// Separation: 가까운 이웃들과 거리를 유지하려는 힘
private Vector2 CalculateSeparation(List<Enemy> neighbors)
{
Vector2 force = Vector2.zero;
foreach (Enemy neighbor in neighbors)
{
float distance = Vector2.Distance(transform.position, neighbor.transform.position);
if (distance < separationDistance)
{
Vector2 direction = (Vector2)transform.position - (Vector2)neighbor.transform.position;
force += direction.normalized / distance;
}
}
return force;
}
}
먼저 1번 2번 3번 부터 해결했다
결과는 나쁘지않다 150->350 정도로 약 두배이상의 성능개선이 나타났다.
하지만 이정도로는 택도없다 2~3천마리가 나와도 거뜬한 정도의 성능이 필요하다
역시 빅오 O(n^2)인 GetNeighbors함수를 손봐야할것같다
쿼드 트리와 그리드 분할 기법의 장단점을 먼저 파악해보자
가장 끌린 요소는 바로 동적 객체 처리이다. 뱀서라이크는 매 순간 많은 객체가 빠르게 움직인다
이렇게 동적으로 움직이는 객체를 빠르게 처리할수있는게 중요할것이다.
그래서 그리드 기반 분할을 사용해보기로 했다.
먼저 단일 객체에 대한 테스트를 진행해봤다
몹이 이동함에 따라 그리드에 불이 들어오는 모습을 볼수있다. 해당 셀에 객체가 있다는것을 잘 인식하는것같다.