■ 공간 해시 그리드(Spatial Hash)
Flow Field의 방향을 따라 이동하는 적들은 동일한 방향으로 이동하기 때문에 뭉쳐서 오게 된다.
- 따라서 분리 및 조향을 통해 서로 겹치지 않게 처리해주어야 한다.
적의 주변에 있는 다른 적들을 파악하기 위해 OverlapSphere + 태그 방식을 쓰면 결국 적의 객체 수(N)만큼 돌기 때문에 오버헤드가 심해지게 된다.
따라서 서로의 분리에 필요한 건 “물리적인 충돌 정보”가 아닌, “근처에 같은 종류의 객체 어디 있나?”라는 위치 정보뿐이다. ⇒ 물리 엔진을 거칠 필요가 없음.
■ SpatialHash 구현
공간 해싱 그리드의 핵심은 객체 스스로가 주변의 다른 객체를 일일이 찾는 것이 아니라, 등록 → 조회의 방식으로 이루어진다는 점이다.
모든 객체를 미리 격자 셀에 등록해두면, 특정 위치의 주변을 찾을 때 인접한 셀만 조회하면 된다. 객체는 매 프레임 이동하므로 등록 정보도 매번 새로 갱신해야 하며, 따라서 초기화 → 등록 → 조회의 순서로 진행된다.
1. SpatialHash<T>
public class SpatialHash<T> where T : ISpatialItem
{
private readonly int _cellSize;
private readonly Dictionary<long, List<T>> _buckets = new();
}
공간 해싱 그리드에 담기는 객체는 한 종류가 아니다. 서로 밀쳐내며 흩어지는 적뿐 아니라, 적이 피해 가야 하는 정적인 장애물도 같은 방식으로 그리드에 등록해 이웃으로 조회해야 한다.
그래서 그리드를 특정 클래스에 묶지 않고 제네릭 SpatialHash<T>로 두되, 담기는 타입을 ISpatialItem을 구현한 객체로 한정한다.
public interface ISpatialItem
{
public Vector3 Position { get; }
public float Radius { get; }
}
ISpatialItem은 두 개의 프로퍼티를 요구한다.
- Position : 객체의 월드 위치를 반환.
- Radius : 이 객체가 주변 객체를 어느 범위까지 밀쳐내는지를 정한다.
객체를 어느 셀 버킷에 넣고 어느 셀에서 찾을지 계산하는 데 위치(Position)만 필요하다.
Radius는 뒤에서 다룰 반발력 계산 단계에서 쓰인다. 조회로 추려낸 이웃과의 거리를 그 이웃의 Radius와 비교해 밀어내는 세기를 정하는 식이다.
2. 초기화
using System.Collections.Generic;
using UnityEngine;
public class SpatialHash<T> where T : ISpatialItem
{
private readonly int _cellSize;
private readonly Dictionary<long, List<T>> _buckets = new();
public SpatialHash(int size)
{
_cellSize = size;
}
public void Clear()
{
foreach (var b in _buckets.Values)
{
b.Clear();
}
}
private long Key(int cx, int cy) => ((long)cx << 32) | (uint)cy;
}
객체가 속한 셀의 좌표를 key로, 그 셀에 들어 있는 객체들의 List를 value로 하는 딕셔너리를 생성한다. 객체가 매 프레임 이동하기 때문에, 이 버킷 정보는 매 프레임 초기화한 뒤 다시 채워야 한다.
Clear에서 한 가지 짚어둘 점은, 딕셔너리 자체를 비우는 것이 아니라, 각 버킷의 List만 비우고 딕셔너리 구조와 List 객체는 그대로 재사용한다.
- 매 프레임 딕셔너리를 통째로 새로 만들면 그때마다 List들이 새로 할당되어 GC(가비지 컬렉션) 부담이 커짐.
private long Key(int cx, int cy) => ((long)cx << 32) | (uint)cy;
딕셔너리의 key는 하나의 값이어야 하므로, 객체가 위치한 셀의 2차원 좌표 (cx, cy)를 하나의 값으로 합쳐야 한다. int는 4바이트이고 좌표값 두 개를 담아야 하니, 8바이트인 long 하나에 둘을 이어 붙인다.
- cx를 왼쪽 32비트로 밀어 올리고(<< 32), 그 오른쪽 32비트 자리에 cy를 채우는(| (uint)cy) 방식이다.
이렇게 하면 (3, 4)와 (4, 3)처럼 값만 뒤바뀐 좌표도 서로 다른 키를 갖게 된다.
cy를 (uint)로 캐스팅하는데, cy가 음수일 때 그냥 long에 OR 하면 부호 확장 때문에 상위 32비트가 1로 채워져 cx 자리를 오염시킨다. 반면 (uint)로 먼저 변환하면 이 문제가 사라져 음수 좌표에서도 두 좌표가 서로 침범하지 않는다. Mathf.FloorToInt가 음수를 반환할 수 있으므로(맵 원점 기준으로 좌표가 음수가 되는 경우) 필요한 처리다.
3. 등록
using System.Collections.Generic;
using UnityEngine;
public class SpatialHash<T> where T : ISpatialItem
{
private readonly int _cellSize;
private readonly Dictionary<long, List<T>> _buckets = new();
public void Insert(T agent)
{
var pos = agent.Position;
var cx = Mathf.FloorToInt(pos.x / _cellSize);
var cy = Mathf.FloorToInt(pos.z / _cellSize);
var key = Key(cx, cy);
if (!_buckets.TryGetValue(key, out var list))
{
list = new List<T>();
_buckets.Add(key, list);
}
list.Add(agent);
}
}
각 객체가 자기 자신을 격자에 등록하기 위해 호출하는 메서드다. 객체의 월드 위치를 셀 좌표로 바꾼 뒤, 그 좌표로 만든 key의 버킷에 자신을 추가한다.
var cx = Mathf.FloorToInt(pos.x / _cellSize);
var cy = Mathf.FloorToInt(pos.z / _cellSize);
var key = Key(cx, cy);
먼저 월드 좌표를 셀 좌표로 변환하는 부분을 보자. pos.x와 pos.z를 각각 _cellSize로 나눈 뒤 Mathf.FloorToInt로 내림한다.
나눗셈은 월드 공간을 셀 크기 단위로 묶는 과정이고, 내림은 그 값을 정수 셀 인덱스로 떨어뜨리는 과정이다.
- Ex) _cellSize가 4일 때 x좌표 0~3.99는 셀 0, 4~7.99는 셀 1로 묶인다.
- 탑 뷰 게임 기준이라 높이축인 y는 격자 분할에 관여하지 않음.
if (!_buckets.TryGetValue(key, out var list))
{
list = new List<DummyEnemy>();
_buckets.Add(key, list);
}
list.Add(agent);
다음으로 key로 버킷을 찾는다. TryGetValue로 해당 키의 List가 이미 있는지 확인하고, 없으면 새 List를 만들어 딕셔너리에 넣은 뒤 거기에 자신을 추가한다.
즉 버킷은 미리 전부 만들어두는 것이 아니라 객체가 실제로 들어오는 순간에만 생성된다. 앞서 딕셔너리 방식이 배열과 달리 "객체가 존재하는 셀만 메모리에 잡힌다"라고 했던 것이 바로 이 지연 생성으로 구현된다.
4. 조회
using System.Collections.Generic;
using UnityEngine;
public class SpatialHash<T> where T : ISpatialItem
{
private readonly int _cellSize;
private readonly Dictionary<long, List<T>> _buckets = new();
public void Query(Vector3 pos, List<T> result)
{
result.Clear();
var cx = Mathf.FloorToInt(pos.x / _cellSize);
var cy = Mathf.FloorToInt(pos.z / _cellSize);
for (var dx = -1; dx <= 1; ++dx)
{
for (var dy = -1; dy <= 1; ++dy)
{
if(_buckets.TryGetValue(Key(cx + dx, cy + dy), out var list))
result.AddRange(list);
}
}
}
}
특정 위치 주변의 객체들을 모아 반환하는 메서드다. 결과를 담을 result 리스트를 인자로 받아, 주변 셀에 등록된 객체를 여기에 채워준다.
- 조회할 위치 pos를 등록 때와 동일한 방식으로 셀 좌표 (cx, cy)로 변환한다
// (-1,+1) (0,+1) (+1,+1)
// (-1, 0) (0, 0) (+1, 0)
// (-1,-1) (0,-1) (+1,-1)
for (var dx = -1; dx <= 1; ++dx)
{
for (var dy = -1; dy <= 1; ++dy)
{
if(_buckets.TryGetValue(Key(cx + dx, cy + dy), out var list))
result.AddRange(list);
}
}
좌표를 변환한 다음 이 중심 셀을 기준으로 dx, dy를 각각 -1, 0, 1로 돌려 자기 셀과 인접한 8개 셀, 총 9개(3×3) 버킷을 순회한다. 각 버킷이 존재하면 그 안의 객체를 모두 result에 더한다.
중심 셀 하나만 보지 않고 주변 3×3을 함께 보는 이유는 셀 경계 때문이다.
두 객체가 물리적으로는 바로 옆에 붙어 있어도, 셀 경계선을 사이에 두면 서로 다른 버킷에 등록된다. 예를 들어 셀 크기가 4일 때 x좌표가 3.9인 객체와 4.1인 객체는 거리가 0.2에 불과하지만 각각 셀 0과 셀 1에 나뉘어 들어간다. 중심 셀만 조회하면 이렇게 경계 너머에 있는 코앞의 이웃을 놓치므로, 인접 셀까지 함께 살펴 빠뜨림을 막는다.
■ 적 관리 시스템
개별 적이 각자 SpatialHash를 들고 있을 필요는 없다. 공간 해시는 "모든 적의 위치를 한데 모아 격자에 등록하고, 거기서 이웃을 조회하는" 구조라, 무리 전체가 공유하는 하나의 인스턴스만 있으면 된다. 그래서 적들을 통합 관리하는 시스템을 두고, 여기서 매 프레임 초기화 → 삽입 → 조회를 돌린다.
- 또한 움직이는 객체가 정적인 장애물을 회피할 수 있도록 반발력을 계산한다.
1. 적 생성
using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;
public class WaveManager : MonoBehaviour
{
[SerializeField] private FlowField flowField;
[SerializeField] private Transform obstacleParent;
[SerializeField] private DummyEnemy enemy;
private List<DummyEnemy> _waveEnemies;
private SpatialHash<DummyEnemy> _enemyHash;
private SpatialHash<Obstacle> _obstacleHash;
private List<DummyEnemy> _rangeBuffer;
private List<Obstacle> _obstacleBuffer;
public void Start()
{
_waveEnemies = new List<DummyEnemy>();
_enemyHash = new SpatialHash<DummyEnemy>(4);
_obstacleHash = new SpatialHash<Obstacle>(4);
_rangeBuffer = new List<DummyEnemy>();
_obstacleBuffer = new List<Obstacle>();
for (var i = 0; i < 100; ++i)
{
var obj = Instantiate(enemy);
obj.FlowField = flowField;
obj.transform.position = transform.position +
new Vector3(Random.Range(-1f, 1f), 0, Random.Range(-1f, 1f));
_waveEnemies.Add(obj);
}
for (var i = 0; i < obstacleParent.childCount; ++i)
{
_obstacleHash.Insert(obstacleParent.GetChild(i).GetComponent<Obstacle>());
}
}
}
Start에서는 먼저 런타임에 쓸 컨테이너들을 만든다.
- 생성한 적을 들고 있을 _waveEnemies
- 적과 장애물을 각각 셀 버킷에 담을 _enemyHash와 _obstacleHash
- 이웃 조회 결과를 받아올 _rangeBuffer와 _obstacleBuffer
테스트를 위해 적 100마리를 생성하고, 각 적에게 flowField 참조를 넘겨 스스로 이동 방향을 조정할 수 있게 한다. 적을 생성할 땐 겹쳐서 생성되지 않도록 약간의 랜덤 오프셋을 준다.
obstacleParent의 자식들을 순회하며 각 Obstacle을 _obstacleHash에 등록한다. 적은 매 프레임 움직이므로 Start에서 해시에 넣지 않고, 뒤에서 볼 Update에서 매 프레임 비우고 다시 넣는다. 반면 장애물은 고정되어 움직이지 않으므로 Start에서 한 번만 등록하고 이후 건드리지 않는다.
각 buffer는 start에서 미리 만들어 재사용한다. 이웃 조회는 매 프레임마다 객체 수만큼 발생하는데, 조회할 때마다 새 리스트를 할당하면 그만큼 GC가 자주 돌게 된다.
2. 초기화와 삽입
public class WaveManager : MonoBehaviour
{
private void Update()
{
_spatialHash.Clear();
foreach (var wave in _waveEnemies)
{
_spatialHash.Insert(wave);
}
}
}
객체의 위치는 매 프레임마다 바뀌므로, Update에서 해시를 초기화하고, 그다음에 다시 모든 적들을 삽입한다.
■ 분리력 계산
using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;
public class WaveManager : MonoBehaviour
{
private void Update()
{
// 초기화 및 삽입 생략...
foreach (var self in _waveEnemies)
{
_enemyHash.Query(self.transform.position, _rangeBuffer);
_obstacleHash.Query(self.transform.position, _obstacleBuffer);
var selfPos = self.transform.position;
var sep = Vector3.zero;
var obsForce = Vector3.zero;
var count = 0;
foreach (var other in _rangeBuffer)
{
if(other == self) continue;
if (AccumulateRepulsion(selfPos, other, ref sep))
count++;
}
foreach (var obs in _obstacleBuffer)
{
AccumulateRepulsion(selfPos, obs, ref obsForce);
}
if(count > 0)
sep /= count;
self.Separation = sep;
self.ObstacleForce = obsForce;
}
}
}
여기가 가장 중요한 부분이니 천천히 살펴보자.
1. 인접한 적과 장애물 얻어오기
foreach (var self in _waveEnemies)
{
_spatialHash.Query(self.transform.position, _rangeBuffer);
_obstacleHash.Query(self.transform.position, _obstacleBuffer);
var selfPos = self.transform.position;
var sep = Vector3.zero;
var obsForce = Vector3.zero;
var count = 0;
// ....
}
먼저 인접한 위치에 있는 적들과 장애물을 각각의 Buffer에 저장한다. 이후 분리력(sep)과 장애물 반발력(obsForce)을 초기화하고 자기 자신의 위치를 저장한다.
2. 분리력 계산
Query가 채워준 _rangeBuffer(주변 3×3 셀의 적들)를 하나씩 돌면서, 각 이웃으로부터 멀어지는 방향의 힘을 모아 self.Separation 에 저장한다.
foreach (var other in _rangeBuffer)
{
if(other == self) continue;
if (AccumulateRepulsion(selfPos, other, ref sep))
count++;
}
- 자기 자신은 밀어낼 수 없으니 건너뛴다.
// 분리력 계산 함수
private bool AccumulateRepulsion(Vector3 selfPos, ISpatialItem item,
ref Vector3 separation)
{
var away = selfPos - item.Position;
away.y = 0f;
var dist = away.magnitude;
if (dist > 0.0001f && dist < item.Radius)
{
separation += away.normalized * (1 - dist / item.Radius);
return true;
}
return false;
}
self(내 위치)에서 다른 객체(other)로 향하는 벡터가 아닌, other에서 self로 향하는 벡터를 계산한다. 즉 away는 “그 이웃 방향으로부터 멀어지는 방향”을 가리키게 되고, 이 크기를 구해 dist에 저장한다.
1. 두 개의 조건 검사
if (dist > 0.0001f && dist < item.Radius)
dist > 0.0001f는 두 적이 거의 같은 위치에 겹쳐 있을 때를 걸러낸다. 거리가 0에 가까우면 바로 다음 줄의 away.normalized가 0벡터를 정규화하려다 정의되지 않은 값(NaN)이 되기 때문이다.
dist < item.Radius는 반경 안에 든 이웃만 밀어내기 대상으로 삼는다.
2. 거리에 따른 가중치
separation += away.normalized * (1 - dist / item.Radius);
away.normalized는 방향만 남긴 단위벡터고, 거기에 (1 - dist / item.Radius)라는 가중치를 곱한다. 이 가중치가 "가까울수록 강하게"를 만드는 부분이다.
거리가 0에 가까우면 dist / item.Radius가 0에 가까워져 가중치는 1(최대)이 되고, 거리가 separationRadius에 근접하면 가중치는 0(최소)으로 떨어진다. 즉 바로 옆의 이웃은 세게, 반경 끝자락의 이웃은 거의 0으로 밀어내며, 이 감소는 거리에 정비례하는 선형이다.
- 이렇게 만든 벡터를 sep에 계속 누적하고, 힘을 실제로 받은 이웃 수를 count로 센다.
3. 장애물 반발력 계산
foreach (var obs in _obstacleBuffer)
{
AccumulateRepulsion(selfPos, obs, ref obsForce);
}
적은 다른 적뿐 아니라 맵에 배치된 장애물도 피해 가야 한다. 그래서 주변 장애물이 담긴 _obstacleBuffer를 순회하며, 적끼리 분리력을 모을 때와 똑같은 AccumulateRepulsion으로 반발력을 누적한다. 적이든 장애물이든 ISpatialItem으로 취급되므로 같은 함수가 그대로 재사용된다.
다만 적 루프와 결정적으로 다른 점이 하나 있다. 적을 순회할 때는 AccumulateRepulsion의 반환값으로 count를 셌지만, 장애물 루프는 반환값을 무시하고 개수를 세지 않는다.
합산 후 평균
if(count > 0)
sep /= count;
self.Separation = sep;
self.ObstacleForce = obsForce;
누적된 sep을 이웃 수로 나눠 평균을 낸다. 나누지 않고 합산만 하면 주변 적이 많을수록 분리력이 그 수에 비례해 커진다
- 스무 마리에 둘러싸인 적은 두 마리 옆에 있는 적보다 열 배 세게 튕겨 나가는 식이다.
count로 나누면 몇 마리에 둘러싸이든 힘이 "평균적으로 얼마나 가까운가"를 반영하게 되어, 무리가 폭발적으로 흩어지지 않고 안정적으로 간격만 벌어진다.
반면 장애물 반발력 obsForce는 나누지 않고 합산한 값을 그대로 쓴다. 장애물은 적처럼 한 지점에 수십 개가 몰리는 경우가 드물고, 오히려 좁은 통로처럼 여러 장애물 사이에 낀 상황에서는 각 장애물이 밀어내는 힘이 더해져 더 확실히 빠져나가는 편이 낫기 때문이다.
마지막으로 이 결과를 self.Separation 와 self.ObstacleForc에 대입한다. DummyEnemy는 이후 이 값을 FlowField 방향과 합성해 최종 이동을 정하게 된다.
'Unity,C# > Unity 정보' 카테고리의 다른 글
| [Unity] 다수의 적을 어떻게 움직일까(1) - Flowfield 길찾기 (0) | 2026.08.03 |
|---|---|
| [Unity] 이동 정리 - 벡터 개념부터 물리 이동까지(Transform, Rigidbody, CharacterController) (1) | 2026.06.23 |
| [Unity] 총알 시스템으로 알아보는 Object Pool (1) | 2026.05.07 |
| [Unity, C#] 델리게이트에 대한 모든것(Action, Func, Lambda) (0) | 2026.05.07 |
| [Unity, C#] SOLID 원칙 (1) | 2025.11.21 |