[멋쟁이사자처럼 부트캠프 TIL회고] Unity 게임 개발 3기 18일차

Queue

개념

• 선입선출(First In First Out, FIFO) 개념을 따르는 자료구조

자주쓰는 연산

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

 

참고 : 

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.queue-1?view=net-8.0

Queue<T> 클래스 (System.Collections.Generic)

 

노드로 Queue 만들어보기

 

노드 기반 Queue의 장점

• 동적 크기 : 메모리의 효율적 사용, 크기 제한 없음
• 삽입/삭제 : O(1)의 시간 복잡도. (포인터만 변경하면 됨)
• 메모리 관리 : 필요한 만큼만 메모리를 사용함.

우선 노드를 정의해야 한다. 

우리는 노드를 데이터와 다음 노드를 갈리키는 연결을 가진 클래스로 정의하고

생성자를 만들어줄 것이다.

public class Node<T>
{
    public T Data { get; set; }
    public Node<T> Next { get; set; }

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

 

이제, 노드를 사용해 Queue 의 성질을 가진 NodeQueue<T> 클래스를 만들어본다.

필요한 것은 가장 마지막에 들어간 노드를 나타내는 rear, 가장 처음 들어간(오래된 노드)를 나타내는 front,

그리고 data 이다. 마찬가지로 생성자로 기본값을 할당해준다. 

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

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

 

기능들을 만들어줄 차례이다. 넣고자 하는 기능들은 위에에서 살펴본 기능들이다.

(Enqueue, Dequeue, Peek, IsEmpty)

 

Enqueue는 가장 위(rear) 값의 위에(뒤에) 데이터를 얹어 주는 것이라고 생각하면 편하다. 

자료구조상, node들의 Next 방향은 front에서 rear로 향하는 것이 편하다.

1. [ rear ] -> [ ] -> [front ]

2. [ rear ] <- [ ] <- [front ]

라는 방향이 다른 두 자료구조가 있다고 할 때, 새로운 노드를 추가하는 것은 상관없지만(둘 다 편하지만)

원래 있던 노드를 지우는 것(front) 이 2번이 더 편하다. 

 

그렇다면 우리가 만들어야 하는 Enqueue 구조는 다음과 같다.

1. 새로운 노드를 생성한다. 
2. 원래 있던 rear에서 새로운 노드로 Next를 연결한다
3. 새로운 노드를 rear라고 이름붙인다.

 public void Enqueue(T item)
    {
        Node<T> newNode = new Node<T>(item);
        
        if (IsEmpty())
        {
            front = newNode;
            rear = newNode;
        }
        else
        {
            rear.Next = newNode;
            rear = newNode;
        }
        size++;
    }

 

*노드가 비어 있을경우의 예외처리와 Count를 위한 size 늘림

 

Dequeue를 구현하기 위한 구조는 다음과 같다.

1. 반환하기 위한 데이터를 T data에 저장한다
2. front의 Next에 front 값을 할당한다.
3.  

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

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

        if (IsEmpty())
        {
            rear = null;
        }

        return data;
    }

*마찬가지로 예외처리와 size를 조절해줬다.

 

나머지 코드들은 다음과 같다.

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

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

    public int Size()
    {
        return size;
    }
}

 

오브젝트 풀링 시스템

• 자주 생성되고 파괴되는 오브젝트(총알 등)을 효율적으로 관리하기 위한 시스템
• 다음 예제는 비활성화된 오브젝트들을 저장하고 관리하는데 사용

// ObjectPool.cs

using UnityEngine;
using System.Collections.Generic;

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();
        }
    }
}

 

 매 번 똑같은 오브젝트들을 생성하고, 파괴하는 것보다. 미리 만들어둔 오브젝트들을 활성화 비활성화 하는 것이

성능측면에서 좋고, 메모리 낭비를 줄일 수 있다.

 

Heap

개념

• 완전 이진 트리의 일종으로, 우선순위 큐를 위해 만들어짐
• 최대 힙(max heap), 최소 힙(min heap) 이 있음, 각각 최댓값과 최솟값을 효율적으로 구하기 위한 방식
• 반정렬 상태(느슨한 정렬상태)
• 중복된 값 허용
• 완전이진트리 -> 비어있는 공간 x -> 배열로 구현하기 용이.

우선 그림을 보고 다시 보면 이해가 편하다.

참조 :
https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap

[자료구조] 그림으로 알아보는 힙(Heap)

 

우선순위 Queue

개념

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

사용 예제

• 게임 AI 행동 결정 : AI 캐릭터의 다양한 행동을 우선순위에 따라 실행
• 이벤트 시스템      : 게임 내 이벤트들을 중요도에 따라 처리
• 자원 관리             : 한정된 자원을 우선순위에 따라 할당
• 패스파인딩          : A* 알고리즘에서 다음 탐색할 노드 결정 ( A* 알고리즘이 뭐지)

구현

 

 우선, heap이라는 이름의 리스트로 만들어준다.

 

 min heap, 즉 최솟값이 가장 위에 올라와 표현되는 구조를 만들 것이다.

1. Enqueue로 데이터를 넣었을 때 부모객체와 크기를 비교해 작으면 올라가고, 아니면 그대로 있게 만듬

2. Dequeue로 데이터를 삭제했을 때, 데이터를 재정렬

  -1 제일 위 데이터가 바로 삭제되고 밑의 트리에서 데이터를 하나씩 올리는 과정보다, 데이터 하나를 맨 위에 집어넣고

      내릴 수 있을때까지 내리는 방식으로 데이터 재정렬

 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;
    }

Enqueue()는  데이터를 추가하고  HeapifyUP(currentIndex) 라는 함수를 통해 재정렬한다.

 

Dequeue()는 데이터를 저장하고, list의 끝에 있는 데이터를 0번 인덱스(트리의 맨 위) 부분에 올리고,

HeapifDown(0) 함수를 통해 재정렬한다.

 

HeapifUP(); 

1. index가 >0 인 동안 반복한다, 자식 인덱스를  부모 인덱스(( index-1)/2) 와 비교한다.
                                               -1 부모 데이터보다 작으면, 데이터를 뒤바꾸고
                                                    index를 parent의 인덱스로 할당한다
                                                   (재반복을 위한 인덱스 할당)
                                               -2 부모 데이터보다 크면 반복문 밖으로 나간다(break).

HeapifDown();

멈추기 전까지 계속 반복해야 하므로 while(true) 를 사용한다. (루프에 주의, 꼭 break로 탈출하기)

1. 새로운 변수 smallest를 만든다.( 교체할 인덱스를 지정해주기 위해)
2. 0부터 시작할 것이므로, 자식 인덱스를 구한다. 
                               -1 leftChild = index * 2 + 1 
                               -2 rightChild = index * 2 +2 
3. 인덱스의 데이터 값과, 자식 인덱스의 데이터 값을 비교한다. 
                                - 1 자식 인덱스의 데이터 값이 더 작다면, 자식 인덱스를 smallest로 지정한다.
                                - 2 leftChild와 rightChild를 모두 비교해 smallest를 찾는다.
                                 -3 만일 smallest가 원래 인덱스와 같다면, 반복문을 탈출한다(break).
4. 인덱스의 데이터 값과, smallest(자식 인덱스)의 데이터 값을 바꾼다.
5. 반복을 위해, smallest 인덱스를 index에 할당한다.

    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;
        }
    }

 

재정렬 과정에서 나온 swap은 편의를 위해 만들었다. 

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

 

추가적으로 람다식을 이용해 Count 함수도 만든다. 

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

 

속도가 살짝만 더 빨라지면 좋을지도... ? 주말이 있으니까 부족한 부분들이랑 개념들 공부 열심히 해놔야지..

코테도 입문 문제들은 다 푸는 것을 목표로 !