
Algorithms and Networking for Computer Games
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
Reviews / Votes
Review copy sent to MagPi Magazine 14/08/2017More details
Other editions
Additional editions


Persons
Content
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
1
Introduction
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 (competition) describes games where the aim is to beat the opponent and luck does not play a significant role (e.g. chess);
- alea (chance) describes games where luck or chance is the decisive factor on the outcome (e.g. Roulette);
- mimicry (role-play) describes games where the players go through an adventure with their characters in a game world (e.g. Dungeons & Dragons);
- ilinx (vertigo) describes games that affect the player's observations or movements (e.g. Dance Dance Revolution).
Games are usually a combination of the aforementioned forms. Moreover, Caillois notes that games form a continuum from structured, rule-governed games (ludus) to spontaneous, unstructured play ( paidia).
Wittgenstein argues that it is impossible to define a game: 'For how is the concept of a game bounded? What still counts as a game and what no longer does? Can you give the boundary? No.' (Wittgenstein 2009, Aphorism 68). Suits responds to Wittgenstein's challenge directly by giving the following definition:
To play a game is to attempt to achieve a specific state of affairs [prelusory goal], using only means permitted by rules [lusory means], where the rules prohibit use of more efficient in favour of less efficient means [constitutive rules], and where the rules are accepted just because they make possible such activity [lusory attitude]. I also offer the following simple and, so to speak, more portable version of the above: playing a game is the voluntary attempt to overcome unnecessary obstacles. (Suits 2014, p. 43)
Crawford (1984, Chapter 1) defines a game as 'a closed formal system that subjectively represents a subset of reality'. Accordingly, a game is self-sufficient, follows a set of rules, and has a representation in the real world. These observations are echoed by the definitions of Costikyan (2002, p. 24), who sees a game as 'an interactive structure of endogenous meaning that requires players to struggle toward a goal', and by Salen and Zimmerman (2004, p. 80), for whom a game is 'a system in which players engage in an artificial conflict, defined by rules, that results in a quantifiable outcome'. A widely known, practical definition of a game, attributed to the game designer Sid Meier, states that a game is a series of meaningful choices (Rollings and Morris 2000, p. 38). Schell (2015, p. 47) shares this point of view, defining a game as 'a problem-solving activity, approached with a playful attitude'.
Apart from formal features, the gameplay also includes subjective elements such as an immersion in the game world, a sense of purpose, and a sense of achievement from mastering the game. One could argue that the sense of purpose is essential for the immersion. What immerses us in a game (as well as in a book or a film) is the sense that there is a purpose or motive beneath the surface. In a similar fashion, the sense of achievement is essential for the sense of purpose (i.e. the purpose of a game is to achieve goals, points, money, recognition, etc.). From a human point of view, we get satisfaction in the process of nearing a challenging goal and finally achieving it - and then realizing that we can relive that feeling. These aspects, however, are outside the scope of our current discussion, and we turn our focus to a subset of games, namely computer games.
1.1 Anatomy of Computer Games
Computer games are a subset of games. To be more precise, let us define a computer game as a game that is carried out with the help of a computer program. This definition leaves us some leeway, since it does not imply that the whole game takes place in the computer. For example, a game of chess can be played on the screen or on a real-world board, regardless of whether the opponent is a computer program. Also, location-based games (see Chapter 11) further obscure the traditional role of a computer game by incorporating real-world objects into the game world.
In effect, a computer program in a game can act in three roles:
- coordinating the game process (e.g. realizing a...
System requirements
File format: ePUB
Copy protection: Adobe-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Install the free reader Adobe Digital Editions prior to download (see eBook Help).
- Tablet/smartphone (Android; iOS): Install the free app Adobe Digital Editions or the app PocketBook before downloading (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (not Kindle).
The file format ePub works well for novels and non-fiction books – i.e., „flowing” text without complex layout. On an e-reader or smartphone, line and page breaks automatically adjust to fit the small displays.
This eBook uses Adobe-DRM, a „hard” copy protection. If the necessary requirements are not met, unfortunately you will not be able to open the eBook. You will therefore need to prepare your reading hardware before downloading.
Please note: We strongly recommend that you authorise using your personal Adobe ID after installation of any reading software.
For more information, see our ebook Help page.