[Unity] 유니티 C#) SpatialPartition패턴

공간 분할 패턴

게임 내의 공간을 여러 영역으로 분할하여 충돌 감지나 객체 검색을 최적화하는 패턴

 

기본 구현 방법

1. 그리드의 각 셀에 들어갈 게임 유닛을 위한 인터페이스

public interface IGameObject
{
    Vector2 Position { get; }
    void CheckCollision(IGameObject other);
}

 

2. 실제 게임 유닛 클래스

public class Unit : MonoBehaviour, IGameObject
{
    public Vector2 Position => transform.position;
    
    public void CheckCollision(IGameObject other)
    {
        // 충돌 처리 로직
        Debug.Log($"Checking collision with other unit at {other.Position}");
    }
}

 

3. 공간 분할을 위한 그리드 시스템

public class Grid
{
    private float cellSize;
    private Dictionary<string, List<IGameObject>> cells;

    public Grid(float cellSize)
    {
        this.cellSize = cellSize;
        cells = new Dictionary<string, List<IGameObject>>();
    }

    // 그리드 좌표로 변환
    private string GetCellKey(Vector2 position)
    {
        int x = Mathf.FloorToInt(position.x / cellSize);
        int y = Mathf.FloorToInt(position.y / cellSize);
        return $"{x},{y}";
    }

    // 유닛을 그리드에 추가
    public void AddUnit(IGameObject unit)
    {
        string cellKey = GetCellKey(unit.Position);
        
        if (!cells.ContainsKey(cellKey))
        {
            cells[cellKey] = new List<IGameObject>();
        }
        
        cells[cellKey].Add(unit);
    }

    // 유닛을 그리드에서 제거
    public void RemoveUnit(IGameObject unit)
    {
        string cellKey = GetCellKey(unit.Position);
        
        if (cells.ContainsKey(cellKey))
        {
            cells[cellKey].Remove(unit);
        }
    }

    // 주변 셀의 유닛들과 충돌 체크
    public void CheckCollisions(IGameObject unit)
    {
        string cellKey = GetCellKey(unit.Position);
        
        // 현재 셀과 주변 8개 셀 확인
        for (int xOffset = -1; xOffset <= 1; xOffset++)
        {
            for (int yOffset = -1; yOffset <= 1; yOffset++)
            {
                Vector2 checkPos = unit.Position + new Vector2(xOffset * cellSize, yOffset * cellSize);
                string checkKey = GetCellKey(checkPos);
                
                if (cells.ContainsKey(checkKey))
                {
                    foreach (var other in cells[checkKey])
                    {
                        if (other != unit)
                        {
                            unit.CheckCollision(other);
                        }
                    }
                }
            }
        }
    }
}

 

4. 게임 매니저 예시

public class GameManager : MonoBehaviour
{
    private Grid grid;
    private List<Unit> allUnits;

    void Start()
    {
        grid = new Grid(5f); // 5x5 크기의 셀
        allUnits = new List<Unit>();

        // 유닛들 생성 및 그리드에 추가
        SpawnUnits();
    }

    void Update()
    {
        // 모든 유닛의 위치가 변경되었다고 가정하고 그리드 업데이트
        UpdateGrid();
    }

    void UpdateGrid()
    {
        foreach (var unit in allUnits)
        {
            grid.RemoveUnit(unit);
            grid.AddUnit(unit);
            grid.CheckCollisions(unit);
        }
    }

    void SpawnUnits()
    {
        // 유닛 생성 및 초기화 로직
    }
}

 

핵심 개념

• 게임 공간을 균일한 크기의 그리드로 분할
• 각 객체는 자신이 속한 그리드 셀을 알고 있음
• 충돌 검사는 같은 셀과 인접 셀의 객체들만 대상으로 함

 

사용 목적

• 광범위한 공간에서의 충돌 검사 최적화
• 특정 영역 내 객체 검색 성능 향상
• 대규모 객체 관리의 효율성 증가
• 연산 복잡도를 O(n²)에서 O(n)으로 감소

 

사용사례

• RTS 게임의 유닛 충돌 감지
• 오픈 월드의 NPC/몬스터 관리
• 파티클 시스템의 최적화
• AI의 시야 범위 체크

 

사용 사례 예시 코드

RTS 유닛의 효율적인 충돌 감지

public class UnitGrid 
{
    private float cellSize;
    private Dictionary<string, List<Unit>> grid;

    public UnitGrid(float size) 
    {
        cellSize = size;
        grid = new Dictionary<string, List<Unit>>();
    }

    private string GetCellKey(Vector3 position) 
    {
        int x = Mathf.FloorToInt(position.x / cellSize);
        int z = Mathf.FloorToInt(position.z / cellSize);
        return $"{x},{z}";
    }

    public void UpdateUnitPosition(Unit unit) 
    {
        string key = GetCellKey(unit.transform.position);
        foreach(var cell in grid.Values) 
            cell.Remove(unit);
            
        if (!grid.ContainsKey(key))
            grid[key] = new List<Unit>();
            
        grid[key].Add(unit);
    }

    public List<Unit> GetNearbyUnits(Vector3 position, float radius) 
    {
        List<Unit> nearby = new List<Unit>();
        int cellRadius = Mathf.CeilToInt(radius / cellSize);

        for (int x = -cellRadius; x <= cellRadius; x++) 
        {
            for (int z = -cellRadius; z <= cellRadius; z++) 
            {
                string key = GetCellKey(position + new Vector3(x * cellSize, 0, z * cellSize));
                if (grid.ContainsKey(key))
                    nearby.AddRange(grid[key]);
            }
        }
        return nearby;
    }
}

 

오픈 월드의 NPC / 몬스터 관리

// 플레이어 주변 NPC만 활성화하여 최적화
public class NPCManager 
{
    private float cellSize;
    private Dictionary<string, List<NPC>> npcGrid;
    private Transform player;

    public NPCManager(float size, Transform playerTransform) 
    {
        cellSize = size;
        player = playerTransform;
        npcGrid = new Dictionary<string, List<NPC>>();
    }

    private string GetCellKey(Vector3 position) 
    {
        int x = Mathf.FloorToInt(position.x / cellSize);
        int z = Mathf.FloorToInt(position.z / cellSize);
        return $"{x},{z}";
    }

    public void UpdateActiveNPCs() 
    {
        float activationRange = 50f; // NPC 활성화 범위
        var nearbyNPCs = GetNearbyNPCs(player.position, activationRange);

        foreach(var npc in nearbyNPCs) 
        {
            npc.SetActive(true);
            // AI 업데이트 등 활성화 로직
        }
    }

    public List<NPC> GetNearbyNPCs(Vector3 position, float range) 
    {
        List<NPC> nearby = new List<NPC>();
        int cellRange = Mathf.CeilToInt(range / cellSize);

        for(int x = -cellRange; x <= cellRange; x++) 
        {
            for(int z = -cellRange; z <= cellRange; z++) 
            {
                string key = GetCellKey(position + new Vector3(x * cellSize, 0, z * cellSize));
                if(npcGrid.ContainsKey(key))
                    nearby.AddRange(npcGrid[key]);
            }
        }
        return nearby;
    }
}

 

파티클 시스템 최적화

// 파티클 간 상호작용을 그리드 단위로 처리
public class ParticleGrid 
{
    private float cellSize;
    private Dictionary<string, List<ParticleData>> particleGrid;

    public ParticleGrid(float size) 
    {
        cellSize = size;
        particleGrid = new Dictionary<string, List<ParticleData>>();
    }

    private string GetCellKey(Vector3 position) 
    {
        int x = Mathf.FloorToInt(position.x / cellSize);
        int y = Mathf.FloorToInt(position.y / cellSize);
        int z = Mathf.FloorToInt(position.z / cellSize);
        return $"{x},{y},{z}";
    }

    public void UpdateParticle(ParticleData particle) 
    {
        string key = GetCellKey(particle.position);
        if(!particleGrid.ContainsKey(key))
            particleGrid[key] = new List<ParticleData>();
            
        particleGrid[key].Add(particle);
    }

    public void ProcessCollisions() 
    {
        foreach(var cell in particleGrid.Values) 
        {
            for(int i = 0; i < cell.Count; i++) 
            {
                for(int j = i + 1; j < cell.Count; j++) 
                {
                    // 파티클 간 상호작용 처리
                    ProcessParticleInteraction(cell[i], cell[j]);
                }
            }
        }
    }
}

 

AI 시야 범위 체크

// AI의 시야 범위와 각도를 고려한 시야 체크
public class VisionGrid 
{
    private float cellSize;
    private Dictionary<string, List<GameObject>> objectGrid;

    public VisionGrid(float size) 
    {
        cellSize = size;
        objectGrid = new Dictionary<string, List<GameObject>>();
    }

    private string GetCellKey(Vector3 position) 
    {
        int x = Mathf.FloorToInt(position.x / cellSize);
        int z = Mathf.FloorToInt(position.z / cellSize);
        return $"{x},{z}";
    }

    public bool CheckVision(Vector3 observer, Vector3 target, float visionRange, float visionAngle) 
    {
        if(Vector3.Distance(observer, target) > visionRange)
            return false;

        Vector3 directionToTarget = (target - observer).normalized;
        float angle = Vector3.Angle(observer.forward, directionToTarget);
        
        if(angle > visionAngle * 0.5f)
            return false;

        // 시야선 체크
        return !Physics.Raycast(observer, directionToTarget, out RaycastHit hit, visionRange);
    }

    public List<GameObject> GetVisibleObjects(Vector3 observerPosition, float visionRange, float visionAngle) 
    {
        List<GameObject> visibleObjects = new List<GameObject>();
        int cellRange = Mathf.CeilToInt(visionRange / cellSize);

        for(int x = -cellRange; x <= cellRange; x++) 
        {
            for(int z = -cellRange; z <= cellRange; z++) 
            {
                string key = GetCellKey(observerPosition + new Vector3(x * cellSize, 0, z * cellSize));
                if(objectGrid.ContainsKey(key)) 
                {
                    foreach(var obj in objectGrid[key]) 
                    {
                        if(CheckVision(observerPosition, obj.transform.position, visionRange, visionAngle))
                            visibleObjects.Add(obj);
                    }
                }
            }
        }
        return visibleObjects;
    }
}

 

결론

장점

• 성능 최적화 (특히 대규모 객체 처리 시)
• 메모리 사용 효율성
• 영역 기반 검색 용이성
• 확장성이 좋음

 

주의사항

• 그리드 크기 설정이 중요
• 객체 이동 시 지속적인 업데이트 필요
• 추가적인 메모리 사용
• 동적 환경에서의 관리 복잡성

 

유니티에서 특히 유용한 상황

• 많은 유닛이 있는 RTS 게임
• 대규모 오픈 월드 게임
• 물리 기반 시뮬레이션
• 복잡한 AI 시스템

공간 분할 패턴은 대규모 게임 환경에서
성능을 크게 향상시킬 수 있는 필수적인 최적화 기법인 것 같다