Data structures and algorithms for game developers

1 Introduction to Data Structures 1
Data Structures and Algorithms 2
Data Structures in Games and Simulations 4
C++ versus Java and C# 6
The C++ STL 11
Template Classes and Functions 12
Big-O Notation 15
Summary 17
Chapter Review Questions 17
2 Arrays 19
The Data Structures Known as Arrays 20
Algorithms: Insertion and Deletion 25
Ordered Arrays 31
Algorithms: Basic Searches 33
STL Arrays 47
Bit Arrays 63
Summary 70
Chapter Review Questions 70
Programming Projects 71
3 Recursion 73
Recursion Defined 75
Triangular Numbers 81
Factorials 86
Summary 89
Chapter Review Questions 89
Programming Projects 90
Contents
v
4 Introduction to Sorting 91
Introduction to Sorting 92
The Bubble Sort 93
The Selection Sort 98
The Insertion Sort 101
STL Sorting 105
The Merge Sort 109
Summary 115
Chapter Review Questions 116
Programming Projects 118
5 Link Lists 119
Introduction to Link Lists 120
Singly and Double-Ended Linked Lists 124
Doubly Linked Lists 135
STL Link Lists 141
Tips and Things to Remember When Using Link Lists 151
Summary 152
Chapter Review Questions 152
Programming Projects 153
6 Stacks and Queues 155
Introduction to Stacks 156
STL Stacks 168
Introduction to Queues 172
STL Queues 194
Summary 206
Chapter Review Questions 206
Programming Projects 207
7 Hash Tables 209
Introduction to Hash Tables 210
Hash Functions 213
Working with Hash Tables 215
Implementing Hash Tables 220
Nonstandard Hash Containers 242
Summary 250
Chapter Review Questions 251
Programming Projects 252
8 Advanced Sorting 253
Advanced Sorting Topics 254
vi Contents
Shellsort 255
Partitioning 260
Quicksort 265
Radix Sort 275
Additional Types of Sorting 280
Summary 282
Chapter Review Questions 282
Programming Projects 284
9 Trees 285
Introduction to Trees 286
Tree Example 289
Binary Trees 298
k-dimensional Trees 315
Additional Types of Trees 322
Summary 324
Chapter Review Questions 324
Programming Projects 326
10 Heaps 327
Introduction to Heaps 328
Heap Sort 336
Priority Queues Using Heaps 339
STL Heap Functions 346
Summary 348
Chapter Review Questions 348
Programming Projects 350
11 Graphs 351
Introduction to Graphs 352
Searching with Graphs 357
Topological Sorting 376
Weighted Graphs 385
Artificial Intelligence 391
Summary 393
Chapter Review Questions 394
Programming Projects 396
12 Additional STL Algorithms 397
Strings 398
map and multimap 404
set and multiset 411
Contents vii
STL Algorithms 415
Summary 427
Chapter Review Questions 428
Programming Projects 429
13 Scene Management 431
Introduction to Scene Management 432
Game Math 435
Scene Graphs 449
Binary Space Partitioning Trees 460
Quad-Trees and Octrees 466
Additional Management Topics 472
Summary 477
Chapter Review Questions 478
Programming Projects 479
14 Data Compression 481
Introduction to Data Compression 482
Introduction to Texture Compression 494
Introduction to Data Encryption 514
Summary 515
Chapter Review Questions 515
Programming Projects 517
15 Conclusions 519
Quick Review 520
The Next Step 524
Summary 525