search

fkdl0048 / CodeReview

게임 개발자 관련 정보 모음집
5 stars 0 forks source link

UNSEEN: 온라인 TEST 정리 #27

Closed fkdl0048 closed 7 months ago

fkdl0048 commented 7 months ago

UNSEEN Online Test

언씬 온라인 테스트 준비를 위한 기록

서류 통과가 되고 이후에 온라인 TEST를 잘 보기 위해 정리한다.

개인적인 생각으로 지원서에 지원하게 된 이유와 포폴에 프로젝트를 기재했지만, 다 보지는 않았을 것 같다.

그리고 C++과 언리얼에 경험이 없음을 적었기 때문에 이후 온라인 TEST에서 C++과 언리얼에 대해서 출제 범위가 포함되어 있음은 약 5일간 공부를 하고 시험을 치러라는 의미로 해석된다.

즉, 교육 프로그램에 참여하기 전 개인적 학습 역량을 체크한다고 생각. (물론 알고 있는 부분이 있다면 유리)

기회는 준비된 사람만 잡기 때문에 늦게라도 정리하고 공부를 시작하려고 한다.

Online Test

지원서 심사를 통과한 사람들에 한해 개발 및 프로그래밍에 대한 이해와 역량을 판단하기 위해 온라인 TEST를 진행

TEST는 객관식, 주관식 혼합 유형이며, 아래 출제 범위가 기재되어 있다.

온라인으로 120분(2시간)을 진행하며 총 36문제다. (약 3분씩 풀어야 함)

출제 유형 분석

1기 참가자의 말: C++ 그 중서도 문법 관련 문제가 많이 나옴 언리얼에 대한 문제는 거의 없음, 게임 최적화, 게임 알고리즘, 자료구조 but 문제가 바뀌었을 확률이 큼

코딩 테스트가 아니라 주관식, 객관식의 문제

후기에서 대부분 수학이 조금 어렵고 나머지는 공부를 하고 간다면 문제가 없다고 한다.

나의 경우엔 C++, 언리얼, 수학 3개가 많이 약할 것 같다.

우선 내가 생각하는 기준으로 공부 후 다른 글들을 참고하여 채워넣을 생각

대부분 정리되어 있는 글들을 참고하였다.

객체지향 프로그래밍: 객체지향 프로그래밍 특징

관련 책을 어느정도 읽어서 개념에 대한 넓은 이해는 있지만, 문제가 지엽적으로 출제될 경우는 자신이 없다.

따라서 관련 내용에 대해서 용어 정리와 내가 생각하는 객체지향에 관해 더 적어볼 생각

객체지향이란? (내 생각)

내가 생각하는 객체지향은 객체간의 협력을 통해 의사소통하는 과정을 말하는 것 같다.

대부분 객체지향을 지향하면서도 절차지향적인 코드를 짜기 마련인데, 객치 자체를 지향한다는 의미와 내부적으론 절차지향을 포함하고 있다고 생각한다.

절차지향이라고 해서 객체지향이 아닌 것은 아니며 객체지향은 그보다 한 단계 높은 설계관점에서 유리한 프로그래밍 패러다임같다. (더 큰 프로그램을 설계 하기 위함)

장점은 크게 가독성, 중복 최소화, 유연한 코드 등이 있을 수 있다.

객체지향으로 설계하는 방법에는 가장 크게 주어진 도메인 모델을 생각하여 객체간의 협력(메시지)를 은유하여 표현한다. 이를 인터페이스로 드러내고 각 객체마다의 역할과 책임을 추상적으로 생각한다. 이 과정이 동적 모델을 설계하는 과정이고 이후 이를 투사하여 정적 모델(클래스)로 나타내는 과정이 실제로 코딩하는 과정이다.

대부분은 바로 코드를 치면서 작업하지만 이제는 객체의 동적인 협력을 생각하고, 구조를 설계하는 것이 더 중요한 것을 알게된 것 같다.

이 과정은 테스트 코드를 짜는 과정에서 많이 훈련이 된 것 같다고 느끼고, 단순하게 몇 달 공부한다고 좋아진다고 생각하지 않는다.

가장 좋은 객체지향 설계를 보는 방법은 SOLID도 있지만, 자신이 작성한 클래스의 이름과 Public메서드를 나열해보는 것이다.

해당 클래스의 책임이 제대로 할당되어 있는지 직관적으로 알 수 있다.

완벽한 설계는 없고 매번 다른 설계가 나올 수 있다. 이는 지속적인 개선이 필요한데, 객체지향은 이런 과정이 매우 유리하다.

객체지향이란? (책)

객체지향 책에 관련된 내용을 간략하게 정리

객체지향이란? (정보 글)

사실 이런 내용이 중요하다고 생각되지 않는다. 위 내용을 다 이해하고 읽으면 많은 정보를 담은 글 인걸 알겠지만, 이것을 읽고 공부한다면 무의미한 발차기라고 생각한다.

객체 지향 프로그래밍 (Object-Oriented Programming, OOP)은 프로그래밍에서 필요한 데이터를 추상화 시켜 상태와 행위를 가진 객체로 만들고, 객체들간의 상호작용을 통해 로직을 구성하는 프로그래밍 방법이다.

객체는 프로그램에서 사용되는 데이터 또는 식별자에 의해 참조되는 공간을 의미하며 값을 저장 할 변수와 작업을 수행 할 메소드를 서로 연관된 것들끼리 묶어서 만든 것을 객체라고 할 수 있다.

객체 지향 프로그래밍은 크게 추상화 , 캡슐화 , 상속 , 다형성 의 네가지 특징을 가진다.

C++ 프로그래밍: C++ 언어 특징

내 생각엔 가장 부족한 부분..

대략적인 흐름을 이해하고, C#과 차이를 통해 이해하고자 함.

C++ 특징

C++과 C#의 차이점

C++ 문법

대부분 C와 비슷하지만 특징적인 부분을 위주로 C#과 비교하여 작성

auto

auto는 C++11부터 지원하는 키워드로, 변수의 타입을 자동으로 추론하는 기능을 제공한다.

auto a = 10; // int
auto b = 10.0; // double
auto c = "Hello"; // const char*

auto는 초기화를 통해 타입을 추론하기 때문에 초기화가 없으면 사용할 수 없다.

auto a; // error

auto는 포인터, 참조, const, volatile, const volatile를 모두 지원한다.

int a = 10;
auto b = &a; // int*
auto& c = a; // int&
auto d = const_cast<const int&>(a); // const int
auto e = const_cast<volatile int&>(a); // volatile int
auto f = const_cast<const volatile int&>(a); // const volatile int

auto는 함수의 반환 타입을 추론할 때도 사용할 수 있다.

auto add(int a, int b) -> int {
    return a + b;
}

auto는 반복자를 사용할 때도 사용할 수 있다.

std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << std::endl;
}

auto는 람다식을 사용할 때도 사용할 수 있다.

auto f = [](int a, int b) -> int {
    return a + b;
};

auto는 템플릿을 사용할 때도 사용할 수 있다.

template <typename T, typename U>
auto add(T a, U b) -> decltype(a + b) {
    return a + b;
}

C#의 var와 차이점은 auto는 초기화를 통해 타입을 추론하기 때문에 초기화가 없으면 사용할 수 없다는 것이다.

C#의 var는 초기화가 없어도 사용할 수 있지만, 초기화가 없으면 object로 추론된다.

따라서 C#의 var는 컴파일러에게 타입 추론을 요청하는 반면, C++의 auto는 컴파일러가 타입을 추론하여 변수를 선언할 때 사용됩니다.

C++ 11에 추가

const auto&

const auto&는 const로 선언된 변수를 참조하는 것이다.

const auto& a = 10;

const auto&는 const로 선언된 변수를 참조하기 때문에 const로 선언된 변수와 동일한 특성을 가진다.

const auto& a = 10;
a = 20; // error
typedef

별칭 선언을 사용하여 이전에 선언된 형식의 동의어로 사용할 이름을 선언할 수 있습니다. (이 메커니즘은 비공식적으로 형식 별칭이라고 도 함). 이 메커니즘을 사용하여 사용자 지정 할당자에 유용할 수 있는 별칭 템플릿을 만들 수도 있습니다.

using identifier = type;

C#의 using과 비슷하다.

constexpr

constexpr는 C++11부터 도입된 키워드로, 컴파일 시간에 평가되고 실행 시간에 상수로 사용될 수 있는 함수나 변수를 선언하는 데 사용됩니다. 즉, constexpr를 사용하면 컴파일러가 컴파일 시간에 계산할 수 있는 값을 미리 계산하여 상수로 사용할 수 있습니다.

constexpr int square(int x) {
    return x * x;
}

int main() {
    constexpr int result = square(5); // 컴파일 시간에 square(5)가 25로 계산됩니다.
    return 0;
}
iterator

C#의 IEnumerator와 다르지만, 비슷하다.

C++ 프로그램이 서로 다른 데이터 구조로 균일한 방식으로 작업할 수 있도록 하는 포인터의 일반화입니다.

STL(Standard Template Library)에서는 각 컨테이너에 대해 적절한 종류의 반복자를 제공하여 일관된 방식으로 컨테이너를 순회할 수 있도록 지원합니다. 종종 반복자는 범위 기반(for-range) 루프와 함께 사용되어 컨테이너를 편리하게 순회할 수 있습니다.

C#에선 IEnumerable을 사용하여 컨테이너를 순회할 수 있지만, C++에선 반복자를 사용하여 컨테이너를 순회할 수 있다.

인터페이스를 통해 이터레이터 패턴을 구현하여 사용하는 것

실제로 컨테이너 함수에 이터레이터 함수를 사용하여 컨테이너를 순회할 수 있다.

#include <array>
#include <iostream>

typedef std::array<int, 4> MyArray;

int main()
{
    MyArray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    std::cout << "it1:";
    for (MyArray::const_iterator it1 = c0.begin();
        it1 != c0.end();
        ++it1) {
        std::cout << " " << *it1;
    }
    std::cout << std::endl;

    // display first element " 0"
    MyArray::const_iterator it2 = c0.begin();
    std::cout << "it2:";
    std::cout << " " << *it2;
    std::cout << std::endl;

    return (0);
}
연산자 관련

연산자는 전위로 쓰는게 좋다.

시스템 프로그래밍: 메모리(힙과 스택)

image

프로그램이 실행되려면 먼저 프로그램을 메모리에 로드해야 한다.

프로그램 코드가 담고 있는 명령어와 프로그램 내에서 사용될 변수 등을 위해서 메모리가 필요하기 때문이다. 이때, 프로그램이 메모리에 탑재되어 실제로 실행되고 있는 것을 가리켜 프로세스라 부른다.

힙 영역은 동적할당되는 영역, 스택은 지역 변수등의 영역

스택은 함수를 호출할 때 할당되고 함수가 반환될 때 소멸된다.

메모리 스택은 그림 영역과 같이 아래로 할당되고 힙은 위로 할당된다.

지정된 메모리 할당을 넘어 영역을 넘어가게 되면 오버플로우가 발생한다.

malloc(), calloc(), realloc()으로 할당

free()로 해제

#include <stdio.h>

int a = 10; // 데이터 영역

int main() {
    int b = 20; // 스택 영역
    int *c = (int *)malloc(sizeof(int)); // 힙 영역
    *c = 30;
    printf("%d %d %d\n", a, b, *c);
    free(c);
    return 0;
}

위 전체 코드가 코드 영역에 해당

스택은 힙보다 빠르다. (힙은 메모리를 할당하고 해제하는 과정이 필요하기 때문)

힙은 메모리를 할당하고 해제하는 과정이 필요하기 때문에 느리다.

delete로 해제

개인적인 생각

오버플로우가 나는 상황은 대부분 재귀를 잘 못 돌리거나 C#이 아닌 C/C++에서 메모리 관리를 하지 못하여 일어난다. (전자는 스택, 후자는 힙)

메모리영역이 다른 언어와 C/C++이 가지는 유일한 차이점이자 장점 그리고 단점이다.

개발속도에 영향을 주기 때문에 단점이 될 수 있지만, 게임의 최적화/속도에 가장 직접적인 영향을 주기 때문에 이를 관리한다면 장점이 될 수 있다.

이러한 차이점을 이해하고 언어의 선택을 하는 것이 중요하다.

자료구조: 주요 컨테이너(map, unordered_map, list, vector, array) 동작원리

이 컨테이너도 C#과의 차이점을 비교하여 이해하고자 한다.

C++ 특성상 STL라이브러리에서 다양한 컨테이너를 제공한다.

c++문법도 같이 학습해서 내용이 조금 깊은 부분도 있지만, 아마도 각 컨테이너의 장단점, 비교부분이 제일 중요할 것이다.

기본 배열

실제 컨테이너 구현은 이 기본 배열로 이뤄져 있기 때문에 이해하고 넘어간다.

실제 공식문서를 참고하는 게 좋다.

기존 C스타일 대신 C++의 스타일을 사용하는 것이 좋다고 한다.

값을 지정하지 않으면 기본 0이 할당된다.

스택선언

스택 선언은 다음과 같다.

constexpr size_t size = 1000;

    // Declare an array of doubles to be allocated on the stack
    double numbers[size] {0};

    // Assign a new value to the first element
    numbers[0] = 1;

    // Assign a value to each subsequent element
    // (numbers[1] is the second element in the array.)
    for (size_t i = 1; i < size; i++)
    {
        numbers[i] = numbers[i-1] * 1.1;
    }

    // Access each element
    for (size_t i = 0; i < size; i++)
    {
        std::cout << numbers[i] << " ";
    }

스택 기반 배열은 힙 기반 배열보다 더 빠르게 할당하고 액세스할 수 있습니다

힙선언

힙선언은 다음과 같다.

void do_something(size_t size)
{
    // Declare an array of doubles to be allocated on the heap
    double* numbers = new double[size]{ 0 };

    // Assign a new value to the first element
    numbers[0] = 1;

    // Assign a value to each subsequent element
    // (numbers[1] is the second element in the array.)
    for (size_t i = 1; i < size; i++)
    {
        numbers[i] = numbers[i - 1] * 1.1;
    }

    // Access each element with subscript operator
    for (size_t i = 0; i < size; i++)
    {
        std::cout << numbers[i] << " ";
    }

    // Access each element with pointer arithmetic
    // Use a copy of the pointer for iterating
    double* p = numbers;

    for (size_t i = 0; i < size; i++)
    {
        // Dereference the pointer, then increment it
        std::cout << *p++ << " ";
    }

    // Alternate method:
    // Reset p to numbers[0]:
    p = numbers;

    // Use address of pointer to compute bounds.
    // The compiler computes size as the number
    // of elements * (bytes per element).
    while (p < (numbers + size))
    {
        // Dereference the pointer, then increment it
        std::cout << *p++ << " ";
    }

    delete[] numbers; // don't forget to do this!

}
int main()
{
    do_something(108);
}

스택에 할당하기에는 너무 크거나 컴파일 시간에 크기를 알 수 없는 배열이 필요할 수 있습니다.

연산자는 첫 번째 요소에 대한 포인터를 반환합니다. (포인터로 배열접근, *p++)

제대로 사용하려면 다음을 보장해야 한다. (사용자가)

코드를 보면 배열로 순회하는 법, 포인터로 사이즈만큼 반복하여 순회하는 법, 포인터로 실제 메모리 크기만큼 반복하는 법을 알 수 있다.

규칙에 나와 있듯이 3가지 방법다 배열의 범위를 지날 수 없는 기저사례들로 반복하고, 원본 포인터를 유지하여 마지막에 delete[]로 메모리를 해제해야 한다.

배열 초기화

다음 두 내용은 동일하다.

    int a[10];
    for (int i = 0; i < 10; ++i)
    {
        a[i] = i + 1;
    }

    int b[10]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
함수에 배열 전달

배열이 함수에 전달되면 스택 기반 배열이든 힙 기반 배열이든 관계없이 첫 번째 요소에 대한 포인터로 전달됩니다.

배열을 함수에 전달할 때는 항상 별도의 매개 변수의 요소 수를 지정해야 합니다. 또한 이 동작은 배열이 함수에 전달될 때 배열 요소가 복사되지 않음을 의미합니다. 함수가 요소를 수정하지 못하도록 하려면 매개 변수를 요소에 대한 포인터 const 로 지정합니다.

즉, 길이를 인자로 같이 전달하는데 오류를 막기 위해 불변으로 지정하는 것이다.

void process(double *p, const size_t len)
{
    std::cout << "process:\n";
    for (size_t i = 0; i < len; ++i)
    {
        // do something with p[i]
    }
}

포인터로 전달하기 때문에 복사본이 아닌 원본을 전달한다.

// Unsized array
void process(const double p[], const size_t len);

// Fixed-size array. Length must still be specified explicitly.
void process(const double p[1000], const size_t len);

같음.

배열 초기화

클래스 생성자가 있는 개체의 배열은 생성자에 의해 초기화됩니다

C#과 똑같이 동작, 인자가 있는 생성자 구현 시 기본 생성자를 구현해야 함.

// initializing_arrays1.cpp
class Point
{
public:
   Point()   // Default constructor.
   {
   }
   Point( int, int )   // Construct from two ints
   {
   }
};

// An array of Point objects can be declared as follows:
Point aPoint[3] = {
   Point( 3, 3 )     // Use int, int constructor.
};

int main()
{
}

여기서 aPoint객체 배열의 첫 번째 인자는 (int, int)생성자를 통해 초기화되고, 나머지는 기본 생성자를 통해 초기화된다.

배열 요소 접근
// using_arrays.cpp
int main() {
   char chArray[10];
   char *pch = chArray;   // Evaluates to a pointer to the first element.
   char   ch = chArray[0];   // Evaluates to the value of the first element.
   ch = chArray[3];   // Evaluates to the value of the fourth element.
}

C언어와 동일하게 생각하면 된다.

array

길이가 N인 Ty 형식의 요소 시퀀스를 제어하는 개체를 설명합니다. 시퀀스는 array<Ty, N> 개체에 포함된 Ty의 배열로 저장됩니다.

template <class Ty, std::size_t N>
class array;

형식에 기본 생성자 array()와 기본 대입 연산자 operator=가 있고 aggregate에 대한 요구 사항을 충족합니다

array<int, 4> ai = { 1, 2, 3 };

초기화 과정, 4번째 요소는 0으로 초기화된다.

C#의 Array와 동일하다.

array::array
array();

array(const array& right);

기본 생성자와 복사 생성자를 제공한다.

#include <array>
#include <iostream>

typedef std::array<int, 4> Myarray;
int main()
{
    Myarray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    for (const auto& it : c0)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    Myarray c1(c0);

    // display contents " 0 1 2 3"
    for (const auto& it : c1)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    return (0);
}
array::at
#include <array>
#include <iostream>

typedef std::array<int, 4> Myarray;
int main()
{
    Myarray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    for (const auto& it : c0)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    // display odd elements " 1 3"
    std::cout << " " << c0.at(1);
    std::cout << " " << c0.at(3);
    std::cout << std::endl;

    return (0);
}

멤버 함수는 위치 off에서 제어되는 시퀀스의 요소에 대한 참조를 반환합니다. 해당 위치가 잘못된 경우 함수는 out_of_range 클래스의 개체를 throw합니다.

array::back
reference back();

constexpr const_reference back() const;

마지막 요소에 액세스합니다.

#include <array>
#include <iostream>

typedef std::array<int, 4> Myarray;
int main()
{
    Myarray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    for (const auto& it : c0)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    // display last element " 3"
    std::cout << " " << c0.back();
    std::cout << std::endl;

    return (0);
}
array::begin
iterator begin() noexcept;
const_iterator begin() const noexcept;
#include <array>
#include <iostream>

typedef std::array<int, 4> Myarray;
int main()
{
    Myarray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    for (const auto& it : c0)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    // display first element " 0"
    Myarray::iterator it2 = c0.begin();
    std::cout << " " << *it2;
    std::cout << std::endl;

    return (0);
}
array::empty
constexpr bool empty() const;

멤버 함수는 N == 0인 경우에만 true를 반환합니다.

#include <array>
#include <iostream>

typedef std::array<int, 4> Myarray;
int main()
{
    Myarray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    for (const auto& it : c0)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    // display whether c0 is empty " false"
    std::cout << std::boolalpha << " " << c0.empty();
    std::cout << std::endl;

    std::array<int, 0> c1;

    // display whether c1 is empty " true"
    std::cout << std::boolalpha << " " << c1.empty();
    std::cout << std::endl;

    return (0);
}

// 0 1 2 3
// false
// true
array::iterator
#include <array>
#include <iostream>

typedef std::array<int, 4> MyArray;

int main()
{
    MyArray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    std::cout << "it1:";
    for (MyArray::iterator it1 = c0.begin();
        it1 != c0.end();
        ++it1) {
        std::cout << " " << *it1;
    }
    std::cout << std::endl;

    // display first element " 0"
    MyArray::iterator it2 = c0.begin();
    std::cout << "it2:";
    std::cout << " " << *it2;
    std::cout << std::endl;

    return (0);
}

이터레이터 반환

array::max_size
#include <array>
#include <iostream>

typedef std::array<int, 4> Myarray;
int main()
{
    Myarray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    for (const auto& it : c0)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    // display (maximum) size " 4"
    std::cout << " " << c0.max_size();
    std::cout << std::endl;

    return (0);
}

멤버 함수는 N를 반환합니다.

array::operator[]
reference operator[](size_type off);

constexpr const_reference operator[](size_type off) const;
#include <array>
#include <iostream>

typedef std::array<int, 4> Myarray;
int main()
{
    Myarray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    for (const auto& it : c0)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    // display odd elements " 1 3"
    std::cout << " " << c0[1];
    std::cout << " " << c0[3];
    std::cout << std::endl;

    return (0);
}

멤버 함수는 위치 off에서 제어되는 시퀀스의 요소에 대한 참조를 반환합니다. 해당 위치가 유효하지 않을 경우 동작이 정의되지 않습니다.

또한 멤버 get 가 아닌 함수를 사용하여 요소에 대한 참조를 가져올 수 있습니다 array.

array::pointer
#include <array>
#include <iostream>

typedef std::array<int, 4> Myarray;
int main()
{
    Myarray c0 = { 0, 1, 2, 3 };

    // display contents " 0 1 2 3"
    for (const auto& it : c0)
    {
        std::cout << " " << it;
    }
    std::cout << std::endl;

    // display first element " 0"
    Myarray::pointer ptr = &*c0.begin();
    std::cout << " " << *ptr;
    std::cout << std::endl;

    return (0);
}

Myarray::pointer ptr = &*c0.begin();

해당 코드는 c0.begin()의 반환값을 *로 역참조하여 &로 주소를 가져온다. (없어도 동일하게 동작)

vector

C#의 List와 동일하다. (동적 배열)

template <class Type, class Allocator = allocator<Type>>
class vector

C++ 표준 라이브러리 벡터 클래스는 시퀀스 컨테이너에 대한 클래스 템플릿입니다. 벡터는 지정된 형식의 요소를 선형 배열에 저장하고 모든 요소에 대한 빠른 임의 액세스를 허용합니다.

벡터를 사용하면 시퀀스 끝에서 상수 시간 삽입 및 삭제할 수 있습니다. 벡터 중간에 요소를 삽입하거나 삭제하려면 선형 시간이 필요합니다. (배열기반이기 때문)

자세한 내용은 동적배열에 관한 문서 참고

벡터는 재할당 과정에서 상당한 자원이 소모된다. 따라서 reserve 메서드를 통해 원하는 크기만큼 새로운 공간을 재할당할 수도 있다.

push_back
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v1;

    v1.push_back(10);
    v1.push_back(20);

    std::cout << "The first element is " << v1[0] << std::endl;
    std::cout << "The second element is " << v1[1] << std::endl;
}

벡터의 끝에 요소를 추가합니다.

pop_back
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v1;

    v1.push_back(10);
    v1.push_back(20);

    std::cout << "The first element is " << v1[0] << std::endl;
    std::cout << "The second element is " << v1[1] << std::endl;

    v1.pop_back();

    std::cout << "The first element is " << v1[0] << std::endl;
}

벡터의 끝에서 요소를 제거합니다.

insert
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v1;

    v1.push_back(10);
    v1.push_back(20);

    std::cout << "The first element is " << v1[0] << std::endl;
    std::cout << "The second element is " << v1[1] << std::endl;

    v1.insert(v1.begin() + 1, 15);

    std::cout << "The first element is " << v1[0] << std::endl;
    std::cout << "The second element is " << v1[1] << std::endl;
    std::cout << "The third element is " << v1[2] << std::endl;
}

벡터의 지정된 위치에 요소를 삽입합니다.

at

벡터의 지정된 위치에 있는 요소에 대한 참조를 반환합니다.

// vector_at.cpp
// compile with: /EHsc
#include <vector>
#include <iostream>

int main( )
{
   using namespace std;
   vector <int> v1;

   v1.push_back( 10 );
   v1.push_back( 20 );

   const int &i = v1.at( 0 );
   int &j = v1.at( 1 );
   cout << "The first element is " << i << endl;
   cout << "The second element is " << j << endl;
}

주소값을 반환하기 때문에 const가 아니라면 값을 변경할 수 있다.(원본의 값을 변경)

back

벡터의 마지막 요소에 대한 참조를 반환합니다.

#include <vector>
#include <iostream>

int main() {
   using namespace std;
   vector <int> v1;

   v1.push_back( 10 );
   v1.push_back( 11 );

   int& i = v1.back( );
   const int& ii = v1.front( );

   cout << "The last integer of v1 is " << i << endl;
   i--;
   cout << "The next-to-last integer of v1 is "<< ii << endl;
}
begin

벡터의 첫 번째 요소에 대한 임의 액세스 반복기를 반환합니다.

const_iterator begin() const;

iterator begin();
#include <vector>
#include <iostream>

int main()
{
    using namespace std;
    vector<int> c1;
    vector<int>::iterator c1_Iter;
    vector<int>::const_iterator c1_cIter;

    c1.push_back(1);
    c1.push_back(2);

    cout << "The vector c1 contains elements:";
    c1_Iter = c1.begin();
    for (; c1_Iter != c1.end(); c1_Iter++)
    {
        cout << " " << *c1_Iter;
    }
    cout << endl;

    cout << "The vector c1 now contains elements:";
    c1_Iter = c1.begin();
    *c1_Iter = 20;
    for (; c1_Iter != c1.end(); c1_Iter++)
    {
        cout << " " << *c1_Iter;
    }
    cout << endl;

    // The following line would be an error because iterator is const
    // *c1_cIter = 200;
}
capacity

가용 공간의 길이를 반환합니다.

#include <vector>
#include <iostream>

int main( )
{
   using namespace std;
   vector <int> v1;

   v1.push_back( 1 );
   cout << "The length of storage allocated is "
        << v1.capacity( ) << "." << endl;

   v1.push_back( 2 );
   cout << "The length of storage allocated is now "
        << v1.capacity( ) << "." << endl;
}

2배씩 늘어난다. (동적 배열의 기본)

clear

배열을 비운다.

// vector_clear.cpp
// compile with: /EHsc
#include <vector>
#include <iostream>

int main( )
{
   using namespace std;
   vector <int> v1;

   v1.push_back( 10 );
   v1.push_back( 20 );
   v1.push_back( 30 );

   cout << "The size of v1 is " << v1.size( ) << endl;
   v1.clear( );
   cout << "The size of v1 after clearing is " << v1.size( ) << endl;
}

list

C++ 표준 라이브러리 목록 클래스는 해당 요소를 선형 배열로 기본 시퀀스 내의 모든 위치에서 효율적인 삽입 및 삭제를 허용하는 시퀀스 컨테이너의 클래스 템플릿입니다. 시퀀스는 각각 일부 형식 Type의 멤버를 포함하는 양방향 연결된 요소 목록으로 저장됩니다.

C#의 LinkedList와 동일하다.

차이점

공통점

연결리스트에 기반을 두므로 데이터가 메모리 상에 저장되는 위치가 불연속적이다.

데이터 검색은 vector가 유리하고, 데이터 삽입/삭제는 list가 유리하다. 정리하면, 데이터 검색은 배열 기반의 vector가 유리하고, 데이터 삽입/삭제는 연결리스트 기반의 list가 유리하다.

임의접근이 가능하지 않기 때문에 검색이 느리다. (순차적으로 탐색해야 하기 때문)

std::list는 상수 시간에 원소를 삽입하고 삭제할 수 있는 컨테이너이다.

일반적으로 자료구조에서 말하는 이중 연결리스트 혹은 양방향 연결리스트(doubly-linked list)로 구성된다. 연결리스트는 기본적으로 노드 기반으로 데이터를 저장하는 자료구조를 말하는데, 각 노드는 데이터 필드와 다른 노드를 가리키는 링크 필드로 나뉜다.

// list_assign.cpp
// compile with: /EHsc
#include <list>
#include <iostream>

int main()
{
    using namespace std;
    list<int> c1, c2;
    list<int>::const_iterator cIter;

    c1.push_back(10);
    c1.push_back(20);
    c1.push_back(30);
    c2.push_back(40);
    c2.push_back(50);
    c2.push_back(60);

    cout << "c1 =";
    for (auto c : c1)
        cout << " " << c;
    cout << endl;

    c1.assign(++c2.begin(), c2.end());
    cout << "c1 =";
    for (auto c : c1)
        cout << " " << c;
    cout << endl;

    c1.assign(7, 4);
    cout << "c1 =";
    for (auto c : c1)
        cout << " " << c;
    cout << endl;

    c1.assign({ 10, 20, 30, 40 });
    cout << "c1 =";
    for (auto c : c1)
        cout << " " << c;
    cout << endl;
}

나머지 함수들은 동일해서 생략

새로운 데이터를 삽입하는 함수에는 push_front(), push_back(), insert()가 있다.

push_front: 시작 지점에 원소를 삽입 push_back: 마지막에 원소를 삽입 insert: 현재 반복자가 가리키고 있는 위치에 원소를 삽입 상수 시간에 데이터를 삽입하고 삭제할 수 있다는 특징 덕분에 세 함수 모두 O(1)의 시간 복잡도로 수행된다.

삭제의 경우 pop_front(), pop_back(), erase, remove, remove_if 등이 있다.

pop_front()는 첫 번째 원소를, pop_back()은 마지막 원소를 삭제한다. erase는 인자로 넘긴 반복자가 가리키는 노드를 제거한다. remove와 remove_if는 주어진 조건을 만족하는 원소를 모두 삭제한다. 연결리스트는 현재 가리키는 원소만을 삭제할 수 있으므로, 두 함수는 처음부터 끝까지 주어진 std::list를 순회하며 조건에 맞는 원소를 지워나간다.

앞의 세 개는 시간 복잡도가 O(1)이지만 remove, remove_if는 모든 노드를 순회해야 하므로 시간 복잡도가 O(n)이다.

장단점

요소의 삽입, 삭제는 상수 시간 O(1)이 걸린다.

std::list는 연결리스트에 기반을 두는데, 덕분에 어디에서든 데이터를 삽입하고 삭제할 때 속도가 빠르다. 삽입할 때, 삭제할 때 모두 두 노드를 연결하는 링크만을 변경해 주면 되기 때문이다.

다만, 실제로 원하는 요소를 찾아 지우려면 탐색이 느리기 때문에 O(n)의 시간이 걸린다.

반면 벡터와 달리 임의로 접근하는 것이 불가능하므로, 원하는 노드를 탐색할 때 최대 N번의 탐색이 필요하다.

그리고 선형탐색할 때에도 캐시 효과로 인해 불연속적인 메모리의 선형탐색이 연속적인 메모리에서보다 느리기 때문에, 탐색도 느린 편이다. 그 때문에 벡터를 쓰는 게 더 빠른 경우가 많다.

시간 복잡도를 정리하면 다음과 같다.

요소의 삽입/삭제: 어디든지 상수 시간 O(1) 요소의 탐색: O(N)

map

std::map (C++) C++의 표준 라이브러리(STL)에 포함되어 있습니다. 키가 정렬된 순서로 유지됩니다. 이진 검색 트리(Binary Search Tree, BST)를 사용하여 구현되어 있어 검색 및 삽입 연산이 빠릅니다. 키에 대한 범위 검색이 가능합니다. std::map<Key, T> 형태로 사용됩니다.

맵(std::map)은 키(Key)와 값(value)의 쌍들을 저장하는 이진탐색트리 기반의 컨테이너이다.

이때, 키는 중복될 수 없다.

맵의 각 원소는 std::pair<key,value>로 저장된다.

pair는 순서쌍을 가리키는데 여기서는 pair.first에 key가, pair.second에 value가 저장된다.

C++에서 맵은 Key를 기준으로 자동 정렬되는데, 내부적으로는 레드블랙트리로 구현된다. (균형트리)

std::map은 균형 이진 탐색 트리의 일종인 레드블랙트리를 사용하여 삽입, 삭제, 탐색이 빠르다(O(logN)).

다만 자동으로 정렬되는 것이 필요하지 않을 때는 굳이 map을 사용할 이유가 없다. map은 레드블랙트리 기반이기 때문에 삽입할 때마다 트리의 균형을 맞춰야 한다. 게다가 map은 해시맵, 해시테이블과 달리 상수 시간 O(1)에 데이터를 처리하지 못한다.

만약 해시맵 기반의 자료구조가 필요하면 unordered_map을 사용해야 한다.

삽입, 삭제, 탐색: 시간 복잡도 O(logN)

template <class Key,
    class Type,
    class Traits = less<Key>,
    class Allocator=allocator<pair <const Key, Type>>>
class map;

C++ 표준 라이브러리 map 클래스의 특징은 다음과 같습니다.

연결된 키 값을 기반으로 요소 값을 효율적으로 검색하는 다양한 크기의 컨테이너

이는 해당 요소에 액세스할 수 있는 양방향 반복기를 제공하기 때문에 되돌릴 수 있습니다.

요소가 지정된 비교 함수에 따른 키 값으로 정렬되므로 정렬되어 있습니다.

고유합니다. 각 요소에 고유 키가 있어야 하기 때문입니다.

요소의 데이터 값은 키 값과 구별되기 때문에 쌍 연관 컨테이너입니다.

클래스 템플릿은 제공하는 기능이 제네릭이며 요소 또는 키 형식과 독립적이기 때문입니다. 요소와 키에 사용되는 데이터 형식은 비교 함수 및 할당자와 함께 클래스 템플릿에서 매개 변수로 지정됩니다.

#include <map>
#include <iostream>

typedef std::map<char, int> Mymap;
int main()
    {
    Mymap c1;

    c1.insert(Mymap::value_type('a', 1));
    c1.insert(Mymap::value_type('b', 2));
    c1.insert(Mymap::value_type('c', 3));

// find and show elements
    std::cout << "c1.at('a') == " << c1.at('a') << std::endl;
    std::cout << "c1.at('b') == " << c1.at('b') << std::endl;
    std::cout << "c1.at('c') == " << c1.at('c') << std::endl;

    return (0);
    }
#include <map>
#include <iostream>

int main( )
{
   using namespace std;
   map <int, int> m1;

   map <int, int> :: iterator m1_Iter;
   map <int, int> :: const_iterator m1_cIter;
   typedef pair <int, int> Int_Pair;

   m1.insert ( Int_Pair ( 0, 0 ) );
   m1.insert ( Int_Pair ( 1, 1 ) );
   m1.insert ( Int_Pair ( 2, 4 ) );

   m1_cIter = m1.begin ( );
   cout << "The first element of m1 is " << m1_cIter -> first << endl;

   m1_Iter = m1.begin ( );
   m1.erase ( m1_Iter );

   // The following 2 lines would err because the iterator is const
   // m1_cIter = m1.begin ( );
   // m1.erase ( m1_cIter );

   m1_cIter = m1.begin( );
   cout << "The first element of m1 is now " << m1_cIter -> first << endl;
}

unordered_map

std::unordered_map은 기존 std::map의 문제를 해결하기 위해 나온 컨테이너로 C++ 11부터 적용된다.

기존 std::map은 O(logN)의 시간 복잡도를 갖으므로 요소의 삽입/삭제가 빈번하면 성능 저하가 있다.

반면 std::unordered_map은 이름처럼 정렬을 수행하지 않기 때문에 시간 복잡도가 O(1)이다.

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string, int> unordered;

    unordered["Alice"] = 50;
    unordered["Bob"] = 60;
    unordered["Sam"] = 70;

    for (auto it = unordered.begin(); it != unordered.end(); it++)
        std::cout << it->first << ": " << it->second << std::endl;

    return 0;
}

이렇게 입력하면, 결과가 정렬되지 않고 랜덤하게 나타난다.

std::unordered_map은 map과 마찬가지로 키와 값의 쌍(pair)을 저장하며 키도 중복 불가이다. 하지만 Hash Map 기반으로 만들어진 컨테이너이기 때문에 정렬을 수행하지 않는다. 이 컨테이너는 삽입, 삭제에 걸리는 시간 복잡도가 O(1)이다.

해시 맵 사용

std::unordered_map에서 사용되는 자료구조는 해시맵 또는 해시테이블로, 여러 개의 버킷을 두고 해시 함수(Hash function)를 통해 색인(index)한다.

해시 함수는 키 값을 정수로 변환하는 역할을 한다. 동일한 키 값이 주어지면 동일한 정수로 변환해 준다. 하지만 정수 값을 통해 키 값을 구하는 것은 불가능하다.

해시 함수를 이용하면 함수 한 번으로 데이터가 들어갈 인덱스를 구할 수 있어 탐색이 훨씬 빠르다.

정리

각각의 자료구조인 std::list, std::vector, std::array에는 각각의 장단점이 있습니다. 다음은 각각의 자료구조의 장단점을 설명한 것입니다:

std::list:

장점:

  1. 요소의 삽입 및 삭제가 효율적입니다.
  2. 삽입 및 삭제 연산이 상수 시간(O(1))에 수행됩니다.
  3. 메모리의 조각화가 발생하지 않습니다.
  4. 중간에 요소를 삽입하거나 삭제하는 경우에 유용합니다.

단점:

  1. 인덱스로 직접 요소에 접근하는 것이 불가능합니다.
  2. 요소의 검색에 선형 시간(O(n))이 소요됩니다.
  3. 요소에 연속적으로 접근하는 경우에는 효율적이지 않습니다.
std::vector:

장점:

  1. 요소에 대한 랜덤 접근이 가능합니다.
  2. 요소의 삽입 및 삭제가 배열의 끝에서 상수 시간(O(1))에 수행됩니다.
  3. 메모리 효율성이 좋습니다.

단점:

  1. 요소의 삽입 및 삭제가 배열의 중간에서 발생하는 경우에는 선형 시간(O(n))이 소요됩니다.
  2. 메모리 재할당이 발생할 때마다 요소들을 복사해야 합니다.
  3. 메모리를 연속적으로 할당하기 때문에 중간에 요소를 삽입하거나 삭제하는 경우에 비효율적입니다.
std::array:

장점:

  1. 요소에 대한 랜덤 접근이 가능합니다.
  2. 크기가 고정되어 있으므로 메모리를 효율적으로 사용할 수 있습니다.
  3. 요소의 삽입 및 삭제가 발생하지 않기 때문에 삽입 및 삭제 연산의 오버헤드가 없습니다.

단점:

  1. 크기가 고정되어 있기 때문에 동적으로 크기를 조정할 수 없습니다.
  2. 배열의 크기가 컴파일 시간에 정의되어야 합니다.
  3. 요소의 삽입 및 삭제가 발생하지 않기 때문에 삽입 및 삭제 연산이 필요한 경우에는 적합하지 않습니다.

따라서 각각의 자료구조는 자신만의 특징과 장단점을 가지고 있으며, 사용하고자 하는 상황과 요구 사항에 따라 적절한 자료구조를 선택해야 합니다.

std::map과 std::unordered_map은 둘 다 키-값 쌍을 저장하는 연관 컨테이너로서, 각각의 장단점이 있습니다. 다음은 각각의 자료구조의 특징과 장단점을 설명한 것입니다:

std::map:

장점:

  1. 키가 정렬되어 저장됩니다.
  2. 이진 검색 트리(Binary Search Tree, BST)를 사용하여 구현되어 있어 효율적인 검색이 가능합니다.
  3. 키에 대한 범위 검색이 가능합니다.

단점:

  1. 삽입 및 삭제 연산이 느립니다. BST의 균형을 유지하기 위해 재배열 과정이 필요하기 때문입니다.
  2. 해시 함수를 사용하지 않기 때문에 std::unordered_map에 비해 검색이 느릴 수 있습니다.
std::unordered_map:

장점:

  1. 해시 테이블을 사용하여 구현되어 있어 검색, 삽입 및 삭제 연산이 상수 시간(O(1))에 수행됩니다.
  2. 키의 순서가 유지되지 않습니다.
  3. 해시 충돌을 최소화하기 위한 좋은 해시 함수를 사용한다면 매우 효율적입니다.

단점:

  1. 해시 충돌이 발생할 경우 성능이 저하될 수 있습니다.
  2. 해시 함수의 선택이 중요하며, 나쁜 해시 함수를 사용할 경우 성능이 저하될 수 있습니다.
  3. 키에 대한 범위 검색이 불가능합니다.

따라서 std::map은 정렬된 키가 필요하거나 범위 검색이 필요한 경우에 유용하며, std::unordered_map은 검색 및 삽입 연산이 빈번하게 발생하고 정렬된 키가 필요하지 않은 경우에 유용합니다. 선택하는 것은 사용하고자 하는 요구 사항에 따라 다르며, 각각의 자료구조는 자신만의 장단점을 가지고 있습니다.

게임 알고리즘: A* 길찾기, FSM, 비헤이비어트리, Quadtree 공간 분할

대략적인 내용은 알지만, 문제로 나온다면 다시 공부해야 할 것 같다.

A* 길찾기

다양한 길 찾기 알고리즘 중 가장 대중적인 길찾기 알고리즘

요즘 강곽 받는 JPS가 있다.

가장 이해가 잘 된 블로그 글

중요 포인트
구현 포인트
수도 코드
PQ.push(start_node, g(start_node) + h(start_node))       //우선순위 큐에 시작 노드를 삽입한다.

while PQ is not empty       //우선순위 큐가 비어있지 않은 동안
    node = PQ.pop       //우선순위 큐를 pop한다.

    if node == goal_node       //만일 해당 노드가 목표 노드이면 반복문을 빠져나온다. 기저사례
        break

    for next_node in (next_node_begin...next_node_end)       //해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
        PQ.push(next_node, g(node) + cost + h(next_node))       //우선순위 큐에 다음 노드를 삽입한다.

print goal_node_dist       //시작 노드에서 목표 노드까지의 거리를 출력한다.
실제 코드
using ii = pair<int, int>;

priority_queue<ii, vector<ii>, greater<ii> > pq;
/// N_VER은 그래프의 정점의 개수를 의미한다.
int dist[N_VER], cost[N_VER][N_VER]; /// dist[i]는 i번째 정점까지 가는 최단 거리를 의미한다.
vector<ii> edges[N_VER]; /// edges[i]는 i와 연결된 정점과 가중치를 묶어 저장하는 벡터이다.

int minDist(int src, int dst) {
    pq.emplace(0, src);
    bool success = false;
    while (!pq.empty()) {
        int v = pq.top(); pq.pop();
        if (v == dst) {
            success = true;
            break;
        }
        for (ii& adj : edges[v]) {
            if (dist[adj.first] < g(v) + adj.second + h(adj.first)) {
                dist[adj.first] = g(v) + adj.second + h(adj.first); // 이완 (relaxation)
                pq.emplace(dist[adj], adj); // 다음 정점 후보에 탐색하고 있는 정점을 넣는다.
            }
        }
    }
    if (!success) return -1;
    else return dist[dst];
}
생각

휴리스틱에 따라 값이 달라진다면 아마 가장 최악은 f(x)와 g(x)의 값이 같아지는 경우가 아닐까 싶다.

그렇다면 노드들이 일렬로 늘어선 경우에는 최악의 성능을 보일 것이다.

어느정도 방사형으로 뻗어나가는 경우에는 최적의 성능을 보일 것이다. (휴리스틱에 따라)

스타크래프트도 A*를 사용한다고 한다.

FSM

가장 잘 정리된 유튜브 영상 참고

유한 상태 기계로 게임 알고리즘 중 가장 유명하다.

구현

다양한 방법으로 가능 (if-else, enum & switch-case, State 패턴)

대부분 State 패턴을 사용한다.

class FSMState
{
  virtual void onEnter();
  virtual void onUpdate();
  virtual void onExit();
  list<FSMTransition> transitions;
}

인터페이스 (추상클래스)로 각 State패턴에 맞게 동작할 행위, 전이 조건이 담긴 list를 가진다.

class FSMTransition
{
  virtual bool isVaild();
  virtual FSMState* getNextState();
  virtual void onTransition();
}

전환 가능한지 여부, 다음 상태, 전이 시 수행할 동작을 가진다.

class FiniteStateMachine
{
  void update();
  list<FSMState> states;
  FSMState* initialState;
  FSMState* activeState;
}

Update를 통해 상태를 업데이트하고, 상태들을 가진다.

단점
정리

많은 장점과 단점이 같이 존재

규모가 크지 않다면 사용하는걸 권장하지만 상태가 많아짐에 따라 엔트로피 증가

HFSM으로 대부분 커버가 가능하다.

생각

과거 체리플젝에서 보스, 몬스터, 플레이어의 상태를 FSM으로 관리했는데, 플레이어와 몬스터는 FSM형태로 작성되었지만, 코드 간의 의존성은 좋지 못한 상태로 관리되었다.

보스에 가서는 좀 더 좋은 코드를 짜고 싶어서 Attack State를 한번 래핑하여 Pattern으로 구분하여 페이즈, 패턴에 맞게 호출되도록 짰는데 이게 HFSM인지 몰랐다.

좋은 경험이였고, 좀 더 넓은 이해가 된 것 같다.

Behavior Tree

가장 잘 설명된 영상 참고

10년전부터 사용되고 있으며, 언리얼의 의사결정 시스템에도 BT가 사용되고 있다.

이제는 대부분의 회사가 BT로 의사결정 시스템을 만든다.

행동트리라고 부름

FSM(finite state machine)은 State중심으로 결정했다면, BT는 행동중심으로 결정한다.

구성
알고리즘
특징
Utility System

효용 경제학의 용어

대부분의 AI Logic은 Boolean questions으로 이뤄져있다. (양극화)

나는 적을 볼 수 있는가? yes or no

if (canSeeEnemy()) {
  attack();
}

하지만 실세계의 의사결정은 그렇지 않다. (복잡함, 수많은 가능성)

고려해야 할 요소들이 매우 많음 (적이 얼마나 남았고, 탄약이 얼마나 있고, 내 상태는?)

이러한 상황을 if case로 잡을 수 없음, 결과들이 단순히 할까, 말까로 결정되지 않음

따라서 어떠한 행동을 할 가능성으로 형태가 적합 (확률)

Utility System은 잠재적인 행동의 선호도를 결정한다. 고려사항에 대한 측정, 가중치, 결합, 비율, 우선순위, 정렬 등을 수행

보통은 AI아키텍처의 전환논리가 필요할 때 사용, 전체 의사결정 엔진으로 구축할 수 있음

이것은 "네가 해야할 유일한 액션"으로 귀결되지 않음

취할 수 있는 가능한 옵션을 제공하는 형태

대표적으로 심즈

Quadtree

참고 블로그

쿼드트리는 각 내부 노드에 정확히 4개의 자식이 있는 트리 데이터 구조이다. 2차원 공간을 재귀적으로 4개의 영역으로 분할하는 데 사용된다.

참고

게임 수학: 게임에서의 벡터, 행렬, 내적, 외적의 활용, 회전의 표현

가장 약한 부분.. 최대한 OpenGL의 기억을 살려서 공부

게임에서의 벡터

영상 참고

벡터는 게임 개발에서 중요한 개념으로 사용된다.

스칼라는 크기

표현
성질
상대좌표, 절대좌표
벡터의 덧셈

각 피연산자들의 성분끼리 더한다.

$$ \vec{a} + \vec{b} = \vec{c} $$ $$ \vec{a}(1,4) + \vec{b}(3,2) = \vec{c}(4,6) $$

image

벡터의 뺄셈

각 피연산자들의 성분끼리 뺀다.

$$ \vec{a} - \vec{b} = \vec{c} $$ $$ \vec{a}(1,4) - \vec{b}(3,2) = \vec{c}(-2,2) $$

벡터의 뺄셈은 벡터 더하기 마이너스 벡터로 표현할 수 있다.

벡터의 스칼라 곱

벡터의 실수배

각 성분에 스칼라를 곱한다.

$$ k\vec{a} = \vec{c} $$ $$ 3\vec{a}(1,4) = \vec{c}(3,12) $$

방향벡터

벡터를 통해 방향과 거리를 포현하는 경우 상당히 비직관저임

따라서 방향*거리로 쪼개어 표현하는 것이 직관적임

방향을 표현하는 벡터를 방향벡터라고 한다. (크기가 1인 벡터)

방향 x 크기 = 벡터

방향벡터를 구하는 방법

image

크기를 구하는 방법

image

(3,-4, 0)

$$ \sqrt{3^2 + (-4)^2 + 0^2} = 5 $$ $$ \frac{1}{5}(3,-4,0) = (0.6, -0.8, 0) $$

벡터의 내적

두 벡터가 이루는 각을 구하려면 내적을 사용한다.

벡터의 내적은 한 벡터를 다른 벡터에 투영시켜 그 크기를 곱하는 연산

$$ \vec{a} \cdot \vec{b} = |\vec{a}||\vec{b}|cos\theta $$ $$ \vec{a} \cdot \vec{b} = a_xb_x + a_yb_y + a_zb_z $$ $$ \frac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|} = cos\theta $$

image

cosangle구하는 법

내적은 벡터의 곱셉 하지만 값은 스칼라

내적의 값이 0이라면 두 벡터는 수직이다.

내적의 값이 양수라면 0도와 90도 사이에 있다. (1) 즉, 두 벡터가 같은 방향을 가지고 있다.

내적의 값이 음수라면 90도와 180도 사이에 있다. (-1) 즉, 두 벡터가 반대 방향을 가지고 있다.

image

총알의 진행 방향과, 현재 뱡향의 내적이 0 초과라면 데미지를 입는다. 즉 같은 방향을 가진다면 데미지를 입는다.

image

image

에너지 총량의 법칙 때문에 빛이 닿는 면적의 밝기는 코사인 세타이다.

45도는 약 0.7정도로 나옴(코사인 45도)

벡터의 외적

$$ \vec{a} \times \vec{b} = |\vec{a}||\vec{b}|sin\theta $$ $$ \vec{a} \times \vec{b} = (a_yb_z - a_zb_y, a_zb_x - a_xb_z, a_xb_y - a_yb_x) $$

image

frontDirection은 현재 면의 앞을 가리키는 벡터이다.

sinagngle은 두 벡터가 이루는 각도이다.

image

image

회전

3차원 벡터를 사용하여 회전을 나타내는 방법을 오일러 각이라고 한다.

짐벌락 문제가 발생한다.

한 차원이 자유도를 잃는 상황

따라서 쿼터니언을 사용한다.

$$ q = w + xi + yj + zk $$

오일러각은 순차적인 회전이 반면, 쿼터니언은 N차원 공간상에서 한 번에 회전한다.

대신 계산이 매우 복잡함

따라서 헬퍼함수를 사용하여 쿼터니언에 접근한다.

쿼터니언 회전의 추가는 곱셈으로 구현

이유는 행렬연산으로 이뤄지기 때문에 곱셈으로 구현

행렬

행과 열로 이뤄진 수의 집합

유니티의 Transform은 행렬로 이뤄져있다.

행렬으로 회전, 이동, 크기 조절을 한다.

이는 행렬의 곱셈으로 이뤄지는데, 이 곱셈은 내적이다. (선형대수학)

image

3차원을 다루기 위해선 4차원 행렬을 사용한다. (그래픽스는 Column Major)

1열은 x축, 2열은 y축, 3열은 z축, 4열은 이동을 나타낸다.

image

image

행렬식은 변환의 크기를 나타낸다.

언리얼 C++ 프로그래밍: 언리얼 엔진에서 사용하는 C++ 프로그래밍 프레임웤

언리얼 게임 프레임웤: 언리얼 엔진이 게임 제작을 위해 제공하는 프레임웤에 대한 기초 지식