서리 개인 개발 블로그

1. 힙(Heap)

- 최대값 혹은 최소값을 빠르게 찾아낼 수 있도록 고안된 완전이진트리 자료구조이다.

- 부모노드와 자식노드의 키 값 사이에 대소관계가 성립해야하는 조건을 만족해야한다.

- 부모노드의 키 값이 자식노드의 키 값보다 큰 힙을 '최대 힙', 반대를 '최소 힙'이라 부른다.

- 힙의 시간복잡도는 log n이다.

- 위키 (힙 트리)

2. 코드

※ A-star pathfind에서 OpenList의 최소 F cost를 가진 노드를 가져오기 위해 적용한 Heap tree 코드이다.

※ 유튜브 영상에 있는 소스를 수정하여 사용했는데, 기존 코드는 배열을 사용하여 맵 사이즈만큼 할당하여 힙을 사용하고 있었다.

※ 그 결과, 실제로 맵 사이즈만큼의 할당이 필요없는데도 불구하고 많은 할당이 일어나 가비지가 많이 발생되므로 List로 변경하고 Capacity를 지정해줌. (만약의 경우 추가 할당이 필요한 경우가 있을 수 있으므로 List로 구성했다.)

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

public interface IHeapItem<T> : IComparable<T>
{
    int HeapIndex { get; set; }
}

public class HeapList<T> where T : class, IHeapItem<T>
{
    private List<T> m_items;
    public int Count => m_items.Count;
    public int Capacity => m_items.Capacity;

    public HeapList(int maxCapacity = 256)
    {
        m_items = new List<T>(maxCapacity);
    }

    public void Add(T item)
    {
        item.HeapIndex = m_items.Count;
        m_items.Add(item);
        SortUp(m_items[m_items.Count - 1]);
    }

    public void UpdateItem(T item)
    {
        SortUp(item);
    }

    private void SortUp(T item)
    {
        while(true)
        {
            int parentIndex = (item.HeapIndex - 1) / 2;
            T parentItem = m_items[parentIndex];

            if(item.CompareTo(parentItem) > 0)
            {
                Swap(item, parentItem);
            }
            else
            {
                break;
            }
        }
    }

    private void Swap(T itemA, T itemB)
    {
        m_items[itemA.HeapIndex] = itemB;
        m_items[itemB.HeapIndex] = itemA;

        int swapIndex = itemA.HeapIndex;
        itemA.HeapIndex = itemB.HeapIndex;
        itemB.HeapIndex = swapIndex;
    }

    public T GetRoot()
    {
        T rootItem = m_items[0];
        //List의 원소가 1개일 때 List.Count로 원소를 가져오면 에러가 발생하므로 index값을 저장한다.
        int lastIndex = m_items.Count - 1;

        m_items[0] = m_items[lastIndex];
        m_items[0].HeapIndex = 0;
        m_items.RemoveAt(lastIndex);

        SortDown(lastIndex);

        return rootItem;
    }

    private void SortDown(int lastIndex)
    {
        int currentIndex = 0;
        while(true)
        {
            int childLeft = currentIndex * 2 + 1;
            int childRight = currentIndex * 2 + 2;
            int swapIndex = currentIndex;

            //왼쪽 자식 노드 유무 확인
            if(childLeft < lastIndex)
            {
                swapIndex = childLeft;
                //오른쪽 자식 노드 유무 확인
                if(childRight < lastIndex)
                {
                    //양쪽 자식 노드가 존재하면 두 자식 노드의 값을 비교해서 swapIndex 결정
                    //FCost 비교해서 오른쪽 자식노드가 작으면 swapIndex를 childRight로 변경해준다.
                    if(m_items[childLeft].CompareTo(m_items[childRight]) < 0)
                    {
                        swapIndex = childRight;
                    }
                }

                //현재 노드와 자식노드의 값을 비교해서 Swap
                if(m_items[currentIndex].CompareTo(m_items[swapIndex]) < 0)
                {
                    Swap(m_items[currentIndex], m_items[swapIndex]);
                    currentIndex = swapIndex;
                }
                else
                {
                    return;
                }
            }
            else
            {
                return;
            }
        }
    }

    public bool Contains(T item)
    {
        return item.HeapIndex >= m_items.Count ? false : Equals(m_items[item.HeapIndex], item);
    }
}

• GetRoot()로 루트노드를 힙에서 빼면 말단노드를 Root로 이동 후, 정렬(Sort down)한다.
• 노드를 추가하면, 말단노드에 추가한 뒤 정렬(Sort up)해서 노드의 위치를 지정해준다.

2-1) 힙을 사용하는 노드의 코드 (CompareTo() 구현)

public class Node : IHeapItem<Node>
{
    private int m_hCost;
    private int m_gCost;
    private int m_heapIndex;
    public int HeapIndex { get => m_heapIndex; set => m_heapIndex = value; }
    public int FCost => m_hCost + m_gCost;

    //Heap tree용 compare구현
    public int CompareTo(Node other)
    {
        int compare = FCost.CompareTo(other.FCost);
        if (compare == 0)
        {
            compare = m_hCost.CompareTo(other.m_hCost);
        }

        //힙에서 작은수가 루트로 올라가야하므로 -를 붙여서 반환한다.
        return -compare;
    }
}

※ 참고 유튜브 (맵 사이즈 만큼 배열을 할당하는 힙)

https://youtu.be/3Dw5d7PlcTM

보통 카메라 흔드는 기능에 대해 구글링을 해보면 Random.insideUnitCircle이나 Sphere로 카메라를 흔드는 코드를 많이 볼 수 있었다. 그런데 이런식으로 구성을하면 끊기면서 흔들리는(?) 느낌이 강하게 들어서 좀 더 찾아보니 관련된 에셋이 몇개 있었는데 받아서 뜯어보니 Mathf.PerlinNoise라는 노이즈 함수를 이용해서 카메라를 흔드는것을 봤다.

에셋에서는 위치 및 회전값까지 변경해서 건드리고있었는데, 회전값까지 변경하는 코드는 카메라 흔들림이 너무 정신없어서 전부 빼고 x, y 좌표만 변경하는 방법으로 코드를 바꿨다.

※ Perlin noise (펄린노이즈)

- 단계적 텍스처를 만들기 위해 개발된 노이즈 함수, 지형(마인크래프트 등)을 생성할 때 이용한다고한다.

- 위키 링크 (영어)

- 유니티 링크 (영어)

코드

using System.Collections;
using UnityEngine;

public class CamShake : MonoBehaviour
{
    [SerializeField]
    private float m_roughness;      //거칠기 정도
    [SerializeField]
    private float m_magnitude;      //움직임 범위

    private void Update()
    {
        if(Input.GetKeyDown(KeyCode.Space))
        {
            StartCoroutine(Shake(1f));
        }
    }

    IEnumerator Shake(float duration)
    {
        float halfDuration = duration / 2;
        float elapsed = 0f;
        float tick = Random.Range(-10f, 10f);

        while (elapsed < duration)
        {
            elapsed += Time.deltaTime / halfDuration;

            tick += Time.deltaTime * m_roughness;
            transform.position = new Vector3(
                Mathf.PerlinNoise(tick, 0) - .5f,
                Mathf.PerlinNoise(0, tick) - .5f,
                0f) * m_magnitude * Mathf.PingPong(elapsed, halfDuration);

            yield return null;
        }
    }
}

※ roughness : 거칠기 정도, 카메라가 움직이는 동안 카메라의 떨림을 제어하는 수치이다. 값이 높아질수록 카메라가 움직이는 시간동안 많이 떨린다.

※ magnitude : 카메라 움직임 범위, 카메라가 움직이는 범위 수치이다.

※ tick : 펄린노이즈 함수에 들어갈 값이다. 초반에 랜덤으로 값을 설정하는 이유는 노이즈 함수에 들어가는 값을 다르게하기 위해서이다. (항상 같은 움직임으로 흔들게 하고싶으면 틱값을 랜덤이 아닌 고정값으로 초기화하면 된다.)

결과

유니티 에셋스토어에서 받은 모델에 베지어 커브로 움직이는 스크립트가 있었는데, 해당 스크립트를 Record기능으로 녹화를 하면 다음과 같은 에러가 발생했다.

- Invalid AABB

- Assertion failed on expression: 'IsFinite(distanceForSort)'

- Assertion failed on expression: 'IsFinite(distanceAlongView)'

구글링을 해봤는데 어떤 글에서는 모델의 문제라고 하고, 어떤 글에서는 Physics 설정문제라는 글이 보였는데..

나같은 경우엔 0으로 나눗셈을 하는데서 발생하는 에러였다.

베지어 커브 스크립트에 변수를 Time.deltaTime으로 나누는 코드가 있었는데, Time.deltaTime을 Record로 녹화를 시작하면 값이 0이되는것같다.

그래서 Time.deltaTime을 고정값으로 따로 수정하니 해당 에러가 발생하지 않고 정상적으로 작동했다.