Description
Book SynopsisThe essential guide to solving algorithmic and networking problems in commercial computer games, revised and extended
Algorithms and Networking for Computer Games, Second Editionis written from the perspective of the computer scientist. Combining algorithmic knowledge and game-related problems, it explores the most common problems encountered in game programing.
The first part of the book presents practical algorithms for solving classical topics, such as random numbers, procedural generation, tournaments, group formations and game trees. The authors also focus on how to find a path in, create the terrain of, and make decisions in the game world.
The second part introduces networking related problems in computer games, focusing on four key questions: how to hide the inherent communication delay, how to best exploit limited network resources, how to cope with cheating and how to measure the on-line game data.
Thoroughly revised, updated, and
Trade Review
“More than 70 algorithms are presented, covering random numbers, noise in data (a realistic world is full of imperfections), procedural generation, tournaments, game trees, path finding, group movement, decision making, and modelling uncertainty – as well as networking problems, including dealing with cheating. The exercises at the end of each chapter range from simple thought exercises to studying Braben and Bell’s namegeneration algorithm from Elite (1984) … use of pseudocode throughout ensures the book works equally well for C, C++, Java, Python, or even C# programmers.” MagPi, Issue 64, December 2017
Table of ContentsPreface xiii
1 Introduction 1
1.1 Anatomy of Computer Games 4
1.2 Game Development 6
1.2.1 Phases of development 7
1.2.2 Documentation 8
1.2.3 Other considerations 11
1.3 Synthetic Players 12
1.3.1 Humanness 13
1.3.2 Stance 14
1.4 Multiplaying 14
1.5 Interactive Storytelling 15
1.5.1 Approaches 16
1.5.2 Storytelling in games 17
1.6 Outline of the Book 19
1.6.1 Algorithms 20
1.6.2 Networking 20
1.7 Summary 21
Exercises 21
I Algorithms 25
2 Random Numbers 26
2.1 Linear Congruential Method 27
2.1.1 Choice of parameters 30
2.1.2 Testing the randomness 32
2.1.3 Using the generators 33
2.2 Discrete Finite Distributions 36
2.3 Random Shuffling 40
2.4 Summary 44
Exercises 44
3 Noise 49
3.1 Applying Noise 50
3.2 Origin of Noise 51
3.3 Visualization 52
3.4 Interpolation 55
3.4.1 Utility routines for value conversions 56
3.4.2 Interpolation in a single parameter 58
3.4.3 Interpolation in two parameters 61
3.5 Composition of Noise 62
3.6 Periodic Noise 65
3.7 Perlin Noise 68
3.8 Worley Noise 73
3.9 Summary 83
Exercises 83
4 Procedural Generation 88
4.1 Terrain Generation 89
4.2 Maze Algorithms 96
4.2.1 Depth-first algorithm 98
4.2.2 Randomized Kruskal’s algorithm 99
4.2.3 Randomized Prim’s algorithm 101
4.3 L-Systems 101
4.3.1 Examples 103
4.3.2 City generation 105
4.4 Hierarchical Universe Generation 108
4.5 Summary 109
Exercises 111
5 Tournaments 115
5.1 Rank Adjustment Tournaments 118
5.2 Elimination Tournaments 123
5.3 Scoring Tournaments 131
5.4 Summary 135
Exercises 138
6 Game Trees 143
6.1 Minimax 144
6.1.1 Analysis 147
6.1.2 Partial minimax 148
6.2 Alpha-Beta Pruning 152
6.2.1 Analysis 156
6.2.2 Principal variation search 157
6.3 Monte Carlo Tree Search 157
6.4 Games of Chance 166
6.5 Summary 168
Exercises 170
7 Path Finding 177
7.1 Discretization of the Game World 178
7.1.1 Grid 179
7.1.2 Navigation mesh 180
7.2 Finding the Minimum Path 182
7.2.1 Evaluation function 183
7.2.2 Properties 184
7.2.3 Algorithm A* 185
7.3 Realizing the Movement 187
7.4 Summary 189
Exercises 190
8 Group Movement 194
8.1 Flocking 195
8.2 Formations 200
8.2.1 Coordinating formations 200
8.2.2 Behaviour-based steering 204
8.2.3 Fuzzy logic control 205
8.2.4 Mass-spring systems 207
8.3 Summary 208
Exercises 208
9 Decision-Making 211
9.1 Background 211
9.1.1 Levels of decision-making 212
9.1.2 Modelled knowledge 213
9.1.3 Methods 214
9.2 Finite State Machines 218
9.2.1 Computational FSM 221
9.2.2 Mealy and Moore machines 224
9.2.3 Implementation 227
9.2.4 Discussion 228
9.3 Influence Maps 231
9.4 Automated Planning 235
9.5 Summary 237
Exercises 240
10 Modelling Uncertainty 246
10.1 Statistical Reasoning 246
10.1.1 Bayes’ theorem 246
10.1.2 Bayesian networks 248
10.1.3 Dempster–Shafer theory 249
10.2 Fuzzy Sets 252
10.2.1 Membership function 253
10.2.2 Fuzzy operations 255
10.2.3 Defuzzification 255
10.3 Fuzzy Constraint Satisfaction Problem 257
10.3.1 Modelling the criteria as fuzzy sets 259
10.3.2 Weighting the criteria importances 262
10.3.3 Aggregating the criteria 262
10.3.4 Making a decision 263
10.4 Summary 263
Exercises 265
II Networking 268
11 Communication Layers 269
11.1 Physical Platform 270
11.1.1 Resource limitations 271
11.1.2 Transmission techniques and protocols 272
11.2 Logical Platform 274
11.2.1 Communication architecture 274
11.2.2 Data and control architecture 275
11.3 Networked Application 277
11.4 Summary 278
Exercises 278
12 Compensating Resource Limitations 283
12.1 Aspects of Compensation 284
12.1.1 Consistency and responsiveness 284
12.1.2 Scalability 287
12.2 Protocol Optimization 291
12.2.1 Message compression 291
12.2.2 Message aggregation 292
12.3 Dead Reckoning 293
12.3.1 Prediction 293
12.3.2 Convergence 295
12.4 Local Perception Filters 297
12.4.1 Linear temporal contour 301
12.4.2 Adding bullet time to the delays 305
12.5 Synchronized Simulation 307
12.6 Interest Management 308
12.6.1 Aura-based interest management 310
12.6.2 Zone-based interest management 310
12.6.3 Visibility-based interest management 312
12.6.4 Class-based interest management 312
12.7 Compensation by Game Design 314
12.7.1 Short active turns 314
12.7.2 Semi-autonomous avatars 315
12.7.3 Interaction via proxies 316
12.8 Summary 317
Exercises 318
13 Cheating Prevention 321
13.1 Technical Exploitations 322
13.1.1 Packet tampering 323
13.1.2 Look-ahead cheating 324
13.1.3 Cracking and other attacks 330
13.2 Collusion 331
13.2.1 Classification 333
13.2.2 Collusion detection 335
13.3 Rule Violations 337
13.4 Summary 338
Exercises 338
14 Online Metrics 341
14.1 Players 344
14.2 Monetization 345
14.3 Acquisition 347
14.4 Game Session 347
14.5 Summary 348
Exercises 348
A Pseudocode Conventions 351
A.1 Changing the Flow of Control 355
A.1.1 Expressions 355
A.1.2 Control structures 357
A.2 Data Structures 360
A.2.1 Values and entities 360
A.2.2 Data collections 360
A.3 Format of Algorithms 365
A.4 Conversion to Existing Programming Languages 367
B Practical Vectors and Matrices 371
B.1 Points and Vectors 372
B.2 Matrices 381
B.3 Conclusion 387
Bibliography 391
Ludography 408
Index 409
