Algorithms and Networking for Computer Games

Preface 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