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 Offices
John 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 Office
The 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 Warranty
While 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
1. 2.1 Linear Congruential Method
2. 2.2 Discrete Finite Distributions
3. 2.3 Random Shuffling
4. 2.4 Summary
5. Exercises
6. Note
3 Noise
1. 3.1 Applying Noise
2. 3.2 Origin of Noise
3. 3.3 Visualization
4. 3.4 Interpolation
5. 3.5 Composition of Noise
6. 3.6 Periodic Noise
7. 3.7 Perlin Noise
8. 3.8 Worley Noise
9. 3.9 Summary
10. Exercises
11. Note
4 Procedural Generation
1. 4.1 Terrain Generation
2. 4.2 Maze Algorithms
3. 4.3 L-Systems
4. 4.4 Hierarchical Universe Generation
5. 4.5 Summary
6. Exercises
5 Tournaments
1. 5.1 Rank Adjustment Tournaments
2. 5.2 Elimination Tournaments
3. 5.3 Scoring Tournaments
4. 5.4 Summary
5. Exercises
6 Game Trees
1. 6.1 Minimax
2. 6.2 Alpha-Beta Pruning
3. 6.3 Monte Carlo Tree Search
4. 6.4 Games of Chance
5. 6.5 Summary
6. Exercises
7 Path Finding:
1. 7.1 Discretization of the Game World
2. 7.2 Finding the Minimum Path
3. 7.3 Realizing the Movement
4. 7.4 Summary
5. Exercises
8 Group Movement
1. 8.1 Flocking
2. 8.2 Formations
3. 8.3 Summary
4. Exercises
9 Decision-Making:
1. 9.1 Background
2. 9.2 Finite State Machines
3. 9.3 Influence Maps
4. 9.4 Automated Planning
5. 9.5 Summary
6. Exercises
10 Modelling Uncertainty
1. 10.1 Statistical Reasoning
2. 10.2 Fuzzy Sets
3. 10.3 Fuzzy Constraint Satisfaction Problem
4. 10.4 Summary
5. Exercises

Part II Networking

11 Communication Layers
1. 11.1 Physical Platform
2. 11.2 Logical Platform
3. 11.3 Networked Application
4. 11.4 Summary
5. Exercises
12 Compensating Resource Limitations
1. 12.1 Aspects of Compensation
2. 12.2 Protocol Optimization
3. 12.3 Dead Reckoning
4. 12.4 Local Perception Filters
5. 12.5 Synchronized Simulation
6. 12.6 Interest Management
7. 12.7 Compensation by Game Design
8. 12.8 Summary
9. Exercises
13 Cheating Prevention
1. 13.1 Technical Exploitations
2. 13.2 Collusion
3. 13.3 Rule Violations
4. 13.4 Summary
5. Exercises
14 Online Metrics
1. 14.1 Players
2. 14.2 Monetization
3. 14.3 Acquisition
4. 14.4 Game Session
5. 14.5 Summary
6. Exercises

Appendices

A Pseudocode Conventions
1. A.1 Changing the Flow of Control
2. A.2 Data Structures
3. A.3 Format of Algorithms
4. A.4 Conversion to Existing Programming Languages
B Practical Vectors and Matrices
1. B.1 Points and Vectors
2. B.2 Matrices
3. B.3 Conclusion
4. Notes

Bibliography

Ludography

Index

EULA

List of Illustrations

Figure 1.1 Components, relationships, and aspects of a game.
Figure 1.2 Model, View and Controller in a computer game.
Figure 1.3 Basic design parts of a game.
Figure 1.4 The phases of a game development project.
Figure 1.5 The game documents created and used in a game development project.
Figure 1.6 The story structure can be illustrated as a graph, where episodes (or levels) are represented as vertices and transitions as directed edges. (a) In a linear structure, the story always unfolds the same way. (b) In a branching structure, each transition leads to a unique episode. (c) In parallel paths, although the episodes can branch, they can also conjoin, limiting the number of episodes.

Figure 2.1 If m = 10 and w = 4, the Monte Carlo method does not provide a uniform distribution.
Figure 2.2 The Las Vegas method distributes the original interval uniformly by defining the excess area as invalid.
Figure 2.3 Two-dimensional spectral test results for the case where m = 256, a = 21, and c = 11.
Figure 2.4 A plane of size 600 × 600 units consisting of n randomly generated points. (a) n = 3000 with discrete uniform distribution (DU) over the whole plane. (b) n = 3048 over the partition of 36 subplanes, each with DU of X ∼ Pois(3000/(6 · 6)) points; X varies in [70, 107]. (c) n = 2977 over the 900 subplanes, each with DU of X ∼ Pois(3000/(30 · 30)) points; X varies in [0, 11]. (d) n = 2994 in 400 uniformly randomly placed subplanes, each with DU of X ∼ Pois(3000/(20 · 20)) points; X varies in [2, 16].
Figure 2.5 In riffle shuffle the deck is divided into two packets, which are riffled together by interleaving them.
Figure 2.6 Probability distribution of a phantom die |x − y| + 1 when x and y are integers from [1, 6].

Figure 3.1 Application of noise to a regular recurrence with two perturbed sine functions. On the left, two perpendicular sine waves are merged by weighting them linearly. The amount of noise rippling the waves increases linearly to the right.
Figure 3.2 (a) The result of NOISE-RANDOM(i, j) where 0 ≤ i, j ≤ (640 − 1) with scaling to the greyscale values . (b) Detail from the top-left part of (a) zoomed in by magnification 32 revealing the individual pixels [0, 19] × [0, 19] on the discrete integer grid of image coordinates.
Figure 3.3 A grid of distorted squares inside a square-sized image, generated with Algorithm 3.4.
Figure 3.4 Simple interpolation functions ϱ(t) for : (a) value-hold 0, (b) nearest-neighbour STEP(), (c) linear t, (d) cosine , (e) smoothstep − 2t³ + 3t², and (f) smootherstep 6t⁵ − 15t⁴ + 10t³.
Figure 3.5 The effect of applying the interpolation functions in Figure 3.4 to the noise values placed on an integer grid. The grid is generated by Algorithm 3.2 (see also Figure 3.2) and then zoomed in by magnification 64: (a) value-hold, (b) nearest-neighbour, (c) linear, (d) cosine, (e) smoothstep, and (f) smootherstep.
Figure 3.6 Two noise composition methods of nesting layers ℓ, initial amplitude , and initial frequency f₀ = 2. The left column is by NOISE-COMPOSITION and the right one by NOISE-TURBULENCE. The noise generator is NOISE-INTERPOLATION-2 with the one-dimensional smootherstep interpolation function.
Figure 3.7 Tiling of a plane with a periodic noise.
Figure 3.8 The phases of a Perlin noise generator in the unit square . The positions at the integer grid are (0, 0), (1, 0), (1, 1), and (0, 1). The position of interest is (x, y) for which we want to determine a noise value. (a) The grid positions are populated with uniformly random unit vectors . These vectors are fixed for their positions. (b) Position (x, y) is used to define vectors that together are unique to it. (c) The noise values are calculated for the grid positions. These values are specific to (x, y) in this particular grid region. (d) The values are interpolated to the resulting noise value d_{(x, y)}.
Figure 3.9 Variations of Perlin noise on a plane: (a) the original zoomed in to a region of 5 × 5 integer grid positions; (b) composed (); (c) periodic based on the original with 10 × 10 grid positions; and (d) turbulenced ().
Figure 3.10 Worley noise generated from the feature distance f_i(•), i = 1, 2, 3, with n = 3 and μ = 3. The left column is by distance metric euclidean and the right one by maximum.
Figure 3.11 Worley noise generated by various mappings. The source values v in the left column are the right column in Figure 3.10, modified by RUNG(). In the right column the distance metric is euclidean; the top image is generated from f₂(•) − f₁(•), the middle from f₂(•) · f₁(•), and the bottom with turbulence (ℓ = 3, a₀ = 0.03, f₀ = 1.97) from generator f₂(•) (n = 3, μ = 3).

Figure 4.1 A height map divides the terrain into a grid: (a) the height values in a matrix; (b) the corresponding greyscale picture; (c) the corresponding oblique greyscale picture.
Figure 4.2 Randomly generated terrains where h_max = 256. (a) Simple random terrain. (b) Limited random terrain where d_max = 64. (c) Particle deposition terrain where m = 10⁷, i = 1 and b = 4. (d) Fault line terrain where f = 1000 and c = 2. (e) Circle hill terrain where c = 400, r = 32 and s = 16. (f) Midpoint displacement terrain using diamond-square where d_max = 128 and s = 1.
Figure 4.3 In particle deposition, each dropped grain falls down until it reaches an equilibrium. If the threshold b = 1, the grey grain moves downwards until its height difference with respect to its neighbourhood is at most b.
Figure 4.4 Fault lines are selected randomly. The terrain is raised on one side of the fault line and lowered on the other.
Figure 4.5 Midpoint displacement method consists of the diamond step, shown in (a) and (c), and the square step, shown in (b) and (d). The circles represent the values calculated.
Figure 4.6 Comparison of a labyrinth and a maze: (a) a labyrinth has only one path from s to r, whereas (b) a maze offers choices along the way.
Figure 4.7 A square and hexagonal grid as a graph.
Figure 4.8 Procedurally created mazes: (a) depth-first algorithm; (b) randomized Kruskal’s algorithm; and (c) randomized Prim’s algorithm.
Figure 4.9 Fibonacci words as fractals.
Figure 4.10 Plant created with an L-system after eight iterations.
Figure 4.11 Road patterns: (a) basic rule; (b) New York rule; (c) Paris rule; (d) San Francisco rule.
Figure 4.12 Creating buildings by extruding.
Figure 4.13 The positions in a two-dimensional galaxy are enumerated row by row, starting from the origin.
Figure 4.14 The seed value is used to create the characteristics of the star including the rest of the star system.
Figure 4.15 Generation of numbers in Elite.

Figure 5.1 Tournaments for the seven brothers. (a) In a scoring tournament, everybody has one match against everybody else. (b) In an elimination tournament (or a cup), the players are paired and only the winners get to the next round. (c) In a hill-climbing tournament, the reigning champion defends the title against players who have not yet had the possibility of becoming the champion.
Figure 5.2 A bracket for an elimination tournament with 16 players (circles), which has 15 matches (squares).
Figure 5.3 A clique graph representation of the matches in a round robin tournament with seven players.
Figure 5.4 A partition of the matches into two rounds of a round robin tournaments with seven players: (a) the matches for the initial round; (b) the matches for the next round.

Figure 6.1 Partial game tree for the first two moves of noughts and crosses. The tree has been simplified by removing symmetrical positions.
Figure 6.2 Game tree for Division Nim with seven matches. To reduce size, identical nodes in a ply have been combined.
Figure 6.3 Complete game tree with valued nodes for Division Nim with seven matches.
Figure 6.4 Evaluation function e(•) in noughts and crosses. (a) MAX (crosses) has six possible winning lines, whereas MIN (noughts) has five: e(•) = 6 − 5 = 1. (b) MAX has four possible winning lines and MIN has five e(•) = 4 − 5 = −1. (c) Forced win by MAX, hence e(•) = +∞
Figure 6.5 Pruning the game tree. MAX node A has the maximum value 4 when it expands node B. If the minimum value of node B gets below 4, node B can be discarded from the search and unexpanded children can be omitted.
Figure 6.6 An example of alpha-beta pruning: (a) searching subtree B; (b) searching subtree E; (c) searching subtree G. The values of α and β represent the situation when a node has been searched.
Figure 6.7 An extract from a general game tree for copper noughts and crosses consists of a MAX node (the labile triangle), MIN nodes (the stable triangles) and CHANCE nodes (the squares).
Figure 6.8 A game tree with three possible outcomes (from the perspective of MAX): win, draw, loss.
Figure 6.9 A game tree with outcomes in the range [ − 4, +4].
Figure 6.10 Partial game tree for One-Two-Three Nim.
Figure 6.11 Partial game tree for Nim with heaps of size 1, 2 and 3.
Figure 6.12 An example of n²-Pile Flipflop where n = 6. Round pieces represent the tokens for FLIP, FLOP or empty pieces for NEUTRAL; square pieces represent the fixed tokens. When a FLOP token is added to a pile, all the piles along the marked lines are reversed. The reversing line ends at another FLOP token, at a fixed FLIP token, or at the end of the board.

Figure 7.1 Real-world path finding is reduced to a graph problem by discretizing the search space into waypoints. The waypoints are the vertices and the connections between them the edges of the graph.
Figure 7.2 A square grid is laid over the game world. If the majority of the world inside a tile is open, the tile is included in the waypoints.
Figure 7.3 The square grid, triangular grid, and hexagonal grid are the only regular two-dimensional tessellations.
Figure 7.4 A square grid allows (a) four-connectivity and (b) eight-connectivity.
Figure 7.5 A navigation mesh is a convex partitioning of the game world geometry. (a) The waypoints have been placed in the middle of each polygon. (b) The centre of each shared edge is a waypoint.
Figure 7.6 After triangulation, the Hertel–Mehlhorn method begins to remove non-essential edges to form a convex partition. (a) Edge e₁ is non-essential, because it divides only convex angles at points p₂ and p₅. If it is removed, the resulting polygon p₁, p₂, p₃, p₅ will be convex. (b) When e₁ has been removed, edge e₂ becomes essential and cannot be removed, because it divides a concave angle at point p₅.
Figure 7.7 Expanding the vertices in the neighbourhood. (a) Breadth-first search does not consider the order in which the neighbourhood of vertex v is expanded. (b) Best-first search uses a heuristic function to rank the neighbours but does not exclude any of them. (c) Beam search expands only a subset of the neighbourhood.
Figure 7.8 An example of a heuristic function. If the weight of an edge is the distance between the vertices using Manhattan metric, a heuristic function h can estimate them with truncated Euclidean distances.
Figure 7.9 An example of Algorithm A*. The boxes next to a vertex v represent the values π(v), , and . Filled circles indicate the selected vertices.
Figure 7.10 (a) The path through the waypoints may have sharp and unrealistic turns. (b) Sharp turns can be smoothed out when the movement is realized.
Figure 7.11 Line-of-sight testing allows the original path (dotted line) to be improved by skipping waypoints (solid line). It is not necessary to visit the waypoints, and the heading can be changed immediately whenever a farther waypoint becomes visible (dashed line).
Figure 7.12 Avoiding dynamic obstacles. (a) The straight path from s to r is obstructed. (b) The desired direction towards the destination and the repulsion direction away from the obstacle are combined to form the velocity vector .
Figure 7.13 Monkey (M), box (X) and banana (B) in a cage formed by a square grid.
Figure 7.14 A game world as a polygon.
Figure 7.15 One possible solution to the eight-queens problem.
Figure 7.16 Two-dimensional game world in which the white area represents open space.

Figure 8.1 Human groups tend to move (a) side by side in low-density surroundings, (b) in a V-shape in moderate-density surroundings and (c) in a row in high-density surroundings.
Figure 8.2 Steering behaviour rules. (a) Separation: do not crowd flockmates. (b) Alignment: move in the same direction as flockmates. (c) Cohesion: stay close to flockmates. (d) Avoidance: avoid obstacles and enemies.
Figure 8.3 Basic formation types: (a) column, (b) line, (c) wedge, (d) vee, (e) box, (f) right flank, (g) left flank, and (h) diamond.
Figure 8.4 Formation models: (a) leader referenced, (b) unit-centre referenced, (c) neighbour referenced, (d) social potentials, (e) virtual structure, and (f) virtual leaders.
Figure 8.5 Strategies for realizing the movement into the formation: (a) entities move first into the formation and then to the destination; (b) entities move to a formation rally-point along the way to the destination and move from there to the destination; and (c) entities move into a formation at the destination.
Figure 8.6 Zones for the magnitude of the control vector for maintaining the formation: the control vector is maximum in the ballistic zone, zero in the dead zone, and decreases linearly in the controlled zone the closer the entity gets to the dead zone.
Figure 8.7 An example of a mass–spring system. The circles represent point masses, the dashed lines the structural springs, the solid lines the shear springs, and the bold lines the flexion springs.
Figure 8.8 A box formation facing a canyon.

Figure 9.1 The primitive events and states originating from the world are used in pattern recognition and stored for later use. The decision-making system uses the observations made in pattern recognition to choose an appropriate action among the possibilities allowed by the world.
Figure 9.2 The model over a sequence S of symbols from the alphabet Σ = {J, U, C, H} can be used in (a) prediction and (b) production.
Figure 9.3 An objective function gives the optimality of a solution. The goal is to find the global optimum, but the search space is usually scattered with local optima.
Figure 9.4 To model the underlying generator, the function is fitted to the solution samples according to the feedback.
Figure 9.5 A statechart diagram for a finite state machine for a simple patrol robot. The start state is ‘Homing’ and there is no final state, because the robot remains operational until it is destroyed.
Figure 9.6 Three independent properties that an FSM can include: (a) an acceptor, (b) a transducer, and (c) a computator.
Figure 9.7 A generic FSM for a single pull-down menu with an online help logic.
Figure 9.8 Detecting breaks in the repeating rhythm of ‘ti’ and ‘taa’ with (a) a Mealy machine, and (b) a Moore machine. The irregular beat outputs value 1.
Figure 9.9 An FSM as a software object has a static structure, dynamic context, a fixed interface, and a use environment.
Figure 9.10 A combinatorial FSM that waits for signals ‘e’, ‘f’, and ‘g’ before proceeding. (a) Many-to-one signalling for detecting all erroneous situations is managed by a composite state. (b) The same FSM is collapsed by using a choice point and three Boolean guards.
Figure 9.11 An FSM that joins two independent properties together.
Figure 9.12 Two concurrent FSMs where the properties are disjoint. The FSMs discard every unknown event by the transition labelled as < <any> >.
Figure 9.13 Let the circled tile represent the strength and position of own troops and squared tiles enemy’s troops. (a) After the initial influence values have been assigned, their effect is propagated over the map. The fall-off halves the influence in the neighbouring tiles. (b) The same is done to the influence map based on the enemy’s troops. (c) By aggregating the two influence maps, we get a new influence map which combines the troop information. (d) The resulting map demarcates, for example, the frontier between the players.
Figure 9.14 The game world of Hunt the Wumpus is a graph, where the vertices are the rooms and the edges the tunnels connecting them. The hunter (H) moves from room to room avoiding bats (B) and pits (P), and is ready to shoot the wumpus (W).
Figure 9.15 Guard’s decision-making represented as a hierarchical task network using the and–or tree notation.
Figure 9.16 A closed acyclic maze on a square grid. The maze has walls (dark tiles) and an interior (white tiles), which are four-connected.
Figure 9.17 An acceptor FSM on a square grid.
Figure 9.18 Game world for Goldrush. The gold-digger starts from home (H) and must visit all gold piles (G) and return home. The towers (T) shoot arrows to the four principal compass points. The colour of a tile illustrates the height of the terrain (i.e. the lighter the colour, the higher the ground). To conserve his vitality the gold-digger should avoid travelling uphill and getting too close to the towers.

Figure 10.1 A Bayesian network as a directed acyclic graph.
Figure 10.2 Belief and plausibility.
Figure 10.3 Uncertain or complex dependencies can be modelled with fuzzy sets that cover the solution space.
Figure 10.4 Membership functions μ_sword, μ_spear and μ_bow for the attribute ‘accuracy’ of weapons with respect to the distance (in metres) to the target.
Figure 10.5 Fuzzy operations for different attributes. (a) The membership function for mobility. (b) The membership function for strength. (c) The membership function for the union of mobility and strength. (d) The membership function for the intersection of mobility and strength. (e) The membership function for expensiveness. (f) The membership function for the intersection of the complement of expensiveness and strength.
Figure 10.6 A monkey puzzle of 3 × 4 tiles. The monkey is depicted as an arrow with separated tail and head ends. The solution is an arrangement of the tiles so that tiles are not rotated (i.e. the black circle stays in the upper left corner of each tile) and all the tails and heads match (i.e. form a one-directed arrow) inside the 3 × 4 rectangle.
Figure 10.7 The set-up of Dog Eat Dog for three players. Player p₁ has the enemy p₂ and the prey p₃, player p₂ has the enemy p₃ and the prey p₁, and player p₃ has the enemy p₁ and the prey p₂. The dashed circles represent the limit of the players’ visual range and dotted circles their olfactory range. Players p₁ and p₂ can see one another but cannot smell the pond. Player p₃ does not see the other players but can smell the pond. The game world is a rectangle of size w × h.
Figure 10.8 Membership function μ_a(θ) for the attraction of the direction θ. The complement 1 − μ_a(θ) gives a membership value for avoidance.
Figure 10.9 Membership functions for the reliability of sensory inputs: μ_s(d) for the reliability of visual input at the distance d, and μ_o(d) for the reliability of olfactory input at the distance d.
Figure 10.10 Membership function μ_c(x, y) for the centralness of position (x, y).
Figure 10.11 Monkey puzzle variant where the tiles can be adjacent only when their corner letters match.

Figure 11.1 Classification of shared-space technologies by transportation and artificiality.
Figure 11.2 The effect of latency on the performance in different game types (Claypool and Claypool 2006). The players’ threshold for latency is around the performance level 0.75.
Figure 11.3 Transmission techniques. (a) In unicasting, the message is sent to a single receiver. (b) In multicasting, the message is sent to one or more receivers that have joined a multicast group. (c) In broadcasting, the message is sent to all nodes in the network.
Figure 11.4 Communication architectures as degrees of deployment: (a) a single node; (b) a peer-to-peer architecture; (c) a client–server architecture; and (d) a server-network architecture.
Figure 11.5 Data and control architectures. (a) In a centralized data architecture, one (data server) node stores all the data. (b) In a replicated architecture, each node manages a replica of all the data. (c) In a distributed architecture, the data are partitioned among the nodes.
Figure 11.6 An example of the three communication layers to implement authentication and account management features. The physical platform consists of nodes (circles), data stores (cylinders), and cabling (lines). The logical platform includes a server-network (i.e. a communication architecture), distributed and replicated data (i.e. a data architecture), and timing functionality (i.e. a control architecture).
Figure 11.7 The game 2n-Gong with n = 3 has six players indicated by numbers [0, 5]. Each player controls a paddle (rectangle) that can be used to bounce the ball (circle).

Figure 12.1 The information principle equation as a radar diagram.
Figure 12.2 A data and control architecture defines how messages are relayed between local and remote nodes in a communication architecture.
Figure 12.3 A relay has two basic alternatives for its structure: (a) A two-way relay sends the local control messages to the network, which sends back data messages to the node. (b) A short-circuit relay sends the local control messages to the network and passes them locally back to the node.
Figure 12.4 Serial and parallel execution in computer games. (a) Separate real-time games can run in parallel but without interaction. (b) A turn-based game is serialized and interactive but not real-time, unless the turns are very short. (c) An interactive real-time game runs both in serial and in parallel.
Figure 12.5 Game world parallelization where the clients c_i are connected to the servers s_j managing regions A–D: (a) By dividing the game world into zones we can assign a separate server for each zone. (b) Certain regions of the game world can be copied into parallel servers which run independently of one another.
Figure 12.6 Dead reckoning is used to calculate positions between the update messages. The actual movement (indicated by the grey arrow) differs from the movement predicted by dead reckoning (black arrows). The dotted lines indicate a position change caused by the update message which has to be corrected using a convergence method.
Figure 12.7 Dead reckoning comprises prediction and convergence. Open circles represent predicted information about the entity’s position p at given time t. The closed circle represents the entity’s received position p and velocity v at given time t when the communication delay is 1 s. In zero-order convergence (or snap), the position is corrected immediately at t = 2 to the new predicted path. In linear convergence, the change is made smoothly along a linear convergence path during a convergence period of 0.5 s.
Figure 12.8 Locational problems caused by dead reckoning. (a) If prediction is not used with collision detection, the ship following its predicted path can pass through a wall. (b) If the predicted path has led the ship to the wrong side of a wall, convergence has to correct the situation, possibly letting the ship pass through the wall.
Figure 12.9 An example of local perception filters with two stationary players (white and grey ship) and one moving passive entity (a bullet shot by the white ship). On the left, from top to bottom, are the rendered views from the white ship’s perspective; on the right are the corresponding views from the grey ship’s perspective. Dashed ovals indicate the actual position of the bullet and black rectangles its rendered position. As the bullet closes on the grey ship, the white ship perceives it to slow down, while the grey ship perceives it to gain speed.
Figure 12.10 The -dimensional temporal contour from the white ship’s perspective. The bullet travels ‘uphill’ until it reaches the t value of the grey ship.
Figure 12.11 Examples of the linear delay function of Equation (12.7) defining the temporal contour in (a) a one-dimensional game world and (b) a two-dimensional game world.
Figure 12.12 Player p shoots at player r in a one-dimensional world. (a) The temporal contour from the perspective of player p. The corresponding values on the t-axis illustrate the delay (i.e. the temporal difference) between the actual and rendered position at each actual spatial point on the x-axis. (b) The temporal contour from the perspective of player r.
Figure 12.13 Temporal contours are adjusted by the distance the entity travels in the communication delay. (a) The corrected temporal contour of player p, where the peak is pushed forward to r′. (b) The corrected temporal contour of player r, where the peak is pushed forward to p′.
Figure 12.14 Two approaches to aggregate the temporal contour of player p, when there are two remote players r and q. (a) Minimize the number of entities that are not in local time. (b) Minimize the number of delay changes.
Figure 12.15 Player p shoots player r, and player p is using bullet time. (a) The temporal contour of player p. (b) The temporal contour of player r.
Figure 12.16 Player p shoots player r, and player r is using bullet time. (a) The temporal contour of player p. (b) The temporal contour of player r.
Figure 12.17 Communication turns in synchronized simulation delay the execution of both local and remote commands so that they occur at the same time in all nodes. The rounds have an equal duration. The commands from round r_j (a, b and c) are executed two rounds later in round r_{j + 2}.
Figure 12.18 Aura-based interest management. (a) When two entities’ auras intersect, they are aware of each other and receive update messages. (b) With focus (dashed areas) and nimbus (grey areas) the awareness need not be symmetric. The grey ship’s focus intersects the white ship’s nimbus, which means that the grey ship receives update messages from the white ship. Because the white ship’s focus does not intersect the grey ship’s nimbus, it does not receive update messages from the grey ship.
Figure 12.19 In zone-based interest management the entities express interest in their nearby zones.
Figure 12.20 Examples of frontier sets. (a) The players are in cells c and g and the frontier sets are F_{c → g} = {c, f, i} and F_{g → c} = {a, b, d, g}. The cells e and h do not belong to the frontier: if e ∈ F_{g → c} it could be seen from i ∈ F_{c → g}, and similarly for the case h ∈ F_{c → g}. (b) The players are in cells e and f and the frontier sets are F_{e → f} = {a, b, d, e, g} and F_{f → e} = {c, f}. (c) The players are in cells c and h and the frontier sets are F_{c → h} = {c} and F_{h → c} = {a, b, d, e, g, h}. (d) The players are in cells d and h and can possibly see one another; the frontier sets are and .
Figure 12.21 Each player has a short active turn followed by passive turns in which the other players take their turn.
Figure 12.22 Players p₁, p₂ and p₃ issue tactical instructions to the corresponding avatars a₁, a₂ and a₃.
Figure 12.23 A level layout for the game Entrappers. The columns represent level alternatives for a player. The arrows indicate the routes already taken by players p₁ and p₂. Inside each level are traps set by the computer (c) or the players.

Figure 13.1 Typical attacks in a networked multiplayer game.
Figure 13.2 Assume the senders must time-stamp (i.e. include the value s in) their outgoing messages, and the latency between the players is 3 time units. (a) If both players are fair, p₁ can be sure that the message from p₂, which has the time-stamp t + 2, was sent before the message issued at t has arrived. (b) If p₂ has a latency of 1 time unit but pretends that it is 3, look-ahead cheating using forged time-stamps allows p₂ to base decisions on information that it should not have.
Figure 13.3 Lockstep and pipeline lockstep protocols. (a) The lockstep protocol synchronizes after each turn and waits until everybody has received all commitments. (b) The pipelined lockstep protocol has a fixed size buffer (here the size is 3), which holds several commitments.
Figure 13.4 Collusion in a hill-climbing tournament, where c₀ and c₁ can win against p₀, p₀ can win against p₁, and p₁ can win against c₀ and c₁. (a) If everyone plays normally, p₁ wins the tournament. (b) If players c₀ and c₁ collude, c₀ can deliberately lose his match so that c₁ will get an easier opponent later in the tournament.
Figure 13.5 Players and participants are the partakers of a game. The relationship is usually assumed to be one-to-one, but one human participant can control two or more players, a player can be controlled by a computer program (i.e. a bot), or two or more participants (e.g. a sweatshop).
Figure 13.6 Collusion is detected when the observed results using a measure m deviate significantly from the expected results r_e. Suspicion arises at the moment t_s when the results are getting either too ‘good’ and cross the threshold r_g or too ‘bad’ and cross the threshold r_b.
Figure 13.7 The pay-off of collusion per colluder increases until the optimum number of colluders is reached, after which it asymptotically approaches the fair play pay-off.
Figure 13.8 An example of the situation after the first round of Fortress Circle with eight players. Each player’s fortress dominates the area around it.

Figure 14.1 Demand curves of the purchase price and quantity (i.e. products sold) for (a) a premium game and (b) a freemium game.
Figure 14.2 Player groups: P all players, P_a active players, P_p paying players, P_s players who have started, and P_q acquired players.

Figure B.1 The problem of the closest distance of approach. (a) The reference point of the world is on ‘map’. (b) The reference point is on ‘you’.
Figure B.2 The same right-handed frame of the real-number axes x, y, and z from three viewing angles. Arrows indicate positive directions. The axis pointing outwards, towards the rear left of the reader, from this page is the (a) z-axis, (b) y-axis, and (c) x-axis.
Figure B.3 Examples of applying a vector to a point. (a) applied to point p fixes point q. (b) Visualizing using q as the midpoint. (c) The dashed arrow demonstrates the vector applied to p.
Figure B.4 Vectors applied to point p. (a) Vectors and . (b) Vector . (c) Linear combination vector of vectors and with scalers .
Figure B.5 Vector components. (a) The vector is projected in the direction so that the angle ∠prq is a right angle. The projection is vector . (b) The vector components of in the direction are and .
Figure B.6 The sizes of the projection vectors onto are additive, implying distributivity .
Figure B.7 An instance of the matrix multiplication defined by Equation (B.6): matrices of sizes 3 × 2 and 2 × 4 are multiplied together, resulting in a 3 × 4 matrix. The value c_{1, 1} = a_{1, 1}b_{1, 1} + a_{1, 2}b_{2, 1}, and for example c_{2, 4} = a_{2, 1}b_{1, 4} + a_{2, 2}b_{2, 4}.
Figure B.8 Barnsley’s wreath.

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