Algorithms and Networking for Computer Games

Informationen zum Autor Jouni Smed holds a doctorate in Computer Science and acts as a Senior Lecturer and Adjunct Professor at the University of Turku, Finland. He is also the co-founder of Turku Game Lab, which aims at bringing together technologically- and artistically-oriented students to collaborate on game projects and jump-start their careers in the game industry. For the past twenty years, his research interests have focused on various areas of game development: from code tweaking to software processes and from simple puzzles to multisite game development. Harri Hakonen works as a senior software developer at Ericsson, being a member of a small team implementing embedded real-time products over Linux. He has thirty years of computer-related experience, covering various professions at academy, software industry and startups. Harri has always been keen on concrete software construction, from implementing low level bit-fiddling to catalyzing teamwork, and he will never stop programming. Klappentext The essential guide to solving algorithmic and networking problems in commercial computer games, revised and extendedAlgorithms and Networking for Computer Games, Second Edition is 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 expanded to reflect the many constituent changes occurring in the commercial gaming industry since the original, this Second Edition, like the first, is a timely, comprehensive resource offering deeper algorithmic insight and more extensive coverage of game-specific networking problems than ordinarily encountered in game development books.Algorithms and Networking for Computer Games, Second Edition:* Provides algorithmic solutions in pseudo-code format, which emphasises the idea behind the solution, and can easily be written into a programming language of choice* Features a section on the Synthetic player, covering decision-making, influence maps, finite-state machines, flocking, fuzzy sets, and probabilistic reasoning and noise generation* Contains in-depth treatment of network communication, including dead-reckoning, local perception filters, cheating prevention and on-line metrics* Now includes 73 ready-to-use algorithms and 247 illustrative exercisesAlgorithms and Networking for Computer Games, Second Edition is a must-have resource for advanced undergraduate and graduate students taking computer game related courses, postgraduate researchers in game-related topics, and developers interested in deepening their knowledge of the theoretical underpinnings of computer games and in learning new approaches to game design and programming. Zusammenfassung The essential guide to solving algorithmic and networking problems in commercial computer games, revised and extended Algorithms and Networking for Computer Games, Second Edition is written from the perspective of the computer scientist. Inhaltsverzeichnis Preface xiii1 Introduction 11.1 Anatomy of Computer Games 41.2 Game Development 61.2.1 Phases of development 71.2.2 Documentation 81.2.3 Other considerations 111.3 Synthetic Players 121.3.1 Humanness 131.3.2 Stance 141.4 Multiplaying 141.5 Interactive Storytelling 151.5.1 Approaches 161.5.2...

List of contents

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

Report

"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

Product details

• Authors: Harri Hakonen, Harri (University of Turku Hakonen, Hakonen Harri, J Smed, Joun Smed, Jouni Smed, Jouni (University of Turku Smed, Jouni Hakonen Smed, Smed Jouni
• Publisher: Wiley, John and Sons Ltd
• Languages: English
• Product format: Hardback
• Released: 31.08.2017
• EAN: 9781119259763
• ISBN: 978-1-119-25976-3
• No. of pages: 416
• Subjects: Guides > Hobby, home > Games, quizzes; Natural sciences, medicine, IT, technology > Mathematics; Computerspiel, Informatik, Programmierung, Netzwerke, Networking, computer science, Electrical & Electronics Engineering, Elektrotechnik u. Elektronik, Numerische Methoden u. Algorithmen, Numerical Methods & Algorithms, Computer Science - General Interest, Populäre Themen i. d. Informatik, Kommunikationsnetz