[💬] 게임 최적화를 해보자

[123123(121.150)]

step 1. 최적화 해야 할것 찾기.

최소한 최적화를 시작하려면 뭘 최적화 해야할지 찾아야 최적화를 할수있음.

프로파일러건, 로그 수집이건, 테스트건 어디서 보틀넥이 걸리는지 찾아야함.

게임 역시 프로그램이고, 프로그램의 격언에 따라 20:80 법칙이 아주 잘 이뤄지는곳중 하나임.

20%의 코드가 80%의 부하를 담당한다거나,

핵심 코드가 20%라면 나머지 80%는 단순한 게터/세터에 불과하다던지 하는 등등의 격언이 그대로 적용됨...

그러면 우리 게임을 망치는 20%는 어디에 있을까?

이론적으로 게임의 알고리즘 의 시간복잡도 부터 알아보자.. (공간 복잡도는 포기한다! 으악!)

대충 이런걸로 나누는데 O(~~) ~~에 아래 숫자를 넣어서 씀.

1(constant) -  입력자료의 수에 관계 없이 일정한 실행 시간을 가짐. 

예를 들어 리스트 같은 경우에 isEmpty 같은 함수가 상수시간이 걸린다고 보면 됨. 또는 해쉬맵의 서치 시간 등등이 있음.

log N(로가리슴) - 만약 입력 자료의 수에 따라 실행 시간이 이 log N 만큼 걸림. (여기서 log는 log2를 주로 말함. 이진수라 그럼.) 

정렬된 리스트의 이진 탐색이 이런 시간이 걸림.  또는 이진 탐색 트리의 탐색 시간 ?

N(Linear) - 입력 자료의 수에 따라 선형적으로 실행 시간이 걸림

for loop 및 여러 루프 나 그냥 리스트의 탐색 시간 이 이럼. 

N logN - 입력한 자료의 수에 따라 nlogn만큼 걸림.

머지솔트 (merge sort)나 퀵솔트 (quick sort) 등의 정렬 알고리즘의 시간 복잡도임. 예들은 공간 복잡도가 올라간 대신 시간을 잡았다 라고 보면 됨. 

N^2(quadratic) - 입력한 자료의 수의 제곱만큼 걸림. 

버블 솔트, 셀렉션, 인설션 솔트, 물리 엔진 알고리즘 등등이 이런데 속함.

N^3 (Cubic) - 입력한 자료의 수의 세제곱만큼 걸림. 

이런건 딱히 본적이 없지만 3중루프 돌리면 이렇게 됨. 예를 들어  a,b,c를 비교해야 하는 알고리즘이 아마 이럴거임.

2^n (지수함수;;) - 이런 알고리즘은 본적 없어서 모르겠음;; 대충 유전학이나 생물학, 사회과학 등등의 경우는 이런 시간 복잡도를 가지는 경우가 많음.

물론 이 이상도 있고... 그래서 수학을 잘 알아야;;

공간 복잡도는 

array가 가장 좋고, vector, list, map/set, unorderd map(hash map) 등등의 순서로 복잡해짐.

array랑 list 랑 이론적으로 비슷 한거 아님?

할수 있는데 cpu에서 돌때 캐시를 쓰기 때문에 어레이가 더 좋음. 

실제로 해쉬맵으로 O(1) 로 찾아오는것과 어레이에서 O(N) 으로 찾아오는것의 실행 속도가 비슷함.

그래서 리스트가 쓰기 편해도 vector 나 array를 쓰는거고

union과 malloc/free를 아직까지 쓰고 있다고 보면 됨.

다시 본문으로 돌아가서

게임에서 이론적으로 게임 로직은 O(N) 만큼의 시간 복잡도를 가지고

그래픽은 O(N) ~ O(NlogN) 만큼의 시간 복잡도를 가짐. (이상적일 경우 O(N), 최악의 경우 O(NLogN))

물리는 O(N^2) 만큼의 시간 복잡도를 가지게 됨.

여기서의 로직의 시간복잡도는 로직전체를 실행하는데 N 번만큼의 실행이 필요 하다는 뜻임.

이 말은 오브젝트에 강체와, 충돌체, 스프라이트가 있고, 컨트롤러 로직 까지 있다면

이 오브젝트가 추가 되었을시 각각의 시스템에 저만큼의 N+1의 부하를 더 준다는 뜻임.

사람들은 똑똑해서? 그래픽의 경우에는 컬링과, 클리핑 등등을 이용해서 부하를 줄여줌.

(그래픽은 덜배워서 다른 알고리즘은 잘 모르겠읍니다... ㅈㅅ합니다...)

물리의 경우에는 Broad Phase 알고리즘을 사용해서 부하를 줄여줌. 

대충 방식들을 말하자면 N의 숫자를 줄여주는 계산 방식임.

물리의 경우 O(N^2) 을 실행하기전에, O(N)정도 되는 알고리즘을 통해서,

N의 숫자를 현저하게 줄이는 이런 방식으로 최적화를 함.

대충 이상적인 상황에서 R-Tree 방식의 브로드 페이즈를 했다고 보자. 

한계 objject를 3개라 두고, 오브젝트 1000개가 돈다면,

O(1000) 이후에 O(1800) 을 하는식으로 줄어들 여지가 있음.

그냥 하게 된다면 O(1000000) 만큼 돌아버리는 현상이 일어남....

이렇게 되면 O(1000000) 와 O(2800)의 차이는 게임에서 엄청 큰 효과를 불러 일으킬수 있음.

이런 상황은 물론 별로 없고, O(1000000) 을 돈다면 O(5000~50000) 정도의 기댓값이 있다고 보면 됨.

알고리즘에 따라 대충 실행시간이 1/5000 배 만큼 줄어들거나 적어도 1/100 배 만큼 줄어든다고 함.

물론 과도하게 최적화를 하게되면, 충돌 했지만, 충돌을 안했다고 인식하던지, 갑자기 속도가 튀어버린다던지

이런 부작용이 생겨서. 도저히 원인을 알수 없는 버그의 원인이 되기도 함. 

유명한 물리엔진인 박스 2D 나 불렛 같은 경우는 진짜 공간 복잡도까지 엄청 고려 해서 짰기 때문에

실행시간이 직접만든 엔진에 비해 엄청나게 빠른경우가 많다고 함. (그래서 상용엔진들도 요 물리엔진을 쓰는거...)

하복이나 피직스는 말할것도 없다고 보면 될듯.

그럼 step 2. 최적화를 해보자;;

요건 물리에서 최적화 할만한 방법임.

이건 둠에서 한 방식인데, 고전적이지만 확실한 방법중 하나임.

둠(옛날거)의 경우는 전투가 일어날때 한 방에서 일어나는데, 짱개식으로 모든 오브젝트를 검사하지 말고,

이 방만 검사 하는 방식으로 하는거임. 

그렇게 되었을 때 복도 나 이런곳에서는 적을 일부러 출현시키지 않거나, 애니메이션으로 바로 이동 시킨다던지 하는 식으로 

물리 부하를 회피 할수 있음.

윾니티에서 적용할만하게 사용한다면,

게임 씬을 잘게 쪼게서

구역 구역마다 씬을 만드는 방식으로 구현하는게 요런 느낌이라 볼수 있음.

대신에 이 경우에는 게임 스테이트를 저장하고 불러오는데 걸리는 로딩타임 부하가 생긴다고 볼수 있음.

오픈월드 게임에서는 리전을 만드는 식으로 최적화를 하는거 같은데, 전 수준이 낮아서 모르겠읍니다... 

그래픽에서 할만한 최적화 방법.

이건 2D 게임에서 가장 유용한 팁인데 3D에서는 깊이 버퍼 테스트 할때 다 걸러버려서 이런 짓거리를 안해도 된다고 들었음.

2D게임에서 alpha 칼라 값은 졸라 이유를 알수 없는 느려짐을 유발할수 있음.

그래픽 랜더링에서 쉐이더가 vertex 버퍼를 지나고, 픽셀 버퍼를 계산할때

한 픽셀 마다 color 값을 계속 변경한다고 생각하면 되는데, 이경우에 alpha 값은.

sort 한다 하더라도, 멀리있는 색깔과 가까이 있는 색깔역시 전부 그려야 하는 문제가 생김. 그러다보니 오버드로우 문제가 생기고 

이때문에 최적화 문제가 생긴다고 볼수 있음.

대충 보면 1920*1080 의 해상도를 가진 게임이라면, 매 프레임마다 2,073,600 개의 픽셀을 그려야 하는데

하나의 픽셀을 여러번 그린다면 문제가 생긴다고 볼수 있음...

마찬가지로 백그라운드 오버드로우 역시 피해야 하는데, 이건 내 느낌에 약간의 예쁨과 이펙트를 포기하고,

성능을 얻는 효과라 볼수 있음. 멀리 있는 배경에 수많은 sprite 오브젝트들을 배치해서 생기는 랙이라 보면 됨...

또 파티클 시스템을 카메라 앞에 두는것도 피하는게 좋음. 이거도 픽셀을 여러번 그리는게 많아져서 랙이 생긴다고 보면 됨.

게임 로직에서 할만한 최적화? 팁?

솔직히 이건 케바케인데, 이건 루프 돌리는 팁 정도? 계산 하는 팁? 이런 정도?

밖에 뭐라 설명 해줄게 없어 보임.

루프를 돌릴때 될수 있는한 함수는 밖에서 사용하고 루프를 돌리는게 좋다 이런것들?

for(int i = 0; i < str.length(); ++i) {...}

 이런식의 루프 보다

int len = str.length();

for(int i=0; i< len; ++i) {...}

이런식으로 사용하는게 훨씬 줄어드는 팁이라 볼수 있음.

이 경우에 프로파일러로 결과를 보면 A(위에거) 방식으로 하면 

length가 n이라 했을때,

str.length(); 함수가 n번이나 불리는 현상이 생김.

반면에 아래거는 한번만 불리고, 시간 복잡도로 보면 

O(N) 과 O(1)의 시간 복잡도의 차이를 불러옴.

예를 들어 AI가 pathfinding을 해야하면 skip 리스트의 구현 방법을 빌려와서

path를 크게 16분할을 한다던지 하는식으로 미리 갈 곳에 대한 큰 결과를 만들어 두고,

그 다음에 세부적으로 들어가서 계산하면, 물리엔진에서 하는 broad phase와 비슷한 역할을 해준다고 볼수 있음.

그냥 1600개의 타일을 계산 하는것보다

먼저 100개 씩 큰덩어리로 묶어서 16개의 결과를 계산하고, 거기서 10개, 10개 를 계산한다거나,

100개를 계산 하는식으로 하면 알고리즘의 공간복잡도는 4배정도 올라가더라도 (메모리가 더 필요 하다는것임)

시간 복잡도는 현저히 줄일수 있음.

마이크로 최적화 팁으로는 부동소수들 double이나 float을 계산 할때는 * 오퍼레이터를 쓰는게 좋음.

예를 들어 pi = 3.14159 라는 숫자를 2로 나눠야 한다면

value = pi / 2.0; 이렇게 하는것보다

value = pi * 0.5; 이렇게 하는게 실행 시간이 빠르다고 함.

물론 만들어지는 ASM 코드에 따라 다른데, 어셈블리 레벨에서 아래 방식이 변수 레지스터를 하나 덜쓰는걸로 알고 있음.

요즘엔 별로 신경 안써도 되긴 하지만, (어떤 경우에는 /2 를 하는게 빠른 경우도 있다고 하니;;)

아래쪽이 더 빠르다고 배웠음... 

마찬가지로 정수형 변수들은 비트 연산이 좀더 빠름.

예를 들어 2를 곱한다고 할때

int val = 14;

val = val << 1;

이렇게 하는게 *2 를 쓰는것보다 빠름.

2로 나누는 경우는 >>1를 하는것도 있고...

3이나 이런걸 곱할때는 그냥 쓰는게 나으니 이런 미립자 팁들은 무시해도 됨;;

또 cos, sin이나 sqrt 등의 수학 함수들은 컴퓨터에서 테일러 급수를 통해 계산하는 값인데,

이게 또 부하가 많이 먹는 함수들임. 요런것중에 자주 쓰는 숫자나 결과들은 미리 계산해서, 값으로 저장해두는 방법도 있음.

솔직히 말해서 0도 ~ 360도의 경우는 숫자가 크지만 라디안으로 0~ 2pi, 6.28 정도 까지는 의외로 값이 크게 안느껴지는 것처럼 보임.

이럴때 미리 계산 해둔걸 쓴다던지 하는 방법이 있음.  

솔직히 이런 최적화는 처음에 말한 80%의 부하가 별로 안걸리는 상황에서의 최적화인데, 이런것보다는

보틀넥이 걸리는곳을 최적화 하는게 맞다고 봄.

step 3. 최적화를 했으면 디버깅을 해야 함.

unit test도 좋지만, 이럴때는 오토매틱 테스트 등등 

여튼 짧은 시간에 많은 테스트를 해보는게 좋음.

테스트 하는 도중에 이상한 결과나, 원하지 않는 크래쉬가 날수 있으니;;

디버깅 하다보면 힙에서 nbit 짜리 메모리 찾는게 제일 ㅈ같은거 같은데 이건 진짜 자주 자주 찾아봐야 하는거 같다...

코드 설계 부터 제대로 해서 메모리릭, 크래쉬, 버그없는 게임을 만들자... (이건 가능하기는 한건지 궁금 함...)

메모리 릭을 도저히 못잡겠으면

1. 메모리 얼로케이터를 만든다.

2. 스마트 포인터로 대체한다. (쓰고 있었다면 GG 추천 드립니다;;)

3. 코드를 다 지우고 새로 쓴다.

4. 때려 친다.

의 방법이 있음. ㅋㅋㅋㅋ.

 

[123123(121.150)]

와 글 한번 썼는데 1시간 가까이 걸리는걸 봐선 앞으론 쓰면 안되겠다...

[KB오BK(wintmiller)]

뀨츄드립니다

[율냥이(alszmtm)]

좋은 내용이긴 한데, 본문에 나온 사례들까지 최적화해야하는 정도면 최적화 엄청 잘한거란 생각이 듬... 보통은 좀더 초보적인 실수에서 슈퍼병목이 걸리기 때문에 본문 맨앞에 소개된 "병목찾기"가 굉장히 중요한거 같다.

[Otoflak(badlow)]

좋은 글이군요. 물론 다 읽었습니다

[Otoflak(badlow)]

메모리 풀을 써서 생성과 제거하는 부분을 명확하게 해도 좋을듯

[김젤딘(i12fly2u)]

규츄 (울면서 개추한다는 뜻)

[아둔이는요.(oppacoding)]

인디라이언에 퍼가도되나여?

[123123(121.150)]

똥글인데;;