基本信息
源码名称：c++常用游戏算法及数据结构设计.pdf
源码大小：1.16M
文件格式：.pdf
开发语言：C/C++
更新时间：2021-02-06
   友情提示：（无需注册或充值，赞助后即可获取资源下载链接）

     嘿，亲！知识可是无价之宝呢，但咱这精心整理的资料也耗费了不少心血呀。小小地破费一下，绝对物超所值哦！如有下载和支付问题，请联系我们QQ(微信同号)：813200300

本次赞助数额为： 2 元　
   源码介绍
Algorithms and Data Structures for Games Programming.pdf

Contents
1 Introduction and Overview 1
1.1 Aims and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Syllabus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.1 Continuous Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Reading List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Array Containers 1
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2 An Array class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2.1 Major points to note in Array.h . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 A Simple Client Program for Array . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 The Big-Three . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Defence against naive defaults . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Overloading the Stream Output Operator . . . . . . . . . . . . . . . . . . . . . . 17
2.6 std::vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6.1 Points to note in vectort1.cpp . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Analysis of Algorithms 1
3.1 O Notation (Big-oh) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.2 Estimating the Growth Rate of an Algorithm . . . . . . . . . . . . . . . . . . . . 3
3.2.1 Simple Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2.2 Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2.3 Counting Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Sorting and Searching 1
4.1 Bubble-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
4.1.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
4.2 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.2.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.3 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.3.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.4 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.4.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.5.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.5.2 Standard Library Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.6 Comparison: Bubble, Selection, Insertion and Merge and Quick Sorts . . . . . . . 9
0–1
4.7 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.7.1 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.7.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.7.3 Logarithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.7.4 Is Binary Search Really Faster than Linear? . . . . . . . . . . . . . . . . . 12
5 Linked Lists 1
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
5.2 A Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
5.2.1 Class Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
5.2.2 Dissection of List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.2.3 Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.3 A simple List client program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.4 Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.4.1 Brief Discussion of the Doubly Linked List . . . . . . . . . . . . . . . . . 19
5.4.2 Simple Test Program, ListT1.cpp . . . . . . . . . . . . . . . . . . . . . . 20
5.4.3 Doubly Linked List Implementation . . . . . . . . . . . . . . . . . . . . . 24
5.5 Arrays versus Linked List, Memory Usage . . . . . . . . . . . . . . . . . . . . . . 31
5.6 Arrays versus Linked List, Cache issues . . . . . . . . . . . . . . . . . . . . . . . . 31
6 Stacks and Queues 1
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
6.2 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
6.2.1 Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
6.2.2 A simple client program . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
6.3 Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
6.3.1 Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
6.3.2 A simple client program . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.4 Stack Application — RPN Calculator . . . . . . . . . . . . . . . . . . . . . . . . 10
6.4.1 RPN Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.4.2 Conversion from Infix to Postfix . . . . . . . . . . . . . . . . . . . . . . . 14
6.5 Stack Application — Balancing Brackets . . . . . . . . . . . . . . . . . . . . . . 16
6.6 Appendix. Illustration of Dijkstra’s Shunting Algorithm . . . . . . . . . . . . . . . 18
7 Trees 1
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
7.2 Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
7.2.1 Binary Search Tree Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
7.2.2 Notes on BST.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
7.2.3 Traversal of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2.4 Exercising Program, BSTT1.cpp . . . . . . . . . . . . . . . . . . . . . . . 9
7.3 n-ary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8 Recursion 1
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
8.2 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
8.2.1 Deduction versus Induction . . . . . . . . . . . . . . . . . . . . . . . . . . 3
8.3 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
8.4 Recursion in Compilers and Calculators . . . . . . . . . . . . . . . . . . . . . . . 8
8.4.1 Prefix, infix, postfix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
0–2
8.5 Proving Termination of Recursive and Other Non-deterministic Algorithms . . . . 9
8.6 Divide-and-Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.6.1 Maximum of an Array using Divide and Conquer . . . . . . . . . . . . . . 10
8.6.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.6.3 Towers of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.6.4 Drawing a Ruler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8.7 Trees and Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
8.7.1 Recursive drawing of a ruler . . . . . . . . . . . . . . . . . . . . . . . . . 21
8.7.2 Recursive maximum of an array . . . . . . . . . . . . . . . . . . . . . . . 21
8.7.3 Recursive evaluation of a prefix expression . . . . . . . . . . . . . . . . . . 23
8.8 Elimination of Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
9 Trees Miscellany 1
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
9.2 n-ary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
9.3 Game Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
9.3.1 Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
9.3.2 Minimax Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
9.3.3 Recursive Minimax Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 7
9.3.4 Minimax Applied to Tic-tac-toe . . . . . . . . . . . . . . . . . . . . . . . 8
10 Simple Pathfinding 1
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
10.2 Deque Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
10.2.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
10.2.2 Discussion of sDeque.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
10.3 Path-finding in a Maze — Depth-first and Breadth-first Searching . . . . . . . . . 4
10.3.1 Maze implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
10.3.2 Depth-first pathfinding solution . . . . . . . . . . . . . . . . . . . . . . . 8
10.3.3 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
10.3.4 Absolute dead end . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
10.3.5 Breadth-first pathfinding solution . . . . . . . . . . . . . . . . . . . . . . 13
10.4 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
11 Graphs 1
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
11.2 Examples of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
11.2.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
11.2.2 Games and Path-finding . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
11.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
11.4 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
11.4.1 Depth-first Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
11.4.2 Breadth-first Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
11.5 Software Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
11.5.1 Basics of Graph.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
11.5.2 Depth-first Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
11.5.3 Use of Stack for Depth-first? . . . . . . . . . . . . . . . . . . . . . . . . 11
11.5.4 Animated Display of the Traversal . . . . . . . . . . . . . . . . . . . . . . 12
11.5.5 Breadth-first Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
0–3
11.5.6 Depth-first and Breadth-first, a Summary . . . . . . . . . . . . . . . . . . 14
12 Pathfinding 1
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
12.2 Pathfinding as a graph search problem . . . . . . . . . . . . . . . . . . . . . . . . 1
12.3 Graph search — informed or uninformed? . . . . . . . . . . . . . . . . . . . . . . 4
12.4 Graph search pathfinding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
12.4.1 Uninformed graph search . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
12.4.2 Breadth-first pathfinding — basic algorithm . . . . . . . . . . . . . . . . . 4
12.4.3 Informed graph search — add a heuristic . . . . . . . . . . . . . . . . . . 6
12.4.4 Depth-first pathfinding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
12.5 Practical examples of graph-search algorithms . . . . . . . . . . . . . . . . . . . . 8
12.5.1 Silly Breadth-first . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
12.5.2 Breadth-first . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
12.5.3 Distance-first . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
12.5.4 ’Simple’ Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
12.5.5 Distance Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
12.5.6 AStar Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
12.6 Algorithms Applied to a Maze problem . . . . . . . . . . . . . . . . . . . . . . . . 17
12.7 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
12.7.1 Performance Measures for Breadth first . . . . . . . . . . . . . . . . . . . 19
12.7.2 Performance Measures for Depth first . . . . . . . . . . . . . . . . . . . . 21
12.8 Pathfinding in non-tile-based environments . . . . . . . . . . . . . . . . . . . . . . 21
12.9 Software Implementations of the Algorithms . . . . . . . . . . . . . . . . . . . . . 22
13 Sets and Maps 1
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
13.2 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
13.3 Bitvector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
13.4 Hashing and Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
13.5 Example Use of set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
13.6 Sets need to be able to order elements . . . . . . . . . . . . . . . . . . . . . . . . 5
13.7 Example Use of multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
13.8 A Name class whose objects we want to insert in set . . . . . . . . . . . . . . . . 8
13.9 Set of Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
13.10A Telephone Directory using a map . . . . . . . . . . . . . . . . . . . . . . . . . 13
13.11A Telephone Directory using a multimap . . . . . . . . . . . . . . . . . . . . . . . 16