Algorithms and Networking for Computer Games

Jouni Smed, Harri Hakonen

• Publisher: Wiley
• Year: 2017
• Print ISBN: 9781119259763
• eBook ISBN: 9781119259831
• Edition: 2
• Topic: Computer Science
• Subtopic: Programming Algorithms
• Index: Computer Science

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.

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.

1. 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.
2. 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.
3. 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:

1. coordinating the game process (...

Table of contents

• Cover
• Title page
• Copyright
• Preface
• Acknowledgements
• 1 Introduction
• Part I Algorithms
• Part II Networking
• Appendices
• Bibliography
• Ludography
• Index
• EULA