Kim Geon Woo Unreal Client

프로젝트를 진행하기 전에 내가 어떤 프로젝트를 만들고 어떤 기능을 구현할까.. 라고 생각을 하던 도중

제가 플레이 했던 FPS게임 중 벽이 파괴되어 사실적인 전투를 묘사할 수 있는 게임이 있었습니다.

이러한 기능들을 프로젝트를 진행할 때 구현하고싶어 다양한 방법을 찾아보았습니다.

해당 기법은 Destructible Mesh라고 부르며, 다양한 방법들이 있었습니다.

이번 포스팅에서는 블루프린트를 사용해 구현한 파괴가능한 메시들에 대해 알아보겠습니다.

Destructible Mesh

• 물리적으로 파괴 가능한 3D 모델
• 특정 이벤트에 의해 분해, 재구성되는 특성을 가진다
• 충격, 폭발, 물리적 충돌 등을 통해 모델이 분해되는 방식으로 구현된다
• 파괴된 상태는 메모리에 저장되어 게임 내 파괴된 물체를 다시 불러오는 작업을 할 수 있다.

장점 및 단점

• 플레이어가 물체를 파괴할수있어 게임 내 몰입감을 높이고 물리적 상호작용을 더 다양한 방식으로 표현할 수 있다.
• 런타임 환경에서 파괴하여 플레이 시 생동감있는 표현을 보여줄 수 있다.
• 나무, 금속, 유리 등 각기 다른 재질들의 파괴방식을 다르게 구현하는데 있어 설계의 난이도가 높다.
• 파괴 시 계산하는 작업에 있어 메모리 사용량이 증가하며 성능에 영향을 줄 수 있다.

Dynamic Mesh Component

• 동적 변형이 가능한 메쉬
• 런타임 환경에서 물리적 충격, 폭발 등으로 해당 메쉬를 동적으로 변경할 수 있다 - 1
• 파괴된 조각들이나 물리적 충돌을 처리하는 방식에 있어 성능 최적화가 가능하다.
• 해당 물체의 각 부분을 세밀하게 제어할 수 있기때문에 물리적 처리를 더 디테일하게 조절할 수 있다.
• 런타임 환경에서 실시간 렌더링을 하는 과정 중 성능에 문제가 생길 수 있다 - 2

Dynamic Mesh Actor을 사용한 블루프린트 클래스 내 구현

1. BeginPlay

Allocate Compute Mesh : 동적 메쉬의 메모리 할당 및 변형 처리를 담당한다.

Append Sphere Box : Sphere와 Box 두 가지 다른 형태의 충돌 영역을 하나로 결합하며, Sphere와 Box가 충돌될 경우를 처리하기 위해 사용한다.

2.OnRebuildGenerateMesh

OnRebuildGeneratedMesh : 동적 메쉬가 재구성 시 발생하는 이벤트

Append Box : 여러개의 박스 충돌 영역을 결합하여 충돌범위를 최적화 하는데 사용한다.

Enable Complex as Simple Collision : 복잡한 메쉬 충돌들을 단순한 충돌체로 대체한다. 복잡한 Dynamic Mesh 모델에 대한 물리적 계산을 더 빠르게 처리할 수 있다.

3. Destruction(인터페이스)

Break Hit Result : Collision 발생 시 그것에 대한 정보들을 가지고 있는 구조체

• Location : 충돌이 발생한 위치
• Normal : 충돌 지점에서의 법선 벡터
• Impact Point : 충돌이 발생한 좌표
• Impact Normal : 충돌 지점에서 물체의 표면 법선
• Hit Actor : 충돌한 액터
• Hit Component : 충돌한 컴포넌트

Apply Mesh Boolean : Boolean 연산을 메쉬에 적용하는데 사용되는 함수로 메쉬의 결합, 차집합, 교집합의 작업을 설정할 수 있다.

• Union : 두 메쉬가 겹치는 부분을 포함한 전체 메쉬를 생성한다.
• Subtract : 한 메쉬에서 다른 메쉬의 영역을 빼고 남은 부분을 생성한다.
• Intersection : 두 메쉬가 겹치는 부분만을 포함하는 새로운 메쉬를 생성한다.

https://link.springer.com/article/10.1007/s11042-022-13049-x

개요

개발자로써 취업을 하는 과정에서 다양한 회사들이 코딩테스트를 보는 경우가 많습니다.

코딩테스트는 알고리즘과 자료구조에 많이 관련이 되있는데, 취업시의 코딩 테스트를 제외하고서도

시간 복잡도를 이해해야 하는 이유는 알고리즘을 빠르게 분석 및 상황에 맞춰 써야 할 알고리즘을 파악, 자신의 코드를 평가 할 수 있기 때문에 시간 복잡도를 이해를 해야합니다.

요약하자면, 효율적인 코딩을 하려면 자료구조와 알고리즘을 필수적으로 잘 다뤄야 한다고 볼 수 있습니다.

그러기 위해서 알고리즘의 최적화된 사용법을 알아야하는데, 그중 시간복잡도와 공간복잡도에 대해 알아보려고 합니다.

1. 시간 복잡도

입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며, 주요 로직의 반복횟수를 중점으로 측정된다.

시간복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하며, 알고리즘을 위해 필요한

연산의 횟수 또한 의미합니다.

※ 시간 복잡도의 빠르다, 느리다 라는 시간적인 의미를 두지 않는 이유는 각각의 하드웨어마다 차이가 있는점과

같은 하드웨어 더라도 사용중인 메모리의 상태에 따라 시간값이 달라지기 때문입니다.

2. 공간 복잡도

입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리의 양을 의미합니다.

예시로는 변수를 선언 또는 요소들을 담을 공간(자료구조)들이 전부 메모리에 들어가는데, 이것을 공간 복잡도라고 할 수 있습니다.

3. 시간 복잡도와 공간 복잡도의 연관 관계

시간 복잡도는 알고리즘에서 입력 크기에 따라 알고리즘의 실행시 걸리는 연산의 횟수를 의미하며,

공간 복잡도는 입력 크기에 대해 알고리즘의 실행시 필요한 메모리 양을 의미합니다.

일반적으로 메모리 연산 횟수를 줄이기 위해(시간 복잡도)서 더 많은 메모리 공간(공간 복잡도)을 사용 하거나,

반대로 메모리 사용을 최소화 하기위해 메모리 연산이 증가하는 경향이 있습니다.

두 복잡도는 알고리즘의 다양한 요인에 의해 영향을 받을 수있으며, 한 측면이 향상되면 한 측면이 저하될 수 있습니다.

이것을 트레이드 오프 (Trade-off)관계라고 합니다.

결론적으로, 시간 복잡도와 공간 복잡도는 알고리즘의 성능에 대해 각각 연산횟수, 메모리 사용량을 나타낼 수 있으며

상황에 따라 시간 복잡도와 공간 복잡도의 우선도를 고려하거나, 시간 복잡도와 공간 복잡도를 동시에 고려 해야합니다.

4. Big O 표기법

빅오(Big-O) 표기법은 시공간 복잡도를 수학적으로 표시하는 표기법중 가장 대표적인 방법입니다.

빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간을 고려할 수 있습니다.

표기법의 방식은 가장 빠르게 증가하는 항만을 고려하는 방식이며, 인풋 데이터 증가율에 따른 알고리즘 성능을

논리적으로 예측하기 위해 사용합니다.

• 가장 빠르게 증가하는 항만을 고려한다. 즉, 가장 높은 차수만 남기는 방식을 취한다.
• 빅오는 점근선의 상한 범위를 찾는 것이다.
• 작은 N이나 상수 인자는 고려하지 않는다.

• 빅오  표기법에서 n이란 입력되는 데이터 (Data Input)을 나타냅니다.

시간 복잡도 성능 비교에 따라 

O(1) < O(㏒ N) < O(N) < O(N ㏒ N) < O(N²) < O(2ⁿ)

상수 함수 < 로그 함수 < 선형 함수 < 다향 함수 < 지수 함수 

순이며, 오른쪽으로 갈수록 효율이 떨어집니다.

Big-O 표기법의 종류와 예제

1. O(1) - 상수

입력 데이터의 크기에 상관없이 동일한 수의 연산이 필요하며 즉시 출력값을 얻어낼 수 있는것을 의미합니다.

대표적으로는 자료구조 Stack의 Push, Pop이 있습니다.

Stack, Queue

해당 이미지는 각각 Stack과 Queue의 내부 구조입니다.

Stack을 예시로 할 경우 pop함수를 사용하여 저장해둔 값을 꺼내오는데, 이때 pop의 특성은 Stack의 가장 마지막에 들어온 데이터를리턴하며, 삭제하는 구조로 가장 최상위 데이터 하나를 제외한 다른 탐색은 하지않고 즉시 출력값을 얻어낼 수 있습니다.

2. O(log N) - 로그

입력 데이터의 크기가 커질수록 처리 시간이 log만큼 짧아지는 경우에 log 시간을 표현합니다. 대표적인 예시로 BST(Binary Search Tree)가 있으며, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기때문에 데이터 개수가 절반씩 줄어든 다는 점, 2배로 늘어나도 나뉘는 수가 1개 더 늘어날 뿐인 점에서 O(log N)이라 표현할 수 있습니다.

이진탐색트리 (BST)

해당 이미지는 이진탐색트리의 예시이며, 탐색하려는 값을 왼쪽에 있는 Branch 부터 비교, 탐색하는 형태로 이루어져 있는 자료구조입니다. BST는 하나의 branch로 치우쳐진 경우 O(n)을 될 수 있지만, 일반적으로는 트리의 높이 h에 따른 최대 노드의 수는 2^h - 1의 개수를 가질 수 있으며, 이로인해 O(log N)이라 표현할 수 있습니다.

3. O(N) - 선형

입력값이 증가함에 따라 시간또한 비례해서 증가합니다. 

대표적인 예시로 조건의 값이 참이 될때까지 증감연산을 하는 for문이 있습니다.

4. O(N log N) - 선형 로그

입력 데이터가 많아질수록 처리 시간이 로그 배만큼 늘어납니다.

대표적인 예시로 퀵 정렬(Quick Sort), 병합정렬(Merge Sort), 힙 정렬(Heap Sort)가 있습니다.

병합정렬의 예시

병합정렬 시간복잡도 예시

병합정렬 (Merge Sort)의 경우 List,Array 등의 저장된 값을 절반씩 나누어 번호순, 사전순과 같이 정해진 순서대로 정렬하는 알고리즘입니다.

정렬된 두 집합을 하나의 정렬된 집합으로 합치는데에 필요한 시간복잡도가 O( 두 집합의 원수의 개수),

그리고 분할 정복을 이용하여 병합정렬을 구현하면 총 시간복잡도가 O(N log N)입니다.

5. O(N²) - 다항

2차 복잡도 라고 부르기도하며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비례하여 증가하는 것을 의미합니다.

대표적인 예시로는 루프 안에서의 루프를 실행하는 이중 for 문이 있습니다.

6. O(2ⁿ) - 지수

기하급수적 복잡도 라고 불리기도하며, Big-O 표기법중 가장 느린 시간 복잡도를 가지고 있습니다.

데이터의 양이 많아질수록 처리시간이 기하급수적으로 증가합니다.

대표적인 예시로는 피보나치 수열이 있습니다.

정리

시간 복잡도는 메모리가 실행되는데 걸리는 시간이 아닌, 메모리의 연산 횟수를 의미한다.

공간 복잡도는 메모리의 사용량을 의미한다.

시간 복잡도와 공간 복잡도는 서로 반비례 형태로 이루어져 있으며,알고리즘의 성능을 최적화 하기위해

두 복잡도를 고려해야한다.

복잡도의 표기법에는 대표적으로 최악의 상황을 고려하는 빅오 (Big-O)표기법이 있으며 

사용하는 데이터의 개수와 소모되는 시간에 따라 미분, 적분형식의 그래프 형태를 나타내기도한다.

출처 및 참고 자료

내일배움캠프를 통한 C++ 학습 과정 중 인터페이스를 사용한 다형성 및 캡슐화를 다루는 미니과제가 있었습니다.

UML 클래스 다이어그램 과정은 이렇습니다.

해당 다이어그램에서 인터페이스 Animal을 상속받는 Dog,Cat,Cow 클래스와,

Animal 객체들을 생성, 메서드 호출을 담당하는 Zoo클래스가 있습니다.

해당 다이어그램을 보았을 때 Zoo::addAnimal 메서드의 매개변수들을 전달하기 위해서는 Main 클래스에서 

Animal의 구현클래스들을 선언하는 구조가 되어있었습니다.

다형성 및 캡슐화를 중점으로 다루는 해당 과제에서 어떤 디자인 패턴이 어울리는지 찾아보던 도중, 팩토리 메서드 패턴을 적용하여 매개변수를 전달하는것이 가장 어울리는 것 같아 팩토리 메서드 패턴에 대한 포스팅을 하게 되었습니다.

이번 포스팅에서는 팩토리 메서드 패턴의 정의 및 특징, 그리고 장단점에 대해 알아보겠습니다.

Factory Method Pattern(팩토리 메서드 패턴)

• 객체 생성을 공장(Factory) 클래스로 캡슐화 처리하여 대신 생성하게 하는 생성 디자인 패턴
• 새로운 제품(클래스)를 추가 시에도 서브클래스만 추가하면 된다. -> 유지보수성 및 유연성이 높다.
• 구체적인 클래스에 의존하지 않아 결합도를 낮추고 확장성을 높일 수 있다.

장점 및 단점

• 기존의 코드에 영향을 미치지 않으면서, 새로운 서브 클래스만 추가하면 된다.
• 객체 생성에 대한 세부사항을 캡슐화 하여 유지보수성을 향상시킨다.
• 객체 생성 방식이 변경되어도 클라이언트는 영향을 받지 않는다.
• 객체 생성이 여러 단계의 추상화로 이루어지기때문에, 불필요한 복잡성이 높아질 수 있다.

사용 예시

해당 사용 예시는 미니 과제를 중점으로 제작하였으며, Simple Factory Pattern으로 구현되었습니다.

해당 사유는 미니 과제를 중점이며 동시에 캡슐화를 사용한 정보은닉을 목적으로 하며 동시에 직관적으로 표현하기 위해서입니다.

팩토리 메서드 패턴으로 변형을 하려면 createAnimal 메서드를 추상화 하여 하위 클래스에서 구현 및 각 Animal 클래스들의 생성부분을 구현해야합니다.

Factory

Factory에서는 클라이언트에서 AnimalType을 매개변수로 받아 그에 맞는 객체 생성을 담당합니다.

class AnimalFactory
{
public:
	static Animal* createAnimal(const AnimalType& type);
};

Animal* AnimalFactory::createAnimal(const AnimalType& type)
{
	switch (type)
	{
	case DOG:
		return new Dog;
		break;
	case CAT:
		return new Cat;
		break;
	case COW:
		return new Cow;
		break;
	default:
		throw std::invalid_argument("AnimalType Eroor");
		break;
	}
}

Client

	// 재사용성 고려 보다는 협업 시 명확한 의도를 전달하기 위해 열거형을 사용했습니다.
	switch (randNum)
	{
	case DOG:
		return AnimalFactory::createAnimal(AnimalType::DOG);
		break;
	case CAT:
		return AnimalFactory::createAnimal(AnimalType::CAT);
		break;
	case COW:
		return AnimalFactory::createAnimal(AnimalType::COW);
		break;
	default:
		break;
	}

팩토리클래스의 createAnimal는 전역 함수이기때문에 해당 팩토리의 객체를 생성하지않고 호출할 수 있게 구현하였습니다.

정리

• 객체 생성을 Factory 클래스로 캡슐화 처리하여 해당 객체를 대신 생성하는 디자인 패턴.
• 객체 생성에 대한 세부사항을 캡슐화하여 유지보수성 향상 및 정보은닉성을 향상시킨다.
• 기존의 코드에 영향을 미치지 않으며, 수정시 새로운 서브클래스만 추가하면 된다.
• 하나의 Factory에서 생성을 담당한다 - Simple Factory Pattern
• 상위 Factory 클래스를 인터페이스화, 하위 클래스에서 구현한다 - Factory Method Pattern