70,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
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. 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 exercises Algorithms 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.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 715
Veröffentlichungsjahr: 2017
Ähnliche
Algorithms and Networking for Computer Games
Second Edition
Jouni Smed
University of Turku Turku, FI
Harri Hakonen
Turku, FI
This edition first published 2017 © 2017 John Wiley & Sons, Ltd
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.
The right of Jouni Smed and Harri Hakonen to be identified as the authors of this work has been asserted in accordance with law.
Registered OfficesJohn Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA John Wiley & Sons, Ltd. The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK
Editorial OfficeThe Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK
For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.
Wiley also publishes its books in a variety of electronic formats and by print-on-demand. Some content that appears in standard print versions of this book may not be available in other formats.
Limit of Liability/Disclaimer of WarrantyWhile the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
Library of Congress Cataloging-in-Publication Data
Names: Smed, Jouni, author. | Hakonen, Harri, author. Title: Algorithms and networking for computer games / Jouni Smed, Harri Hakonen. Description: Second edition. | Hoboken, NJ, USA : John Wiley & Sons Inc., 2017. | Includes bibliographical references and index. Identifiers: LCCN 2017005948 (print) | LCCN 2017006972 (ebook) | ISBN 9781119259763 (cloth) | ISBN 9781119259824 (Adobe PDF) | ISBN 9781119259831 (ePub) Subjects: LCSH: Computer games--Programming. | Computer algorithms. Classification: LCC QA76.76.C672 S62 2017 (print) | LCC QA76.76.C672 (ebook) | DDC 794.8/1526--dc23 LC record available at https://lccn.loc.gov/2017005948
Cover Design: Wiley Cover Image: © Pobytov / Getty Images
Contents
Preface
Acknowledgements
1 Introduction
1.1 Anatomy of Computer Games
1.2 Game Development
1.3 Synthetic Players
1.4 Multiplaying
1.5 Interactive Storytelling
1.6 Outline of the Book
1.7 Summary
Exercises
Part I Algorithms
2 Random Numbers
2.1 Linear Congruential Method
2.2 Discrete Finite Distributions
2.3 Random Shuffling
2.4 Summary
Exercises
Note
3 Noise
3.1 Applying Noise
3.2 Origin of Noise
3.3 Visualization
3.4 Interpolation
3.5 Composition of Noise
3.6 Periodic Noise
3.7 Perlin Noise
3.8 Worley Noise
3.9 Summary
Exercises
Note
4 Procedural Generation
4.1 Terrain Generation
4.2 Maze Algorithms
4.3 L-Systems
4.4 Hierarchical Universe Generation
4.5 Summary
Exercises
5 Tournaments
5.1 Rank Adjustment Tournaments
5.2 Elimination Tournaments
5.3 Scoring Tournaments
5.4 Summary
Exercises
6 Game Trees
6.1 Minimax
6.2 Alpha-Beta Pruning
6.3 Monte Carlo Tree Search
6.4 Games of Chance
6.5 Summary
Exercises
7 Path Finding:
7.1 Discretization of the Game World
7.2 Finding the Minimum Path
7.3 Realizing the Movement
7.4 Summary
Exercises
8 Group Movement
8.1 Flocking
8.2 Formations
8.3 Summary
Exercises
9 Decision-Making:
9.1 Background
9.2 Finite State Machines
9.3 Influence Maps
9.4 Automated Planning
9.5 Summary
Exercises
10 Modelling Uncertainty
10.1 Statistical Reasoning
10.2 Fuzzy Sets
10.3 Fuzzy Constraint Satisfaction Problem
10.4 Summary
Exercises
Part II Networking
11 Communication Layers
11.1 Physical Platform
11.2 Logical Platform
11.3 Networked Application
11.4 Summary
Exercises
12 Compensating Resource Limitations
12.1 Aspects of Compensation
12.2 Protocol Optimization
12.3 Dead Reckoning
12.4 Local Perception Filters
12.5 Synchronized Simulation
12.6 Interest Management
12.7 Compensation by Game Design
12.8 Summary
Exercises
13 Cheating Prevention
13.1 Technical Exploitations
13.2 Collusion
13.3 Rule Violations
13.4 Summary
Exercises
14 Online Metrics
14.1 Players
14.2 Monetization
14.3 Acquisition
14.4 Game Session
14.5 Summary
Exercises
Appendices
A Pseudocode Conventions
A.1 Changing the Flow of Control
A.2 Data Structures
A.3 Format of Algorithms
A.4 Conversion to Existing Programming Languages
B Practical Vectors and Matrices
B.1 Points and Vectors
B.2 Matrices
B.3 Conclusion
Notes
Bibliography
Ludography
Index
EULA
List of Table
2
Table 2.1
3
Table 3.1
5
Table 5.1
Table 5.2
Table 5.3
Table 5.4
9
Table 9.1
10
Table 10.1
11
Table 11.1
12
Table 12.1
Table 12.2
13
Table 13.1
A
Table A.1
Table A.2
Table A.3
Table A.4
Table A.5
Table A.6
Table A.7
Table A.8
Table A.9
Guide
Cover
Table of Contents
Preface
Pages
xix
xx
xxi
23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
Preface
When students at MIT competed against each other in the first real-time graphical computer game Spacewar in 1962 (Graetz 1981), probably none of them could have dreamt how realistic and complex computer games would develop in five decades and how large a business would grow around them. Commercial arcade games such as Pong and Space Invaders arrived in the 1970s, and home computers brought computer games within the reach of all enthusiasts in the 1980s. Since then game development has grown from small amateur enterprises into an industry, which is now – in spite of popular claims – the second largest branch of the entertainment industry, steadily narrowing the lead of the film industry (Newzoo 2014; Statista 2016).
Games are also becoming ever more pervasive in our lives. Smartphones and mobile gaming are a handy pastime in almost any situation, and technological advances in augmented and virtual reality along with internet of things are pushing forward the frontiers of gaming. This has coincided with a change in the ecosystem for game distribution from bricks-and-mortar stores into digital online stores and new monetization methods. Single-player mode – which is an anomaly in the known 5000-year history of games starting from the Egyptian Senet and the Sumerian Royal Game of Ur – is no longer the standard playmode, and networking can now bring massive numbers of players together to participate in the same game. We have witnessed the rise of gamification and application areas outside of pure entertainment to assist, guide, rehabilitate and teach children, youngsters, adults and elders alike. Game development has also become more democratized, because the development platforms make it easy and quick for everyone to create digital games. Finally, there is more knowledge and research on various aspects of games from design to productization, and modern game developers are more educated and aware of the possibilities of their medium. Behind the seven established forms of art (Canudo, 1988,b; Hegel 1975), games are truly emerging as the eighth art form.
The first edition of this book was published ten years ago in 2006. It was a time before smartphones, tablets, digital distribution and social networks. Massive multiplayer games such as World of Warcraft and Eve Online had just been released and were gathering momentum, the social media of today were still in their infancy, and the verb ‘to google’ had just been added to the Oxford English Dictionary. The single-player PC games delivered in DVDs were the top of the line, and mobile games resembled simple games from the early 1980s. If we were back then careful in asserting that computer games are a valid topic for academic research, there is today no argument as to their importance.
Despite the changes, something still remains the same: the algorithms and networking making it all possible. Game programming is not an isolated field of study but intersects many essential research areas of ‘traditional’ computer science. Solving an algorithmic or networking problem is always more than just getting it done as quickly as possible; it is about analysing what is behind the problem and what possibilities there are to solve it. This is the the motivation for this book, and our intention – right from the beginning – has been to provide the reader with a glance into the world of computer games as seen from the perspective of a computer scientist.
We assume that the reader is familiar with the fundamentals of algorithms and data structures (e.g. complexity analysis and graph theory). In a case of uncertainty, the reader can consult basic textbooks such as Introduction to Algorithms (Cormen et al. 2001) and, of course, the ever inspirational The Art of Computer Programming (Knuth 1998a,b,c, 2011). We describe classical game algorithms and review problems encountered in commercial computer games. Thus, in selecting material for this book we have walked a tight-rope between these two worlds. The current selection may seem a bit of a ragbag, but the common factor in the choice of the topics has been a combination of algorithmic and practical interest.
Going through the original files of the first edition, we were pleasantly surprised how fresh many of the ideas have remained. Hardly anything was outdated; rather the problems the developers are facing today are still the same. It also inspired us to continue and expand the work with a similar mindset. We have tried again to pick relevant topics from both academic literature and trade journals, forum posts and blogs to squeeze out their essence. We have still refrained from tying our hands with a particular platform (of which there have been many throughout the past decade) and programming language (of which there have been equally many). We are aware that that has been a common critique over the years, but we have strived to unlock the timeless beauty that many of the ideas conceal. Granted, there are many things that escape our grasp or which we could only briefly introduce, which is why we provide references to the works of the wiser and better informed. Also, the exercises at the end of each chapter hide many gold nuggets and possibilities for expanding one’s thoughts and even venturing into uncharted waters.
Revising and expanding this book has been a fun process, and a hard process – a task one gladly undertakes once a decade.
Acknowledgements
First of all, we acknowledge our dear friend Dr Timo Kaukoranta’s role in gathering and analysing the topics which formed the basis for the first edition of this book. His untimely death was a wake-up call to realize in written form the ideas we had been tossing around for several years. Timo’s spirit is still present throughout this book.
Many people have guided us on our journey to view the world as computer scientists. Professor Olli Nevalainen’s pivotal role in steering us to the world of algorithms as well as the support from the late Professor Timo Raita have been both inspiring and invaluable to us.
We would like to thank our colleagues and co-authors over the years – of whom we would like to mention here (alphabetically) Andy Best, Sami Hyrynsalmi, Antero Järvi, Kai Kimppa, Timo Knuutila, Ville Leppänen and Tomi ‘bgt’ Suovuo – for widening our perspectives and sharpening our thoughts. We are also grateful for the feedback we have received from the students who have taken part in our various game-related projects, courses and seminars in the Department of Information Technology, University of Turku and Turku Centre for Computer Science during 2001–2016.
It has again been a pleasure to work with the people at Wiley. We thank Tiina Wigley for initiating this opportunity to write a second edition, and Sandra Grayson and Preethi Belkese for giving us the freedom to enjoy this treat – it has tasted as sweet as the first one.
Jouni. First and foremost, I am grateful to Professor Erkki Sutinen for his most positive and encouraging attitude towards this endeavour. I am also in debt to my doctoral students Jussi Laasonen and Tapani Liukkonen as well as my master’s students Ilmari Lahti, Eero Itkonen and Juhani Kyrki for their valuable insights. Over the years collaboration with the local game scene has been priceless to me and I would like to thank: Turku Game Lab (Adjunct Professor Mika Luimula, Taisto Suominen, Nataša Bulatović Trygg and the rest of the lab staff), TEPE Research Group on Health Games (Professor Sanna Salanterä, Heidi Parisod and Anni Pakarinen), Game Turku and Turku Science Park (Patrik Uhinki and Marko Puhtila), Up Your Game Network (Aki Koponen and Jukka Vahlo), and IGDA Finland Turku Hub. As always, it was good to team up again with Harri to play a little Lennon–McCartney as this project also marked the twentieth anniversary of co-authoring with him (which is always a pleasure). Finally, Lilia and Julian, thank you for being wonderful, amazing little creatures with your own view of the world – and for inviting Dad to take part in your games. And Iris, my words cannot express my gratitude for all the love, care, wit, warmth and understanding.
Harri. Thank you to all my friends for your benevolence, encouragement, support, inspiration, and the warm hugs. To my colleagues at Oy LM Ericsson Ab for allowing me to be part of a small and hard-working team of experienced specialists; I am still learning a lot from you all, you gracious kuomat! To Jouni, when my writing deep-dived into the tar pit you said ‘Do not worry, we’ll figure it out, it’ll turn out OK as always’, and you were right again. To my son Pyry for having the patience to test-read the scribbles and drafts, and then give honest feedback; love has wonderfully numerous manifestations. As dear emo has evinced. In the kind of environment that you radiate it has been fun to linearize the wrinkles of my thoughts, I am so lucky to have you!
Turku, Finland
June 2016
Jouni Smed
Harri Hakonen
1Introduction
Let us play a little thought game. Get a pen and paper. Choose any game you know, and think about the elements required to make it work. Write down a list of these elements. Be as specific or indiscriminate as you want. Once you have finished, choose another game and think about it. Try to find items in the list of the first game that correspond to the second game and mark them. If there are features in the second game that the first one does not have, add them to the list. Repeat this procedure for two or three more games. Next, take the five most common items in your list and compare them to the following list. For each corresponding item you get one point.
The key elements of a game are:
players who are willing to participate in the game;
rules which define the limits of the game;
goals which the players try to achieve during the game;
opponents or opposing forces which prevent the player from achieving the goals;
a representation of the game in the real world.
How many points did you score?
The five components we have listed seem to be present in every game, and the relationships between them form three aspects of a game, which are illustrated in Figure 1.1 (Smed and Hakonen 2003, 2005b):
Figure 1.1 Components, relationships, and aspects of a game.
Challenge
. Rules define the game and, consequently, the goal of the game. When players decide to participate in the game, they agree to follow the rules. The goal motivates the players and drives the game forward, because achieving a goal in the game gives the players enjoyment.
Conflict
. The opponent (which can include unpredictable humans and random processes) obstructs the players from achieving the goal. Because the players do not have a comprehensive knowledge of the opponent, they cannot determine precisely the opponent’s effect on the game.
Play
. The rules are abstract but they correspond to real-world objects. This representation concretizes the game to the players.
The challenge aspect alone is not enough for a definition of a game, because games are also about conflict. For example, a crossword puzzle may be a challenge in its own right but there is hardly any conflict in solving it – unless someone erases the letters or changes the hints or keeps a record of the time to solve the puzzle. Obviously, the conflict arises from the presence of an opponent, which aims to obstruct the player from achieving the goal. The opponent does not have to be a human but it can be some random process (e.g. throw of dice or shuffling of the deck of cards). The main feature of the opponent is that it is non-deterministic to the player: because the player cannot predict exactly what another human being or a random process will do, outwitting or outguessing the opponent becomes an important part of the game.
Challenge and conflict aspects are enough for defining a game in an abstract sense. However, in order to be played the game needs to be concretized into a representation. This representation can be a board and plastic pieces as well as non-tactile words or three-dimensional graphics rendered on a computer screen. Even the players themselves can be the representation, as in the children’s game of tag. Regardless of the representation there must exist a clear correspondence to the rules of the game.
Let us take the game of poker as an example. The players agree to follow the rules, which state (among other things) what cards there are in a deck, how many cards one can change, and how the hands are ranked. The rules also define the goal, having as good a hand as possible when the cards are laid on the table, which is the player’s motivation. The other players are opponents, because they try to achieve a better hand to win – or, at least, to give such an impression. Also, the randomness of the deck caused by shuffling opposes the player, who cannot determine what cards will be dealt next. The game takes a concrete form in a deck of plastic-coated cards (or pixels on the screen), which represent the abstractions used in the rules.
One of the earliest written collection of games, Libro de los juegos (‘Book of games’), commissioned by King Alfonso X of Castile, León and Galicia and completed in Toledo 1283, divides the games into three groups: games of skill (e.g. chess), games of chance (e.g. dice games) and games combining skill and chance (e.g. backgammon). This division reflects the conflict aspect and the type of the opponent.
Huizinga’s definition of play from his classical work Homo Ludens, the playful human, captures most of the features we listed earlier:
[Play] is an activity which proceeds within certain limits of time and space, in a visible order, according to rules freely accepted, and outside the sphere of necessity or material utility. The play-mood is one of rapture and enthusiasm, and is sacred or festive in accordance with the occasion. A feeling of exaltation and tension accompanies the action, mirth and relaxation follow. (Huizinga 1955, p. 132)
Moreover, Huizinga’s idea of a magic circle tries to capture the complete game (or play) experience, which resides outside ordinary life.
Caillois (2001) builds upon Huizinga’s work and divides games further into four forms:
agon
