[게임개발] 자료구조, 알고리즘

BIG-O 표기법

Big O는 연산 횟수를 추정해 데이터 증가에 따른 성능 변화를 파악
Big O는 데이터 규모 증가에 따른 성능 변화 추세를 보는 거라, 가장 영향력이 큰 최고차항만 남기고 상수나 낮은 차수의 항은 무시
O(n²)는 데이터 크기(n)가 커질수록 연산 횟수가 n의 제곱에 비례해 매우 빠르게 증가해요. 대규모 데이터에선 큰 부담

게임 프로그램에서 반복적으로 실행되는 메인 루프

입력 처리, 게임 로직 실행, 화면 렌더링

선형구조

자료를 순차적으로 나열한 구조
-배열 : 배열은 크기가 고정되어 있고 메모리에 연속적으로 저장, 동적 배열과 연결 리스트는 크기 변경이 자유로운 편
-연결리스트 : 연결 리스트는 노드의 다음/이전 연결만 바꿔주면 되기에 O(1)로 삽입/삭제가 빠름. 동적 배열은 뒤따르는 요소들을 모두 이동시켜야 해서 O(n)이 걸림

비선형 구조

하나의 자료 뒤에 다수의 자료가 올수 있는 형태
-트리, 그래프

미로생성 알고리즘

1, Binary Tree : 각 셀에서 오른쪽이나 아래 중 하나를 무작위로 생성
2, SideWinder : 오른쪽으로 연속된 셀 중 하나를 골라 아래로 파는 방식  
맵은 가로, 세로 좌표를 가지는 2차원 공간. 각 좌표의 타일 정보를 저장하고 접근하기 위해 2차원 배열이 가장 기본적인 형태로 사용

길찾기 알고리즘

1, 우수(오른손) 법칙 : 진행 방향을 기준으로 오른쪽에 벽이 있는지, 앞으로 갈 수 있는지, 아니면 왼쪽으로 돌아야 하는지를 우선순위에 따라 체크하며 이동
	1-1, 현재 바라보는 방향을 기준으로 오른쪽으로 갈수 있는 지 확인
    2-1, 현재 바라보는 방향을 기준으로 전진할수 있는 지 확인
    3-1, 왼쪽 방향으로 회전 
    
    ex)
    Up: 0, 
    Left: 1,
    Down: 2,
    Right: 3 
    오른쪽:  (N - 1 + 4) % 4
    왼쪽:  (N + 1 + 4) % 4

* 델타 타임은 이전 프레임과 현재 프레임 사이의 경과 시간. 이 시간을 누적하여 일정 기준을 넘으면 움직임을 실행하는 방식으로 속도를 조절.

그래프 이론

현실세계의 사물과 추상적인 개념간 연결관계 표현, 수학적그래프와 무관
정점: 데이터를 표현(사물, 개념 등)
간선: 정점들을 연결하는데 사용

*가중치 그래프: 간선에 수치
*방향 그래프: 간선에 화살표 표현

*그래프 순회방법
1, DFS(Depth First Search) : 깊이 우선 탐색
2, BFS(Breadth First search) : 너비 우선 탐색    

트리

계층적 구조를 갖는 데이터를 표현하기 위한 자료구조
노드: 데이터
간선: 노드의 계층구조를 표현

이진 검색 트리: 각 노드가 최대 두개의 자식노드를 갖는 트리
-왼쪽을 타고 가면 현재 값보다 작음
-오른쪽을 타고 가면 현재 값보다 큼
-기준없이 추가하면 한쪽으로 기울어져 균형이 깨지므로, 트리 재배치를 통해 균형을 유지하는게 중요(AVL, Red-Black)
	
힙 트리 1법칙: [부모노드]의 값은 [자식노드]의 값보다 크다
	제악조건: 1, 마지막 레벨을 제외한 모든레벨에 노드가 다 차있다
    		2, 마지막 레벨에 노드가 있을 경우 항상 왼쪽부터 순서대로 채워야 한다
힙 트리 2법칙: 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다.
	-> 배열을 통해 힙 구조를 바로 표현할 수 있다.
    	1) i번 노드의 왼쪽 자식은 [ (2*i)+1 ] 번
        2) i번 노드의 왼쪽 자식은 [ (2*i)+2 ] 번
        2) i번 노드의 부모는 [ (i-1)/2 ] 번
        
A Star
점수 매기기 : F = G+H
			F: 최종점수(작을 수록 좋음, 경로에 따라 달라짐)
            G: 시작점에서 해당 좌표까지 이동하는데 드는 비용(작을수록 좋음, 경로에 따라 달라짐)
            H: 목적지에서 얼마나 가까운지(작을수록 좋음, 고정값)