게임 프로그래머를 위한 자료구조와 알고리즘

제1부 개념

제1장 기본적인 알고리즘 분석
알고리즘 분석의 개요
빅 O 표기
여러 가지 복잡도들의 비교
그래픽 데모: 알고리즘 복잡도
결론

제2장 템플릿
템플릿이란 무엇인가?
템플릿 함수
기존의 방식
템플릿으로 해결
템플릿 클래스
여러 개의 매개변수화된 형식들
값을 템플릿 매개변수로 사용
특정 자료형의 값을 사용
다른 매개변수화된 형식의 값을 사용
템플릿의 문제점
Visual C++와 템플릿
템플릿의 내부적인 작동 방식
결론


제2부 기초

제3장 배열
배열이란 무엇인가?
그래픽 데모: 배열
배열 크기를 늘리거나 줄이기
항목을 삽입 또는 삭제
C/C++ 고유의 배열과 포인터
정적 배열들
동적 배열
배열 클래스와 유용한 알고리즘들
자료
생성자
소멸자
크기 변경 알고리즘
접근 연산자
변환 연산자
기존의 두 항목들 사이에 새 항목을 삽입
배열에서 항목 하나를 제거
더 빠른 제거 방법
배열의 크기 조회
예제 3-3
배열을 디스크에 저장, 로드
배열을 디스크에 기록
디스크로부터 배열을 읽기
파일 쓰기, 읽기에 대한 고려사항들
응용: 배열을 이용해서 게임 데이터를 저장
Monster 클래스
몬스터 배열의 선언
몬스터를 게임에 추가
더 나은 삽입 알고리즘
게임에서 몬스터를 제거
몬스터 제거 판단
게임 실행
분석: 게임에서의 배열
캐시 문제
배열의 크기 변경 문제
항목의 삽입, 제거
결론

제4장 비트벡터
비트벡터란 무엇인가?
그래픽 데모: 비트벡터
메인 화면
버튼 사용법
비트벡터 클래스의 작성
자료
생성자
소멸자
크기 변경 알고리즘
접근 연산자
Set 함수
ClearAll 함수
SetAll 함수
WriteFile 함수
ReadFile 함수
예제 4-1
응용: 빠른 저장
플레이어 클래스 작성
게임의 플레이어들을 저장
자료구조의 초기화
플레이어 속성의 변경
플레이어들을 디스크에 저장
게임 실행
비트필드
비트필드의 선언
비트필드의 사용
게임에서의 비트벡터와 비트필드
결론

제5장 다차원 배열
다차원 배열이란?
그래픽 데모: Array2D
C/C++ 고유의 다차원 배열
다차원 배열의 선언
다차원 배열의 접근
다차원 배열의 내부
동적인 다차원 배열
Array2D 클래스
Array3D 클래스
응용: 2차원 배열을 타일맵으로 사용
타일맵의 저장
타일맵의 생성
타일맵 그리기
게임 실행
응용: 계층적 타일맵
타일맵의 정의
타일맵의 초기화
수정된 렌더링 알고리즘
게임 실행
성능 비교
크기의 비교
분석: 게임에서의 다차원 배열
결론

제6장 연결된 목록
연결된 목록이란?
단일하게 연결된 목록
그래픽 데모: 단일하게 연결된 목록
구조
예제 6-4
단일 연결 목록의 장단점
이중으로 연결된 목록
그래픽 데모: 이중 연결 목록 데모
이중 연결 목록 클래스의 작성
이중 연결 목록의 알고리즘들
목록을 디스크에서 읽거나 디스크에 저장하기
연결 목록 쓰기
연결 목록 읽기
응용: 게임 인벤토리
Player 클래스
Item 클래스
아이템을 인벤토리에 추가
인벤토리에서 아이템을 제거
게임 플레이
응용: 개선된 계층적 타일맵
타일맵의 정의
타일맵의 생성
타일맵 그리기
연결 목록들의 분석과 비교
알고리즘 비교
크기 비교
실제 활용 상의 문제들
결론

제7장 스택과 대기열
스택
스택이란?
그래픽 데모: 스택
스택 함수들
스택의 구현
응용: 게임 메뉴
대기열
그래픽 데모: 대기열
대기열 함수들
대기열의 구현
응용: 명령 대기열
결론

제8장 해시 테이블
희소 자료란 무엇인가?
기본적인 해시 테이블
충돌
해시 함수
해시 테이블 구조의 개선
선형 오버플로우
2차 오버플로우
연결된 오버플로우
그래픽 데모: 해시 테이블
해시 테이블의 구현
HashEntry 클래스
HashTable 클래스
예제 8-1: 해시 테이블의 사용
응용: 해시 테이블에 자원 저장하기
String 클래스
테이블 사용
이 데모가 자원들을 로드하는 방식
데모 실행
결론

제9장 종합: 기초
클래스가 좋은 이유
자료를 클래스에 저장
정보의 은폐
상속
게임에서 클래스를 사용
게임 만들기
Adventure: Version One
데모 2 - 맵 편집기
결론


제3부 재귀와 트리

제10장 재귀
재귀란 무엇인가?
간단한 예: 거듭제곱
하노이의 탑
규칙
퍼즐 풀기
컴퓨터로 풀기
종료 조건
예제 10-1: 알고리즘의 실제 구현
그래픽 데모: 하노이의 탑
결론

제11장 트리
트리란 무엇인가?
트리의 재귀적 성질
트리의 공통적인 구조
그래픽 데모: 트리
튜토리얼
트리 클래스 만들기
구조
생성자
소멸자
Destroy 함수
Count 함수
트리 반복자
구조
기본적인 반복자 함수들
수직 반복자 함수들
수평 반복자 함수들
기타 함수들
트리 만들기
하향식
상향식
트리의 운행
전위 운행
후위 운행
그래픽 데모: 트리 운행
게임 데모 11-1: 플롯 라인
플롯 라인을 트리에 담기
게임 실행
결론

제12장 이진 트리
이진 트리란?
포화성
조밀성
균형
이진 트리의 구조
연결된 이진 트리
배열로 된 이진 트리
그래픽 데모: 이진 트리
이진 트리 작성
구조
생성자
소멸자와 Destroy 함수
Count 함수
BinaryTree 클래스의 사용
이진 트리의 운행
전위 운행
후위 운행
중위 운행
그래픽 데모: 이진 트리 운행
응용: 파싱
산술식
산술식의 파싱
재귀적인 하향식 파싱
데모 실행
결론

제13장 이진 검색 트리
BST란?
BST에 자료 삽입
BST의 자료 검색
BST에서 자료 제거
BST 규칙
최적이 아닌 트리
그래픽 데모: BST
BST의 구현
구조
비교 함수
생성자
소멸자
Insert 함수
Find 함수
예제 13-1: BST 클래스의 사용
응용: 다시 만든 자원 저장 데모
Resource 클래스
비교 함수
자원의 삽입
자원 찾기
데모 실행
결론

제14장 우선순위 대기열과 힙
우선순위 대기열이란?
힙이란 무엇인가?
힙과 우선순위 대기열의 관계
그래픽 데모: 힙
힙 클래스의 작성
구조
생성자
Enqueue 함수
WalkUp 함수
Dequeue 함수
WalkDown 함수
응용: 건물 짓기 대기열
유닛들
제조 공장 만들기
힙
힙에 유닛 추가
생산 시작
생산 완료
데모 실행
결론

제15장 게임 트리와 최소최대 트리
게임 트리란 무엇인가?
최소최대 트리란 무엇인가?
그래픽 데모: 최소최대 트리
게임 상태
좀 더 복잡한 게임
응용: 조약돌 옮기기 게임
게임 상태
전역 변수들
게임 트리의 생성
게임의 진행
게임 실행
좀 더 복잡한 게임들
끝이 없는 게임들
방대한 게임들
제한된 깊이의 게임들
결론

제16장 종합: 트리
게임 확장
맵 형식 수정
게임 데모 16-1: 개선된 게임
맵 편집기
이후의 개선
결론


제4부 그래프

제17장 그래프
그래프란 무엇인가?
연결된 목록과 트리
그래프
그래프의 구성 요소
그래프의 종류
양방향 그래프
단방향 그래프
가중 그래프
타일맵
그래프의 구현
인접성 참조표
방향 참조표
범용적인 연결된 그래프
그래픽 데모: 그래프
그래프의 운행
깊이 우선 탐색
너비 우선 탐색
그래프 운행에 대해 한 마디
그래픽 데모: 그래프 운행
그래프 클래스
GraphArc 클래스
GraphNode 클래스
Graph 클래스
응용: 방향 참조표 그래프를 이용한 던전 만들기
맵
맵 만들기
맵 그리기
맵을 돌아다니기
데모 실행
응용: 포탈 엔진
구역들
구역의 가시성 판정
데모 작성
데모 실행
결론

제18장 그래프를 AI에 이용: 유한상태기계
유한상태기계란 무엇인가?
복잡한 유한상태기계
유한상태기계의 구현
그래픽 데모: 유한상태기계
좀 더 복잡한 유한상태기계
상태의 중복
조건부 사건
조건부 사건 기계의 표현
그래픽 데모: 조건부 사건
게임 데모 18-1: Intruder
코드
데모 실행
결론

제19장 종합: 그래프
새 맵 형식
새로운 방 항목 구조
파일 형식
게임 데모 19-1: 새 맵 형식을 도입
방향맵
게임 로직의 변화
게임 실행
기존 맵의 변환
방향맵 편집기
초기 맵
타일의 설정, 해제
맵 불러오기
맵 저장
편집기 사용법
타일맵 편집기의 수정
Save 함수
Load 함수
결론


제5부 알고리즘

제20장 자료의 정렬
가장 간단한 정렬: 거품 정렬
거품 정렬의 최악의 경우
그래픽 데모: 거품 정렬
거품 정렬의 구현
저절로 정렬: 힙 정렬
그래픽 데모: 힙 정렬
힙 정렬의 구현
가장 빠른 정렬: 퀵정렬
기준값 선택
퀵정렬의 수행
그래픽 데모: 퀵정렬
퀵정렬의 구현
그래픽 데모: 경주
현명한 정렬: 기수 정렬
그래픽 데모: 기수 정렬
기수 정렬의 구현
다른 정렬 방법들
응용: 깊이에 기반한 게임
Player 클래스
전역 변수들
플레이어 비교 함수
플레이어들의 초기화
플레이어들의 정렬
플레이어들을 그리기
게임 실행
결론

제21장 자료의 압축
자료를 압축해야 하는 이유
자료의 전송 통로
인터넷
연속열 길이 인코딩
RLE에 적합한 형태의 자료는 어떤 것일까?
그래픽 데모: RLE 압축
RLE 압축기, 해제기의 작성
허프만 트리
허프만 디코딩
허프만 트리의 생성
허프만 트리 클래스의 작성
예제 21-3
시험용 파일들
예제 21-4
자료의 암호화
기타 기법들
결론

제22장 난수
정수 난수의 생성
프로그램 안에서 난수 생성하기
rand와 srand
가변적인 종자값
특정 범위의 난수 생성
난수 비율의 생성
부동소수점 난수의 생성
비선형 난수의 생성
확률 분포 그래프
두 난수 더하기
세 난수 더하기
그래픽 데모: 난수 분포 그래프
결론

제23장 길찾기
기본적인 길찾기
무작정 튀기기
벽 짚고 따라가기
견고한 길찾기 방법들
너비 우선 탐색
좀 더 똑똑한 길찾기
발견적 방법의 개선
A* 길찾기
그래픽 데모: 경로 비교
가중치가 부여된 맵
응용: 잠입
타일맵이 아닌 맵에서의 길찾기
선 기반 길찾기
4진 트리
웨이포인트
결론

제24장 종합: 알고리즘
길찾기로 적 유닛들을 좀 더 똑똑하게 만들기
길찾기 기능을 TileMap 클래스에 추가
DirectionMap 클래스에 길찾기 기능을 추가
GetClosestDirection 함수의 시각화
추가적인 개선
효율성
게임 실행
결론

제25장 결론
추가적인 주제들
추천 도서, 참고자료
자료구조 책들
C++ 책들
게임 프로그래밍 책들
웹 사이트들
결론


제6부 부록

부록 A C++ 기초
기본적인 비트 산술
이진수
컴퓨터의 저장 방식
비트 단위 부울 연산
C++의 비트 단위 부울 연산
비트 이동
이 책에 쓰인 표준 C/C++ 함수들
기본 입출력
파일 입출력
수학 함수들
time 함수
난수 함수들
예외와 오류 처리
ASSERT 매크로
반환 코드
예외
왜 C++인가?
클래스에 대해
생성자
소멸자
연산자 중복
변환 연산자
this 포인터
인라인 함수
함수 포인터
결론

부록 B 컴퓨터 프로그램의 메모리 구조
메모리 구역들
코드 메모리
전역 메모리
전역 변수들
정적 변수들
스택
지역 변수
매개변수
반환값
자유 저장소
결론

부록 C SDL 입문
사용권
SDL 사용 준비
파일들
파일 준비
Visual C++ 설정
프로젝트 설정
SDL_TTF 설정
프로그램의 실행과 배포
SDL 사용법
SDL_Video
SDL 이벤트 처리
SDL_Timer
SDL_TTF
SDLHelpers 라이브러리
SDLFrame
SDLGUI 라이브러리
SDLGUI 클래스
SDLGUIItem 클래스
SDLGUI 요소들
SDLGUIFrame
결론

부록 D STL 입문
STLPort
STL 대 이 책
이름공간
STL의 구성
컨테이너들
순차 컨테이너
연관 컨테이너들
컨테이너 어댑터
기타 컨테이너들
결론

찾아보기