[멋쟁이사자처럼 부트캠프 TIL] 유니티 게임 스쿨 3기 14일차

 

 

 

14일차 요약

큐

• FIFO형식의 자료구조
• BFS, 서버 메시지 큐 등 다양한 방식으로 활용 가능

 

우선순위 큐

• 큐의 형식과 유사하며 우선순위에 따라 처리하는 요소를 결정하는 자료구조
• 힙(heap) 기반으로 만들어졌다.
• 다익스트라, 스케줄링 등 활용 가능

 

오브젝트 풀링

• 오브젝트를 생성, 소멸시키는 작업은 비용이 많이 발생한다.
• 오브젝트를 소멸시키지 않고 재활용하는 방법 = 오브젝트 풀링
• 구현하는 방법은 다양한다.
  • 큐, 맵 등 다양한 자료구조 사용 가능
• 생성, 소멸 비용이 줄어드는 대신 메모리를 차지하고 있으며 너무 많아질 시 단편화 문제 발생 가능

 

애니메이션 리타게팅

• 애니메이션이 없는 mesh에 다른 mesh의 애니메이션을 적용하는 방법
• Rig의 Animation Type을 Humanoid로 설정해야 한다.
• Animator에 애니메이션을 넣으면 본에 맞춰 애니메이션이 리타게팅 된다.

---

 

 

 

 

 

큐 (Queue)

큐는 '선입선출' (First In First Out, FIFO) 원칙을 따르는 선형 자료구조이다.

이는 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 의미합니다.

 

큐의 주요 연산

• Enqueue: 큐의 뒤쪽(rear)에 새로운 요소를 추가
• Dequeue: 큐의 앞쪽(front)에서 요소를 제거하고 반환
• Peek/Front: 큐의 맨 앞 요소를 조회 (제거하지 않음).
• IsEmpty: 큐가 비어있는지 확인
• Size: 큐에 있는 요소의 개수를 반환

 

큐 직접 구현

public class NodeQueue<T>
{
    private Node<T> front;
    private Node<T> rear;
    private int size;

    public NodeQueue()
    {
        front = null;
        rear = null;
        size = 0;
    }

    public void Enqueue(T item)
    {
        Node<T> newNode = new Node<T>(item);

        if (IsEmpty())
        {
            front = newNode;
            rear = newNode;
            return;
        }

        rear.Next = newNode;
        rear = newNode;
        size++;
    }

    public T Dequeue()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("큐가 비어있습니다.");
        }

        T data = front.Data;
        front = front.Next;
        size--;

        if (IsEmpty()) rear = null;

        return data;
    }


    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("큐가 비어있습니다.");
        }
        
        return front.Data;
    }

    public bool IsEmpty()
    {
        return size == 0;
    }

    public int Size()
    {
        return size;
    }
}

• Enqueue: 큐가 비어있다면 새로 생성한 노드를 front, rear로 설정
• Dequeue: front의 데이터를 반환, front의 Next를 다음 front로 지정 (+하나만 남았다면 rear로 설정)
• Peek: front의 data를 반환
• IsEmpty: 큐가 비어있는지 확인
• Size: size 반환

 

노드 기반 큐의 장점

• 동적 크기: 메모리를 효율적으로 사용하며 크기 제한이 없다.
• 삽입/삭제 효율성: 포인터만 변경하면 되므로 O(1) 시간 복잡도를 가진다.
• 메모리 관리: 필요한 만큼만 메모리를 사용하여 메모리 낭비가 적다.

---

 

 

 

 

 

우선순위 큐

우선순위 큐는 일반적인 큐와 비슷하지만, 각 요소가 우선순위를 가지고 있어 우선순위가 높은 요소가 먼저 처리되는 자료구조이다.

우선순위 큐 직접 구현

public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> heap = new List<T>();
    
    public void Enqueue(T item)
    {
        heap.Add(item);
        int currentIndex = heap.Count - 1;
        HeapifyUp(currentIndex);
    }

    public T Dequeue()
    {
        if (heap.Count == 0)
        {
            throw new InvalidOperationException("우선순위 큐가 비어있습니다.");
        }

        T root = heap[0];
        int lastIndex = heap.Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);

        if (heap.Count > 0) HeapifyDown(0);

        return root;
    }

    private void HeapifyUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (heap[index].CompareTo(heap[parentIndex]) >= 0) break;

            Swap(index, parentIndex);
            index = parentIndex;
        }
    }

    private void HeapifyDown(int index)
    {
        int lastIndex = heap.Count - 1;
        while (true)
        {
            int smallest = index;
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;

            if (leftChild <= lastIndex && heap[leftChild].CompareTo(heap[smallest]) < 0) smallest = leftChild;
            if (rightChild <= lastIndex && heap[rightChild].CompareTo(heap[smallest]) < 0) smallest = rightChild;

            if (smallest == index) break;

            Swap(index, smallest);
            index = smallest;
        }
    }

    private void Swap(int i, int j)
    {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public int Count => heap.Count;
    public bool IsEmpty => heap.Count == 0;
}

• Enqueue: 힙의 마지막에 새로운 데이터를 추가, 추가된 요소의 위치를 조정
  • HeapifyUp: 부모와 비교하여 자신이 작다면 부모와 교체
• Dequeue: 가장 앞의 요소(heap[0])을 제거 후 반환, 가장 마지막 요소를 가장 앞으로 임시로 배치한 후 위치 조정
  • HeapifyDown: 자식 중 작은 자식과 교체하며 자리를 찾음
• Swap: i, j번째 요소를 교환

 

HeapifyUp, HeapifyDown은 우선순위 큐의 정렬 기준에 따라 다르게 적용해도 된다.

현재는 작은 수가 가장 우선순위가 높게 되는 최소 힙이다.

---

 

 

 

 

 

MaxHeap Visualization

우선순위 큐에서 사용하는 Heap을 유니티를 통해 visualization 해보자.

결과물은 다음과 같다.

이를 구현하는데 필요한 것이 여러 개 있다.

• 데이터를 나타낼 노드
• 노드를 연결할 라인
• 이를 관리하고 생성해 주는 매니저
• 입력을 받을 UI

 

우선, 노드를 Prefab으로 제작해 보자.

우선, 라인보다는 앞에 출력되어 라인에 겹쳐지지 않도록 해야 하기 때문에, Z포지션을 -1로 설정하여 카메라에 더 가깝게 설정한다.

Sprite Renderer를 추가하여 Sprite가 보일 수 있게 준비한다.

이때, Sprite의 Texture를 설정해 주어야 제대로 출력된다.

데이터를 표현할 TMP의 Z포지션을 SpriteRenderer보다 더 작게 설정해야 화면에 보인다.

 

이제 Line을 Prefab으로 만들어 보자.

Positions을 조절해 Line의 두께를 설정할 수 있다.

만약, 색을 조절하고 싶다면 Materials를 설정하면 된다.

 

두 Prefab을 모두 생성했다면 이제 Node를 관리하기 위한 Script를 만들어 보자.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using TMPro;

public class HeapNode : MonoBehaviour
{
    public TextMeshPro valueText;
    public SpriteRenderer nodeSprite;
    public bool bMoveEnded;

    IEnumerator MoveToPosition(Vector3 targetPos)
    {
        var oldPos = transform.position;
        float time = 0f;
        float duration = 0.3f;
        
        while (time <= duration)
        {
            transform.position = Vector3.Lerp(oldPos, targetPos, time/duration);
            time += Time.deltaTime;
            
            yield return null;
        }

        bMoveEnded = true;
        transform.position = targetPos;
    }

    public void SetValue(int value)
    {
        valueText.text = value.ToString();
    }

    public void MoveTo(Vector3 position)
    {
        StartCoroutine(MoveToPosition(position));
    }
}

MoveToPosition은 Node에 Animation을 추가하기 위한 코루틴이다.

 

이제 노드와 라인을 관리할 매니저 클래스를 제작해 보자.

우선, MaxpHeap을 구현한 뒤 매니저 클래스를 만드는 것이 좋다.

public class MaxHeap
{
    private int[] heap;
    private int size;
    private int capacity;
    
    public System.Action<int[]> OnHeapUpdated;

    public MaxHeap(int capacity)
    {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    private int Parent(int index) => (index - 1) / 2;
    private int LeftChild(int index) => 2 * index + 1;
    private int RightChild(int index) => 2 * index + 2;

    public void Insert(int value)
    {
        if (size >= capacity)
        {
            throw new System.InvalidOperationException("힙이 가득 찼습니다.");
        }

        heap[size] = value;
        int current = size;
        size++;

        // 부모보다 큰 값이면 위로 이동 (최대 힙으로 변경)
        HeapifyUp(current);
        
        OnHeapUpdated?.Invoke(GetHeapArray());
    }

    private void HeapifyUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = Parent(index);
            // 현재 노드가 부모 노드보다 크면 교환 (부등호 방향 변경)
            if (heap[index] > heap[parentIndex])
            {
                Swap(index, parentIndex);
                index = parentIndex;
            }
            else
            {
                break;
            }
        }
    }

    private void HeapifyDown(int index)
    {
        int largest = index;
        int left = LeftChild(index);
        int right = RightChild(index);

        // 왼쪽 자식이 더 큰 경우 (부등호 방향 변경)
        if (left < size && heap[left] > heap[largest])
        {
            largest = left;
        }

        // 오른쪽 자식이 더 큰 경우 (부등호 방향 변경)
        if (right < size && heap[right] > heap[largest])
        {
            largest = right;
        }

        if (largest != index)
        {
            Swap(index, largest);
            HeapifyDown(largest);
        }
    }

    public int ExtractMax()  // ExtractMin에서 ExtractMax로 이름 변경
    {
        if (size <= 0)
        {
            throw new System.InvalidOperationException("힙이 비어있습니다.");
        }

        int max = heap[0];  // max로 변수명 변경
        heap[0] = heap[size - 1];
        size--;

        if (size > 0)
            HeapifyDown(0);

        OnHeapUpdated?.Invoke(GetHeapArray());
        
        return max;
    }

    private void Swap(int i, int j)
    {
        (heap[i], heap[j]) = (heap[j], heap[i]);
    }

    public int[] GetHeapArray()
    {
        int[] currentHeap = new int[size];
        System.Array.Copy(heap, currentHeap, size);
        return currentHeap;
    }

    public int GetMax() => size > 0 ? heap[0] : throw new System.InvalidOperationException("힙이 비어있습니다.");
    public int GetSize() => size;
    public bool IsEmpty() => size == 0;
}

 

MaxHeap이 위에서 구현한 우선순위 큐와 크게 다르지 않다.

중요한 부분은 다음 부분이다.

public System.Action<int[]> OnHeapUpdated;

이는 C#에서 제공하는 Action이라는 델리게이트이다.

이는 int[]타입의 변수를 담은 델리게이트를 의미한다.

사용 시에는 다음과 같이 하면 된다.

OnHeapUpdated?.Invoke(GetHeapArray());

GetHeapArray()라는 함수에서는 현재 힙을 배열로 변환하여 반환해 준다.

이를 델리게이트에 넣어 Invoke하면 이를 구독한 함수들이 실행된다.

이는 앞서 말한 매니저 클래스에서 구독할 예정이다.

해당 델리게이트는 힙이 업데이트되었을 때 발동시킨다.

이제, 매니저 클래스를 봐보자.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;

public class HeapVisualizer : MonoBehaviour
{
    public GameObject nodePrefab;
    public Transform nodesContainer;
    public Button insertButton;
    public Button extractButton;
    public TMPro.TMP_InputField inputField;
    public LineRenderer lineRendererPrefab;  // 노드 간 연결선을 그리기 위한 프리팹

    private List<HeapNode> nodes = new List<HeapNode>();
    private List<LineRenderer> lines = new List<LineRenderer>();
    private MaxHeap heap;
    
    private float horizontalSpacing = 3f;
    private float verticalSpacing = 2f;
    private Vector2 rootPosition = new Vector2(0, 0);

    private void Start()
    {
        heap = new MaxHeap(15);
        heap.OnHeapUpdated += UpdateHeapVisualization;
        
        insertButton.onClick.AddListener(() => {
            if (int.TryParse(inputField.text, out int value))
            {
                InsertWithVisualization(value);
                inputField.text = "";
            }
        });

        extractButton.onClick.AddListener(ExtractMinWithVisualization);
    }

    private void InsertWithVisualization(int value)
    {
        GameObject nodeObj = Instantiate(nodePrefab, nodesContainer);
        HeapNode node = nodeObj.GetComponent<HeapNode>();
        node.SetValue(value);
        nodes.Add(node);

        heap.Insert(value);
    }

    private void ExtractMinWithVisualization()
    {
        if (nodes.Count > 0)
        {
            nodes[0].Highlight();
            Destroy(nodes[0].gameObject);
            nodes.RemoveAt(0);

            heap.ExtractMax();
        }
    }

    // HeapVisualizer.cs의 UpdateHeapVisualization 메서드를 수정
    private void UpdateHeapVisualization(int[] heapArray)
    {
        // 기존 노드들의 GameObject 제거
        foreach (var node in nodes)
        {
            if (node != null)
                Destroy(node.gameObject);
        }
        nodes.Clear();

        // 힙 배열의 각 요소에 대해 새 노드 생성
        for (int i = 0; i < heapArray.Length; i++)
        {
            GameObject nodeObj = Instantiate(nodePrefab, nodesContainer);
            HeapNode node = nodeObj.GetComponent<HeapNode>();
            node.bMoveEnded = false;
            node.SetValue(heapArray[i]);
            nodes.Add(node);
            node.MoveTo(CalculateNodePosition(i));
        }

        StartCoroutine(UpdateLines());
    }

    private Vector3 CalculateNodePosition(int index)
    {
        int level = Mathf.FloorToInt(Mathf.Log(index + 1, 2));
        int levelStartIndex = (1 << level) - 1;
        int positionInLevel = index - levelStartIndex;
        int nodesInLevel = 1 << level;
    
        float xPos = (positionInLevel - (nodesInLevel - 1) / 2.0f) * horizontalSpacing;
        float yPos = -level * verticalSpacing;
    
        return new Vector3(xPos, yPos, 0);
    }

    private IEnumerator UpdateLines()
    {
        // 기존 라인 제거
        foreach (var line in lines)
        {
            if (line != null)
                Destroy(line.gameObject);
        }
        lines.Clear();
        
        yield return new WaitUntil(() =>
        {
            bool bEnded = true;
            foreach (var node in nodes)
            {
                if (node.bMoveEnded == false)
                {
                    bEnded = false;
                    break;
                }
            }

            return bEnded;
        });

        // 새로운 라인 생성
        for (int i = 0; i < nodes.Count; i++)
        {
            int leftChild = 2 * i + 1;
            int rightChild = 2 * i + 2;

            if (leftChild < nodes.Count)
            {
                LineRenderer line = Instantiate(lineRendererPrefab, nodesContainer);
                Vector3 startPos = nodes[i].transform.position;
                Vector3 endPos = nodes[leftChild].transform.position;
            
                line.positionCount = 2;
                line.SetPosition(0, startPos);
                line.SetPosition(1, endPos);
                line.startWidth = 0.1f;
                line.endWidth = 0.1f;
                lines.Add(line);
            }

            if (rightChild < nodes.Count)
            {
                LineRenderer line = Instantiate(lineRendererPrefab, nodesContainer);
                Vector3 startPos = nodes[i].transform.position;
                Vector3 endPos = nodes[rightChild].transform.position;
            
                line.positionCount = 2;
                line.SetPosition(0, startPos);
                line.SetPosition(1, endPos);
                line.startWidth = 0.1f;
                line.endWidth = 0.1f;
                lines.Add(line);
            }
        }
    }

    private void CreateLine(int parentIndex, int childIndex)
    {
        LineRenderer line = Instantiate(lineRendererPrefab, nodesContainer);
        line.positionCount = 2;
        line.SetPosition(0, nodes[parentIndex].transform.position);
        line.SetPosition(1, nodes[childIndex].transform.position);
        lines.Add(line);
    }

    private void OnDestroy()
    {
        if (heap != null)
            heap.OnHeapUpdated -= UpdateHeapVisualization;
    }
}

대부분 시각화에 대한 함수라 크게 신경 쓰지 않아도 된다.

단, 데이터를 추가하고 삭제하는 부분만 주의 깊게 봐 보자.

우선, 추가는 Start함수에서 등록한 람다에 의해 실행된다.

insertButton.onClick.AddListener(() => {
    if (int.TryParse(inputField.text, out int value))
    {
        InsertWithVisualization(value);
        inputField.text = "";
    }
});

insertButton이 눌렸다면 inputField에 있는 text를 int로 변환하여 InsertWithVisualization이라는 함수를 실행한다.

InsertWithVisualization에서는 앞서 제작한 노드 Prefab을 이용하여 새로운 노드를 생성한 뒤 노드 List에 추가한다.

그리고 heap에도 추가하는데 이때 힙에서는 데이터가 추가되어 델리게이트를 발동시킨다.

델리게이트가 발동된다면  Start함수에서 등록해 놓은 Callback함수가 실행된다.

//Callback 함수 등록
heap.OnHeapUpdated += UpdateHeapVisualization;

Callback으로 실행되는 UpdateHeapVisutalization함수에서는 기존에 생성해 놓은 노드 오브젝트를 모두 삭제하고 노드 List에 있는 모든 노드를 다시 오브젝트로 생성하여 각자의 위치로 이동시킨다.

이때, 코루틴을 이용하여 노드가 움직이는 애니메이션을 실행할 수 있다.

만약, 코루틴을 사용한다면 UpdateLine이라는 함수가 제대로 동작하지 않는다.

왜냐하면, UpdateLine에서는 모든 노드가 제자리에 있다고 가정한 상태에서 진행된다.

하지만, 코루틴이 추가되면 하직 노드가 자리 잡기 이전에 라인을 그리려 한다.

이를 해결하기 위해 UpdateLine에도 코루틴을 적용시켜 모든 노드가 자리 잡기까지 대기하도록 설정한다.

yield return new WaitUntil(() =>
{
        bool bEnded = true;
    foreach (var node in nodes)
    {
        if (node.bMoveEnded == false)
        {
            bEnded = false;
            break;
        }
    }

    return bEnded;
});

 

이제 삭제하는 로직을 봐 보자.

private void ExtractMinWithVisualization()
{
    if (nodes.Count > 0)
    {
        Destroy(nodes[0].gameObject);
        nodes.RemoveAt(0);

        heap.ExtractMax();
    }
}

0번 노드를 삭제한 뒤 heap을 변화시킨다.

그렇다면 추가하는 로직과 동일하게 델리게이트에 의해 노드와 라인을 업데이트하는 Callback이 실행된다.

---

 

 

 

 

 

오브젝트 풀링

게임에서 자주 생성되고 파괴되는 오브젝트(예: 총알, 파티클 효과)를 효율적으로 관리하기 위해 오브젝트 풀링 시스템을 구현할 때 큐를 사용할 수 있다.

오브젝트 생성, 삭제는 Instantiate / Destroy를 사용한다.

하지만, 비용이 많이 발생하기 때문에 만약 자주 사용되는 오브젝트라면 풀링 해두었다가 필요할 때 꺼내 쓰는 것이 유리하다.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ObjectPool : MonoBehaviour
{
    public GameObject prefab;
    public int poolSize = 10;
    public int CreateCount;

    private Queue<GameObject> objectPool = new Queue<GameObject>();
    public List<GameObject> objects = new List<GameObject>();

    void Start()
    {
        for (int i = 0; i < poolSize; i++)
        {
            GameObject obj = Instantiate(prefab);
            obj.SetActive(false);
            objectPool.Enqueue(obj);
        }
    }

    public GameObject GetPooledObject()
    {
        if (objectPool.Count > 0)
        {
            GameObject obj = objectPool.Dequeue();
            obj.SetActive(true);
            return obj;
        }
        else
        {
            for (int i = 0; i < poolSize; i++)
            {
                GameObject obj = Instantiate(prefab);
                obj.SetActive(false);
                objectPool.Enqueue(obj);
            }

            return objectPool.Dequeue();
        }
        return null;
    }

    public void ReturnToPool(GameObject obj)
    {
        obj.SetActive(false);
        objectPool.Enqueue(obj);
    }
    
    void Update()
    {
        if (Input.GetKeyDown(KeyCode.Space))
        {
            for (int i = 0; i < CreateCount; i++)
            {
                float x = Random.Range(-100, 100);
                float y = Random.Range(-100, 100);
                float z = Random.Range(-100, 100);

                var go = GetPooledObject();
                go.transform.position = new Vector3(x, y, z);
                objects.Add(go);
            }
        }
        else if (Input.GetKeyDown(KeyCode.Delete))
        {
            for (var i = 0; i < objects.Count; i++)
            {
                ReturnToPool(objects[i]);
            }
            
            objects.Clear();
        }
    }
}

하지만, 풀링을 통한 객체관리는 메모리를 차지하게 된다는 점을 유의해야 한다.

---

 

 

 

 

 

애니메이션 리타게팅

메시를 다운로드하여서 임포트 한 다음 Rig로 가면 Generic 하고 Humanoid가 대표적으로 사용된다.

애니메이션을 리타겟팅할때는 보통 Humanoid를 사용하고(인간형 타입) 그 외에는 Generic을 사용한다.

 

리타게팅하는 방법을 알아보자.

애니메이션이 있는 에셋에서 Rig을 Humanoid로 설정한 후 Apply를 누르면 Avatar가 생긴다.

Avatar의 본을 설정할 수도 있다.

 

이를 프리팹화 시키면 자동으로 Animator가 붙는다.

Animator Controller를 생성해서 Controller에 넣어준다.

 

fbx에 들어있는 애니메이션을 클릭하고 컨트롤+d를 누르면 애니메이션이 밖으로 빠진다.

해당 애니메이션을 애니메이터에 넣으면 리타게팅되어 애니메이션 실행이 가능하다.

---