[게임프로그래밍전문가] 필기이론 간단정리 - 프로그래밍기반이론(2)

제3과목 프로그래밍 기반 이론(2)

4. 검색알고리즘

(1) 순차검색 : 자료 파일에 특정한 원소를 첫번째 레코드부터 해당키로 순차적으로 찾는 것

대상의 자료가 정렬되어 있지 않을 경우 탐색

(2) 트리탐색

① 트리종류

- 순서트리 : 레벨이 같은 노드들의 좌우 배열 순서의 위치가 고정되어 노드들의 위치가 중요한 트리

- 비순서트리 : 계층상 의미가 중요, 형제노드들 위치 중요하지 않음

- 닮은트리 : 트리의 노드와 위치는 같으나 내용만 다른 트리

- 경사트리 : 좌측 또는 우측 트리만 존재하는 트리

- 이진트리 : 자식노드가 2개 이하인 트리, 차수가 2이하인 트리

+ 이진트리 종류 : 경사트리, 전이진트리, 정이진트리

+ 이진트리표현 : 연결리스트(기억장소 낭비 적음)

+ 이진탐색 : 순차적으로 정리되어 있는 자료에 대하여 항상 중간값과 비교해서 자료를 탐색하는 방법

+ 검색시 반드시 정렬되어 있어야 함

+ 검색효율 좋음, 알고리즘구현 쉬움, 자료수가 많을수록 효율

+ 자료의 개수가 많아짐에 따라 순차탐색에 비해 사용되는 시간이 절약

+ 이진트리의 순회

전위순회(Preorder) : DLR, 중위순회(Inorder) : LDR, 후위순회(Postorder) : LRD

(3) 보관탐색 : 키의 분포를 미리 알고 있을 때 능률적인 탐색, 반드시 정렬되어 있어야 함

(4) 피보나치탐색 : 이분검색과 유사하나 비교 후 결과를 피보나치 수열에 따라 다음 비교 대상 선정 평균 비교횟수가 적다

(5) 해싱법 : 값을 비교하지 않고 키값에서 자료가 저장되어 있는 주소로 직접계산

- 해시함수종류 : 나눗셈법(나머지주소), 제곱중간법(중간부분값), 폴딩법(키를 나눠서 각 부분을 더하거나 XOR(배타적논리합)취함으로써 주소 계산)

* 서로 다른키가 같은 홈수소를 가지는 현상(Collicion, crach)

5. 그래픽알고리즘

* V(G) : 그래프 정점들의 집합, E(G) : 그래프의 간선들의 집합

(1) 종류

- 무향그래프 : 간선에 방향성이 업어서 연결된 정점들의 순서가 없는 그래프, 실선을 간선 표현

- 유향그래프 : 간선에 방향성이 있어서 정점들의 순서가 정해진 그래프 화살표 간선의 방향표시

- 완전그래프 : 모든 정점의 쌍을 연결하는 간선의 존재, 같은 수의 정점을 가지는 그래프들 중 가장 많은 간선보유

- 차수 : 한 정점에 연결된 간선의 수, 인입(들어가는)과 인출(나가는)

(2) 그래프표현방법

① 인접행렬M은 n*n 정방 핼렬로서 N 은 그래프 내의 정점수 n(n-1)간선표현, 완전그래프를 제외한 그래프는 행렬원소 0값을 가진다, 상당량이 장소 낭비

② 인접리스트 : 인접한 정점들의 연결리스트 표현, 기억장소 절약, 간선의 수가 많으면 기억장소 낭비

(3) 순회

① 깊이우선탐색

- 특정정점을 시점으로 선택, 방문표시, 여러 정점들 검사, 방문하지 않은 정점은 새롭게 선택 원래 정점을 스택에 삽입, 방문한 것이 없으면 최종적인 정점을 꺼내서 새롭게 선택, 스택이 빌 때까지 과정반복

② 너비우선탐색 : 큐가 비워질 때까지 위 과정 반복, 인접한 모든 정점 방문

(4) 신장트리(Spanning Tree)

- 최소 서브그래프

- 그래프 G의 서브 그래프 중에서 G의 모든 정점을 연결하는 트리

- 깊이우선 스패닝트리 : DFS 결과로 스패닝트리 구성

- 너비우선 스패닝트리 : BFS

(5) 최소비용 신장트리

- Prim 알고리즘 : 임의의 정점에서 가중치가 가장 적은 간선 선택

- Kruskal 알고리즘 : 현재 간선들의 LIST에서 가중치가 가장 적은 간선 선택

6. 스트링처리 알고리즘

- 스트링은 문자의 연속 문자열을 의미

(1) 문자열검색 알고리즘

- Brute force 알고리즘 : 문자열을 찾고 하는 것

- Rk(Rabin-karp Algorithm)알고리즘 : 해시값과 비교하여 해시값만 필요

- kmp알고리즘 : 비교 실패시 지금까지 일치성을 이용해서 부분 매칭결과를 도출

- Boyer-moore algorithm(BM 알고리즘) : 텍스트상의 문자이용 이동량, 긴 경우 효율, 패턴을 오른쪽에서 왼쪽으로 조사, O(n)

(2) 문자열의연산

- 결합 치환 삽입 제거 패터매칭 : 문자열검색

7. 장르별 게임알고리즘 적용

(1) 알고리즘 적용 대상의 분류

- 네트워크, 3D그래픽, 2D그래픽, 사운드 알고리즘, 인공지능 알고리즘

- 게임제작 기술면에서 분류에 대한 알고리즘

- 서버/클라이언트 알고리즘

(2) 3D알고리즘

- BSP : 3D공간상의 폴리곤들을 카메라 위치에 따라 동적으로 정렬시켜 좌표상에 뒤에서부터 앞쪽으로 앞쪽에서 뒤쪽으로 정렬되는 페인트 알고리즘의 확장된 형태

- 옥트리(Octree) : x, y, z축 세 개를 기준으로 공간을 분할하여 생성한 트리

- Portal : 카메라로부터 뷰볼룸일 이 Portel 에 Projection시키는 것

- pvs : Visible surface Detemination의 알고리즘하나이다

- LOD : 카메라와 대상 물체와의 거리에 따라서 적절한 모델을 사용하는 방법, 가변적이다

- 스카이박스 : 배경은 렌더링 시간을 줄이기 위하여 배경 그림을 텍스쳐 형태로 처리, 렌더링하지 않아도 된다, 렌더링 시간 절약

- 하이트필드 : 지형표현 방법하나, 모델링으로 표현하지 않음, 각 정점에 대한 고도 정보만 저장

지형과 카메라에 따라 다른 형태가 나온다, 동적 생성

- 충돌검사 : 총알이나 미사일같은 객체들 사이에서 서로 간의 충돌 여부를 검사하는 알고리즘

물체가 복잡해질수록 문제가 발생

(3) 2D그래픽 알고리즘

- Isormetric 알고리즘 : 스타크와 같은 쿼터뷰 수학형태 알고리즘

- 타일처리알고리즘, 스프라이트알고리즘

(4) 3D사운드알고리즘

- 3D위치와 거리, 스테레오 도플러 효과를 고려한 음을 지원하는 알고리즘

(5)인공지능알고리즘

- 유한상태머신(FSM) : 캐릭터의 현재상태에 대한 다음 상태가 정해지는 알고리즘, 이벤트처리를 위하여 가장 보편적

- 디시전 메이킹 알고리즘 : 상태머신 다음으로 널리 사용, 현대 상태에 따라 트리형태로 나누어 해당하는 행동을 처리하는 알고리즘

- 규칙기반 시스템 : 규칙기반 시스템은 현재의 입력 상태는 IF THEN으로 사용

- 신경망 : 결과가 도달할 때까지 가중치를 조절하여 자동적으로 학습하는 것

- 스크립트 : 언어의 복잡한 작업을 단순화하기 위하여 생성된 언어

- 퍼지로직 : 애마한 처리를 가능하도록 한 불학실정 성격을 가진 수학적인 모델

- 플래닝 : 최종적으로 결과를 위한 액션에 대한 계획을 만드는 알고리즘

(6) 게임장르 면에서 알고리즘

- 슈팅게임 : AI알고리즘필요, 슈테게임 스크립트 : 적의 출현위치 및 적의 이동방법

- RPC, 어드벤처게임 : 인공지능알고리즘필요

- RTS(실시간전략게임) A*알고리즘사용, 보드게임 : AI알고리즘

8. 물리/수학 알고리즘

??