C++ Edition
C++ Edition
2D Game Development: From Zero To Hero (C++ edition, version 0.7.7) is distributed under the terms of the
If you want to view a copy of the license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/ or check the
The PDF and EPub releases of this book can be found at the following address:
This book’s source code can be found in the following official repositories:
This work shall be attributed to Daniele Penazzo and the ”2D Game Development: From Zero To Hero” community,
to see a full list of the contributors, please check the CONTRIBUTORS file in the repository, or head to the Contributors
Anonymous
To my family
Daniele Penazzo
Contents
1 Foreword 1
2 Introduction 2
2.2.4 Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.4 Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4.2 You can multiple or divide any non-zero number on both sides . . . . . . . . . . . . . . . 11
3.6 Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.7 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.9 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.10 Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.10.4 Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.11 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
III
2D Game Development: From Zero To Hero
3.11.4 Transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.12 Trigonometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.12.4 Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.12.5 Shifts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.15.1 Stretching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.15.2 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.15.3 Shearing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.1.1 Decimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.1.2 Binary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
CONTENTS IV
2D Game Development: From Zero To Hero
4.1.1.3 Octal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.1.1.4 Hexadecimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.2.1 AND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.2.2 OR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.2.3 NOT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2.2.4 XOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.5.1.2 By Paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.8.1 O(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.8.2 O(log(n)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.8.3 O(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.8.4 O(n·log(n)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2
4.8.5 O(n ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
n
4.8.6 O(2 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
CONTENTS V
2D Game Development: From Zero To Hero
4.11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.11.2 Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.11.5 Mixins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.11.7 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.11.10 Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.13.1.1 Actors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.13.1.3 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.13.2.1 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.13.2.2 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
CONTENTS VI
2D Game Development: From Zero To Hero
CONTENTS VII
2D Game Development: From Zero To Hero
6.2.3 Brainstorming: the good, the bad and the ugly . . . . . . . . . . . . . . . . . . . . . . .149
CONTENTS VIII
2D Game Development: From Zero To Hero
CONTENTS IX
2D Game Development: From Zero To Hero
CONTENTS X
2D Game Development: From Zero To Hero
CONTENTS XI
2D Game Development: From Zero To Hero
9.7.2.2 Projecting the shapes into the axes and exiting the algorithm . . . . . . . . . . . .247
10.2.1 How scene trees can make drawing entities easier . . . . . . . . . . . . . . . . . . . . .251
11 Cameras 253
CONTENTS XII
2D Game Development: From Zero To Hero
12.2.1 Remind the player about the mechanics they learned . . . . . . . . . . . . . . . . . . . .261
12.3.4 Reward the player for not immediately following the given direction . . . . . . . . . . . .263
12.3.5 Reward the player for not trusting you entirely . . . . . . . . . . . . . . . . . . . . . . .263
CONTENTS XIII
2D Game Development: From Zero To Hero
CONTENTS XIV
2D Game Development: From Zero To Hero
CONTENTS XV
2D Game Development: From Zero To Hero
CONTENTS XVI
2D Game Development: From Zero To Hero
CONTENTS XVII
2D Game Development: From Zero To Hero
CONTENTS XVIII
2D Game Development: From Zero To Hero
18.2.2.5 Story and set game events are harder to script . . . . . . . . . . . . . . . . . . .424
CONTENTS XIX
2D Game Development: From Zero To Hero
19.5.6 Turn enemy bullets into collectibles at the end of a boss fight . . . . . . . . . . . . . . . .457
CONTENTS XX
2D Game Development: From Zero To Hero
CONTENTS XXI
2D Game Development: From Zero To Hero
CONTENTS XXII
2D Game Development: From Zero To Hero
23.1.1.1 Does your FPS counter roam around a certain “special” value? . . . . . . . . . . .496
23.1.1.2 Is the animation of your game stuttering but the FPS counter is fine? . . . . . . . .496
23.1.2.3 Is your game eating up more and more RAM as it’s running? . . . . . . . . . . . .497
23.3.2 Use the right data structures for the job . . . . . . . . . . . . . . . . . . . . . . . . . . .508
CONTENTS XXIII
2D Game Development: From Zero To Hero
24.6.1 How DRM can break a game down the line . . . . . . . . . . . . . . . . . . . . . . . . . .521
CONTENTS XXIV
2D Game Development: From Zero To Hero
26.1.2.3 Can’t run away from battles, but enemies can . . . . . . . . . . . . . . . . . . . .537
CONTENTS XXV
2D Game Development: From Zero To Hero
26.2 The first good game - VVVVVV: Slim story and essential gameplay . . . . . . . . . . . . . . . . .542
26.2.10 Characters are memorable, even if you don’t see them a lot . . . . . . . . . . . . . . . .545
26.3.2 The game doesn’t take itself very seriously (sometimes) . . . . . . . . . . . . . . . . . .545
CONTENTS XXVI
2D Game Development: From Zero To Hero
28.4 Hacking is better than planning (But still plan ahead!) . . . . . . . . . . . . . . . . . . . . . . . .557
A Glossary 564
E Contributors 586
CONTENTS XXVII
2D Game Development: From Zero To Hero
1 Foreword
Every time we start a new learning experience, we may be showered by a immeasurable amount of doubts and
fears. The task, however small, may seem daunting. And considering how large the field of Game Development can
This book is meant to be a reference for game developers, oriented at 2D, as well as being a collection of “best
practices” that you should follow when developing a game by yourself (or with some friends).
But you shouldn’t let these “best practices” jail you into a way of thinking that is not yours, actually my first tip in
Do it wrong.
Learn why these best practices exist by experience, make code so convoluted that you cannot maintain it anymore,
Your toolbox is there to aid you, your tools don’t have feelings that can be hurt (although they will grumble at you
many times) in the same way that you cannot hurt a hammer when missing the nail head. You cannot break a
computer by getting things wrong (at least 99.9999% of the time). Breaking the rules will just help you understand
them better.
Write your own code, keep it as simple as you can, and practice.
Don’t let people around you tell you that “you shouldn’t do it that way”, if you allow that to happen you’re depriving
yourself of a great opportunity to learn. Don’t let others’ “lion tamer syndrome” get to you, avoid complex structures
as much as possible; cutting and pasting code will get you nowhere.
There will be times where you feel like giving up, because something doesn’t work exactly as you want it to, or
because you feel you’re not ready to put out some code. When you don’t feel ready, just try making something
simple, something that will teach you how to manipulate data structures and that gives you a result in just a couple
days of work. Just having a rectangle moving on the screen, reacting to your key presses can be that small confidence
boost that can get you farther and farther into this world.
And when all else fails, take a pen, some paper and your favorite Rubber Duck (make sure it is impact-proof) and
think.
Coding is hard, but at the same time, it can give you lots of satisfaction.
I really hope that this book will give you tips, tricks and structures that one day will make you say “Oh yeah, I can
use that!”. So that one day you are able to craft an experience that someone else will enjoy, while you enjoy the
1 FOREWORD 1
2D Game Development: From Zero To Hero
2 Introduction
A journey of a thousand miles begins with a single step
Welcome to the book! This book aims to be an organized collection of the community’s knowledge on game devel-
opment techniques, algorithms and experience with the objective of being as comprehensive as possible.
It’s really common in today’s game development scene to approach game development through tools that abstract
and guide our efforts, without exposing us to the nitty-gritty details of how things work on low-level and speeding
up and easing our development process. This approach is great when things work well, but it can be seriously
detrimental when we are facing against issues: we are tied to what the library/framework creators decided was the
best (read “applicable in the widest range of problems”) approach to solving a problem.
Games normally run at 30fps, more modern games run at 60fps, some even more, leaving us with between 33ms
These are only some basic things that can be subject to change in a game, every single frame.
When things don’t go well, the game lags, slows down or even locks up. In that case we will be forced to take the
matter in our hands and get dirty handling things exactly as we want them (instead of trying to solve a generic
problem).
When you are coding a game for any device that doesn’t really have “infinite memory”, like a mobile phone, consoles
or older computers, this “technical low-level know-how” becomes all the more important.
This book wants to open the box that contains everything related to 2D game development, plus some small tips
and tricks to make your game more enjoyable. This way, if your game encounters some issues, you won’t fear diving
Or why not, make everything from scratch using some pure-multimedia interfaces (like SDL or SFML) instead of fully
2 INTRODUCTION 2
2D Game Development: From Zero To Hero
This book aims to be a free (as in price) teaching and reference resource for anyone who wants to learn 2D game
Enjoy!
When talking about logic theory, the variables will be represented with a single uppercase letter, written in math
mode: A
The logical negation of a variable will be represented with a straight line on top of the variable, so the negation of
Listings, algorithms and anything that is code will be shown in monotype fonts, using syntax highlighting where
8 c l a s s ExampleClass {
There will be times when it’s needed to write down something from another source verbatim, for that we will use
Hi, I’m a block quote! You will see me when something is… quoted!
2 INTRODUCTION 3
2D Game Development: From Zero To Hero
2.2.4 Boxes
In your journey through this book, you may find some boxes, let’s see which ones you may come across.
Tip!
This is a tip box, here you will find tips that are loosely related to the chapter at hand.
These small tips will help you make a better game, or wiggle your way through some-
thing difficult.
Pitfall Warning!
This is a pitfall box, it will warn you of traps behind the corner, as well as possible
Random Trivia!
This is a trivia box, it will give out some small facts that can help you understand things
better, or just give you a small break from all the learning.
Note!
This is just a note box, it’s not a pitfall, a tip or a trivia. This is used for reminders and
Advanced Wizardry!
This will warn you of complex sections, or sections treating advanced topics that have
Most editions of this book does not use any engine. All algorithms will be presented pretending there is some
“generic engine” behind the scenes that handles sprites, vectors and the like. The objective of this book is teaching
algorithms, tips and tricks and game design in the most engine-agnostic (and language-agnostic, if you’re looking
If instead you’re reading a version that features “language extensions”, all algorithms will be in your favourite
2 INTRODUCTION 4
2D Game Development: From Zero To Hero
This book comes in various editions, and they come with some caveats.
• Pseudocode Edition: This is the standard edition, using a C-like syntax that tries to be as readable as
• Python Edition: Python is considered one of the easiest language to start coding on. Many tend to complain
about its performance, but its similarity to Godot Engine’s GDScript and its flexibility make it a good candidate
for starters.
• C++ Edition: C++ is probably the most used language in game development (along with C#) but it can be
really difficult to manage. It has no garbage collection, forcing you to manage the memory manually, and
• JavaScript Edition: Javascript is the de-facto “internet language” and its influence is spreading to desktop
applications and video games too. Many games now can be played on the browser thanks to it and the HTML5
canvas elements. This is a language that can be very forgiving and frustrating at the same time.
• Lua Edition: Lua is one of the most spread scripting languages in the world of video games. Since it has a very
small interpreter, it can be added to a lot of code bases without weighing them down much. It is not a proper
object-oriented language, but it has very strong metaprogramming capabilities (where you can “program the
programming language”). There are also some libraries that allow for classes and object-oriented concepts
to fit in Lua.
This book is structured in many chapters, here you will find a small description of each and every one of them.
• Introduction: Here we present the structure of the book and the reasons why it came to exist. You are
• The Maths Behind Game Development: Here we will learn the basic maths that are behind any game, like
• Some Computer Science Fundamentals: Here we will learn (or revise) some known computer science
fundamentals (and some less-known too!) and rules that will help us managing the development of our game.
• A game design dictionary: Here we will introduce some basic concepts that will help us in understanding
• Project Management Basics and Tips: Project management is hard! Here we will take a look at some
common pitfalls and tips that will help us deliver our own project and deliver it in time.
• Writing a Game Design Document: In this section we will take a look at one of the first documents that
comes to exist when we want to make a game, and how to write one,
• The Game Loop: Here we will learn the basics of the “game loop”, the very base of any video game.
• Collision Detection and Reaction: In this section we will talk about one of the most complex and compu-
• Scene Trees: Here we will briefly talk about probably the most important structure in games and game
2 INTRODUCTION 5
2D Game Development: From Zero To Hero
• Cameras: In this section we will talk about the different types of cameras you can implement in a 2D game,
• Game Design Tips: In this chapter we will talk about level design and how to walk your player through the
learning and reinforcement of game mechanics, dipping our toes into the huge topic that is game design.
• Creating your own assets: Small or solo game developers may need to create their own assets, in this
section we will take a look at how to create our own graphics, sounds and music.
• Design Patterns: A head-first dive into the software engineering side of game development, in this section
• Useful Containers and Classes: A series of useful classes and containers used to make your game more
• Artificial Intelligence in Video games: In this section we will talk about algorithms that will help you coding
your enemy AI, as well as anything that must have a “semblance of intelligence” in your video game.
• Other Useful Algorithms: In this section we will see some algorithms that are commonly used in game,
• Procedural Content Generation: In this chapters we will see the difference between procedural and random
content generation and how procedural generation can apply to more things than we think.
• Developing Game Mechanics: Here we will dive into the game development’s darkest and dirtiest secrets,
how games fool us into strong emotions but also how some of the most used mechanics are implemented.
• Balancing Your Game: A very idealistic vision on game balance, in this chapter we will take a look inside
the player’s mind and look at how something that may seem “a nice challenge” to us can translate into a
• Accessibility in video games: Here we will learn the concept of “accessibility” and see what options we
can give to our players to make our game more accessible (as well as more enjoyable to use).
• Testing your game: This section is all about hunting bugs, without a can of bug spray. A deep dive into the
• Profiling and Optimization: When things don’t go right, like the game is stuttering or too slow, we have to
rely on profiling and optimization. In this section we will learn tips and tricks and procedures to see how to
• Marketing Your Game: Here we will take a look at mistakes the industry has done when marketing and
maintaining their own products, from the point of view of a small indie developer. We will also check some of
the more controversial topics like loot boxes, micro transactions and season passes.
• Keeping your players engaged: a lot of a game’s power comes from its community, in this section we will
take a look at some suggestion you can implement in your game (and out-of-game too) to further engage your
loyal fans.
• Dissecting Games: A small section dedicated to dissecting the characteristics of one (very) bad game, and
two (very) good games, to give us more perspective on what makes a good game “good” and what instead
• Project Ideas: In this section we take a look at some projects you can try and make by yourself, each project
is divided into 3 levels and each level will list the skills you need to master in order to be able to take on such
2 INTRODUCTION 6
2D Game Development: From Zero To Hero
level.
• Game Jams: A small section dedicated on Game Jams and how to participate to one without losing your mind
• Where to go from here: We’re at the home stretch, you learned a lot so far, here you will find pointers to
• Glossary: Any world that has a g symbol will find a definition here.
• Engines and Frameworks: A collection of frameworks and engines you can choose from to begin your game
development.
• Tools: Some software and tool kits you can use to create your own resources, maps and overall make your
• Premade Assets and resources: In this appendix we will find links to many websites and resource for
• Contributors: Last but not least, the names of the people who contributed in making this book.
2 INTRODUCTION 7
Part 1: The basics
2D Game Development: From Zero To Hero
Do not worry about your difficulties in Mathematics. I can assure you mine
Albert Einstein
This book assumes you already have some knowledge of maths, but we will also try to keep the bar of entry as low
as possible.
Also we will represent derivatives with the f ′ (x) symbol, instead of the more verbose ∂f
∂x .
In this chapter we’ll take a quick look (or if you already know them, a refresher) on the basic maths needed to make
a 2D game.
While reading this book, we may need to delve into some mathematical lingo that not everyone may understand
immediately, so here’s a small glossary of some of mathematical the symbols we may use.
• x∈S Denotes a “set membership”, so the object to the left of the symbol is an element of the set at the
• A ⊆ B Denotes a “subset relationship” where equality is possible: A is a subset of B, but also it may happen
that A equals B;
• A∪B Denotes “set union”, the result is composed by all elements of A and B, combined;
• A∩B Denotes “set intersection”, the result is composed by all elements of A that are also found in B;
Very basic, but sometimes overlooked, function in mathematics is the “modulo” function (or “modulo operator”).
Modulo is a function that takes 2 arguments, let’s call them “a” and “b”, and returns the remainder of the division
represented by a/b.
In most programming languages the modulo function is hidden behind the operator “%”, which means that the
The modulo operator is very useful when we need to loop an ever-growing value between two values (as will be
Pitfall Warning!
Be careful when using the modulo operator with negative arguments: it may lead to
unexpected results, which may depend on the programming language you are using.
We start our revision of maths by remembering powers and roots. A power is just a short way to multiply a number
One rule that we need to remember is that any number, when elevated to the zero-th power is always 1, so 2560 =1
as well as 20 = 1.
Note!
√
Roots are the inverse operation of powers, which means that if 42
2
= 16 then 16 = 4
√
3
√
4
√
9532
Taking the examples of earlier, we have that 8 = 2, 4 = 4 and 0 = 0. Omitting the index n on the root is
a short way to write the “square root”, which is the root with index 2. That means:
√
2
√
4= 4=2
Pitfall Warning!
√
When talking “real numbers”, there is no −1: that would fall into the “complex num-
bers” category, which are a matter outside the scope of this revision. That’s because
there is no real number that multiplied by itself an even amount of times that would
give a negative number. To make things more complex, roots with odd indices of nega-
√
tive numbers are part of the real numbers instead:
3
−8 = −2 because (−2)3 = −8
3.4 Equations
Equations are a way to express equality between two expressions, we’ve seen equations all our lives, just “hidden”.
In their more known form, equations can have one or more “unknowns”, usually represented with letters (the most
used are, in order x, y and z) and “solving an equation” means finding values for the unknowns that make the
equation true.
2 · x = 10
Which can be read as “x is the number, that multiplied by 2, gives 10”, the solution of this equation is x = 5, because
2 · 5 = 10.
This is one of the rules that will help us making things a bit easier. Let’s take the following example:
15 + 2x = 45
−15 + 15 + 2x = 45 − 15
2x = 30
3.4.2 You can multiple or divide any non-zero number on both sides
This is another one of those rules that makes things a lot easier, taking the previous example:
2x = 30
1 1
· 2x = 30 ·
2 2
2x 30
=
2 2
x = 15
Similarly to powers involving simple numbers, we can involve letters in powers too, making them “exponentiations”.
2x = 32
In this case x is the number that makes the previous equation true (by the way, the result is x = 5).
log2 32 = x
In the previous example “2” is called the “base” of the logarithm. So this formula is read as “x is the base 2 logarithm
Here is a quick table of rules that can be used to make logarithms easier to calculate.
Rule Formula
3.6 Limits
Advanced Wizardry!
We’re entering some complex math territory here, so I will give you an “intuitive” defi-
nition of a limit. Having an idea of what it is will suffice for the needs of this book
Limits are an interesting beast: we can see them as the value a function approaches as the input approaches some
lim f (x) = y
x→a
In this case it can be read as “y is the limit, for x approaching a, of f (x)”. Limits can be seen as, “the more x gets
y and a can be any value, including infinity. In fact the following statement is true:
lim x = +∞
x→+∞
The further we count down the line of numbers the closer we get to infinity. Which also means that:
1
lim =0
x→+∞ x
Because as we are counting up with x, we are dividing 1 by bigger and bigger numbers until (at the limit) we reach
0.
Pitfall Warning!
There are some situations where a limit cannot be determined immediately (or some-
∞ 0
times at all). Some of these are +∞ − ∞, 0 · ∞, ∞, 0, ∞0 , 00 and 1∞ .
3.7 Derivatives
Note!
This is not a complete guide to derivatives, there is so much more to it than written
in here. This is mostly for informational purposes when the term “derivative” will be
Derivatives are technically just a limit, to be precise they are the following limit:
f (x + h) − f (h)
lim
h→0 h
They also have a nifty property that is used extensively in calculus: if f ′ (x) > 0 then f (x) is increasing, while if
′ ′
f (x) < 0 then f (x) is decreasing. This means that the equation f (x) = 0 can be used to find local extrema: also
There are some rules to quickly derivative functions, here we list some of the most basic.
Table 2: Some simple derivation rules (k is any constant number and e is Euler’s number)
Function Derivative
k 0
x k
k · xk−1
ex ex
Table 3: Some derivation rules for combined functions (a and b are constants)
Functions Derivative
The Cartesian plane is a plane that features a 2-dimensional coordinate system. This way we can represent points
II y I
8
-8 -7 -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 7 8
-1
x
-2
-3
-4
-5
-6
-7
III -8
IV
Using a Cartesian plane we can represent the position of items, as well as their shape, space occupation, as well as
It is an essential tool for 2D game development, and it will be one of the abstractions we will use to represent items
in a 2-Dimensional plane.
3.9 Vectors
For our objective, we will simplify the complex matter that is vectors as much as possible.
Vectors usually represent a force applied to a body, its velocity or acceleration and are graphically represented with
an arrow.
On a Cartesian plane it can be seen as “the x and y quantities you need to move to get from a point to another”.
y I
8
1
(4,1)
1 2 3 4 5 6 7 8
x
Figure 2: Image of a vector
From the previous example, the vector v = (4, 1) can be thought of as the following:
you need to move 4 units on the x axis and 1 on the y axis to go from the origin to the point P (4, 1)
The pain of learning about vectors is paid off by their capacity of being added and subtracted among themselves,
Adding vectors is as easy as adding its “members”. Let’s consider the following vectors:
v = (4, 1)
u = (1, 4)
s = v + u = (4 + 1, 1 + 4) = (5, 5)
Graphically it can be represented by placing the tail of the arrow v on the head of the arrow u, or vice-versa:
y I
8
1 2 3 4 5 6 7 8
x
Figure 3: Graphical representation of a sum of vectors
v = (2, 4)
u = (1, 5)
s = u + v = (2 + 1, 4 + 5) = (3, 9)
There may be situations where you need to make a vector x times longer. This operation is called “scalar multipli-
v = (1, 2)
3 · v = (1 · 3, 2 · 3) = (3, 6)
y I
8
1 2 3 4 5 6 7 8
x
Figure 4: Example of a vector multiplied by a value of 3
v = (4, 2)
1
2 · v = ( 12 · 4, 12 · 2) = (2, 1)
y I
8
1 2 3 4 5 6 7 8
x
Figure 5: Example of a vector multiplied by a value of 0.5
When you multiply the vector by a value less than 0, the vector will rotate by 180°.
v = (1, 2)
y I
8
1 2 3 4 5 6 7 8
x
Figure 6: Example of a vector multiplied by a value of -2
The dot product (or scalar product, projection product or inner product) is defined as follows:
Given two n-dimensional vectors v = [v1 , v2 , ...vn ] and u = [u1 , u2 , ..., un ] the dot product is defined as:
∑
n
v·u= (vi · ui ) = (v1 · u1 ) + ... + (vn · un )
i=1
So in our case, we can easily calculate the dot product of two two-dimensional vectors v = [v1 , v2 ] and u = [u1 , u2 ]
as:
v · u = (v1 · u1 ) + (v2 · u2 )
Given the vectors v = [1, 2] and u = [4, 3], the dot vector is:
v · u = (1 · 4) + (2 · 3) = 4 + 6 = 10
Given a vector a = [a1 , a2 , ..., an ], you can define the length of the vector as:
√
||a|| = a21 + a22 + ... + a2n
Or alternatively
√
||a|| = a·a
We can get a 1-unit long vector by “normalizing” it, getting a vector that is useful to affect (or indicate) direction
without affecting magnitude. A normalized vector is usually indicated with a “hat”, so the normalized vector of
a = [a1 , a2 , ..., an ] is
a
â =
||a||
Knowing that the length of a vector is a scalar (a number, not a vector), normal scalar multiplication rules apply.
This is not an operation “per se”, but there are occasions where we need to limit the length of a vector: this usually
happens when we are working with velocity, as not limiting it would allow an object to change position faster and
faster, making the game less playable and even breaking time-stepping collision detection algorithms.
To clamp a vector, we need to find its magnitude and direction first, which is the “normalized vector”. Let’s think
√
||v|| = v·v
v
v̂ =
||v||
After that, we can build a new vector using the “clamped magnitude” (which we’ll call ||v||clamp ), calculated as such:
||v|| when ||v|| < ||v||max
||v||clamp =
||v||max otherwise
vclamp = ||v||clamp · v̂
The new vector will have the same direction as the old one, but its magnitude will be clamped, just like we wanted.
3.10 Geometry
Among all the maths we found so far (and the maths we will explain later), we cannot avoid talking a bit about
geometry: in this book we will talk about the minimal amount of geometry necessary to understand the underlying
A polygon is considered convex essentially when any line (not tangent to an edge or corner) drawn through the
shape crosses the shape itself only twice (at its ends).
C B
D A
E F
Figure 7: Example of a convex shape
Any shape where you can find at least one line that crosses the shape more than twice is considered “non-convex”
B
C
A
D
G
E F
Figure 8: Example of a concave shape
Note!
Not all non-convex shapes are technically called “concave” (they should be called “non-
convex”), but for the sake of simplicity we’ll use the term “non-convex” and “concave”
Contrary to what many think, polygons can self-intersect too, which can make calculations a lot harder.
C
A
B
D
Figure 9: Example of a self-intersecting polygon
For the sake of game development, we will usually talk about simple polygons which are polygons that don’t self-
intersect and have no holes in them. More strictly we will (for 99.9% of the time) talk about convex simple poly-
gons.
One of the main topics we will encounter over and over in our game development adventure will be “straight lines”.
We will need to draw them, see if two straight lines collide, project stuff onto them, and much more. So it’s important
ax + by + c = 0
That’s not what you expected, right? What you’ve seen is the “general form” of a straight line’s equation, because
you can represent lines using equations (also circles, and other stuff). This is not a much-used form, though, probably
y = mx + q
Random Trivia!
To transform a “general form” equation into the relative “slope-intercept from” just
a c
m=− q=−
b b
This doesn’t work well when b = 0, which will be subject of the next “pitfall”.
Where in this case m is the slope of our straight line, and q represents the so-called y-intercept (the value of y when
x = 0). If q = 0 the line goes through the origin of the Cartesian coordinate system, if m = 0 the line is horizontal.
Pitfall Warning!
“Vertical straight lines” is where the slope-intercept form fails, in fact vertical straight
lines have an equation in the form of x = k , which would mean that b = 0 which is
problematic (see previous trivia).
We all know that given two points we can strike one and only one line. How many times did you measure two points
(maybe while doing some D.I.Y.) and stroke a line between them?
It will be useful in our adventure to be able to get the equation of a straight line starting from two points, so let’s call
our two points P (x1 , y1 ) and Q(x2 , y2 ), then the straight line that crosses both those points will have equation:
y − y1 y2 − y 1
=
x − x1 x2 − x1
This may seem really complicated, but with some small calculations we can reach a formula for our straight line in
Pitfall Warning!
Again, this formula fails when we are dealing with “vertical lines”, because the denom-
inator at the right side of the equation will be zero. But in that case we’ll already know
If we have a point P (xp , yp ) and the slope m (for instance if we need to find a line perpendicular to another line),
in that case we can use the following formula:
y − yp = m(x − xp )
Pitfall Warning!
Guess what? This (again) doesn’t allow us to create “vertical lines”, because we need
a slope value, which we don’t have when it comes to vertical lines. You can see (non
3.10.4 Projections
In some situations (as you will see in the SAT), we may need to get to project polygons onto a line, this usually
Given the formulas we’ve seen earlier, and doing some thinking, we can easily project a point onto any straight line.
First of all, the line we will be projecting onto will have equation y = mx + q , just as in the slope-intercept formula.
We will assume that we have a point P (xp , yp ) that we want to project onto a line r with equation y = mx + q ,
with m ̸= 0 (thus excluding horizontal lines). We will call the projected point “P onto r” with the name Pr (xr , yr ).
Pr
r
Figure 10: Projecting the point P onto the line r
First, we need to find the line that goes through P and is perpendicular to r , this is really easy. To find a slope m1
of a line perpendicular to another line with slope m we use the formula
1
m1 = −
m
Pitfall Warning!
This is why we excluded the case m = 0 (horizontal lines), if we didn’t we would have
1
the chance of having m1 = 0 which doesn’t make sense.
In this case we can easily conclude that if m = 0, the projection of the point P onto
the line r has coordinates (xP , y) (with y taken from the line we’re projecting onto).
Now we have a point and a slope, so we can use one of the formulas we’ve already seen to find the line with that
1
y − yp = m1 (x − xp ) ⇔ y − yp = − (x − xp )
m
To find Pr we just need to find the point where the two lines collide, which is the solution to the equation system:
y = mx + q
y − yp = − 1 (x − xp )
m
x = xp +myp −mq
m2 +1
y = mxp +m2 yp +q
m2 +1
The coordinates x and y we just found are actually the coordinates xr and yr of our projected point Pr .
Pitfall Warning!
Similarly to what we’ve done with points, we can project arbitrary lines (or, to be precise, the ends of such lines)
onto the axes. This will help us in doing some calculations later (when we’ll talk about SAT).
To project any line r to the x-axis we can just “pass all the line’s points through” the following function:
If we want to project such line on the y-axis, we can just use this other function:
We can see an intuitive representation of projecting a line onto the axes below:
y I
8
1 2 3 4 5 6 7 8
x
Figure 11: Projecting a line onto the axes
Let’s take the point P (2, 5) from the previous figure. We want to project it on the x axis: that means we need to
find a line that is 90 degrees with the x axis and passes through P .
Such line is the line with equation x = 2, now to find the projection of P onto the x axis, we will just need to solve a
simple equation system.
x = 2
y = 0
Where y = 0 is the equation of the x axis. So our projected point is Px (2, 0).
Similar thing goes for projecting the point on the y axis: the line that is 90 degrees with the y axis and goes through
P has equation y = 5, the y axis has equation x = 0, thus the system of equation is solved with Py (0, 5).
3.11 Matrices
Matrices are essentially an m × n array of numbers, which are used to represent linear transformations.
2 1 4
A2,3 =
3 2 0
Summing and subtracting m×n matrices is done by summing or subtracting each element, here is a simple example.
2 1 4 1 3 0
A2,3 = B2,3 =
3 2 0 4 2 4
We have that:
2 1 4 1 3 0 2+1 1+3 4+0 3 4 4
A2,3 + B2,3 = + = =
3 2 0 4 2 4 3+4 2+2 0+4 7 4 4
2 1 4
A2,3 =
3 2 0
Multiplication by a scalar is performed by multiplying each member of the matrix by the scalar, like the following
example:
2 1 4 3·2 3·1 3·4 6 3 12
3 · A2,3 = 3 · = =
3 2 0 3·3 3·2 3·0 9 6 0
3.11.4 Transposition
Given an m × n matrix A, its transposition is an n × m matrix AT constructed by turning rows into columns and
2 1 4
A2,3 =
3 2 0
2 3
AT2,3 = 1 2
4 0
Given 2 matrices with sizes m × n and n × p (mind how the number of rows of the first matrix is the same of the
number of columns of the second matrix):
2 3
2 3 4
A3,2 = 1 2 B2,3 =
0 1 0
4 0
We can calculate the multiplication between these two matrices, in the following way.
First of all let’s get the size of the resulting matrix, which will be always m × p.
2 3 ? ? ?
2 3 4
=
1 2 × ? ? ?
0 1 0
4 0 ? ? ?
Matrix multiplication is called a “rows by columns” multiplication, so to calculate the first row - first column value
we’ll need the first row of one matrix and the first column of the other.
2 3 ? ? ?
2 3 4
=
1 2 × ? ? ?
0 1 0
4 0 ? ? ?
2·2+3·0=4
2 3 4 ? ?
2 3 4
=
1 2 × ? ? ?
0 1 0
4 0 ? ? ?
2 3 4 ? ?
2 3 4
=
1 2 × ? ? ?
0 1 0
4 0 ? ? ?
2·3+3·1=9
Obtaining:
2 3 4 9 ?
2 3 4
1 2 × = ? ? ?
0 1 0
4 0 ? ? ?
Same goes for the last value, when we are done with the first row, we keep going similarly with the second row:
2 3 4 9 8
2 3 4
=
1 2 × ? ? ?
0 1 0
4 0 ? ? ?
1·2+2·0=2
2 3 4 9 8
2 3 4
=
1 2 × 2 ? ?
0 1 0
4 0 ? ? ?
You can try completing this calculation yourself, the final result is as follows:
2 3 4 9 8
2 3 4
=
1 2 × 2 5 4
0 1 0
4 0 8 12 16
Note!
Multiplication between matrices is non commutative, which means that the result of
A×B is not equal to the result of B × A: actually one of the results may not even
be possible to calculate.
Matrices can be used to quickly represent equation systems, with equation that depend on each other. For instance:
x
2 3 6
4
y =
1 4 9 5
z
2x + 3y + 6z = 4
1x + 4y + 9z = 5
Or, as we’ll see, matrices can be used to represent transformations in the world of game development.
3.12 Trigonometry
When you want to develop a game, you will probably find yourself needing to rotate items relative to a certain point
or relative to each other. To do so, you need to know a bit of trigonometry, so here we go!
In everyday life, angles are measured in degrees, from 0 to 360 degrees. In some situations in maths, it is more
You can convert back and forth between radians and degrees with the following formulas:
180
angle in degrees = angle in radians ·
π
π
angle in radians = angle in degrees ·
180
This book will always refer to angles in radians, so here are some useful conversions, ready for use:
Degrees Radians
0° 0
π
30° 6
π
45° 4
π
60° 3
π
90° 2
180° π
360° 2π
The most important trigonometric functions are sine and cosine. They are usually defined in reference to a “unit
Given the unit circle, let a line through the origin with an angle θ with the positive side of the x-axis intersect such
unit circle. The x coordinate of the intersection point is defined by the measure cos(θ), while the y coordinate is
II y I
-1 1
-1
III IV
For the purposes of this book, we will just avoid the complete definition of the tangent function, and just leave it as
sin(θ)
tan(θ) =
cos(θ)
One of the most important identities in Trigonometry is the “Pythagorean Trigonometric Identity”, which is expressed
Also remember that sin2 (θ) = (sin(θ))2 and cos2 (θ) = (cos(θ))2 .
3.12.4 Reflections
Sometimes we may need to reflect an angle to express it in an easier way, and their trigonometric formulas will be
Reflection Formulas
sin(−θ) = −sin(θ)
cos(−θ) = cos(θ)
sin( π2 − θ) = cos(θ)
cos( π2 − θ) = sin(θ)
sin(π − θ) = sin(θ)
cos(π − θ) = −cos(θ)
sin(2π − θ) = −sin(θ) = sin(−θ)
cos(2π − θ) = cos(θ) = cos(−θ)
3.12.5 Shifts
Trigonometric functions are periodic, so you may have an easier time calculating them when their arguments are
shifted by a certain amount. Here we can see some of the shift formulas:
Shift Formulas
sin(θ ± π2 ) = ±cos(θ)
cos(θ ± π2 ) = ∓sin(θ)
sin(θ + π) = −sin(θ)
cos(θ + π) = −cos(θ)
sin(θ + k · 2π) = sin(θ)
cos(θ + k · 2π) = cos(θ)
Sometimes you may need to express a trigonometric formula with a complex argument by splitting such argument
into different trigonometric formulas. If such argument is a sum or subtraction of angles, you can use the following
formulas:
Addition/Difference Identities
Other times (mostly on paper) you may have an argument that is a multiple of a known angle, in that case you can
Double-Angle Formulae
sin(2θ) = 2sin(θ)cos(θ)
cos(2θ) = cos2 (θ) − sin2 (θ)
As with practically all maths formulas, there are inverse formulas for sine and cosine, called arcsin and arccos,
which allow to find an angle, given its sine and cosine.
In this book we won’t specify more, besides what could be the most useful: the 2-argument arctangent.
This formula allows you to find the angle of a vector, relative to the coordinate system, given the x and y coordinates
y
θ = arctan( )
x
II y I
8
(x,y)
4
-8 -7 -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 7 8
-1
x
-2
-3
-4
-5
-6
-7
III -8
IV
Here we will give some pointers over some algorithms and methods that may be useful to better explain some topics
treated in this book. Feel free to skip or quickly read this section if you don’t want to dive into too much detail over
Advanced Wizardry!
This section treats of how to approximate a function value in an iterative way. This will
be useful to know what the “Fast Inverse Square Root” algorithm uses. Feel free to
Also known as Newton’s method, this is an iterative algorithm that is used to get progressively better approximations
The algorithm starts with a “guess”, called x0 , and produces the first approximation using the formula:
f (x0 )
x1 = x0 −
f ′ (x0 )
Each subsequent guess (and thus iteration) can be obtained similarly by using the formula:
f (n)
xn+1 = xn −
f ′ (n)
And such guess will be more precise than the previous one (if we don’t consider some situations where approaching
the root can be problematic or not possible). The algorithm will stop when you reach an approximation that is “good
enough”.
Obviously all limitations of standard functions apply, such as domain and trouble with divisions by zero.
When it comes to 2D graphics on computers, our world gets quite literally turned upside down.
In our maths courses we learned about the Coordinate Plane, with an origin and an x axis going from left to right and
a y axis going from bottom to top, where said axis cross it’s called the “Origin”.
II y I
8
-8 -7 -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 7 8
-1
x
-2
-3
-4
-5
-6
-7
III -8
IV
When it comes to 2D graphics on computers and game development, the coordinate plane looks like this:
The origin is placed on the top left of the screen (at coordinates (0,0)) and the y axis is going from top to bottom.
It’s a little weird at the beginning, but it’s not hard to get used to it.
There will be a time, in our game development journey where we need to rotate an object, and that’s bound to be
pretty easy because rotation is something that practically all engines and tool kits do natively. But also there will be
An instance where it may happen is rotating an item relative to a certain point or another item: imagine a squadron
of war planes flying in formation, where all the planes will move (and thus rotate) relative to the “team leader”.
• Stretching/Squeezing/Scaling;
• Rotation;
• Shearing.
And to do so, we will use the following reference image, complete with a quadrant of the Cartesian plane.
y I
8
1 2 3 4 5 6 7 8
x
Figure 16: Reference image for transformation matrices
3.15.1 Stretching
Stretching is a transformation that enlarges all distances in a certain direction by a defined constant factor. In 2D
graphics you can stretch (or squeeze) along the x-axis, the y-axis or both.
If you want to stretch something along the x-axis by a factor of k , you will have the following system of equations:
x′ = k · x
′
y =y
x′ k 0 x
=
′
y 0 1 y
Likewise, you can stretch something along the y-axis by a factor of k by using the following matrices:
x′ 1 0 x
=
y′ 0 k y
Stretching our reference image along the x and y axes respectively would look something like this:
y I y I
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
x x
Figure 17: Stretching along the x and y axes
You can mix and match the factors and obtain different kinds of stretching, if the same factor k is used both on the
x and y-axis, we are performing a scaling operation, like follows:
x′ k 0 x
=
y′ 0 k y
In instead of stretching you want to squeeze something by a factor of k , you just need to use the following matrices
x′ 1
0 x
= k
y′ 0 1 y
x′ 1 0 x
=
y′ 0 1
k y
3.15.2 Rotation
If you want to rotate an object by a certain angle θ, you need to decide upon two things (besides the angle of
rotation):
Similarly to stretching, rotating something of a certain angle θ leads to the following matrix form:
x′ x
= TR
y′ y
If we want to rotate something clockwise, relative to its reference point, we will have the following transformation
matrix:
cos(θ) sin(θ)
TR =
−sin(θ) cos(θ)
y I
8
1 2 3 4 5 6 7 8
x
Figure 18: The result of applying a rotation matrix
If instead we want our rotation to be counterclockwise, we will instead use the following matrix:
cos(θ) −sin(θ)
TR =
sin(θ) cos(θ)
Pitfall Warning!
These formulas assume that the x-axis points right and the y-axis points up, if
the y-axis points down in your implementation, you need to swap the matrices.
The biggest problem in rotation is rotating an object relative to a certain point: you need to know the point of rotation
(xp , yp ) in relation to the origin of the coordinate system you’re using, and modify the matrices as follows:
x′ x − xp x
= TR + p
y′ y − yp yp
In short, you need to rotate the item by first “bringing it centered to the origin”, rotate it, and then bring it back into
3.15.3 Shearing
During stretching, we used the elements that are in the “main diagonal” to stretch our objects. If we modify the
Shearing will move points along a certain axis with a “strength” defined by the distance along the other axis: if we
x′ 1 k x
=
y′ 0 1 y
While a shear parallel to the y-axis will instead have the following matrix:
x′ 1 0 x
=
′
y k 1 y
y I y I
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
x x
Figure 19: Shearing along the x and y axes
Games can make heavy use of probability: for instance when spawning items and treasures. Having a basic grasp
T he outcome is A
P (A) =
All Outcomes
The numerator is called “event space”, while the denominator is called “sample space”.
For instance: let’s take a coin. We want to calculate the probability that a coin toss ends with “head”: first we count
how many outcomes are possible. Since a coin can land on “tails” or “heads”, we have 2 possible outcomes, and
Thus:
1
P (H) = = 0.5
2
This result can be converted to a percentage, by multiplying it by 100. That means that there’s a 50% chance that
P (A) = 1 − P (A)
1 1
P (H) = 1 − P (A) = 1 − = = P (T )
2 2
But what if we wanted to calculate the probability of more than one event?
If our events are independent (that means that the result of one doesn’t affect the result of others), we can use the
following formula:
Let’s return to our coin example: if we wanted to know the probability of two coin tosses landing both on heads, we
would have:
1 1 1
P (H and H) = P (H) · P (H) = · =
2 2 4
Let’s demonstrate that intuitively: since the example is simple, we can literally count the possible outcomes:
Heads Heads
Heads Tails
Tails Heads
Tails Tails
Now we know that there are 4 possible outcomes, and the “Heads + Heads” is only one of them. This confirms our
formula.
In the exact same way, we can calculate the probability of a “Heads + Tails” result:
1 1 1
P (H and T ) = P (H) · P (T ) = · =
2 2 4
Pitfall Warning!
toss is heads, second toss is tails), is different from “Tails + Heads” (first toss is tails,
second is heads).
In case the events are mutually exclusive (that means, if one event happens, none of the others can happen), the
P (A or B) = P (A ∪ B) = P (A) + P (B)
Going back to our coin example: the probability of a coin toss being “either heads or tails” is 1
2 + 1
2 = 1.
Another example could be done using a 6-sided dice: each face can be on top with a probability of 1
6 . Let’s calculate
the probability of either 1 or 6 being face up:
1 1 2 1
P (1 or 6) = P (1) + P (6) = + = =
6 6 6 3
Note!
Considering the latest “tossing two coins” example, we can calculate the probability
of “one coin lands on heads and the other lands on tails” with the previous formulas,
since coin tosses tick both the “independence” and “mutual exclusivity” boxes.
1 1 1
P ((H and T ) or (T and H)) = P (H and T ) + P (T and H) = + =
4 4 2
Not all events are mutually exclusive. Let’s think, for instance, about a deck of cards: what if you wanted to know
the probability of drawing either a card of hearts or a face card (Jack, Queen or King)?
We need to use a different formula in that case, which is the following one:
Note!
Why are we subtracting P (A and B)? Because if we didn’t, we would be counting the
face cards of hearts twice: once when we count the card of hearts, and once when we
13
A standard deck has 52 cards, 13 for each seed. This means we would have 13 cards of hearts: P (A) = 52 .
12
The same deck of cards also has 3 “face cards” for each seed, totalling 12: P (B) = 52 .
3
Since there are face cards of the hearts seed, we need to account for those too, totalling 3: P (A and B) = 52 .
This means that the probability we’re looking for is calculated as follows:
13 12 3 22 11
P (A orB) = P (A) + P (B) − P (A and B) = + − = =
52 52 52 52 26
Advanced Wizardry!
Conditional probability doesn’t have a lot of uses in game development, but it’s worth
mentioning it if you want to have a probabilistic approach to AI. Feel free to quickly
Sometimes you may need to consider the probability of a certain event, given that another event happens. This is
P (A and B) P (A ∩ B)
P (A|B) = =
P (B) P (B)
Conditional probability can be used to enrich the decision making used in enemy AI, for instance.
Let’s take a concrete example, taken straight from the famous tabletop RPG Dungeons&Dragons, and see how
You’re fighting against an enemy. Both you and the enemy are close to fatal damage: you have 1HP, while
To attack an enemy you need to roll a 20-sided dice (called a d20): if the number rolled is 13 or higher you
If you hit, you will roll a 6-sided dice (called a d6): the number rolled will decide how much damage you will
We need to find the probability of killing the enemy within the next turn to decide our next move.
• H Will be the event “hit”, which means that the d20 rolled a number that is 13 or higher.
• F Will be the event “fatal damage”, which means that the d6 rolled a number that is 3 or higher.
8 2
P (H) = =
20 5
4 2
P (F ) = =
6 3
Our objective is calculating “the probability of doing at least 3HP of damage, given that we hit the enemy”. This is
represented as:
P (F ∩ H)
P (F |H) =
P (H)
This means we will have to calculate another probability, which is quite easy:
2 2 4
P (F ∩ H) = P (F ) · P (H) = · =
3 5 15
P (F ∩ H) 4
4 5 2
P (F |H) = = 15
2 = · =
P (H) 5
15 2 3
Given a 66% chance of success, you may decide that attacking is worth the risk. Such decision may be hard-coded
into an AI, for instance if the probability is higher than 50% the AI may choose to attack instead of retreating and
In most cases, we will speak in terms of “uniform distributions”, that means that we will be operating on a system
That means that all dices are “fair”, all coins are “fair” and all our “bingo bags” have only one instance of a certain
number, all of the same size, shape and feel (thus making it impossible for a number to appear more often than any
other).
In the grand scheme of things, we are assuming that the random() function of our programming language is a uniform
distribution, where any number may come out with the same probability of any other.
You can use probability to govern how items spawn: surely you want more precious items to spawn more rarely (with
less probability), while more common items should spawn more often.
Let’s say we want an item to spawn with 20% probability: how can we do it?
20% probability can be rewritten as the decimal 0.2, such decimal can be obtained with the fraction 1
5 . We have
practically solved the problem: we decide on one number between 1 and 5 (inclusive) and we will know that such
5 i n t main () {
6 i n t happened = 0;
13 i f (n == 1) {
Figure 20: Running the probability_20 example shows the probability floating around 20%
But what if we wanted to be a lot more precise? Let’s say we want to spawn an item with 13% probability, how would
we go at it?
13
It’s actually pretty simple: out 13% probability can be represented by the fraction 100 . Each number between 1 and
1
100 (inclusive) has a 100 chance of being extracted. Since extracting one number bars any other number to appear
1 1 1 13
P (1 or 2 or ... or 13) = P (1) + P (2) + ... + P (13) = + + ... + =
100 100 100 100
Tip!
If the example is not 100% clear yet, try reading the previous formula right-to-left. That
may help.
This means that the event “a number between 1 and 13 appears” has a 13% probability of appearing. We can
simplify that statement with “a number less or equal than 13”. We can experiment that easily with the following
code:
Listing 3: A number less or equal than 13 (out of 100) has 13% probability of appearing
5 i n t main () {
6 i n t happened = 0;
13 i f (n <= 1) {
Figure 21: Running the probability_le_13 example shows the probability floating around 13%
Tip!
You can extend the example above to fractions of a percentage by using bigger num-
bers: if you wanted a 13.5% probability, you would use all numbers less than or equal
We can use what we learned with probability to create a tiered prize pool. For instance we decide that killing a
certain enemy will always drop something, the tier of such item is according to the follow probability list:
• 50% probability for a common item to drop (for instance a scrap of leather);
• 15% probability for a rare item to drop (a good sword, for instance);
30% 5%
Uncommon Epic
50% 15%
0 Common Rare
100
In that case we can chain ifs to bring our tiered prize pool to life:
7 i n t get_tiered_drop () {
10 i f (n <= 50) {
11 // Common Tier
12 r e t u r n 1;
13 }
14 i f (n <= 80) {
15 // Uncommon Tier
16 // Since n <=50 has already returned false , we know this
17 // branch will only happen if 50 <n <=80
18 r e t u r n 2;
19 }
20 i f (n <= 95) {
21 // Rare Tier
22 // Since both n <=50 and n <=80 both returned false , we know
23 // this branch will only happen if 80 <n <=95
24 r e t u r n 3;
25 }
26 // Epic Tier
27 // All other branches failed , so we 'll get here only if
28 // 95 <n <=100
29 r e t u r n 4;
30 }
In many RPGs there is a “luck” statistic that affects how item drops happen, in that case we will need to change how
tiered prize pools are given out. Things can get complicated quite quickly.
Let’s imagine a simple situation: one point of “luck” gives a 1% probability of getting an item of each tier higher
than “Common”, while at the same time reducing the probability of finding a “common” item.
At a first glance, it seems simple: take each “non-common” class and “add 1”, then take the “common” class and
“remove 1 for each point given”. But what would happen if the luck stat is higher than the probability of a “common”
item? It should probably start taking away probability from “uncommon” items to give out “rare” and “epic” items.
6 { EPIC , 5} ,
7 { RARE , 15} ,
8 { UNCOMMON , 30} ,
9 { COMMON , 50} ,
10 };
11
12 // Our " luck stat ": each point gives 1% more chance to get a higher - tier item
13 i n t LUCK = 25;
14
15 // We cap the Luck stat at 100 , the limit is 100% epic items
16 LUCK = std :: min ( LUCK , 100) ;
17
18 // We " overload " the prize pool , making the sum go over 100%
19 i n t overloaded_pool [4][2];
20 i n t overload_factor = 0;
21
22 f o r ( i n t i = 0; i < 4; i ++) {
35 // We need to start from the most common , which means we will iterate backwards
36 f o r ( i n t i = 3; i > 0; i - -) {
Edsger W. Dijkstra
In order to understand some of the language that is coming up, it is necessary to learn a bit of the computer science
This chapter will briefly explain some of the language and terms used, their meaning and how they contribute to
When you work with computers, it’s impossible to avoid learning a bit of number representations. Computers work
with a different logic than humans do: humans have complex minds and thoughts, while most of the time computers
work in ones and zeroes. Most of what we see on a screen can be reduced to electrons going through a semiconductor
Here we will take a quick look at the most used representations. Some are more fundamental than others, but they
Each representation will use a subscript to represent its representation. If no subscript is present it means the
4.1.1.1 Decimal
This is the standard decimal notation everyone is used to, we have 10 digits at our disposal:
0123456789
And we place them in certain positions (units, tens, hundreds, thousands, etc…) to represent a certain quantity. We
So if you want to represent 9 + 1 you will use the 1 digit, followed by the 0 digit to make 10.
4.1.1.2 Binary
This is the most used representation in computer science, we have only two digits at our disposal: 0 1.
Thus if you want to make 1bin + 1bin , you will have to use the 1 digit, followed by the 0 digit, thus making 10bin ,
which is the binary representation of 2.
Decimal Binary
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
9 1001
10 1010
Binary numbers can be used at low level to represent any kind of “binary condition” too: yes/no, true/false are
usually mapped to 1 and 0 respectively. This will probe useful in some cases where we will use “binary numbers” to
represent groups of “binary conditions” in a compact way, but that’s an advanced thing we’ll see later.
4.1.1.3 Octal
01234567
Thus the representation of the decimal number 8 in the octal system is 10oct .
The octal number system doesn’t find much use in computer science besides being a quicker way to represent binary
Decimal Octal
0 0
1 1
2 2
3 3
Decimal Octal
4 4
5 5
6 6
7 7
8 10
9 11
10 12
4.1.1.4 Hexadecimal
Hexadecimal is definitely the second most used representation in computer science, due to how easy it is to represent
0123456789ABCDEF
Here’s a table of the first 20 numbers to clarify a bit how things work:
Decimal Hex
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 A
11 B
12 C
13 D
Decimal Hex
14 E
15 F
16 10
17 11
18 12
19 13
20 14
The algorithm to convert between decimal and binary is quite simple. It is an iterative algorithm that consists in
integer dividing the number by 2, until the result of the division is 1. The modulo of such divisions will make up our
binary number.
First of all, we integer divide 38 by two: the result is 19, there is no remainder, so we’ll use zero.
Dividend Remainder
38 0
19
Dividend Remainder
38 0
19 1
We iterate some more, by integer dividing until we get 1 as a dividend, at that point we make the last division, which
Dividend Remainder
38 0
19 1
9 1
Dividend Remainder
4 0
2 0
1 1
Now we just need to read our remainders from bottom to top. So the binary representation of 38dec is 100110bin .
Note!
This is actually a much more generic algorithm: you can convert from decimal to octal
and hexadecimal for instance, just by dividing by 8 and 16 respectively. You can convert
38 to octal and hexadecimal as an exercise: the results are 46oct and 26hex .
So far we’ve seen how to convert positive integers from decimal to binary, but how do we represent negative
integers?
That’s where “two’s complement” representation comes into play: there is a bunch of theory behind why it’s called
this way, and how it works, but what we need to know will be how to represent a negative number.
Let’s start with a simple example with 3 binary digits (this means we’re pretending our computer can process only
up to 3 bits):
Decimal Binary
-4 100
-3 101
-2 110
-1 111
0 000
1 001
2 010
3 011
As you can see, the most significant bit being set (that means having value of 1) is a telltale sign that a number
is negative. But there are some interesting features about two’s complement that make it a very nice method of
representing integers.
This is because it makes easier to implement hardware that does operations on such numbers. If we sum 3 and −3
in two’s complement we will obtain the following:
011
+ 101
1000
This may look completely wrong, but since our “computer” can only process up to 3 bits, the left-most bit will be
To represent a negative binary number in two’s complement you flip all the bits of such number, then add 1.
As usual, an example is worth a thousand words. We want to convert the number −38 into binary.
First of all we need to define what our range of numbers will be, so that we know how many bits we will use. This is
done because this range will be equally split between positive and negative numbers. In this example I will choose
a normal 8-bit representation, which can represent numbers spacing from -128 to 127.
The first step is to convert 38 to binary, which as we saw is 100110bin . We will pad this binary number to 8 bits,
Now we just need to invert the all the bits in the number, obtaining 11011001bin as a result.
Last step is adding 1 to what we got in the previous step, thus the final result is 11011010bin .
Note!
The more perceptive of you may have noticed a problem: what if we tried to represent
We would obtain 1000000bin which is actually the representation of -128 in two’s com-
plement. This is called an “integer overflow”, so be careful when mixing unsigned and
signed integers.
As mentioned before, octal can be used as a “shorthand way” to represent binary. The conversion is pretty simple.
To convert from binary to octal, take the binary digits in groups of 3 (with the necessary padding) and convert
100 110bin
100bin converts to 4oct , while 110bin converts to 6oct . If we stick them together we obtain the final result: 46oct .
Advanced Wizardry!
Gray code isn’t really used in game development, but it will be briefly explained here
Gray code (sometimes known as “reflected binary code”) is a particular ordering of the binary system where two
Gray code is used in many fields, from Digital (and cable) TV (for error-correction) to analog to digital conversion. In
Here is a simple representation of the first 10 numbers in decimal, binary and gray code:
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
If we want our algorithms to be smart enough to be useful, we have to deal with conditionals. That’s where logic
comes in. In this section we will take a quick look at truth tables as well as logic operations.
Truth tables are used to represent the output of a logic operation. It represents the inputs on the left side, while on
A B f
0 0 0
0 1 0
1 0 1
1 1 0
After we distinguish “true” (1) from “false” (0), we will need to start mixing and matching them (similarly to what
we do with numbers). That’s where operators come into play: they are a bit different than what we’re used to in
4.2.2.1 AND
The “AND” operator is a binary operator that outputs 1 when both inputs are 1. Here is its truth table:
A B AND
0 0 0
0 1 0
1 0 0
1 1 1
This operator is used to express conditionals where you want two conditions to be true at the same time.
4.2.2.2 OR
The “OR” operator (sometimes called “inclusive or”, as opposed to the XOR operator) is a binary operator that
outputs 1 when either of the inputs is 1, including the case when both are 1. Here is its truth table:
A B OR
0 0 0
0 1 1
1 0 1
A B OR
1 1 1
This operator is used to express conditionals where you want at least one condition to be true.
4.2.2.3 NOT
The “NOT” operator is a unary operator that takes a single input and “inverts” it. That means that if the input is 1,
the “NOT” operator will output 0, if the input is 0 the “NOT” operator will output 1 instead.
A NOT
0 1
1 0
4.2.2.4 XOR
The “XOR” operator (called “exclusive or”) is an operator that takes two input and outputs 1 when only one of the
two inputs is 1. If both inputs have the value 1, the “XOR” operator will output 0.
A B XOR
0 0 0
0 1 1
1 0 1
1 1 0
This operator is used when you want to express conditionals where only one of the two inputs is true.
Advanced Wizardry!
The confines between logic operations and bitwise operations can get blurry. This
to fit more data in less space. Feel free to skim over this section.
So far we’ve seen operations that work on single binary digits, which can be seen as the numeric representation of
logical statements (0 meaning “false” and 1 meaning “true”). These are logic operations.
Such operations can be applied on a bit-by-bit basis to groups of bits, that’s when we talk about about “bitwise
operations”.
0110 0010 AN D
0101 1010
0100 0010
As you can see the bitwise AND operation takes each bit of the two bytes and does an “AND” operation on each one
of them.
Let’s imagine the following situation: we have a structure that represents a tile in a maze. We want to efficiently
This can be solved by using a 4-bit positive integer and having each bit represent a side of the tile: if that bit is 1,
After creating a convention, we can start storing data. For instance we can have the bits representing walls starting
This means that 0110 represents a tile having two walls: on the right and bottom side (this is the integer number 6,
by the way). If we wanted to check if a certain tile has a wall, we would just need to AND it (bitwise) with the number
If the result of such operation is not zero, the wall we searched for is in our tile. Continuing with our example, if we
0110 AN D
0001
0000
But if we test for a bottom wall, we will obtain something that is not zero:
0110 AN D
0100
0100
De Morgan’s laws are fundamental in computer science as well as in any subject that involves propositional logic.
In symbols:
(A ∧ B) = Ā ∨ B̄
(A ∨ B) = Ā ∧ B̄
These laws allow us to express our own conditionals in different ways, allowing for more readability and maybe avoid
some boolean manipulation that can hinder the performance of our game.
4.3 Algorithms
When you talk about computer science, you always hear about algorithms: what is an algorithm?
An algorithm can be informally defined as a finite sequence (as in “not infinite”) of instructions that are followed to
Algorithms are usually represented in flow charts, or it’s more modern counterpart: the UML activity diagram. Some-
times algorithms can be represented in “plain language” (in that case we may end up talking about “pseudocode”)
or in a programming language.
4.4 Recursion
Starting from the (arguably hard) theme of recursion may seem weird, but it is important to understand recursion
Your first question will probably be: wouldn’t that make the program lock up forever in some kind of loop? It may.
But if you’re careful, recursion is an amazing tool that allows you to earn a lot of clarity and brevity.
Let’s imagine a simple algorithm: we want to make our program count backwards from a number n to 0. In a simple
Pretty simple, right? A real-world example would be counting back from 10 to 0: we print 10, we subtract 1 to get
Let’s turn our thinking around for a second. We can see counting back from to 10 to 0 like this: we print 10 and then
we count backwards from 9. Counting backwards from 9 would just mean printing 9 and then counting back from 8,
etc…
2 // Stop condition
3 i f (n == 0) {
7 }
8 // Procedure
• A base case (sometimes called a “stop condition”): this allows the function to stop calling itself when a certain
condition is reached;
• A procedure that elaborates on data or simply does something (in our example, it just prints the number);
• A recursive call to the same function we are writing, the call is done in a way that every call gets closer to
the “stop condition”. It can be done by calling the function on a subset of its argument (if it is a list), until the
list has only 1 item or on a smaller number (if the function argument is a number instead).
• By how the recursive call is made: direct (a function calls itself directly) vs indirect (a function A is called
I want to underline the last distinction: what we’ve seen in the previous listing is called “tail recursion”: the recursive
Head recursion is instead done when the recursive call is done before the procedure starts, so we can transform our
“count down” function to a “count up” just by switching from “tail” to “head” recursion and adding a print statement.
4 // Stop condition
5 i f (n == 0) {
9 }
10 // Recursive call
11 count_forwards (n -1) ;
12 // Procedure
13 std :: cout << n << std :: endl ;
14 }
Programming languages are a programmer’s way to talk to a computer (or a console): they are a way to make an
Programming languages can be distinguished by many traits, it is important to know such differences, even though
The way that a programming language gets you from code to “working product” can heavily influence both the final
Compiled languages need to go through a building process before it is possible for the product to be run anywhere.
Among the disadvantages we have that the final product is usually non-portable, that means it cannot be run any-
where besides the machine it was compiled for. This means that you will have to create separate builds for each
Another disadvantage can be development speed: before you can test anything your game needs to be rebuilt. Some-
times the rebuild process can be quick (thanks to some techniques that avoid building things that didn’t change),
A very strong advantage of compiled languages is speed. Being essentially compiled to machine code, compiled
languages have an easier time squeezing every last drop of performance from the platform you’re building for. In
addition, some languages can use features to physically remove unused code from the build: this way release builds
can be much faster than debug ones, because the debug code is physically removed.
Among compiled languages we can find C and C++, as well as Rust and Go.
Interpreted languages, in their strictest sense, are at the other side of the spectrum: the program is not compiled
ahead of time but instead the source code is fed into an interpreter, which executes each row of instructions, one
Most interpreted languages feature an interactive REPL[g] (read-eval-print loop) which allows to test code in real
time.
They have the disadvantage of being usually slower than compiled languages and it’s not easy to create builds
that physically remove unused (debug) code without having to modify the sources manually. Also each console or
operating system will need to have the interpreter installed, which may be an issue.
The advantage is in development speed: you can edit the source code and immediately run the interpreter to see
the result, without having to wait for a new build to complete. Another advantage is portability: you don’t need to
create a new build for every system you want to run your game in, as long as an interpreter is available your game
will run.
In any project, the ability to code quickly is as important as the performance of the final product: there is a thin
balance to strike between “having a product with good performance” and “having a product that is released when
needed”. If your product releases too late, it doesn’t matter how performing it is, the market will have chosen
another product. If your product releases early but it underperforms, it will be replaced by better products.
Thus some hybrid approaches have been invented: one of these is, for instance, bytecode-compiled languages.
Bytecode-compiled languages (sometimes called “Languages with intermediate representation”) are something that
is not quite compiled, but it’s not precisely interpreted either: the code is converted into bytecode, which is then
Being a representation that is “closer to the hardware” than the original source code, there is a gain in performance,
Random Trivia!
Some programming languages, like Haskell and Vala use the C programming language
language.
Other approaches include Just-In-Time compiling, which trades off some longer starting times (sometimes called
Among the bytecode-compiled languages we can find Java and Python, while Lua can be considered a Just-In-Time
4.5.1.2 By Paradigm
A programming paradigm is how the programming language lets you program. There is not a single, definitive way
Imperative languages are probably the most spread in modern programming: they make use of “orders” (called
This paradigm makes use of variables, statements, subroutines to make the program look like a set of instructions,
Functional languages make programs work by applying and composing functions (in the mathematical sense). Func-
tions can be bound to variables and chained together (composed) to reach the result.
Many programming languages tend to “meld together” many programming paradigms, allowing (for instance) for
This means that functions can be bound to variables and passed around as any other object, they can be composed
to reach the result if the programmer decides to do so (for instance for readability).
Sometimes underrated, how types are evaluated can completely change the way you program your game. Not
knowing precisely how your language of choice treats types can lead to hard-to-debug issues.
Statically typed languages have their types decided ahead of time (usually when the program is compiled) and
This means that you have to have full awareness of which types will be used while writing your game. Which can be
difficult at times.
Dynamically typed languages have their types decided at runtime. This allows for simpler syntax, but at the cost of
lower performance, due to the fact that types are determined and verified at runtime.
Duck typing is probably the most misunderstood typing system. It can be described by the following sentence:
If it walks like a duck and it quacks like a duck, then it must be a duck.
This means that types are inferred by their behaviour (their capabilities), thus creating a series of -like objects that
behave more or less the same. This means that types can make use of the iteration capabilities of the language as
long as they implement some basic methods that allow iteration (like nextElement() and length()).
This means that we have “file-like” objects, which behave like files, are used like files, but not necessarily have
a counterpart in mass storage (they could be in-memory files), or “iterables” (sometimes called “list-like”) which
behave like lists of items, but may actually be something else (for instance strings could be seen as a “list of letters”).
In the end, in duck typing, interfaces are treated as some kind of “informal protocol” that tells the language how
to use an object. The “protocol” doesn’t even need to be implemented fully: if you have a “file-like” object that
implements only the reading method, you can still use it in the same way you’d use a file, as long as you don’t try
to write to it.
How types are treated after each variable is instantiated can be the source of a lot of headaches while coding, thus
it is paramount to be aware of how strong your preferred language’s typing system is.
Strongly typed languages don’t allow one type to be treated like it was another type without an explicit conversion
(usually called “cast”). This prevents unforeseen automatic type conversions that may lead to bugs and faults being
Some examples of strongly typed languages are C++, C#, Python and Java.
Weak typed languages allow one type to be treated like another without explicit conversion. This may make the
For instance a string may be treated as it was a number, this means that in some languages (where the operator
+ means both “addition between numbers” and “joining strings together”) you may find that a result is a sum of
Random Trivia!
What about the good old C language? C has strong typing for the great majority of the
time, unless we consider the void* generic pointer. This kind of pointer can be used in
Another way to classify programming languages is how you can (or have to) manage your memory.
Some programming languages allow you to play with your system’s memory as you wish: they give you all the tools
This comes with its advantages and drawbacks: higher performance is surely a big advantage. A huge disadvan-
tage is the fact that memory management is completely manual: dangling pointers and unreachable memory are
Some other languages prefer taking away part of the control on memory to help avoiding the problems that non
Garbage-collected languages bring: there is something that cleans after you, which is the Garbage Collector.
The big disadvantage of this approach is that the garbage collector needs reference counting, CPU cycles to run,
Here is a quick rundown of how the languages used in the various editions of this book (excluding “pseudocode”,
• C++, a compiled programming language with strong static typing. It is multi-paradigm (although it was born
• JavaScript, an interpreted language (although some engines support Just-In-Time compiling), with weak dy-
namic typing that supports some duck typing principles. It is multi-paradigm and features a garbage collector.
• Lua, a bytecode-compiled (or Just-In-Time compiled) language, with strong dynamic typing that supports
• Python, a bytecode-compiled language, with strong duck typing. It is multi-paradigm and garbage-collected.
There are many differences between humans and computers, among those there is one that will keep haunting us
in our journey: humans make calculations in “base 10” (decimal), computers make calculation in “base 2” (binary).
This requires computers to represent numbers differently, usually with the exponent+fraction representation (IEEE
754). Also computers have limited resources, thus have no concept of “infinity” (and conversely of “infinitesimal”).
Let’s assume a computer with a fixed (and reduced) precision and we execute the following C++ program (you can
4 i n t main ()
5 {
6 // This will reduce and fix the computer 's precision for this execution
7 std :: cout << std :: setprecision (20) ;
8
9 f l o a t d1 (1.0) ;
10 std :: cout << " This should be 1.0: " << d1 << std :: endl ;
11
12 f l o a t d2 (0.1) ;
13 std :: cout << " This should be 0.1: " << d2 << std :: endl ;
14
15 f l o a t d3 (0.1*0.1) ;
16 std :: cout << " This should be 0.01: " << d3 << std :: endl ;
17
19 std :: cout << " This should be true (1) : " << x << std :: endl ;
20
21 r e t u r n 0;
22 }
We save it as “precision_test.cpp” and compile it with the following command line (on Linux):
This program will temporarily set a reduced precision in our number representation, and try to output the values of
the numbers 1, 0.1 and 0.12 = 0.01, let’s see the results:
With the number 1 it’s all good, but… what is going on with 0.1? What is all that garbage? The number 0.01 is even
worse! That’s not even close! Why 0.1 + 0.1 + 0.1 comes out as not 0.3! What is maths anymore?
We have just met one of the (many) limitations of computers: computers cannot represent certain numbers without
“approximating”. Compilers and libraries exist to work around these issues, but we need to be ready to avoid
surprises.
Just to reiterate: this is not a problem of the single programming language, we can see that C++ is affected, but
Figure 26: Python 2 has the same issues with precision as C++
Figure 27: Python 3 doesn’t fare much better when it comes to precision
This is a computer issue in general: this may not be a huge problem for general use but, if we try to be too precise
Advanced Wizardry!
Catastrophic cancellation is one of the many pitfalls that you may encounter when
dealing with very small numbers. This doesn’t happen really often in the world of
game development, feel free to just skim through this mostly informative section.
With a name as dangerous-sounding as “catastrophic cancellation”, this sure looks like a dangerous phenomenon,
Catastrophic Cancellation (sometimes called “cancellation error”) is an event that may happen when subtracting
two (usually large) numbers that are close to each other in value.
Warning: from here on, in this section, there will be some technical language. I will try to make it as simple and
understandable as possible.
Let’s imagine a computer, such computer’s memory can handle at most 8 decimals while its A.L.U.[g] (the unit that
x = 0.5654328749846 y = 0.5654328510104
When we transfer such numbers in our memory, the computer will approximate such numbers to fit in its memory
constraints. We’ll represent that by applying to each number a function f l() that we can read as “float representation
This is generally called an “assignment error”, where during the assignment to a variable, a number loses part of its
information.
Let’s try an calculate how off those approximations are (by calculating the percent “relative error”), just to get an
idea of what we lost by just loading the numbers on our “fake computer”:
|x − f l(x)|
δx = = 0.00000088%
x
|y − f l(y)|
δy = = 0.00000017%
y
We can see that our approximations are very close to the numbers we want to calculate, now let’s calculate x − y.
Making things by hand we would have:
x − y = 0.239772 × 10−7
That’s a tiny number right there. Now let’s calculate f l(x) − f l(y), remembering that the A.L.U. will fill up to 16
decimals:
We are off by 16% of the total result, this is actually really bad.
What happened? If you look closely, the numbers are really close and even have 7 decimal digits in common, since
our computer can memorize only 8 digits, the 9th to 13th decimal digits that looked so unimportant suddenly become
a huge part of the result (due to the subtraction) but are already lost.
Computers are deterministic machines, given the same set of instructions and inputs, they will always return the
same output. Someone may think about “random number generators” and sure, those programs look like they spit
The most important number when generating random numbers is called seed and it’s the number used by the
Let’s see an example of a random number generator in C++ (you can copy this program verbatim to try it):
2 i n t main () {
17 }
We can save this program as random_seed.cpp compile this program with the following command:
When we run the program, it will ask us to input a seed (which in our case is a number), after that it will just print
10 random numbers based on that seed. What would happen if we ran the program twice and use the same seed?
Figure 28: Running a random number generator with the same seed will always output the same numbers
Random numbers generated by computers are never truly random, that’s why they are more properly called “pseudo-
random numbers”.
From what we have seen earlier, the seed of our random number generator is something we need to be mindful
about.
Choosing a static seed will make our game completely deterministic (if played in the same conditions), like we didn’t
Some games use internal timers to see the random number generator, be it the time that the game has been running,
the time that has passed from the beginning of the mission or something similar. This allows you to have some kind
Some choices expose the game to the possibility of RNG manipulation: where the player has partial or total control
over the random number generator, by performing specific actions at specific times, for instance.
A very easy way to seed a generator is using the system time. Here’s a more advanced random number generator
that uses system time as its seed: if you run the program reasonably slow (not quicker than once a second) you will
Listing 11: A random number generation program that uses system time as seed
3 i n t main () {
18 }
We can save this program as rand.cpp compile this program with the following command:
This is the result of the program being run twice, one second apart:
Figure 29: Using the system time as RNG seed guarantees a degree of randomness
Now more than ever, you need to be able to be efficient. How do you know how “efficient” some piece of algorithm
is?
Seeing how much time it takes is not an option, computer specifications change from system to system, so we need
Ω() represents a lower bound: this means that the algorithm will take at least as many cycles as specified.
O() represents an upper bound: it’s the most used notation and means that the algorithm will take at most as
Θ() is a tight bound, used when the big-O notation and the big-Ω notation have the same value, which can help
define the behavior of the algorithm better.
We will now talk about the most common Big-O notations, from “most efficient” to “least efficient”.
Pitfall Warning!
Be mindful of one specific thing: these notations simply tie how the algorithm performs
in relation to how a certain variable grows (usually a dataset). If you know for certain
that a dataset stays relatively small, an algorithm with a “worse O() may not make a
4.8.1 O(1)
An algorithm that executes in O(1) is said to execute “in constant time”, which means that no matter how much
data is input in the algorithm, said algorithm will execute in the same time.
An example of a simple O(1) algorithm is an algorithm that, given a list of elements (with at least one element),
3 }
To be precise, this algorithm will perform both in O(1) and Ω(1), so it will perform in Θ(1).
4.8.2 O(log(n))
An algorithm that executes in O(log(n)) is said to execute in “logarithmic time”, which means that given an input of
An example of a O(log(n)) algorithm is the so-called “binary search” on a ordered list of items.
2 i n t first = 0;
4 bool found = f a l s e ;
9 // We found it !
10 r e t u r n midpoint ;
11 } else {
12 i f ( item < lst [ midpoint ]) {
24 }
25 }
The best case is the time when you get the element to find to be the “middle element” of the list, in that case the
algorithm will execute in linear time: Θ(1) - You need at least one lookup (Ω(1)) and at most one lookup (O(1)).
In the worst case, the element is not present in the list, so you have to split the list and find the middle element until
you realize that you don’t have any more elements to iterate - this translates into a tight bound of Θ(log2 n)
4.8.3 O(n)
An algorithm that executes in O(n) is said to execute in “linear time”, which means that given an input of n items,
An example of a simple O(n) algorithm is the one that prints a list, element by element.
It’s evident that this algorithm will call the print function n times, where n is the size of the list. This translates in a
There is no “best” or “worst” case here, the algorithm prints n elements, no matter their order, the alignment of
4.8.4 O(n·log(n))
An algorithm that executes in O(n·log(n)) executes in a time slightly longer than a linear algorithm, but it’s still con-
sidered “ideal”. These algorithms are said to execute in “quasi-linear”, “log-linear”, “super-linear” or “linearithmic”
time.
• Quick Sort
• Heap Sort
These algorithms are more complex than a simple example and would require a chapter on their own, so we’ll leave
4.8.5 O(n2 )
Quadratic algorithms, as the algorithms that execute in O(n2 ) are called, are the door to the “danger zone”.
These algorithms can eat your CPU time quite quickly, although they can still be used for small computations some-
what efficiently.
Given an input of n elements, these algorithms execute n2 cycles, which means that given an input of 20 elements,
A simple example of a quadratic algorithm is “bubble sort”. A pseudo-code implementation is written here.
2 n = A . size () ;
3 // Traverse Through all Elements
4 f o r ( i = 0; i < n; ++ i) {
9 i n t tmp = A[j ];
10 A[ j] = A[j +1];
11 A[ j +1] = tmp ;
12 }
13 }
14 }
15 }
4.8.6 O(2n )
Algorithms that execute in exponential time are considered a major code red, an will usually be replaced with heuristic
Given an input of 20 elements, an algorithm that executes in O(2n ) will execute 220 = 1 048 576 cycles!
When you estimate an algorithm, you usually want to calculate how it functions “in the worst case”, which usually
means that all loops get to their end (of the list or the counter) and everything takes the longest time possible.
This is a simple assignment operation, we are considering this instantaneous. So its complexity is O(1).
In this case we are iterating through a list, we can see that as the list grows, the number of times we print an element
on our screen grows too. So if the list is n items long, we will have n calls to the output statement. This is an O(n)
complexity algorithm.
Now let’s take something we already saw and analyze it: the bubble sort algorithm:
2 n = A . size () ;
3 // Traverse Through all Elements
4 f o r ( i = 0; i < n; ++ i) {
9 i n t tmp = A[j ];
10 A[ j] = A[j +1];
11 A[ j +1] = tmp ;
12 }
13 }
14 }
15 }
This will require a small effort on our part: we can see that there are 2 nested loops in this code. What’s our worst
When the items are in the reverse order, we will need to loop through the whole list to get the biggest item at the
end of the list, then another time to get the second-biggest item on the second-to-last place on the list… and so on.
So every time we bring an item to its place, we iterate through all the list once. This happens for each item.
So, in a list of length “n”, we bring the biggest item to its place “n times” and each “time” requires scanning “n”
There are times when we have code that looks like the following:
1 // -------------------------------------
2 // A is an array of integers
3 i n t n = A . size () ;
4 bool swapped = f a l s e ;
5 do {
6 swapped = f a l s e ;
7 f o r ( i = 0; i < n; ++ i) {
9 i n t tmp = A [i -1];
17 // -------------------------------------
18
As we can see the first part is the bubble sort algorithm, followed by iterating through the (now ordered) list, to print
its values.
We can calculate the total estimate as O(n2 ) + O(n) and that would be absolutely correct, but as the list grows,
the growth rate of O(n) is very minor if compared to O(n2 ), as can be seen from the following figure:
So we can drop the O(n) and consider the entire algorithm as an O(n2 ) algorithm in its entirety: this means that
when dealing with complexity estimates, you always keep the terms that have the largest “growth rate” (check the
An important problem with asymptotic complexity is that it tends to hide coefficients and smaller terms, no matter
Let’s take an example: we need to order a list of 500000 elements and we found two algorithms:
Which one would be more efficient? From a first inspection it may seem surprising that until we reach 1 million
If we plot how the CPU cycles behave for each algorithm, we can see how the reality is different.
1.6e+12
1000000n
n²
1.4e+12
1.2e+12
1e+12
8e+11
6e+11
4e+11
2e+11
0
0 200000 400000 600000 800000 1e+06 1.2e+06
Figure 31: When coefficients have important values, asymptotic complexity may trick us
When recursive algorithms are involved, things get a lot more complex, and they involve building recursion trees
and sometimes you’ll have to use the so-called “master theorem for divide-and-conquer recurrences”.
Here we can see how big-O estimates compare to each other, graphically and how important it is to write not-
inefficient algorithms.
If we had to write it as an inequality, from more to least efficient, we would have something like this (only considering
Big-O notation):
O(1) < O(log n) < O(n) < O(n · log n) < O(n2 ) < O(2n )
There is a very specific reason why the O(2n ) estimate is missing from the previous plot: we wouldn’t be able to
see anything worthwhile if it was included, as seen from the following plot:
Karnaugh maps are a useful tool to simplify boolean algebra expressions, as well as identifying and potentially solving
race conditions.
Table 23: The first truth table we’ll simplify with Karnaugh Maps
A B f
0 0 0
0 1 1
1 0 1
1 1 0
Said table can contain any number of variables (we’ll see how to implement those). To be precise, this table repre-
Let’s arrange it into a double-entry table, like this (Values of A are on top, values of B are on the left):
A
0 1
0 0 1
B
1 1 0
Now we have to identify the biggest squares or rectangles that contain 2n elements equal to 1 so that we can cover
all the “1” values we have (they can overlap). In this case we’re unlucky as we have only two small rectangles that
A
0 1
0 0 1
B
1 1 0
Figure 35: Karnaugh Map where the elements of the two “rectangles” have been marked green and red
In this case, we have the result we want with the following formula: f = (A ∧ B̄) ∨ (Ā ∧ B)
Not an improvement at all, but that’s because the example is a really simple one.
Karnaugh Maps show more usefulness when we have the so-called “don’t care”s, situations where we don’t care
A B f
0 0 0
0 1 1
1 0 1
1 1 x
Putting this truth table into a Karnaugh map we get something a bit more interesting:
A
0 1
0 0 1
B
1 1 x
Now we have a value that behaves a bit like a “wild card”, that means we can pretend it’s either a 0 or 1, depending
on the situation. In this example we’ll pretend it’s a 1, because it’s the value that will give us the biggest “rectangles”.
A
0 1
0 0 1
B
1 1 1
Figure 37: Karnaugh Map where we pretend the “don’t care” value is equal to 1
A
0 1
0 0 1
B
1 1 1
In this case, we can see that the result is 1 when B = 1, no matter the value of A. We’ll keep this in mind.
A
0 1
0 0 1
B
1 1 1
In this case, we can see that the result is 1 when A = 1, no matter the value of B.
This translates into a formula of: f = (A) ∨ (B), considering that we don’t care about the result that comes out
when A = 1 and B = 1.
Note!
If instead of 1, we ended up choosing 0 for our “don’t care”, we would have obtained
f = (A ∧ B̄) ∨ (Ā ∧ B) (the extended form of A XOR B , which we saw earlier). For
A B C D f
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 x
Now we’ll have to group up our variables and put them in a Karnaugh Map using Gray Code, practically each row or
AB
00 01 11 10
00 0 0 1 1
01 0 0 1 1
CD
11 0 0 x 1
10 0 1 1 1
We can see two rectangles that contain 2n items, one with 2 items, the other with 8, considering the only “don’t
care” value as 1.
AB
00 01 11 10
00 0 0 1 1
01 0 0 1 1
CD
11 0 0 x 1
10 0 1 1 1
In this first rectangle, we can see that the values of C and D don’t matter towards the result, as well as the value of
B. The only variable that gives the result on this rectangle is A = 1. We’ll keep that in mind
AB
00 01 11 10
00 0 0 1 1
01 0 0 1 1
CD
11 0 0 x 1
10 0 1 1 1
In this case A doesn’t give any contribution to the result, but at the same time we need B = 1, C = 1 and D = 0
to get the wanted result.
If we didn’t have that “don’t care” value, everything would have been more complex.
Let’s remove the “don’t care” value and have the following truth table:
A B C D f
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
AB
00 01 11 10
00 0 0 1 1
01 0 0 1 1
CD
11 0 0 0 1
10 0 1 1 1
AB
00 01 11 10
00 0 0 1 1
01 0 0 1 1
CD
11 0 0 0 1
10 0 1 1 1
AB
00 01 11 10
00 0 0 1 1
01 0 0 1 1
CD
11 0 0 0 1
10 0 1 1 1
AB
00 01 11 10
00 0 0 1 1
01 0 0 1 1
CD
11 0 0 0 1
10 0 1 1 1
4.11.1 Introduction
One of the biggest programming paradigms in use is surely the “Object Oriented Programming” (from now on:
“O.O.P.”) paradigm. The fundamental unit of a program, in this paradigm is the Object. This paradigm allows to
structure your code in a more modular and re-usable way, as well as implementing abstractions, allowing for more
solid code and making it possible for other code to make use of your own code without needing to know any details
4.11.2 Objects
Objects are the fundamental unit in O.O.P., objects are essentially a collection of data and functions. Objects are
To simplify the concept: a “Class” is a house blueprint, an “Object” is the house itself.
Objects contain data and functions, for the sake of precision, we will use their technical names:
• Functions that are part of an object are called methods and they can be classified as:
– Static Methods when they don’t (usually they’re utility functions), that also means that these methods
• Each piece of data contained in the class is called a Field and they can be classified as:
– Instance Fields when they’re part of the instance and can change from instance to instance;
– Static Fields when they’re part of the class but don’t change between instances (Caution: it does not
mean they cannot change, in that case the change will snowball into all the instances).
Abstraction is a fundamental point in O.O.P., and it is usually taken care of via so-called Interfaces.
Interfaces are the front-end that an object offers to other objects so they can interact.
As an example: the interface to your PC is given by Keyboard, Mouse and Screen - you don’t need to know how
the single electron travels through the circuits to be able to use a computer; same goes for a class that offers a
well-abstracted interface.
Being able to abstract a concept, removing the necessity to know the internal workings of the code that is used,
is fundamental to be able to write solid and maintainable code, because implementations change, but interfaces
rarely do.
Making classes work together with interfaces allows you to modify and optimize your code without having each edit
snowball into a flurry of compiler (or interpreter) errors. For instance: a rectangle class exposes in its interface a
method getArea() - you don’t need to know how to calculate the area, you just call that method and know it will return
The concept of keeping the internal workings of a class is called Information Hiding.
One of the biggest aspects of O.O.P. is inheritance: you can create other classes based on a so-called “base class”,
You can create a “Person” class, with a name, surname and age as fields, and by inheriting from the “Person” class
you can create a “Student” class, which has all the fields from Person, plus the “clubs” and “grade” fields.
This allows to create a “tree of classes” that represents part of your software.
From inheritance, O.O.P. presents a concept called Polymorphism (From “Poly” - Many, “Morph” - Shape), where
you can use the base class to represent the entire class tree, allowing for substitution.
In our “Person-Student” example, you could use a pointer to either a Person or a Student for the sake of getting their
first name.
In some languages it is possible for an object to inherit from multiple other objects, this is called “Multiple Inheritance”
4.11.5 Mixins
Mixins are classes that contain certain methods that are made to be used by other classes. We can see mixins as
Mixins encourage the reuse of code (since the common functionalities get separated into their own classes), allowing
for some interesting mechanisms and enforcing the Dependency Inversion principle.
Many times, Mixins are described as “included” rather than “inherited”, due to their nature.
Random Trivia!
The python web framework Django makes heavy use of mixins in its class-based views:
you can create a standard “View” (representing a web page, for instance), and then add
A code example of mixins is beyond the scope of this book, since each language has its own way of implementing
mixins, some easy (like Python), other a bit more complex (like C++, see “Curiously Recurring Template Patterns”,
or C.R.T.P.).
Usually when you call a method that is not present in the object itself, the program will look through the object’s
parents for the method to execute. This usually works well when there is no ambiguity. What if there is ambiguity
instead?
When multiple inheritance is involved, there is a serious possibility of a situation similar to the following
doStuff()
C B
doStuff() doStuff()
In this example, class A implements a method dostuff() that is overrode by both classes B and C (which inherit from
A): now class D inherits from both B and C but does not override dostuff(), which one will be chosen?
This is the reason many languages do not implement multiple inheritance between classes (like Java, which allows
multiple inheritance only between interfaces), other implement the so-called “virtual inheritance” (C++) and others
This is not something you usually need to worry about, but you may want to be careful when you structure your
4.11.7 Composition
As opposed to inheritance’s “IS-A” relationship, composition makes use of a “HAS-A” type of relationship.
Composition allows to define objects by declaring which properties they have: a player character can be a sprite
This way we can create new objects by reusing basic components, making maintenance easier as well as saving
Let’s be clear right from the get go: there is no “silver bullet” here. Composition and inheritance target different
problems (IS-A vs. HAS-A relationships). Inheritance binds classes closely, while composition tends to induce less
Let’s make an example of inheritance: we have a “Shape” base class, from where we create two new classes:
Rectangle and Circle. For the purposes of our usage (which will be getting perimeter and area), Rectangle IS-A
1 c l a s s Shape {
7 };
8
9 c l a s s Rectangle : p u b l i c Shape {
12 f l o a t height ;
13
14 Rectangle ( f l o a t w , f l o a t h){
15 width = w;
16 height = h;
17 }
18
19 f l o a t area () {
22 }
23
24 f l o a t perimeter () {
27 }
28 };
29
30 c l a s s Circle : p u b l i c Shape {
33
34 Circle ( f l o a t r) {
35 radius = r;
36 }
37
38 f l o a t area () {
41 }
42
43 f l o a t perimeter () {
46 }
47 };
Let’s continue with another example: we have a Coffee machine, such coffee machine HAS-A grinder, as well as
brewing unit. We can express such relationships with composition and build our coffee machine from our compo-
nents.
3 c l a s s Grinder {
11 c l a s s BrewingUnit {
19 c l a s s CoffeeMachine {
24 void make_coffee () {
25 // Uses the brewing component and the grinder to make some fresh coffee
26 grinder . grind () ;
27 brewer . brew () ;
28 std :: cout << " Here 's your fresh coffee !" << std :: endl ;
29 }
30 };
Often cited in programming, the “composition over inheritance” design states that code reuse and polymorphism
should be achieved using composition as the preferred method, while leaving subclassing (inheritance) alone as
much as possible.
This allows for easier code reuse, as well as more flexibility and less coupling. Let’s make a simple example.
Note!
If you’re having trouble understanding the diagrams that follow, head to the Reading
Let’s imagine a physical object that can be Visible/Invisible, Solid/NonSolid and Movable/Immovable. In UML, an
Object
input();
update(dt);
draw();
collide();
If we think of some objects, like a playable character, or a building, things get a lot more complicated: a playable
character is movable, solid and visible, while the building is not movable. Things can get ugly really fast.
Object
input();
update(dt);
draw();
collide();
Building PlayableCharacter
Using composition, we can separate the behaviours into the “Visible”, “Updatable” and “Movable” components and
Implementations
Interfaces
Objects
PlayableCharacter Building
4.11.10 Coupling
Coupling is a term used to define the phenomenon where an edit to some part of a software snowballs into a bunch
of edits in parts of the software that depend on the modified part, and the part that depend on the previously edited
dependency, etc…
The parts involved are defined as “coupled” because, even though they are separated, their maintenance very much
behaves like they were a single entity. This also means that the elements that are coupled are harder to reuse, since
they are so tightly related that they end up serving each other and nothing else.
Introducing unnecessary coupling in our software will come back to bite us in the future, affecting maintainability in
a very negative way, since any edit we make (for instance, to fix a bug) can potentially lead to the need to edit the
Reducing coupling is done by reducing interdependence, coordination and information flow between elements of a
program.
• A module uses code of another module (this breaks the principle of information hiding[g] );
• A module controls the flow of another module (like passing a parameter that decides “what to do”);
• Subclassing.
This means that it’s in our best interest to reduce code coupling as much as possible, following the good principles
Note!
We may be tempted to try and “remove coupling completely”, but that’s usually a
wasted effort. We want to reduce coupling as much as possible and instead improve
the key.
DRY is a mnemonic acronym that stands for “Don’t Repeat Yourself” and condenses in itself the principle of reducing
This allows for each piece of code (and knowledge, since the DRY principle applies to documentation too) to be
Violations of the DRY principle are called “WET” (Write Everything Twice) solutions, which base themselves on
SOLID is a mnemonic acronym that condenses five principles of good design, to make code and software that is
• Single Responsibility: Each class should have a single responsibility, it should take care of one part of
the software specification and each change to said specification should affect only said class. This means
you should avoid the so-called “God Classes”, classes that take care of too much, know too much about the
• Open-closed Principle: Each software entity should be open to extension, but closed for modification. This
means that each class (for instance) should be extensible, either via inheritance or composition, but it should
not be possible to modify the class’s code. This is practically enforcing Information Hiding.
• Liskov Substitution Principle: Objects in a program should be replaceable with instances of their subtypes
and the correctness of the program should not be affected. This is the base of inheritance and polimorphism,
if by substituting a base class with one of its children (which should have a Child-is-a-Base relationship, for
instance “Circle is a shape”) the program is not correct anymore, either something is wrong with the program,
• Interface Segregation: Classes should provide many specific interfaces instead of one general-purpose
interface, this means that no client should depend on methods that it doesn’t use. This makes the software
• Dependency Inversion: Software components should depend on abstractions and not concretions. This is
another staple of nutshell programming and O.O.P. - Each class should make use of some other class’s interface,
not its inner workings. This allows for maintainability and easier update and change of code, without having
Sometimes it can be useful to design your entities as data, instead of making them into static objects that possibly
Designing your objects as data allows you to use configuration files to create, configure, tinker and extend your
product, as well as allow for modifications by people who are fans of your game.
For instance, in a fantasy RPG you could have 3 types of enemies all defined as classes:
• Skeleton
• Zombie
• Ghost Swordsman
Which all have the same behavior but different animations and sprites.
These classes can inherit from an “entity” abstract class which defines the base behavior and then can be extended
Another idea could be designing an “entity” class that can be instantiated, and have a configuration file that defines
1 entity :
2 name : skeleton
3 health : 10
4 damage_on_hit : 2.5
5 spritesheet : "./ skelly . png "
6 animations :
7 walking :
8 start_sprite : 4
9 frame_no : 4
10 duration : 0.2
11 attacking :
12 start_sprite : 9
13 frame_no : 2
14 duration : 0.1
Another often used alternative is JSON, which would look like this:
1 {
2 " entity ": {
3 " name ": " skeleton ",
4 " health ": 10 ,
5 " damage_on_hit ": 2.5 ,
With more complex building algorithms, it is possible to change behaviors and much more with just a configuration
file, and this gives itself well to rogue-like games, which random selection of enemies can benefit from an extension
of the enemy pool. In fact, it’s really easy to configure a new type of enemy and have it work inside the game without
recompiling anything.
UML (Universal Modeling Language) is a set of graphical tools that allow a team to better organize and plan a software
product. Diagrams are drawn in such a way to give the reader an overall assessment of the situation described while
• Class Diagrams
• Activity Diagrams
• Sequence Diagrams
Use Case Diagrams are usually used in software engineering to gather requirements for the software that will come
to exist. In the world of game development, use case diagrams can prove useful to have an “outside view” of our
game, and understand how an user can interact with our game.
GameMenu
Player
Open the Credits Screen
Exit to Desktop
4.13.1.1 Actors
Actors are any entity that can interface with our system (in this case, our game) without being part of it. Actors can
Actors are represented with a stick figure and can inherit from each other: this will create an “IS-A” relationship
between actors.
Ultimate User
Authenticated User
In the previous example, we can see that a “Free User” is an “Authenticated User”, as well as a “Power User” (which
could be a paying user) is itself an “Authenticated User” while an “Ultimate User” (which could be a higher tier
of paying user) is a “Power User” (thus has all the “Power User” capabilities, plus some unique) and by transitive
As seen, inheritance between actors is represented with a solid line with a hollow closed arrow. Such arrow points
towards the “super-type” or “parent” from which the subject (or “sub-type”, or “child”) inherits.
This representation will come back in the UML language for other diagrams too.
Use cases represent the functionalities that our system offers, and the relationships between them.
Use cases are represented with an ellipse with the name of the use case inside. Choosing the right name for a use
case is extremely important, since they will represent the functionality that will be developed in our game.
4.13.1.2.1 Inheritance
As with many other elements used in UML, use cases can inherit from each other. Inheritance (also called “General-
ization”) is represented with a closed hollow arrow that points towards the parent use case.
Player
Website
Search By Name
Search
Search By Category
Search By Tag
4.13.1.2.2 Extensions
Use case extensions specify how and when optional behavior takes place. Extended use cases are meaningful
on their own and are independent from the extending use case, while the extending use case define the optional
Extensions are represented via a dashed line with an open arrow on the end, labeled with the <<extend>> keyword,
System
«extend»
Login Help on Login
User
4.13.1.2.3 Inclusions
Inclusions specify how the behavior of the included use case is inserted in the behavior of the including use case.
Inclusions are usually used to simplify large use cases by splitting them or extract common behaviors of two or more
use cases.
Inclusions are represented via a dashed line with an open arrow on the end, labeled with the <<include>> pointing
User
System
«include» Deposit
Customer Authentication
«include»
Withdraw
4.13.1.3 Notes
In use case diagrams, as well as in many other UML diagrams, notes are used to jot down conditions, comments and
everything useful to better understanding the diagram that cannot be conveyed through a well definite structure
inside of UML.
Notes are shaped like a sheet of paper with a folded corner and are usually connected to the diagram with a dashed
line. Each note can be connected to more than one piece of the diagram.
You can see a note at the beginning of this chapter, in the use case diagram explanation.
Use cases can be further detailed by creating sub-use cases, like the following example.
Checkout
Checkout
«include»
Payment
Clerk
4.13.2.1 Classes
Class diagrams are used a step after analyzing your game, since they are used for planning classes. The central
ClassName
privateVariableType privateVariable
AbstractClassName
publicMethodName()
protectedMethodName() publicAbstractMethodName()
privateMethodName()
publicStaticMethod()
Classes are made up by a class name, which is shown on top of the class; abstract classes are shown with a name
in italics.
Public members are highlighted by a “+” symbol (or in our case, a green symbol) before their name, protected
members use a “#” symbol (or a yellow symbol) and private members use a “-” symbol.
Static members are shown with an underlined name, while abstract members are shown in italics.
4.13.2.2 Interfaces
Sometimes there is a need to convey the concept of “interface” inside a UML class diagram, that can easily be done
in 2 ways:
• By using the class construct, with the keyword (called “stereotype”) <<interface>> written on top of it;
«interface»
SearchInterface
SearchProvider
SearchInterface
SearchProvider
Expressing only single classes on their own doesn’t give UML a lot of expressive power when it comes to planning
your games. Here we’ll take a quick look at the most used relationships between classes.
4.13.2.3.1 Inheritance
Inheritance is represented via a hollow closed arrow head that points towards the base class (exactly like in Actor
inheritance), this means that the classes are in a “super-type and sub-type” relationship.
Person
name: string
age: int
Student
grades: list
getGPA()
In this example we say that “Student IS-A Person” and inherits all Person’s methods and fields.
Interface realization can be complex to understand at first, given its formal definition:
The interface realization relationship specifies that the realizing class must conform to the contract that the
In short, it means that the class is implementing all the methods specified by the interface (thus “realizing” it, as in
making it real).
ConcreteClass
doStuff()
4.13.2.3.3 Association
Association represents a static relationship between two classes. This is usually represented with a solid line with
an arrow. The arrow usually shows the reading order of the association, so if you see an “Author” class and a “Book”
class, the “wrote” association will be pointing from the “Author” to the “Book” class.
In case the relationship is bi-directional, the arrow points are omitted, leaving only a solid line between the two
classes.
Person
name: string
age: int
0..*
subscriber
0..*
Magazine
title: string
An example of an association is the relationship between a “Person” and a “Magazine”, such relationship is the
“Subscription”. In this case the relationship is bi-directional, since a “Magazine” can be subscribed by many people,
Aggregation is a special case of the association relationship, and represents a more specific case of it. Aggregation
Aggregation is represented with a hollow diamond and a line that points to the contained class, classes involved in
an aggregation relationships do not have their life cycles dependent one another, that means that if the container
is destroyed, the contained objects will keep on living. An example could be a teacher and their students, if the
Teacher
University
name: string
name: string
age: int
Student
UniversityDepartment
name: string
name: string
age: int
Composition is represented with a filled diamond instead than a hollow one, in this case there is a life cycle de-
pendency, so when the container is destroyed the contents are destroyed too. Like when a university is dissolved,
its departments will cease to exist. Conversely, a teacher may have some students under their wing, but when a
teacher remains without students they won’t magically disappear: the teacher’s life cycle is independent from their
students’.
4.13.2.3.5 Dependency
The dependency relationship is the one that gives us the least amount of coupling, it represents a “supplier-client”
relationships, where the supplier supplies its functions (methods) to the client. The association is represented in a
dashed line with an open arrow that points towards the supplier.
This means that the client class requires, needs or depends on the supplier.
There are many categories of dependency, like <<create> or <<call>> that explain further the type of dependency
An example could be between a “Car Factory” and a class “Car”: the “CarFactory” class depends on the “Car” class,
CarFactory
Car
4.13.2.4 Notes
As with Use Case diagrams, class diagrams can make use of notes too, and the graphical language used to represent
them is exactly the same one used in the Use Case Diagrams.
Activity diagrams are the more powerful version of flow charts: they represent the flux of an activity in detail, allowing
Take Item
yes
More Items in Shopping List?
no
Go to checkout
Pay
Each diagram begins what a “start node”, represented with a filled black circle, and they end with an “end node”
4.13.3.2 Actions
Each action taken by the software is represented in the diagram via a rounded rectangle, a very short description of
Decisions and loops are enclosed in diamonds. If a condition needs to be written, the diamond can become an
hexagon, to make space for the condition to be written or guards can be used to express the condition.
yes no
number bigger than 0
Get input
[Wrong number]
[Right number]
You won
All the branches that depend on a condition start on the condition itself and end on a diamond, as shown below.
Read cell
yes
cell is even
Figure 72: Example of how nested loops and conditions are performed
Note!
Sometimes loops can make use of empty diamonds (called “merges”) to make the
diagram clearer.
4.13.3.4 Synchronization
Synchronization (or parallel processing) is represented in activity diagrams by using filled black bars that enclose
the concurrent processes: the bars are called “synchronization points” or “forks” and “joins”
Take Order
In the previous example, the activities “Send Order Confirmation” and “Process Order” are processed in parallel,
independently from each other, the first activity that finishes will wait until the other activity finishes before entering
4.13.3.5 Swimlanes
Swimlanes are a way to organize and group related activities in columns. For instance a shopping activity diagram
can have the “Customer”, “Order”, “Accounting” and “Shipping” swimlanes, each of which contains activities related
Place Order
Take Order
Process Order
Record Shipping
Ship Order
Receive Order
Pay Bill
Close Order
4.13.3.6 Signals
Signals are used to represent how activities can be influenced or modified from outside the system. There are two
The “Sent Signal” symbol is represented with a convex pentagon (which reminds an arrow going away from our
system), while the “Received Signal” is represented by a concave pentagon (which reminds a “slot” where the “sent
Customer Store
Search product
Place Order
Accept Order
Deliver Products
Deliverer rings
Confirm Receipt
4.13.3.7 Notes
As with Use Case and Class diagrams, Activity Diagrams can make use of notes, in the same way as the other two
Take Shopping cart Make sure the shopping cart works well!
Take Item
yes
More Items in Shopping List?
no
Go to checkout
Pay
The components of activity diagrams shown here are just a small part of the used components, but they should be
enough to get you started designing and reading most of the activity diagrams that exist.
Sequence diagrams are used to represents how objects (called “participants”) interact with each other and such
4.13.4.1 Lifelines
The central concept of sequence diagrams are lifelines: the represent the time a participant is “alive” and when it
is doing something.
WebServer
Request
Response
WebServer
The time flows from top to bottom, a dashed line represents the participant exists (for instance an object is instan-
tiated in memory), while the rectangle that replaces the dotted line represents the participant being “active” (for
4.13.4.1.1 Participants
The participants don’t have to be actual classes, since sequence diagrams represent interactions at a “higher level”
Some UML drawing software allows for custom shapes for each participant, like the following:
4.13.4.2 Messages
Each object (represented by a lifeline) communicates with other objects (and the “outside”) through “messages”.
Found Message
Synchronous Message
Asynchronous Message
Self-message
Return
Lost Message
• Found Messages are messages that come from “outside”, from the perspective of the part of the system we
are analyzing, they may come from another system or even the user.
• Synchronous Messages and returns are messages that activate a class and wait for a “return message”.
These usually represent a synchronous function call (but it can represent a more abstract concept).
• Asynchronous Messages are messages that activate a class but don’t wait for a return value. These usually
• Self-messages are messages from an object to itself, they usually represent an internal function call.
• Lost Messages are messages sent towards the “outside”, from the perspective of the part of the system we
are analyzing.
Sometimes it may be useful to represent the instantiation and destruction of objects in a sequence diagram. UML
provides such facilities via the <<instantiate>>, <<create>> and <<destroy>> keywords, as well as a symbol for the de-
struction of an object.
Class_1
<<instantiate>> Class_2
doStuff()
result
<<destroy>>
Class_1 Class_2
From time to time, we may need to represent a series of messages being sent in parallel, a loop, or just group some
messages to represent them in a clearer manner. This is where grouping comes of use: it has a representation based
Monte_Carlo_Calculator Input_Generator
User
compute()
generate_input()
result
result
User
Monte_Carlo_Calculator Input_Generator
4.13.4.5 Notes
Like all UML diagrams, it is possible to use notes to add some comments that may be useful for the interpretation
Class_1 Class_2
doStuff()
result
This is a note.
Class_1 Class_2
UML is composed by a ton of diagrams that can be used to communicate with your teammates and organize your
• Component Diagrams;
• Communication Diagrams;
• Deployment Diagrams;
• Package Diagrams;
• Profile Diagrams;
• State Diagrams;
• Timing Diagrams.
In this chapter we just saw the ones that will help you the most when reading the rest of this book, as well as
Sometimes it may be necessary (mostly in the case of containers) to have the same kind of code to work on different
data types, which means that we need to abstract types into variables and be able to code accounting for such
types.
Generic Programming is a blanket-term that defines a style of computer programming where algorithms are
written in terms of “to be specified later” data types, this usually applies to languages that make use of static
typing[g] .
This section is dedicated to give some basic explanation of some advanced containers that are used in computer
science, allowing us to make an informed choice when we want to implement some even more advanced containers
in the future.
We will include big-O performance counters for the basic functions of: adding/removing and item at the beginning,
adding/removing an item at the end, adding/removing an item in an arbitrary position and indexing at a certain
position.
This section is in no way exhaustive, but should be enough to make an informed decision on what containers to use
Note!
This section will be purely theoretical and no code will be shown for any container, this
In many languages, arrays are sized statically, with a size decided at compile time. This severely limits the array’s
usefulness.
Dynamic Arrays are a wrapper around arrays, allowing it to extend its size when needed. This usually entails some
Dynamic_Array
Capacity: 4
Filled: 3
Native_array
123
Inserting an item at the beginning is a heavy task, since it requires either moving all the present items or rebuilding
the internal native array. Such operations require copying or moving each element, giving us a time complexity
averaging on O(n).
0 12 0 12 012
Inserting an item at the end, if we keep a pointer to the last item inserted, is an operation that usually happens
immediately (time complexity O(1)), but when the array is full, we need to instantiate a new native array (usually
double the size of the current one) and copy all elements inside the new array (operation that has time complexity
of O(n)). Since the number of O(1) operations outweighs by a long shot the number of O(n) operations, it’s possible to
demonstrate that in the long run appending an item at the end of a dynamic array has a time complexity averaging
around O(1).
Dynamic_Array Dynamic_Array
The array is full, doubling needed Doubling the size of the array
Capacity: 4 Capacity: 8
Filled: 4 Filled: 0
Native_array Native_array
1234
0 0
Dynamic_Array Dynamic_Array
Capacity: 8 Capacity: 8
Filled: 4 Filled: 5
Native_array Native_array
1234 1234
0 0
Value to Insert
Inserting an item in an arbitrary position, much like inserting an item at the beginning requires moving some items
further into the array, potentially all of them (when the arbitrary position is the beginning of the array), thus giving us
a time complexity of O(n). Such operation could trigger an array resize, which has no real influence on the estimate.
12 12 12 0
0 0
Some implementations of the Dynamic Arrays try to save space when the number of items goes lower than 1
4 of the
array capacity during a deletion, the internal array is rebuilt with half the size. Such operation has a time complexity
of O(n).
Note!
Not all programming languages have native support for arrays, for instance Python
normally uses lists (although it supports arrays via the array standard library).
Indexing O(1)
When To Use it All situations that require direct indexing of a container, but insertions and
removals are not extremely common, and usually take the form of “push back”
Advantages Direct Indexing, Fast iteration through all the elements, given by the fact that
Disadvantages Slow insertions in arbitrary positions and at the head of the array.
Linked Lists are a data structure composed by “nodes”, each node contains data and a reference to the next node in
the linked list. Differently from arrays, nodes may not be contiguous in memory, which makes indexing problematic.
Linked_List
Head
Some implementations feature a pointer to the last element of the list, to make appending items at the end easier
and quicker.
Linked_List
Tail
Head
Since we only have a handler on the first node, indexing requires us to scan all the elements until we reach the one
that was asked for. This operation has a potential time complexity of O(n).
Inserting an item at the beginning is immediate, we just need to create a new node, make it point at the current
head of the list and then update our “handle” to point at the newly created node. The number of operations is
independent of how many data we already have, so the time complexity is O(1).
0 Data Next Data Next Data Next Data Next Data Next Data Next Data Next Data Next Data Next
Data Next
Temporary Variable
Appending an item at the end has a time complexity that varies depending on the chosen implementation: if the
list has a reference to the final node, we just need to create a new node, update the final node’s reference (usually
called “next”) to point at the new node and then update the reference to the final node to point at the newly created
node (time complexity O(1)). If our queue doesn’t have such reference, we will need to scan the whole list to find
Linked_List Linked_List
Tail Tail
Head Head
0 Data Next Data Next Data Next Data Next Data Next Data Next Data Next
Data Next
Figure 90: Inserting a new node at the end of a (double-ended) linked list
Inserting at an arbitrary position requires us to scan the list until we find the position that we want, after that we
just need to split and rebuild the references correctly, which is a fast operation.
Linked_List Linked_List
Linked_List 0 0
Tail Tail
Tail Head
Head Data Next Head Data Next
Data Next Data Next Data Next Data Next Data Next Data Next
0 Data Next Data Next Data Next
Data Next
Temporary Variable
Figure 91: Inserting a new node at an arbitrary position in a (double-ended) linked list
Indexing O(n)
When To Use it All situations that require quick insertions/removals, either on the head or the tail
Advantages Very fast insertions/removals, quite fast iteration through all the elements.
A doubly-linked list is a variation of a linked list where each node not only has a reference to its successor, but
also a reference to its predecessor. This allows for easy processing of the list in reverse, without having to create
All the operations of insertion, indexing and deletion are performed in a similar fashion to the classic singly-linked
Linked_List
Tail
Head
Indexing O(n)
When To Use it All situations that require quick insertions/removals, either on the head or the tail
Advantages Very fast insertions/removals, quite fast iteration through all the elements.
Hash Tables are a good way to store unordered data that can be referred by a “key”. These structures have
The idea behind a hash map is having a key subject to a hash function[g] that will decide where the item will be
Value
Hash Function
0 5
4 7
Figure 93: Hash Table Reference Image (Hash Table with Buckets)
The simplest way to implement a hash table is using an “array with buckets”: an array where each cell has a reference
to a linked list.
On average, finding an item requires passing the key through the hash function, such hash function will tell us where
the item is in our internal structure immediately. Thus giving a time complexity of O(1).
Inserting has more or less the same performance, the key gets worked through the hash function, deciding which
Deletion works in the same fashion, passing the key through the hash function and then deleting the value; giving
Searching O(1)
Insert O(1)
Delete O(1)
When To Use it All situations that require accessing an element by a well-defined key quickly.
Advantages Fast insertions/removals, direct indexing (in absence of hash collisions) by key.
Disadvantages In case of a bad hashing function, it reverts to the performance of a linked list,
cannot be ordered.
Binary search trees, sometimes called “ordered trees” are a container that have an “order relation” between their
own elements.
15
10 25
8 11 30
The order relation allows us to have a tree that is able to distinguish between “bigger” and “smaller” values, thus
making search really fast at the price of a tiny slowdown in insertion and deletion.
Searching in a BST is easy, starting from the root, we check if the current node is the searched value; if it isn’t we
If the searched value is greater, we search on the right child. If it is smaller, we continue our search on the left child.
Recursively executing this algorithm will lead us to find the node, if present. Such algorithm has a O(log(n)) time
complexity.
In a similar fashion, insertion will recursively check subtrees until the right spot of the value is found. The insertion
Deletion is a bit more conceptually complex, since it’s necessary to maintain the ordering of the nodes. Such
Searching O(log(n))
Insert O(log(n))
Delete O(log(n))
When To Use it Situations that require good overall performance and requires fast search times.
Advantages Good insertion and removal times, searching on this structure is fast.
Disadvantages Given the nature of the data structure, there is no direct indexing, nor ordering.
4.15.6 Heaps
Heaps are a tree-based data structure where we struggle to keep a so-called “heap property”. The heap property
• Max-Heap: For each node N and its parent node P, we’ll always have that the value of P is always greater or
• Min-Heap: For each node N and its parent node P, we’ll always have that the value of P is always less or equal
33
34
35
Left Data Right Left Data Right Left Data Right Left Data Right
39 51 49 58
Heaps are one of the maximally efficient implementation of priority queues, since the highest (or lowest) priority
When To Use it All situations where you require to find and/or extract the minimum or maximum
Advantages Good general time complexity, maximum performance when used as priority
queues.
Disadvantages No inherent ordering, there are better solutions for general use.
4.15.7 Stacks
Stacks are a particular data structure, they have a limited way of working: you can only put or remove items on top
Push Pop
Stack Pointer
Stacks are LIFO (Last in - First Out) data structures, and can be implemented with both a linked list or a cleverly-
indexed array.
Depending on the single implementation, the operation used to “pop” an item from the stack will also return the
Stack Pointer
Array 1 5
Linked List 5 1
Stack Pointer
4.15.8 Queues
Queues are the exact opposite of stacks, they are FIFO (First in - First Out) data structures: you can put items on the
back of the queue, while you can remove from the head of the queue.
Enqueue
Dequeue
1 5
Depending on the single implementation, the operation used to “dequeue” an item from the queue will also return
As with stacks, queues leverage limitations in their way of working for greater control over the structure itself.
Usually queues are implemented via linked lists, but can also be implemented via arrays, using multiple indexes and
Head Tail
Array 1 5
Linked List 1 5
Head Tail
Circular Queues are a particular kind of queues that are infinitely iterable, every time an iterator goes after the last
Pointer
3
9
0 4
Circular Queues can be implemented via linked lists or cleverly indexed arrays, with all the advantages and disad-
Head Tail
Array 1 5
Linked List 1 5
Head Tail
This is one of the most-talked about principles in computer science: it usually refers to the principle of “memory
locality”, but it may also refer to other kinds, like “temporal locality” or “branch locality”.
• Spatial locality: (sometimes called “memory locality”) if a certain region of storage (or memory) is refer-
enced, there is a good probability that nearby regions of storage (or memory) will be referenced in the near
• Temporal locality: if a certain region of storage (or memory) is referenced, there is a good probability that
the same region will be referenced in the near future. CPU caches leverage this principle by copying recently-
This is usually done when dealing with pointers, but we may need to use some math to deal with sprites and
animations too.
As we’ll see in the Sprite sheets section, it is more efficient to store sprites and animation frames in sprite sheets.
When dealing with frames of animation, we like our frames to be “one-dimensional”, each “cell” represents a certain
“time”.
0 1 2 3 4 5 6 7
Figure 102: The “easy way” of dealing with frames
When dealing with sprite sheets, we may find that our animation has frames saved in a “matrix” of some sort, like
so:
0 1 2
0 0 1 2
Height: 3
1 3 4 5
2 6 7
Width: 3
Figure 103: A sample sprite sheet with the same frames as before
The images we’ve just seen will help you understand how the following formulas work.
To convert from 2-dimensional (row, column) coordinates to a single index, the formula is:
Note!
Remember that in many programming languages arrays and similar structures are 0-
If you’re using a language that indexes arrays starting from 1 (like Lua), these formulas
So if I want to know the index of the 3rd element of the second row, with index (2,1), the formula becomes:
index = 3 × 1 + 2 = 5
row = ⌊ index ⌋
width
column = index%width
So if we wanted to know the (row,column) position of the frame with index 7 we would have:
row = ⌊ 7 ⌋ = ⌊2.33333⌋ = 2
3
column = 7%3 = 1
Note!
This can be done with structures with n dimensions, but the formula becomes a lot
more complex the more dimensions you add. We’ll stop at 2 for now.
When dealing with certain structures, there are operations that are inherently complex to do: let’s take for example
1 c l a s s List {
2 private :
3 Node * nodeList ;
4 // ...
5 public :
6 i n t getLength () {
7 i n t counter = 0;
10 counter = counter + 1;
11 node = node -> next ;
12 }
13 r e t u r n counter ;
14 }
15 };
It’s easy to see that an algorithm like this has a Θ(n) complexity, which may not be ideal for an operation as common
This is where data redundancy comes into play: the length of a list is an intrinsic property of the list itself, so why
This will obviously require a bit more work in all the methods that will change the number of elements inside the list,
since we need to keep the “length” property in sync with the actual length of the list, but in exchange we can count
1 c l a s s List {
2 private :
3 Node * nodeList ;
4 i n t length ;
5 // ...
6 public :
7 i n t getLength () {
8 r e t u r n length ;
9 }
10
25 void clear () {
Pitfall Warning!
the actual state of our objects, even when exceptions are raised. Not doing so will
create bugs.
Let’s consider another example: we have a standard linked list, like the one that follows:
Pointer
7 9 5
Our “pointer” is pointing the node containing the number “5”, and now we want to know the value of the node that
precedes it. To do that we need to start from the head, saving in a temporary variable our nodes, until we find the
5 previous = pointer ;
6 pointer = pointer -> next ;
7 }
8 r e t u r n previous ;
9 }
This operation has O(n) complexity, which is not great. If we wanted to print a list in reverse with such technique,
Doubly-linked lists are another example of data redundancy. We are saving the content of the “previous” node, so
that we can do a simple lookup with complexity O(1) and easily (and efficiently) do our “reverse printing”.
7 9 5
When it comes to humans, we are used to have everything at our disposal immediately, but when it comes to
computers, each processing unit (CPU) is usually able to perform only one task at a time.
To allow for multi-tasking (doing many activities at once), the CPU switches between tasks at high speeds, giving
us the illusion that many things are happening at once. There are many methods to ensure multi-tasking without
process starvation[g] , the most used is pre-emption[g] where there are forced context switches between processes,
Sometimes Multi-Threading and Multi-Processing are used interchangeably, but this is actually not correct. Let’s see
the differences between the two terms and how they contribute (in different ways) to allow multi-tasking.
Multi-Processing is a practice that makes use of multiple CPUs inside the same machine, this allows to process CPU-
intensive calculations in a parallel manner, thus gaining performance in our software. This style of parallelization is
usually done by spawning multiple processes, each of which will be run on a different CPU (or Core).
Process 1 Process 2
Multi-Processing has some disadvantages: creating a process can be quite expensive and thus give us some tangible
Multi-Threading is a programming practice that allows to run different “lines of execution” (called “threads”), inside
of the same parent process, so to achieve the maximum possible CPU utilization.
Multi-Threading has the advantage of lower overhead, since threads are quite cheap to create, but also has some
more limitations when the tasks to execute are “CPU-bound” (take a lot of CPU time).
Process 1 Process 2
Figure 107: In multi-threading, the CPU uses I/O wait time to take care of another task
Multi-Threading works well when the threads are “I/O bound” (they use network or disk a lot, while the CPU usage
is low), this means essentially that while one thread is waiting for I/O (like loading an asset), another thread can
perform other calculations on the CPU instead of just “wait for the I/O to finish”.
4.19.2 Coroutines
If you search for the word “coroutine” online, you will find a lot of extremely convoluted explanations involving the
knowledge of the difference between preemptive[g] and non-preemptive multitasking, subroutines, threads and lots
First of all, coroutines are computer programs can run in multitasking (so it can run separated from our main game
loop) which are used in non-preemptive multitasking. Differently from the preemptive style defined in the glossary,
in non preemptive multitasking the operating system never forces a context switch, but it’s the coroutine’s job to
Instead of “fighting for resources”, coroutines politely free the processor and give control of it to something else
(could be the caller or another coroutine), this form of multitasking is often called cooperative multitasking.
A particularly interesting point of coroutines is the fact that their execution can be “suspended” and “resumed”
without losing its internal state. Coroutines are used in more advanced engines (using the Actor Model) and in some
particular situations. You may never need to use a single coroutine, or you may need to use them every day, so it’s
When it comes to games and software, we usually think of it as a single line of execution, branching to (not really)
infinite possibilities; but when it comes to games, we may need to dip our toes into the world of multi-threaded
applications.
Multi-Threading means that multiple threads exist in the context of a single process, each thread has an independent
line of execution but all the threads share the process resources.
In a game, we have the “Game Process”, which can contain different threads, like:
• Rendering Thread
• Loading Thread
• …
Many people think of Multi-Threading as “parallel execution” of tasks that leads to faster performance. That is not
always the case. Sometimes Multi-Threading is used to simplify data sharing between flows of execution, other
times threads guarantee lower latency, other times again we may need threads to get things working at all.
For instance let’s take a loading screen: in a single-threaded application, we are endlessly looping in the input-
update-draw cycle, but what if the “update” part of the cycle is used to load resources from a slow storage media
The update function will keep running until all the resources are loaded, the game loop is stuck and no drawing will
be executed until the loading has finished. The game is essentially hung, frozen and your operating system may
even ask you to terminate it. In this case we need the main game loop to keep going, while something else takes
Threads and concurrent execution are powerful tools in our “programmer’s toolbox”, but as with all powers, it has
Imagine a simple situation like the following: we have two threads and one shared variable.
Thread 1 Thread 2
Copy of Copy of
Variable Variable
Variable
1
Result Result
Both threads are very simple in their execution: they read the value of our variable, add 1 and then write the result
This seems simple enough for us humans, but there is a situation that can be really harmful: let’s see, in the following
example each thread will be executed only once. So the final result, given the example, should be “3”.
First of all, let’s say Thread 1 starts its execution and reads the variable value.
Read
Thread 1 Thread 2
Copy of Copy of
Variable Variable
Variable
1
Result Result
Now, while Thread 1 is calculating the result, Thread 2 (which is totally unrelated to Thread 1) starts its execution
...
Read
Thread 1 Thread 2
Copy of Copy of
Variable Variable
1 Variable
1
Result Result
Now Thread 1 is finishing its calculation and writes the result into the variable.
...
Thread 1 Thread 2
Copy of Copy of
Variable Variable
1 Variable 1
1
Result Result
Write
Result
After That, Thread 2 finishes its calculation too, and writes the result into the variable too.
Thread 1 Thread 2
Copy of Copy of
Variable Variable
1 Variable 1
2
Result Result
2 2
Terminated
Write
Result
Something is not right, the result should be “3”, but it’s “2” instead.
Thread 1 Thread 2
Copy of Copy of
Variable Variable
1 Variable 1
2
Result Result
2 2
Terminated Terminated
We just experienced what is called a “race condition”: there is no real order in accessing the shared variable, so
things get messy and the result is not deterministic. We don’t have any guarantee that the result will be right all
Critical Regions (sometimes called “Critical Sections”) are those pieces of code where a shared resource is used, and
as such it can lead to erroneous or unexpected behaviors. Such sections must be protected from concurrent access,
which means only one process or thread can access them at one given time.
Let’s take a look at how to implement multi-threading in a safe way, allowing our game to perform better without
non-deterministic behaviors. There are other implementation approaches (like thread-local storage and re-entrancy)
The easiest way to implement thread-safety is to make the shared data immutable. This way the data can only
be read (and not changed) and we completely remove the risk of having it changed by another thread. This is an
approach used in many languages (like Python and Java) when it comes to strings. In those languages strings are
immutable, and “mutable operations” only return a new string instead of modifying the existent one.
4.20.4.2 Mutex
Mutex (Short for mutual exclusion) means that the access to the shared data is serialized in a way that only one
thread can read or write to such data at any given time. Mutual exclusion can be achieved via algorithms (be careful
of out of order execution[g] ), via hardware or using “software mutex devices” like:
• Semaphores
• Monitors
• Readers-Writer locks
• Recursive Locks
• …
Usually these multi-threaded functionalities are part of the programming language used, or available via libraries.
As seen before, we have a shared variable and two threads that want to add one to it.
Now the first thread reads the variable and “locks” the mutex (thus stopping other threads from accessing the
variable).
When the second thread wants to access the “critical region”, it will check on the Mutex, find it “locked” and be
forced to wait: it cannot read the variable, because we would have a “race condition” otherwise.
As soon as the first thread finishes its job, it will write the result in the variable and “unlock” the mutex, allowing
Since the second thread was waiting, it will read the variable result (now 2) and “lock” the mutex for safety. The
The second thread will do its job as normal, if a third thread tried to access the variable, it would be stopped by the
locked mutex.
When its job is done, the second thread will write to the variable and “unlock” the Mutex, thus allowing other threads
Now both threads finished their jobs and the result inside the variable is correct.
Why should you make games? Do it to give players joy from your unique
perspective and to have fun expressing yourself. You win and the players win.
In this section we will talk about platforms, input systems and game genres, in a quick fashion. This chapter will
introduce you to the language and terms used in game design, this way the following chapters will be easier to
comprehend.
We will talk about the differences and challenges deriving from each decision and the basic way game genres work.
The objective of this chapter is giving you some terminology and knowledge about game design, before deep-diving
5.1 Platforms
There are several different platforms a game can be developed for, and each one has its own advantages and
5.1.1 Arcade
Arcade cabinets have been around for decades, and have still a huge part in the heart of gaming aficionados with
classic series going on like “Metal Slug”. The main objective of these machines is to make you have fun, while forcing
These cabinets’ software is known to be very challenging (sometimes due to the fact that you’re popping quarters
into the machine for the “right to play”), having some nice graphics and sound. Arcade games are usually presented
in the form of an “arcade board”, which is the equivalent of a fully-fledged console, with its own processing chips
In the case of arcades, the hardware is usually tailored to support the software; with some exceptions added later
(like the Capcom Play System, also known as CPS), where the hardware is more stable between arcades, while the
software changes.
5.1.2 Console
Consoles are a huge (if not the biggest) part in the video game industry. Their Hardware is dedicated solely to
gaming (and some very marginal “multimedia functionalities”) and it evolves in “generations”: this means that
each “generation” has a stable hardware programmers can study and exploit.
This hardware stability is a double-edged sword: the hardware can be really hard to master at the beginning, resulting
in some poor-performing games at the beginning of the generation, but when mastered the results are incredible.
4. The games become “too big” for the current generation and a new generation must be introduced.
Personal Computers are another huge part of the video game industry. They are extremely flexible (being general-
purpose machines) but have a huge drawback: their hardware is not the same from one unit to the other. This means
that the programmer needs to use “abstraction layers” to be able to communicate with all the different hardware.
This compounds with the fact that “abstraction layers” used by the developer (like SDL, SFML or GLFW) are running on
top of other “abstraction layers”, like sound servers, device drivers, etc… which can be littered with bugs themselves.
Just look at how many indirections we have on a modern Linux system (which is usually bundled with PulseAudio):
Game
SDL/SFML/GLFW
PulseAudio Engine
Sound Card
Figure 125: How many abstraction layers are used just for a game to be able to play sounds
This can have performance costs, as well as forcing the programmer to add options to lower graphic settings, reso-
All of this just to be able to run on as many computers as possible. The upside is that when the computer is really
powerful, you can get great performance and amazing quality, but that’s a rare occasion.
5.1.4 Mobile
One of the most recent platforms game developers work on is right in your pocket: your smartphone.
Today’s smartphones have enough power to run fully-fledged video games, on the go. Sadly the touch screen can
prove to be really uncomfortable to use, unless the game is specially tailored for it.
5.1.5 Web
Another platform that has seen a massive rise in recent times is the Web: with WebGL and WebAssembly, fully-
fledged games (including 3D games) can run on our browser, allowing for massively-multiplayer experiences (like
Agar.io) without the hassle of manual installation or making sure the game is compatible with your platform.
Figure 127: Fully fledged games can run in your browser nowadays
A drawback of the “web approach” is the limited performance that web browsers, WebGL and WebAssembly can give,
as well as the need to download the game before being able to play (and sometimes you may need to re-download
A game needs a way to be interacted with: this “way” is given by input devices. In this section we will take a brief
One of the most common input devices, most of the currently available frameworks and engine have support for
input via mouse and keyboard. These input methods are great for visual novels, point and click adventures, FPS/TPS
5.2.2 Gamepad
One of the classics of input devices, works well with the majority of games: FPS/TPS games may need some aim
assist mechanic in your game. Point and click adventures feel clunky with this input method.
As with Mouse and Keyboard, most of the currently available engines and frameworks support gamepads.
With the coming of smartphones, touch screen is a new input device that we have to account for. Touch screens
The nature of being a mix between an input device and a screen brings a lot of new ways to experience a game
if well done. Many times touch screens are used to simulate game pads: the lack of the tactile feedback given by
Some of the most recent framework and engines support touch screens, although there’s an additional layer of
complexity given by the specific operating system of the smartphone you’re building for.
Some games require dedicated hardware to work at their best, if at all. Guitars (guitar hero), wheels for racing
games, joysticks for flying simulators, arcade sticks for arcade ports…
Dedicated hardware requires precise programming, and is usually an advanced topic. On PCs many “dedicated input
devices” are recognized as “game pads” and use an “axis” and “buttons” abstraction that makes coding easier.
A special mention is deserved for all the input devices that are “general purpose” (as in not “dedicated”) but are
In this group we see gyroscopes, accelerometers (like the Nintendo Wii/Switch JoyCons), sensors, IR, as well as other
Let’s analyze some game genres to understand them better and introduce some technical language that may be
These genres are quite broad, so a video game is usually a mix of these “classes” (like a strategy+simulation game).
5.3.1 Shooters
Shooters are games that involve… shooting. They can include any kind of projectile (bullets, magic from a fairy,
arrows from a hunter) and can be crossed with any other genre (creating sub-genres in a way), like 2D platformers.
• FPS (first person shooters), 3D games where the game is shown from the point of view of the protagonist.
This involves only seeing a HUD and the weapon, instead of the whole character;
• TPS (third person shooters), 3D games where the game is shown from a behind-the-character perspective.
Some show the whole protagonist, while others adopt an over-the-shoulder perspective;
• Top Down Shooters, usually 2D games where you may be piloting a vehicle (space ship, plane, etc…) and
shoot down waves of enemies, in this category we fit arena shooters (like Crimsonland) and space shooters
(like Galaga);
• Side scroller shooters, usually 2D games and platformers, where you control the protagonist and shoot
5.3.2 Strategy
Strategy games involve long-term planning and resource control, they are slower games, but can be really intense
• RTS (real time strategy), where units are controlled in real time;
5.3.3 Platformer
Platformer games involve difficult jumps and precise movement, they can both be 2D and 3D games. A prime
example of platformer games is the Mario series: Mario 1,2,3 for 2D games and Mario 64 for 3D.
5.3.4 RPG
RPGs or “Role Playing Games” are games where you assume the role of a character in a fictional setting. In RPGs
the world is well-defined and usually have some level or class system and quite advanced item management.
RPGs can be either action/adventure, with real-time actions, turn-based or hybrid, where the movement is done in
real time but battles happen in turns. Some prime examples of RPG games are the Legend of Zelda series, as well
5.3.5 MMO
MMO (Massively Multiplayer Online) is a term used for games that have a heavy multiplayer component via the
internet. The most known MMO genre is MMORPGs (Massively Multiplayer Online Role-Playing Games).
5.3.6 Simulation
Simulation games cover a huge variety of games that are created to “simulate reality”, in more or less precise ways.
• Racing Games: sometimes more simulative others more arcade-like, racing games simulate the experience
of driving a vehicle, more or less realistic (from modern cars to futuristic nitro-fueled bikes);
• Social Simulation: simulating the interaction between characters, a pioneer on the genre is surely “The
Sims”;
But there are also other kinds of simulations, like Sim City, where you manage an entire city.
Rhythm games are based on the concept of following a music beat as precisely as possible, this can be also used as
Some examples of Rhythm games are “Dance-Dance Revolution” (also known as DDR), as well as more innovative
games like “Crypt of the Necrodancer” (a mix between rhythm game and dungeon crawler).
Visual novels are graphical adventures whose primary objective is “telling a story”, they can be linear or have a
“choose your own path” component. They usually feature multiple endings and hand-crafted still images as artwork.
The more modern versions feature more interactive components and fully-fledged 3D graphics, but what ties the
Puzzle games are centered about making the player think: they can test a lot of problem-solving skills from pattern
Some example of puzzle games include Lemmings, Boulder Dash, any match-3 game (started with “Shariki”, followed
by “Bejeweled” until the more modern titles for mobile phones), and Tetris.
Puzzle games can involve math (like Sudoku), Physics (like the game “Peggle”), Hidden objects or even programming
(for instance “Shenzen I/O” for “realistic programming”, or “Opus Magnum” for a different approach).
Nothing stops other genres from including puzzle elements, but this small section is dedicated to the games that
5.4 Miscellaneous
Here we will talk about some other terms that you may hear in the game development and design world, but that
Sometimes, when interacting with simple game mechanics, players can give life to complex situations. When that
Emergent gameplay can take place in open-ended games, where there are many solutions to a situation and none
of them is “preferred by the game”. For instance, we can think of someone guarding a door, there are many ways
• …
Random Trivia!
can either survive, build palaces, build redstone circuits and much more.
Those who plan do better than those who do not plan even though they
Winston Churchill
Project management is a very broad topic but I feel that some basics and tips should be covered in this book. Knowing
some project management can save you a lot of headaches and can make the difference between success and a
colossal failure.
Before delving into the topic at hand, we need to familiarize ourselves with the main figures that are involved in the
process of game design and development, since you’ll probably (if you are the only developer of your game) have
The producer is a figure that has experience in many fields and has an overall view of the project. They essentially
Under the term “project manager” you can find different roles, among them:
• Product Manager;
• Assistant Producer;
• Executive producer.
A good project manager will need tools to manage tasks (Like a Kanban Board), as well as tools that promote
communication in the team (Chats, VoIP) and information repositories (having all information in the same place is
important!).
The game designer takes care of the game concept, usually (but not only!) working with really specific software,
usually provided by the programmers in the team (like specific level editors).
They design balanced game mechanics, manage the learning curve and take care of level design too.
Under the “Game Designer” term you can find different roles, among them:
• Level Designer;
• World Builder;
• Narrative Designer;
• Quest/Mission Designer.
A good game designer must know mathematics, some scripting and be able to use planning tools (again, our friendly
6.1.3 Writer
Writers are the ones who can help you give your game its own story, but also help with things that are outside the
• Writing narration;
• Writing dialogue;
• Writing pieces for the marketing of your game (sometimes known as “Copywriting”).
Under the term of “Writer” you can find more roles, like:
• Editor;
• Narrative Designer;
• Creative Writer.
A good writer must have good language skills, as well as creativity. They must be able to use planning programs
(like everyone, communication is important) as well as writing programs, like LibreOffice/OpenOffice Writer.
6.1.4 Developer
Logic and mathematics are the strong suit of programmers, the people who take care of making the game tick, they
• Problem Solver
• Controls programmer;
• AI developer;
• Visuals Programmer;
• Networking programmer;
• Physics programmer;
• …
They must be familiar with IDEs and programming environments, as well as Source Control Tools (Like Git), knowledge
of game engines like Unity is preferred, but also tied to the kind of game that is made.
In 2D games visual art is as important as in 3D games and good graphics can really boost the game’s quality greatly,
• 2D Artists;
• Animators;
• Environment Artists;
• UI Artists/Designers;
• Conceptual Artists.
In 3D games:
• 3D Modelers;
• Texture Artists.
Visual Artists must be knowledgeable in the use of drawing programs, like Krita, GIMP or their commercial counter-
parts.
As with graphics, sound and music can make or break a game. Sound artists may also be musicians, and their task
is to create audio that can be used in a video game, like sound effects, atmospheres or background music.
• Audio Engineers;
• Game Composers;
• Music Mixers;
• Audio Programmers.
The knowledge of DAW (Digital Audio Workstation) software is fundamental, as well as knowing some so-called
“middlewares”, like FMOD. Another important bit of knowledge is being able to use Audio editors effectively.
6.1.7 Tester
Probably the most important job in a game development team, testing needs people with high attention to detail,
Testers are able to find, describe and help you reproduce bugs and misbehaviors of your game.
The “it would be cool to…” trap, formally called “feature creep”, is a huge problem in all projects that involve any
Saying “it would be cool to do <insert something here>: let’s implement it!” can spiral out of control and make us
implement new features forever, keeping us from taking care of the basics that make a good game (or make a game
at all).
Try to stick to the basics first, and then eventually expand when your game is already released, if it’s worth it: first
make it work, then make it work well and only in the end make it elegant.
When it comes to project management, it’s always tough to gauge the project duration, so it can prove useful to
“If you think a project would last a month, you should add a month of time for unforeseen events. After that,
you should add another month for events that you really cannot foresee.”
This means that projects will last at least 3 times the time you foresee.
That may seem a lot like an exaggeration, but unforeseen events happen and they can have a huge impact on the
release of your game. It’s better to err on the side of caution and even delay the release if something goes wrong.
so maybe being “abundant” with your time estimates is not that wrong.
Brainstorming is an activity that involves the design team writing down all the ideas they possibly can (without
This is a productive activity to perform at the beginning of the game development and design process, but it can be
After the initial phase of brainstorming, the team analyzes the ideas and discards the impossible ones, followed by
the ones that are not “as good as they sounded at first”. The remaining ideas can come together to either form a
In short: brainstorming is a great activity for innovation, but since it’s essentially “throwing stuff at a wall and see
what sticks”.
This activity can sometimes be either unproductive or “excessively productive”: in both cases we end up with nothing
6.2.4 On Sequels
In case your game becomes a hit, you will probably think about making a sequel: this is not inherently a bad thing,
When developing a sequel, you will have to live up to your previous game, as well as the expectations of the players,
and this becomes more and more difficult as the “successful sequels” go on.
Not only a sequel must be “as good or better” than its predecessor, but also it should add something to the original
Your time and resource management must be top-notch to be able to “bring more with less”, since your need for
Also don’t get caught in the some kind of “sequel disease” where you end up making a sequel just to “milk the
intellectual property”: you will end up ruining the whole series: it may end up being hated by the ones who played
the first games, and new players will be discouraged by a series that either overstays its welcome, or has one or
When you are making a new game, it’s easy to feel lost and “out of your comfort zone”, and that’s okay! It’s also
easy to fall into traps and pitfalls that can ruin your experience, here we take a look at the most common ones.
Sometimes it can happen to lose motivation, usually due to having “too much ambition”: make sure you can develop
the kind of game you want to make, for instance leave multiplayer out of the question (multiplayer games are really
hard and network code can be a real pain to work on). It will just suck up development time, and it isn’t that much
of an important feature anyway (and it can still be implemented later, like it happened in Stardew Valley).
Like in music, many people prefer “mediocrity” to “something great”, so don’t force yourself to innovate: do things
If you get tired, take a break, you’re your own boss, and no one is behind you zapping you with a cattle prod: just
It happens: you have a ton of ideas for games of all kinds, and probably you’ll start thinking:
What’s bad about a small “side project”? I want to change things up a bit…
You will end up having lots of “started projects” and nothing finished, your energy will deplete, things will become
confusing and you won’t know what game you’re working on anymore.
Instead, make a small concept for the new mechanic and try to implement it in your current game, you may find a
new mix that hasn’t been tried before, making your game that much more unique.
While making a game you will need to gather some public for it, as well as create some hype around it: making a
game on your own without involving the public is a mistake that deprives you of a huge source of suggestions and
(constructive) criticism (as well as satisfaction, when you manage to get some people interested in your game).
Make your game public, on platforms like itch.io or IndieDB, get feedback and encouragement. Create trailers towards
the end of development, put them on YouTube or Vimeo and if you want to go all out, get in touch with the press (locally
Among all the other things that are happening, we also need to handle feedback from our “potential players”, and
this requires quite the mental effort, since we can’t make it “automatic”.
Not all criticism can be classified as “trolling”, and forging our game without listening to any feedback will only mean
that such game won’t be liked by as many people as we would like, maybe for a very simple problem that could
At the same time, not all criticism is “useful” either, not classifying criticism as “trolling” does not mean that trolling
doesn’t exist, some people will take pride in ruining other people’s mood, either by being annoying and uselessly
If the answer is no, then you may want to ignore such criticism, but if it is constructive, maybe you want to keep it
in consideration.
This is what could be considered the apex of mishandling criticism: the usage of DMCA takedowns to quash criticism
Note!
If you want to know more (as in quantity and quality of information), contact your
favorite lawyer.
Sadly, mostly in the YouTube ecosystem, DMCA takedowns are often used as a means to suppress criticism and
make video-reviews disappear from the Internet. Useless to say that this is potentially illegal as well as definitely
despicable.
Takedowns according to the DMCA are a tool at your disposal to deal with copyright infringements by people who
steal part (or the entirety of) your work, allowing (in the case of YouTube at the very least) to make the allegedly
infringing material. This should be used carefully and just after at the very least contacting the alleged infringer
The so-called “Fair Use” is a limited exception to the copyright law that targets purposes of review, criticism, parody,
The test for “Fair use” has four factors (according to 17 U.S.C. §107):
1. The Purpose and character of the use: if someone can demonstrate that their use advances knowledge
or the progress of arts through the addition of something new, it’s probably fair use. This usually is defined
2. The nature of the copyrighted work: For instance, facts and ideas are not protected by copyright, but
only their particular expression or fixation is protected. Essentially you can’t really sue someone for making
a game very similar to yours (For instance making a 2D sidescrolling, run’n’gun platformer).
3. The amount and substantiality of the portion used in relation to the work as a whole: If someone
uses a small part (compared to the whole) of the work, and if that part is not really substantial, then it’s
4. The effect on the potential market for the copyrighted work: this defines if the widespread presence
of the “allegedly infringing use” can hinder on the copyright owner’s ability to exploit (earn from) their original
work.
There can also be some additional factors that may be considered, but these four factors above are usually enough
Let’s take a simple example: a video-review on our brand new video game, that takes some small pieces of gameplay
(totaling about 5 minutes), on video and comments on the gameplay, sound and graphics. A very common scenario
Let’s take a look at the first point: the purpose is criticism, the review brings something new to the table (essentially
Second point: the game is an interactive medium, while the review is non-interactive by nature, the mean of trans-
mission is different.
Third point: considering the average duration of 8 to 10 hours of a video game, 5 minutes of footage amounts for
around 0.8% to 1% of the total experience, that’s a laughable amount compared to the total experience.
Fourth Point: this is the one many people may get wrong. A review can have a huge effect on the market of a
copyrighted work (a bad score from a big reviewer can result in huge losses), but that’s not really how the test
works. The fourth test can usually be answered by the following questions:
What’s the probability that someone would buy (or enjoy for free) the work from the alleged infringer, instead
This is called “being a direct market substitute” for the original work. The other question is:
Is there a potential harm (other than market substitution) that can exist?
This usually is related to licensing markets. And here lies the final nail on the coffin: there is no direct market
substitution and courts recognize that certain kinds of market don’t negate fair use, and reviews are among those
This is a common mistake when you are focused on making the game: using your own skill as a “universal measure”
for the world’s skill level. You may be an unknown master at 2D platformers, and as such what is “mildly difficult”
for you may be “utterly impossible” for the average player. Or the opposite.
Try to keep the challenge constant through the levels, applying the usual slight upwards curve in difficulty that most
games have (or check the section about difficulty curves for some ideas), and let others test your game.
A beta version with feedback capabilities (or just a beta version and a form or email address can do the trick too) is
pure gold when it comes to understanding what your players think about the game’s challenge level.
Remember: when a level is (perceived as unfairly) too hard, players will stop playing the game.
If you are called “perfectionist” by your friends, that should be a red flag in your game development process from
Finding yourself honing the game over and over, allocating countless hours (that always feel as “not enough”) into
making the game “better”, will end up just sabotaging the development process itself.
Instead try to prefer a more “scientific approach”, where you study your game’s shortcomings (with the help of some
testers, or “friend-made-tester”), order them by their “effort vs improvement” ratio and start with those who require
Quality
I
3. After a certain point, we have
diminishing returns with increasing effort.
Effort
You can see that you can get really good returns for relatively little effort, but if you’re a perfectionist, you may want
to push forward and put more and more hours, with diminishing returns.
• Working Gameplay
You have a complete product. Release it. Updating it is very easy these days, and maybe that will give you the
The game engine is one of the most important decisions you can take at the beginning of your game development
journey. Realizing that you used the wrong engine after months of development can be a huge setback, as well as
Don’t trust market hype over an engine, and don’t trust the vendor’s promises either.
Does the game engine have the features you will need already? No? Then your money should stay where it is, and
If such engine’s producer is promising the feature you want in future, don’t trust it, that version may come, or it may
never come at all. If you bought the engine and such feature won’t ever be there, your money won’t come back.
When talking about project management (in itself or in the broader field of Software Engineering) it is really useful
to talk about some guideline models that can be used to manage your project.
Before getting to the models, we need to discuss the difference between two terms that are often used interchange-
Iteration is a non-deterministic process, during an iteration you are revisiting what you have already done, and
such revisiting can include an advancement or a regression. While iterating, you have no idea when you will finish
your job.
Increment is deterministic instead, with increments you are proceeding by additions over a base. Every increment
creates a “new base” for the next increments, and increments are numbered and limited, giving you an idea of when
The Waterfall model, also known as “sequential model” is the simplest one to understand, easily repeatable (in
different projects) and is composed by phases that are strictly sequential, which means:
• There is no parallelism;
This makes the Waterfall life cycle model extremely rigid, everything needs to be carefully analyzed and documented
(sometimes people define this model “document-driven”) and the coding is done only in its final phases.
In order to have a good result, this model requires quantifying some metrics (time spent, costs, …) and such quan-
tification heavily relies on the experience of the project manager and the administrators.
When a project of a certain size is involved, it’s a bad idea to perform the so-called “big-bang integration” (inte-
grating all the components together). Such approach would make troubleshooting a nightmare, so it’s advisable to
The Incremental Model allows to have a “high-level analysis and planning”, after that the team decides which features
should be implemented first. This way the most important features are ready as soon as possible and have more
time to become stable and integrate with the rest of the software.
Analysis
High-level Planning
The number of iterations
is fixed
Detail Planning
Release 1
Release 2
Production ..........
Release n
This model can make use of strictly sequential phases (detail planning -> release -> detail planning -> release …)
or introduce some parallelism (for instance planning and developing frontend and backend at the same time).
As seen from the diagram, the high-level analysis and planning are not repeated, instead the detail planning and
release cycle for a well-defined number of iterations, and on each iteration we will have a working release or proto-
type.
It’s not always possible to perfectly know the outline of a problem in advance, that’s why the evolutionary model
was invented. Since needs tend to change with time, it’s a good idea to maintain life cycles on different versions of
Initial
Specification Version
Validation Final
Version
Adding a way to implement the feedback you get from your customers and stakeholders completes the micro-
managed part of the life cycle model, each time feedback and updates are implemented, a new version is released.
Analysis
Planning
Detail Planning
Incorporation
Delivery
of Feedback
Customer Feedback
Agile Software Development was born as a reaction to the excessive rigidity of the models we’ve seen so far. The
basic principles of Agile Software Development are presented at the http://agilemanifesto.org website, but we will
• Seek collaboration with the stakeholder instead of trying to negotiate with them;
• Interactions and individuals are more important than processes and tools.
Obviously not everything that shines is actually gold, there are many detractors of the Agile model, bringing on the
• The agile way of working entails a really high degree of discipline from the team: the line between “flexibility”
• Software without documentation is a liability more than an asset: commenting code is not enough - you need
to know (and let others know) the reason behind a certain choice;
• Without a plan, you can’t estimate risks and measure how the project is coming along;
• Responding to change can be good, but you need to be aware of costs and benefits such change and your
response entail.
Agile models are based on “User Stories”, which are documents that describe the problem at hand.
Such documents are written by talking with the stakeholder/customer, listening to them, actively participating in
A User Story also defines how we want to check that the software we are producing actually satisfies our customer.
6.4.5.2 Scrum
The term “scrum” is taken from the sport of American Football, where you have an action that is seemingly product
• Product Backlog: This is essentially a “todo list” that keeps requirements and features our product must
have;
• Sprint: Iteration, where we choose what to do to create a so-called “useful increment” to our product. Each
Sprint lasts around 2 to 4 weeks and at the end of each sprint you obtain a version of your software that can
• Sprint Backlog: Essentially another “todo list” that keeps the set of user stories that will be used for the
next sprint.
As seen from the terminology, the Scrum method is based on well-defined iterations (Sprints) and each sprint is
• Sprint Planning: You gather the product backlog and eventually the previous sprint backlogs and decide
• Daily Scrum: A daily stand-up meeting that lasts around 15 minutes where a check on the daily progress is
done;
• Sprint Review: After the sprint is completed, we have the verification and validation of the products of the
• Sprint Retrospective: A quality control on the sprint itself is done, allowing for continuous improvement
The Scrum approach can quickly become chaotic if User Stories and Backlogs are not well kept and clear. Also, no
matter how short it can be, the Daily Scrum is still an invasive practice that interrupts the workflow and requires
6.4.5.3 Kanban
Kanban is an Agile Development approach taken by the scheduling system used for lean and just-in-time manufac-
The base of Kanban is the “Kanban Board” (sometimes shortened as “Kanboard”), where plates (also called “cards”
The board helps with organization and gives a high-level view of the work status.
Fix Bug #1234 Fix Bug #159 Antigravity Engines World Domination
6.4.5.4 ScrumBan
ScrumBan is a hybrid approach between Scrum and Kanban, mixing the Daily Scrum and Sprint Approach with the
Kanban Board.
This approach is usually used during migration from a Scrum-Based approach to a purely Kanban-based approach.
Lean development tries to bring the principles of lean manufacturing into software development. The basis of lean
• Remove Waste: “waste” can be partial work, useless features, waiting, defects, work changing hands…
• Amplify Learning: coding is seen as a learning process and different ideas should be tested on the field,
• Decide late: the later you take decisions, the more assumptions and predictions are replaced with facts, Also
strong commitments should happen as late as possible, as they will make the system less flexible;
• Deliver early: technology evolves rapidly, and the one that survives is the fastest. If you can deliver your
product free from defects as soon as possible you will get feedback quickly, and get to the next iteration
sooner;
• Empower the team: managers are taught to listen to the developers, as well as provide suggestions;
• Build integrity in: the components of the system should work well together and give a cohesive experience,
• Optimize the whole: optimization is done by splitting big tasks into smaller ones which helps finding and
Obviously the models presented are not set in stone, but are “best practices” that have been proven to help with
Nothing stops you from taking elements of a model and implement them into another model. For example you could
use an Evolutionary Model with a Kanban board used to manage the single increment.
When it comes to managing any resource that is important to the development process of a software, it is vitally
important that a version control system is put in place to manage such resources.
Code is not the only thing that we may want to keep under versioning, but also documentation can be subject to it.
Version Control Systems (VCS) allow you to keep track of edits in your code and documents, know (and blame) users
for certain changes and eventually revert such changes when necessary. They also help saving on bandwidth by
uploading only the differences between commits and make your development environment more robust (for instance,
The most used Version Control system used in coding is Git, it’s decentralized and works extremely well for tracking
text-based files, like code or documentation, but thanks to the LFS extension it is possible for it to handle large files
efficiently.
Other used version control systems are Mercurial and SVN (subversion).
Another useful feature of many version control systems are remote sources, which allow you to upload and synchro-
nize your repositories with a remote location (like GitHub, GitLab or BitBucket for instance) and have it safe on the
During development you need to keep an eye on the quality of your project, that’s when you need a project dash-
board: but before that, you need to decide what your quality metrics are, that means the measurements that
define if your project is “up to par” with what you expect or not.
6.6.1 SLOC
This is probably the simplest metric out there: The “Source Line of Code” (SLOC). It is used to measure the size of a
program by counting its lines of code. Once Bill Gates said the following:
Measuring programming progress by lines of code is like measuring aircraft building progress by weight.
An aircraft must be lightweight and robust, and being heavier than necessary will stop it from flying. The same
reasoning should be applied here: a longer source code doesn’t mean a better product.
It is important to strike a balance between “readability” and “brevity”: your code should be short, but being source
code, it is still meant for humans to read, so readability matters more than brevity.
Usually the SLOC metric is used to give a “order of magnitude” impression of the program: considering 2 programs
that do exactly the same thing, one is 10.000 lines of code, the other one is 100.000, you may start to suspect that
the bigger program is more (probably uselessly) complex and less maintainable.
More precisely called “McCabe’s Cyclomatic Complexity”, this metric defines the number of linearly independent
paths through a program’s source code: the higher the metric, the higher is the number of paths a piece of code
This means that a higher number of paths takes into account a higher number of conditions and decisions and when
such number becomes too high, the code becomes hard to maintain.
The maximum complexity suggested is 10, although sometimes it’s good to relax such metric to a maximum of 15.
When the cyclomatic complexity becomes higher than the maximum value, it is suggested to split the module into
Your IDE, if advanced enough, should already be able to warn you of a high cyclomatic complexity.
Pitfall Warning!
far from a “silver bullet” that will suit all your needs, but as all other metrics, it can
Advanced Wizardry!
This section contains the technical explanation on how to calculate cyclomatic com-
plexity. If you’re not interested in this, feel free to gloss over this section.
As people say, an example is worth a thousand words, so let’s take the following UML activity diagram, that represents
a simple program (I made it a bit more complex for the sake of demonstration).
a=input()
yes no
a == 0
yes no
a % 2 == 0
b = "zero"
b = "even" b = "odd"
return b
Figure 135: UML of the program which we’ll calculate the cyclomatic complexity of
First of all, we need to convert it into the corresponding flow diagram, which usually means eliminating the start
nodes and merge nodes used by UML. The result should look something like the following:
a=input()
a == 0
b='zero' a % 2 == 0
b='even' b='odd'
return b
Figure 136: Flow diagram of the program we’ll calculate the cyclomatic complexity of
• The number of “nodes”: that is the number of boxes and diamonds in our flow diagram. In our case it is 7.
• The number of “edges”: that is the number of arrows that connect the nodes in our flow diagram. In our case
it is 8.
• The number of “exit points”: usually that is the number of stop nodes in our UML diagram, in our flow diagram
Usually a complexity lower than 15 is considered OK, but also the lower the better.
When you have a test suite, you may already be thinking about a metric that tells you how much of your code is
tested. Well, here it is: the code coverage metric tells you what percentage of your code base has been run when
That is both the useful and damaging part of this metric: code coverage doesn’t tell you how well your code is
tested, just how much code was executed, so it’s easy to incur into what I like to call “incidental coverage”: the
code coverage presents a higher value, when the code is merely “executed” and not thoroughly “tested”.
• Branch Coverage: defines which branches (as in portions of the if/else and “switch” statements) are exe-
cuted;
This is also why it’s better to prepare unit tests first, and delay the integration tests for a while.
Code Smells is a blanket term representing all the common (and thus known) mistakes done in a certain programming
language, as well as bad practices that can be fixed more or less easily.
Some of these smells can be automatically detected by static analysis programs (sometimes called Linters), others
may require dynamic execution, but all code smells should be solved at their root, since they usually entail a deeper
problem.
• Duplicated Code;
• Mutating Variables;
• God Objects;
• Long Methods;
When you are collaborating with someone, it is absolutely vital to enforce a coding style, so that everyone in the
team is able to look at everyone else’s code without having to put too much effort into it.
Coding style can be enforced via static analysis tools, when properly configured.
Counting (automatically) the number of coding style infractions can help you estimate how much effort working on
the code is necessary, thus you would be able to foresee slowdowns in the development process.
Some people say that inheritance is evil and should be avoided, some other say it’s good. As with all things, in
medio stat virtus (virtue stands in the middle), sometimes inheritance is better left where it is, other times its usage
The depth of inheritance metric tells us how deep the inheritance hierarchy is, thus this metric will tell the us the
strength of one of the possible dependency types. The deeper the inheritance, the more dependencies we have,
which means that we have more classes that, if edited, will change the behavior of the “children classes”.
It’s better having a short inheritance depth, (although it’s not necessarily wrong) having a longer chain of dependen-
cies might mean we have a structural problem, where some classes are “too generic” and at the top of the hierarchy
Let’s talk numbers: having too many methods or fields in a class can be an indicator of a so-called “god object”:
an object that has too many responsibilities under its wing (does too many things), this is a breach of the single
We can fix this by splitting the class into smaller classes, each with its own single responsibility.
A high number of local variables instead may point to a complexity issue: your algorithm may be more complex than
This metric is specific for functions, when a function has a lot of parameters, it’s harder to call and harder to under-
stand. Functions should have no more than 5 parameters in most cases, more and it will be complex.
Some automated tools in your IDE may be able to warn you in case methods and functions have too many parame-
ters.
To solve this issue, you may need to review the function (maybe it has too many responsibilities?) or pass a so-called
The metrics listed above are not the only ones available to you, some IDEs have aggregated metrics (like the “main-
tainability index” in Visual Studio), while there may be other metrics you want to measure, some follow:
• Lead Time: Time elapsed between the start and end of a process (may be a ticket, or a task);
• MTBF: (Mean Time Before Failure) represents the mean time before the software crashes;
• Crash Rate: The number of times a software crashes, over the number of times it’s used.
If you don’t know where you are going. How can you expect to get there?
Basil S. Walsh
One of the most discussed things in the world of Game Development is the so-called “GDD” or “Game Design
Document”. Some say it’s a thing of the past, others swear by it, others are not really swayed by its existence.
Being an important piece of any software development process, in this book we will talk about the GDD in a more
flexible way.
The Game Design Document is a Body Of Knowledge that contains everything that is your game, and it can take
• A Wiki[g] ;
• A Kanboard[g] ;
The most important thing about the GDD is that it contains all the details about your game in a centralized and
It is not a technical document, but mostly a design document, technical matters should be moved to a dedicated
Each game can have its own attributes, so each Game Design Document can be different, here we will present some
of the most common sections you can include in your own Game Design Document.
This section is used to give the reader a quick description of the game, its genre (RPG, FPS, Puzzle,…), the type of
demographic it covers (casual, hardcore, …). Additional information that is believed to be important to have a basic
This game design document describes the details for a 2D side scrolling platformer game where the player
makes use of mechanics based on using arrows as platforms to get to the end of the level.
The game will feature a story based on the central America ancient culture (Mayan, Aztec, …).
The name is not defined yet but the candidate names are:
7.2.2 Characters
If your game involves a story, you need to introduce your characters first, so that everything that follows will be
clear.
Ohm is the main character, part of the group called “The Resistance” and fights for restoring the electrical
Fad is the main side character, last survivor and heir of the whole knowledge of “The Capacitance” group.
Gen. E. Rator is the main antagonist, general of “The Reactance” movement, which wants to conquer the
circuit world.
If your game does not include a story, you can just avoid inserting this section altogether.
7.2.3 Storyline
After introducing the characters, it’s time to talk about the events that will happen in the game.
It has been 500 mega-ticks that the evil Rator and the reactance has come to power, bringing a new era of
After countless antics by the evil reactance members, part of the circuit world’s population united into what
Strong of thousands of members and the collaboration of the Capacitance, the resistance launched an attack
against the evil reactance empire, but the empire stroke back with a carpet surcharge attack, decimating
the resistance and leaving only few survivors that will be tasked to rebuild the resistance and free the world
This is when a small child, and their parents were found. The child’s name, Ohm, sounded prophetic of a
As with the Characters section, if your game does not include a story, you can just skip this section.
When people read the design document, it is fundamental that the game’s theme is quickly understood: it can be
a comedy-based story, or a game about hardships and fighting for a better future, or maybe it is a purely fantastic
This is a game about fighting for a better future, dealing with hardships and the deep sadness you face when
This game should still underline the happiness of small victories, and give a sense of “coziness” in such small
If you feel that this section is not relevant for your game, you can skip it.
7.2.3.2 Progression
After defining the story, you should take care of describing how the story progresses as the player furthers their
An example:
The game starts with an intro where the ruined city is shown to the player and the protagonist receives their
The first levels are a basic tutorial on movement, where the shaman teaches the player the basic movement
patterns as well as the first mechanic: staff boosting. Combat mechanics are taught as well.
After the tutorial has been completed, the player advances to the first real game area: The stone jungle.
In this section we will define how levels are constructed and what mechanics they will entail, in detail.
The First Level (Tutorial) is based in a medieval-like (but adapted to the center-America theme) training camp,
outside, where the player needs to learn jumping, movement and fight straw puppets. At the end of the basic
fighting and movement training, the player is introduced to staff boosting which is used to first jump to a
ledge that is too high for a normal jump, and then the mechanic is used to boost towards an area too far
Some level artwork can be included in this section, to further define how the levels will look and feel.
7.2.5 Gameplay
This section will be used to describe your gameplay. This section can become really long, but do not fear, as you
7.2.5.1 Goals
This question should be answered in this section. Here you insert the goals of your game, both long and short term.
Optional Long Term Goal: Restore the circuit world to its former glory.
• Neutralize Enemies
In this section, you describe the core game mechanics that characterize the game, extensively. There are countless
resource on how to describe game mechanics, but we’ll try to add an example here below.
The game will play in the style of the well-known match-3 games. Each match of 3 items will add some points
to the score, and new items will “fall” from a randomly chosen direction every time.
Every time an “L” or a “T” match is performed, a special item of a random color will be generated, when a
match including this item is made, all the items in the same row and column will be deleted and bonuses will
be awarded.
Every time a match with 4 items in a row is performed, a special item of a random color will be generated,
when a match including such item is made, all items in a 3x3 grid centered on the item will be deleted and
Every time a match with 5 items in a row is performed, a special uncolored item will be generated, this can
In case the 5-item special is matched with any other special item, the whole game board will be wiped and
7.2.5.3 Skills
Here you will describe the skills that are needed by the users in order to be able to play (and master) your game.
This will be useful to assess your game design and eventually find if there are some requirements that are too high
for your target audience; for instance asking a small child to do advanced resource management could be a problem.
This will also help deciding what the best hardware to use your game on could be, for instance if your game requires
precise inputs for platforming then touch screens may not be the best option.
The user will need the following skills to be able to play the game effectively:
7.2.5.4 Items/Powerups
After describing the basic game mechanics and the skills the user needs to master to be able to play the game
effectively, you can use this section to describe the items and powerups that can be used to alter the core gameplay.
For example:
The player can touch a globular light powerup to gain invincibility, every enemy that will touch the player
Red (incendiary) arrows can be collected through the levels, they can get shot and as soon as they touch the
In this section you describe all items that can be either found or bought from an in-game store or also items derived
from micro-transactions. In-game currency acquisition should be mentioned here too, but further detailed in the
monetization section.
This section can be used to manage how the game gets harder and how the player can react to it. This will expand
This section is by its own nature quite subjective, but describing how the game progresses helps a lot during the
The game will become harder by presenting tougher enemies, with more armor, Health Points and attack. To
overcome this difficulty shift, the player will have to create defense strategy and improve their dodging, as
well as leveling up their statistics and buy better gear from the towns’ shops.
In the later levels, enemies will start dodging too, and will also be faster. The player will need to improve
their own speed statistic to avoid being left behind or “kited” by fast enemies.
As the game progresses, the player will need to acquire heavy weapons to deal with bigger bosses, as well
This section is good if you want to talk about unlocking new missions/maps/levels too.
Many times we focus so much on how the player will get to the end of the game that we absolutely forget how the
Losing conditions must be listed and have the same importance of the winning conditions, since they add to the
A possible example of how a “losing conditions” section could be written is the following:
An interesting idea could be having an “endings” section inside your game, where all endings (both good, bad and
neutral) are listed, encouraging the player to pull themselves out from the “losing condition” that is a bad ending.
Here we describe the ideas on how the game will look like. Describing the graphic style and medium.
This is a 2D side scroller with a dark theme, the graphics should look gloomy and very reminiscing of a circuit
board.
The graphical medium should be medium-resolution pixel art, allowing the player’s imagination to “fill in” the
Sadly, in way too many games, music and sound is an afterthought. A good soundtrack and sound effect can really
In this section we can describe in detail everything about Music and Sound Effects, and if the section becomes hard
Music should be based on the glitch-hop style, to complement the electronic theme. 8 or 16-bit style sounds
Lots of sound effects should be used to give the user positive feedback when using a lever to open a new
part of the level, and Extra Lives/1UP should have a jingle that overrides the main music.
In this section we will describe everything that concerns the User Interface: menus, HUD, inventories and everything
that will contribute to build the user experience that is not strictly tied to the gameplay.
This is especially important in games that make heavy use of menus, like turn-based strategy games or survival
The game will feature a cyberpunk-style main menu, looking a lot like an old green-phosphor terminal but
with a touch of futurism involved. The game logo should be visible on the left side, after a careful conversion
into pixel-art. On the right, we see a list of buttons that remind old terminal-based GUIs. On the bottom of
the screen, there should be an animated terminal input, for added effect.
Every time a menu item is highlighted or hovered by the mouse, the terminal input will animate and write a
command that will tie to the selected menu voice, such as:
The HUD display should remind a terminal, but in a more portable fashion, to better go with the “portability”
of a wrist-based device.
It’s a good idea to add some mock designs of the menu in this section too.
In this section you insert everything that concerns the way the game controls, eventually including special periph-
This will help you focusing on better implementing the input system and limit your choices to what is feasible and
The game will control mainly via mouse and keyboard, using the mouse to aim the weapon and shoot and
Alternatively, it’s possible to connect a twin-stick gamepad, where the right stick moves the weapon crosshair,
while the left stick is used to move the character, one of the back triggers of the gamepad can be configured
to shoot.
If the gamepad is used, there will be a form of aim assistance can be enabled to make the game more
Here you can add all the options that are used to allow more people to access your game, in more ways than you
think.
The game will include a “colorblind mode”, allowing the colors to be colorblind-friendly: such mode will
Additionally, the game will include an option to disable flashing lights, making the game a bit more friendly
The game will support “aim assistance”, making the crosshair snap onto the enemy found within a certain
In order to assist people who have issues with the tough platforming and reaction times involved, we will
include the possibility to play the game at 75%, 50% and 25% speed.
7.2.11 Tools
This section is very useful for team coordination, as having the same toolkit prevents most of the “works for me”
situations, where the game works well for a tester/developer while it either crashes or doesn’t work correctly for
others.
This section is very useful in case we want to include new people in our team and quickly integrate them into the
project.
In this section we should describe our toolkit, possibly with version numbers included (which help reducing incom-
patibilities), as well as libraries and frameworks. The section should follow the trace below:
The tools and frameworks used to develop the game are the following:
7.2.12 Marketing
This section allows you to decide how to market the game and have a better long-term plan on how to market your
Carefully selecting and writing down your target platforms and audience allows you to avoid going off topic when it
Knowing who is your target audience helps you better suit the game towards the audience that you are actually
targeting.
Gender: Everyone
Here you describe the launch platforms, as well as the platforms that will come into the picture after the game
• PC
• Playstation 4
• Nintendo Switch
• XBox 360
After working on all the ports, we may consider porting the game to mobile platforms like:
• Android 9.0 +
• iOS 11.0 +
7.2.12.3 Monetization
In this optional section you can define your plans for the ways you will approach releasing the game as well as
For example:
Monetization efforts will be focused on selling the game itself at a full “indie price” and further monetization
The eventual mobile versions will be given away for free, with advertisements integrated between levels. It
is possible for the user to buy a low-price paid version to avoid seeing the advertisements.
Internationalization and Localization are a matter that can make or break your game, when it comes to marketing
Due to political and cultural reasons, for instance you shouldn’t use flags to identify languages. People from territories
inside a certain country may not be well accepting of seeing their language represented by the flag of their political
adversaries.
Another example could be the following: if your main character is represented by a cup of coffee, your game could
Internationalization Making something accessible across different countries without major changes to its content
Localization Making something accessible across different countries, considering the target country’s culture.
• English
• Italian
• Spanish
• German
• French
This is another optional section where you can use as a “idea bin”, where you can put everything that you’re not
sure will ever make its way in the game. This will help keeping your ideas on paper, so you won’t ever forget them.
• User-made levels
• Achievements
This chapter represents only a guideline on what a Game Design Document can be, feel free to remove any sections
that don’t apply to your current project as well as adding new ones that are pertinent to it.
A Game Design Document is a Body of Knowledge that will accompany you throughout the whole game development
process and it will be the most helpful if you are comfortable with it and it is shaped to serve you.
Anonymous
Animations and movies are an illusion, and so are games. Games and movies show still images tens of times per
Any game and its menus can be abstracted into 3 main operations that are performed one after the other, in a loop:
3) Display (Draw) the updated world (or again, menu) to the screen
Preparation work
Game Loop
Process Input
Draw Screen
yes
game is still running?
no
Clean up
1 void game () {
2 bool game_is_running = t r u e ;
3 while ( game_is_running ){
4 process_user_input () ;
5 update_world () ;
6 draw () ;
7 }
8 }
This abstraction will become really useful when dealing with many rows of code and keeping it neatly organized.
8.2 Input
Some frameworks may be able to further abstract how they process input by giving an API[g] that allows to make
use of events.
Most of the time, events will be put in a queue that will be processed separately. This way it’s easier to program how
to react to each event and keep our code neatly organized. The downside is that the performance of an event-driven
input processing is directly tied to how many events are triggered: the more events are triggered, the longer the
This usually depends on the implementation of the event queue: an event queue is less wasteful in terms of resources
and allows for less coupled code, but the queue could be cluttered with events we’re not interested in (for instance
mouse movement events in a game that uses only keyboard for controls) so we need to take the time to configure
Note!
On the opposite side, we have so-called “real-time input”, where at a certain point of our update routine, we check for
the instantaneous status of the input peripherals and process it immediately. This allows for a faster, more reactive
code and to apply some different logic (for instance pressing left and right on the keyboard can be coded to make
the character stop). Besides being more immediate, this system shares a lot of traits with “polling” which can be
Again, a well-implemented and well-configured event-based system should feel no different from real-time input,
with the advantage of having better performance and having less code coupling.
When it comes to anything that remotely relates to physics (that includes video games), we need to set the relation
to time in our loop. There are many ways to set our delta time (or time steps), we’ll see some of the most common.
A time step (or delta time) is a number that will define “how much time passed” between two “snapshots” of our
world (remember, the world is updating and showing in discrete intervals, giving the illusion of movement). This
number will allow us to make our loop more flexible and react better to the changes of load and machines.
The first and simplest way is to use a fixed time step, our delta time is fixed to a certain number, which makes the
• The PC is powerful enough to make our game work well, 100% of the time
1
An example of fixed time step loop can be the following (assuming 60 frames per second or dt = 60 ):
1 // ...
2 f l o a t dt = 1.0/60.0;
3 bool game_is_running = t r u e ;
5 while ( game_is_running ) {
6 process_user_input () ;
7 update_world ( dt );
8 draw () ;
9 }
10 // ...
Everything is great, until our computer starts slowing down (high load or just not enough horsepower), in that case
This means that every time the computer slows down, even for a microsecond, the game will slow down too, which
can be annoying.
Note!
A similar problem can apply between different computers: if computer A can run the
game at 30fps maximum, while computer B will run at 120fps (and we don’t account for
that), using fixed timesteps the game will run 4 times as fast on computer B.
A way to limit the issues given by a fixed time step approach is to make use of variable time steps, which are simple
The secret is measuring how much time passed between the last frame and the current frame, and use that value
1 bool game_is_running = t r u e ;
6 while ( game_is_running ) {
10 process_user_input () ;
11 update_world ( dt );
12 draw () ;
13 f l o a t end = get_system_time_millis () ;
14 // We update our dt
15 dt = end - begin ;
16 }
This allows to smooth the possible lag spikes, even allowing us to disable Vertical Sync and have a bit less input lag,
Since the delta time now depends on the speed of the game, the game can “catch up” in case of slowdowns; that
can result in a slightly different feeling, depending on the framerate, but if there is a really bad slowdown dt can
become really big and break our simulation, and collision detection will probably be the first victim.
Also this method can be a bit harder to manage, since every movement will have to be scaled with dt.
This is a special case, where we set an upper limit for our time steps and let the update loop execute as fast as
possible. This way we can still simulate the world in a somewhat reliable way, avoiding the dangers of higher spikes.
1
A semi-fixed time step approach is the following (assuming 60 fps or dt = 60 ):
1 f l o a t dt = 1.0/60.0;
2 bool game_is_running = t r u e ;
7 while ( game_is_running ) {
11
14 process_user_input () ;
15 update_world ( dt );
16 frametime = frametime - deltaTime ;
17 draw () ;
18 }
19 f l o a t end = get_system_time_millis () ;
This way, if the loop is running too slow, the game will slow down and the simulation won’t blow up. The main
disadvantage of this approach is that we’re taking more update steps for each draw step, which is fine if drawing
takes more than updating the world. If instead the update phase of the loop takes more than drawing it, we will
We can call it a “spiral of death”, where the simulation will take Y seconds (real time) to simulate X seconds (of game
time), with Y > X, being behind in your simulation makes the simulation take more steps, which will make the
simulation fall behind even more, thus making the simulation lag behind more and more.
Frame limiting is a technique where we aim for a certain duration of our game loop. If an iteration of the game loop
is faster than intended, such iteration will wait until we get to our target loop duration.
1
Let’s again consider a loop running at 60fps (or dt = 60 ):
3 f l o a t targetTime = 1.0/60.0;
4 bool game_is_running = t r u e ;
9 while ( game_is_running ) {
12 f l o a t begin = get_system_time_millis () ;
13 process_user_input () ;
14 update_world ( dt );
15 draw () ;
16 f l o a t end = get_system_time_millis () ;
17 // We update our dt
18 dt = end - begin ;
19 sleep ( std :: max ( targetTime - dt , 0) );
20 }
Even if the frame is limited, it’s necessary that all updates are tied to our delta time to work correctly. With this loop
the game will run at most at 60 frames per second, if there is a slowdown the game will slow down under 60 fps, if
A common solution used when a frame takes longer to update and render than the target time is using the so-called
“frame dropping”. The game won’t render the next frame, in an effort to “catch up” to the desired frame rate.
Higher budget (AAA) games don’t usually use a variation of the “classic” game loop, but instead make use of the
capabilities of newer hardware. Using multiple threads (lines of execution) executing at the same time, making
Multi-threaded loops are created in a way that separates the input-update part of the game loop from the drawing
part of it. This way the update thread can take care of updating our simulation, while the drawing/rendering loop
The catch is that we can’t just wait for the input-update thread to finish before rendering, that wouldn’t make it
quicker than just using a one-threaded game loop: instead we make the rendering thread “lag behind” the input-
update thread by 1 frame - this way while the input-update thread takes care of the frame number n, the drawing
thread will be rendering the prepared frame number n − 1.
Thread
Updating 1 2 3 4 5 6
Rendering 1 2 3 4 5
This 1-frame difference between updating and rendering introduces lag that can be quantified between 16.67ms (at
60fps) and 33.3ms (at 30fps), which needs to be added with the 2-5 ms of the LCD refresh rate, and other factors that
can contribute to lag. In some games where extreme precision is needed, this could be considered unacceptable,
In this section we have a little talk about some common issues related to the game loop and its timing, and some
possible solutions
Screen tearing is a phenomenon that happens when the “generate output” stage of the game loop happens in the
This makes it so that a part of the drawn frame shows the result of an output stage, while another part shows a more
updated version of the frame, given by a more recent game loop iteration.
A very common fix for this phenomenon is double buffering, where two color buffers are used. While the first is
shown on screen, the game loop updates and draws on the second color buffer.
When comes the time to draw the color buffer on screen, an operation called “flipping” is performed, where the
second color buffer is shown on screen, so that the game loop can draw on the first color buffer.
To make the game even smoother, a technique called “triple buffering” can be used, which adds a third color buffer
is used to make the animation smoother at the cost of a higher input lag.
When drawing to screen, the greatest majority of games make use of what is called the “painter’s algorithm”, which
If we divide each “layer” we can see how the painter’s algorithm works:
Just like a real painter, we draw the background items before the foreground ones, layering each one on top of
the other. Sometimes games make use of priority queues to decide which items to draw first, other times game
developers (usually under the time constraints of a game jam) just hard-code the draw order.
Special note about clearing the screen: this is an operation that sometimes may look useless but, like changing the
canvas for a painter, clearing the screen (or actually the “buffer” we’re drawing on) avoids a good deal of graphical
glitches.
Figure 140: How not clearing the screen can create glitches
In the previous image, we can see how a black screen with only a FPS counter can end up drawing all kinds of
glitches when the screen buffer is not cleared: we can clearly see the FPS counter, but the rest of the screen should
be empty, instead the GPU is trying to represent residual data from its memory, causing the glitches.
Figure 141: Another type of glitch created by not clearing the screen
If you forget to clear your screen or set a background every frame, the old buffer data will remain on screen, creating
William Whewell
• Collision Detection: you find out which game objects collided with each other;
• Collision Reaction: you handle the physics behind the collision detected, making the game objects react to
such collision.
Collisions don’t only happen between game objects (two fighters hitting each other), but also between a character
and the world (or they would end up just going through the ground).
In this section we’ll talk about some ways you can detect and react to collisions.
Collision detection algorithms can be quite costly, even more when you are using a brute force approach, but it’s
possible to have a more precise collision detection at a lower cost by combining different collision detection algo-
rithms.
The most common way to apply a multi-pass collision detection is by dividing the process in a “broad” and a “fine”
pass.
The broad pass can use a very simple algorithm to check for the possibility of a collision, the algorithms used are
When the simpler algorithm detects the possibility of a collision, a more precise algorithm is used to check if a
collision really happened, usually such finer algorithms are computationally expensive and will benefit from the first
Note!
In this chapter we’ll see the easier narrow-pass detection first, followed by the more
complex broad-pass algorithms, but remember that a good collision detection system
First of all, we need to see how we can make sure that two objects really collide with each other.
Sometimes this presents a (quite common) problem when it comes to precision: computers have no knowledge of
infinity (due to their finiteness, see computers are (not) precise). This means that we may need to give some leeway
and define an “acceptable error” in our calculations, thus we will create a “small enough value” (which in math is
represented by the Greek letter “epsilon”: ϵ) and change our algorithms accordingly.
This is the simplest case: points are mono-dimensional objects, and the only way two points can collide is when they
3 return true ;
4 } else {
5 return f a l s e ;
6 }
7 }
3 }
Since numbers in computers can be really precise, a collision between two points may be a bit too precise, so it
could prove useful to have a “buffer” around the point, so that we can say that the two points collided when they’re
In this case, it may prove to be a lot more useful to do a point vs circle detection, or even a circle vs circle collision
If instead you want to use a different method that doesn’t involve square roots, you can use epsilon values to have
an approximation of the collision. In this case the collision area won’t be round, but square.
7 }
Now a circle comes into the mix, a circle has two major characteristics: a center and a radius.
We can see that the distance between the center of a circle and our point can be expressed with a formula:
d=r+x
Where r is the circle radius and x is the difference of the distance between the center of the circle and the point
x=d−r
x≤0⇔d−r ≤0⇔d≤r
A point is considered inside of a circle when the distance between the point and the center of the circle is
So we need a function that calculates the distance between two points, and then use it to define if a point is inside
a circle.
3 s t r u c t Circle {
7 };
8
12 }
13
16 return true ;
17 } else {
18 return f a l s e ;
19 }
20 }
3 s t r u c t Circle {
4 Point center ;
5 i n t radius ;
6 };
7
11 }
12
15 }
Although slightly more heavy, computation-wise, this algorithm still runs in O(1).
Let’s add another circle into the mix now, and think in more or less the same way as before:
r1 x r2
We can see the distance between the center of the circles as expressed with the following formula:
d = r1 + x + r2
x = d − (r1 + r2 )
As before, our x can be negative, which means that the circles are colliding if x ≤ 0, which means:
x ≤ 0 ⇔ d − (r1 + r2 ) ≤ 0 ⇔ d ≤ r1 + r2
Two circles are colliding when the distance between their centers is less or equal the sum of their radii
3 s t r u c t Circle {
7 };
8
12 }
13
16 return true ;
17 } else {
18 return f a l s e ;
19 }
20 }
3 s t r u c t Circle {
7 };
8
12 }
13
16 }
Again, this algorithm performs a number of operations that is constant, so it runs in O(1).
This is one of the most used types of collision detection used in games: it’s a bit more involved than other types of
collision detection, but it’s still computationally easy to perform. This is usually called the “Axis Aligned Bounding
To know if we may have a collision, we need to check if one of the sides is “inside” (that means between the top and
In this case we know that the “top side” of the second rectangle (highlighted in blue) has a y coordinate between
the first rectangle’s top and bottom sides’ y coordinates (highlighted in red).
Though this is a necessary condition, this is not sufficient, since we may have a situation where this condition is
This has to happen for all four sides of one of the rectangle.
Now we can try putting down a bit of code, we’ll assume that rectangles are defined by their top-left corner (as
1 s t r u c t Point {
2 // Rewritten as a memo
3 int x;
4 int y;
5 };
6
7 s t r u c t Rectangle {
8 Point corner ;
9 i n t width ;
10 i n t height ;
11 };
12
19 } else {
20 return f a l s e ;
21 }
22 }
• The left side of rectangle A is at the left of the right side of rectangle B;
• The right side of rectangle A is at the right of the left side of rectangle B;
The best way to understand this algorithm properly is to test it by hand and convince yourself that it works.
This is a very light algorithm but can quickly become heavy on the CPU when there are many objects to check for
collision. We’ll see later how to limit the number of checks and make collision detection an operation that is not as
We can represent a segment by using its two extreme points, which proves to be a quite inexpensive way to represent
a line (it’s just two points). Now how do we know if a point is colliding with a line?
Every triangle can be represented with 3 points, and there is a really useful theorem that we can make use of:
The sum of the lengths of any two sides must be greater than, or equal, to the length of the remaining side.
AB + BC ≤ AC
AC + BC ≤ AB
AB + AC ≤ BC
What is more interesting to us is that when the one of the vertices of the triangle is on its opposite side, the triangle
degenerates:
AC + BC = AB
So we can calculate the distance between the point and each of the two extremes of the line and we know that when
the sum of such distances is equal to the length of the line, the point will be colliding with the line.
2 s t r u c t Point {
3 int x;
4 int y;
5 };
6
7 s t r u c t Line {
8 Point A;
9 Point B;
10 };
11
15 }
16
27 return true ;
28 } else {
29 return f a l s e ;
30 }
31 }
It could prove useful to put a “buffer zone” in here too, so that the collision detection doesn’t result too jerky and
precise. In that case you may want to take a look at the line vs circle algorithm, in that case the radius would be the
As in the previous paragraph, we memorize a line as a pair of Points, so checking if the circle collides with either end
1 s t r u c t Point {
2 int x;
3 int y;
4 };
5
6 s t r u c t Line {
7 Point A;
8 Point B;
9 };
10
11 s t r u c t Circle {
12 Point center ;
13 i n t radius ;
14 };
15
16 // ...
17
22 return true ;
23 }
24 // ...
25 }
Now our next objective is finding the closest point on the line to the center of our circle. The details and demon-
strations on the math behind this will be spared, just know the following:
Given a line AB between points A = (x1 , y1 ) and B = (x2 , y2 ) and a point P = (xk , yk ), the point on the line
closest to P has coordinates:
x = x1 + u · (x2 − x1 )
y = y1 + u · (y2 − y1 )
With:
We need to be careful though, cause this formula gives us the point for an infinite line, so the point we find could be
outside of our line. We will use the line/point algorithm to check for that.
After we made sure the point is on the line, we can measure the distance between such point and the center of our
circle, if such distance is less than the radius, we have a hit! (Or just apply the circle/point collision algorithm again).
3 s t r u c t Point {
4 int x;
5 int y;
6 };
7
8 s t r u c t Line {
9 Point A;
10 Point B;
11 };
12
13 s t r u c t Circle {
14 Point center ;
15 i n t radius ;
16 };
17
21 }
22
24 // ...
25 }
26
28 // ...
29 }
30
36 return true ;
37 }
38 // We pre - calculate "u ", we 'll use some variables for readability
39 i n t x1 = line . A.x;
40 i n t x2 = line . B.x;
42 i n t y1 = line . A.y;
43 i n t y2 = line . B.y;
48 f l o a t y = y1 + u * ( y2 - y1 );
49 // " Reuse ", we 'll use some older functions , let 's create a point , with the coordinates we
found
50 Point P;
51 P.x = x;
52 P.y = y;
53 // Let 's check if the " closest point " we found is on the line
54 if (! line_point_collision ( line , P)) {
55 // If the point is outside the line , we return false , because the ends have already been
checked against collisions
56 return f a l s e ;
57 } else {
58 // Let 's Reuse the Point / Circle Algorithm
59 r e t u r n circle_point_collision ( circle , P);
60 }
61 }
If we want to see if a point collides with a rectangle is really easy, we just need to check if the point’s coordinates
rectheight ){
2 // We check if the point is inside the rectangle
3 r e t u r n x1 >= rectx && x1 <= rectx + rectwidth && y1 >= recty && y1 <= recty + rectheight ;
4 }
A possible way to define if a point is inside a triangle, we can use a bit of geometry.
We can use Heron’s formula to calculate the area of the original triangle, and compare it with the sum of the areas
created by the 3 triangles made from 2 points of the original triangle and the point we are testing.
If the sum of the 3 areas (represented in different colors in the figure) equals to the original calculated area, then
3 bool point_triangle_collision ( f l o a t px , f l o a t py , f l o a t x1 , f l o a t y1 , f l o a t x2 , f l o a t y2 , f l o a t
x3 , f l o a t y3 ){
4 f l o a t original_area = std :: abs (( x2 - x1 ) * ( y3 - y1 ) - ( x3 - x1 ) * ( y2 - y1 ));
9 return true ;
10 } else {
11 return f a l s e ;
12 }
13 }
Let’s see how we can change the algorithm to accommodate for some leeway, since the we may be requiring too
much precision from our algorithms. We can do that by using epsilon values.
Our main test is that the sum of the area of the 3 triangles we create (A1 , A2 , A3 ) is equal to the area of the original
A1 + A2 + A3 = A0
A1 + A2 + A3 − A0 = 0
Due to possible precision issues we know that there are some values where the equation above is not true, so we
choose a “low enough error” that we are willing to accept, for example ϵ = 0.0001, and use this test instead:
|A1 + A2 + A3 − A0 | < ϵ
−ϵ < A1 + A2 + A3 − A0 < ϵ
The code wouldn’t change much, but for sake of clarity, here it is:
3 bool point_triangle_collision ( f l o a t px , f l o a t py , f l o a t x1 , f l o a t y1 , f l o a t x2 , f l o a t y2 , f l o a t
x3 , f l o a t y3 ){
4 // We accept anything that is closer than 1/1000 th of unit
5 const f l o a t epsilon = 0.0001;
11 return true ;
12 } else {
13 return f a l s e ;
14 }
15 }
First of all we need to identify which side of the rectangle we should test against, so if the centre of the circle is to
the right of the rectangle, we will test against the right edge of the rectangle, if it’s above we’ll test against the top
After that, we just perform some math on the distances and calculated values to detect if the circle collides with the
rectangle.
3 s t r u c t Point {
4 // Rewritten as a memo
5 int x;
6 int y;
7 };
8
9 s t r u c t Rectangle {
13 i n t height ;
14 };
15
16 s t r u c t Circle {
20 };
21
29
32 // We 're at the left of the rectangle , test against the left side
33 tx = rect . corner .x;
34 } e l s e i f ( circ . center .x > rect . corner .x + rect . width ){
35 // We 're at the right of the rectangle , test against the right side
36 tx = rect . corner .y + rect . width ;
37 }
38
48 // Let 's get the distance between the testing coordinates and the circle center
49 i n t distanceX = circ . center .x - tx ;
52
53 // Note that if the center of the circle is inside the rectangle , the testing coordinates
will be the circle 's center itself , thus the next conditional will always return true
54
56 return true ;
57 }
58
61 }
Line/Line collision is quite simple to implement once you know the inner workings of geometry, but first we need to
y I
8
1 2 3 4 5 6 7 8
x
Figure 151: Example image for line/line collision
Pa = P1 + ua · (P2 − P1 )
xa = x1 + ua · (x2 − x1 )
ya = y1 + ua · (x2 − x1 )
This makes us understand that any point of line A can be represented by its starting point P1 , plus a certain fraction
This also means that 0 ≤ ua ≤ 1, else the point won’t be on the segment.
Pb = P3 + ub · (P4 − P3 )
which becomes:
xb = x3 + ub · (x4 − x3 )
yb = y3 + ub · (x4 − x3 )
The two lines will collide when Pa = Pb , so we get the following equations:
x1 + ua · (x2 − x1 ) = x3 + ub · (x4 − x3 )
y1 + ua · (y2 − y1 ) = y3 + ub · (y4 − y3 )
ua = (x4 −x3 )·(y1 −y3 )−(y4 −y3 )·(x1 −x3 )
(y4 −y3 )·(x2 −x1 )−(x4 −x3 )·(y2 −y1 )
ub = (x2 −x1 )·(y1 −y3 )−(y2 −y1 )·(x1 −x3 )
(y4 −y3 )·(x2 −x1 )−(x4 −x3 )·(y2 −y1 )
Substituting either of the results in the corresponding equation for the line will give us the intersection point (which
• If the denominator for the equations for ua and ub equals to zero, the two lines are parallel
• If both the numerator and denominator for ua and ub are equal to zero, the two lines are coincident
1 bool lineLineCollision ( f l o a t x1 , f l o a t y1 , f l o a t x2 , f l o a t y2 , f l o a t x3 , f l o a t y3 , f l o a t x4 ,
f l o a t y4 ){
6 i f ( den == 0) {
9 }
10
11 f l o a t uA = (( x4 - x3 ) * ( y1 - y3 ) - ( y4 - y3 ) * ( x1 - x3 )) / den ;
12 f l o a t uB = (( x2 - x1 ) * ( y1 - y3 ) - ( y2 - y1 ) * ( x1 - x3 )) / den ;
13
17 }
18
21 }
This collision detection algorithm can be useful for line-based puzzle games, line the untangle puzzle.
Given the previous explanation about the Line/Line collision detection, it’s quite easy to build a Line/Rectangle
algorithm; distinguishing the cases where we want to account for a segment being completely inside of a rectangle
or not.
1 bool lineLineCollision ( f l o a t x1 , f l o a t y1 , f l o a t x2 , f l o a t y2 , f l o a t x3 , f l o a t y3 , f l o a t x4 ,
f l o a t y4 ){
rectheight ){
6 // our previous implementation of a point / rectangle collision detection
7 }
8
f l o a t rectwidth , f l o a t rectheight ){
15 }
16
17 // Now to test the rectangle against the line , if it 's not completely inside
18 bool left = lineLineCollision (x1 , y1 , x2 , y2 , rectx , recty , rectx , recty + rectheight );
recty + rectheight );
20 bool top = lineLineCollision (x1 , y1 , x2 , y2 , rectx , recty , rectx + rectwidth , recty );
, recty + rectheight );
22
26 }
27
30 }
This can prove useful to test for “line of sight” inside an AI algorithm.
Here we are, the most complex matter when it comes to narrow-phase collision detection: detecting collisions
Note!
In this book we will focus on convex polygons “without holes”, which is the most com-
First of all, we will start by talking about some theorems and requirements that will help us on the way to build a
Let’s imagine a plane, like our 2D screen: if we draw a non-self-intersecting, continuous loop in the plane we obtain
a Jordan Curve. This curve separates the plane in two distinct regions: the “inside” and the “outside”.
Inside
Outside
Any non-self-intersecting polygon (be it convex or non-convex) can be seen as a Jordan curve, this means that we
can easily identify (programmatically) if a point is inside or outside the polygon. At least in the “convex” case.
Let’s take a convex polygon, and a point inside such polygon: we can see that if we choose a point outside the
polygon (non-colliding) we can strike a line between the “inside point” and the chosen point, and such line will
intersect one of the polygon’s edges. This gives us an idea on how to check for “point vs. polygon”.
Q
Figure 153: A simple case where a point is outside the polygon
This is all well and good, but we have two problems on hand:
Let’s leave the first problem aside, since talking about it may end up being confusing and just empty talk (or writing,
If we have a non-convex polygon, we may end up with a line that intersects the polygon’s perimeter even if the point
is colliding:
P Q2
Q1
Figure 155: How a non-convex polygon makes everything harder
Here we call P the “point inside the polygon” while Q1 and Q2 are the points we are testing: as we can see Q2
triggers our “non-colliding” test even though it is inside the polygon.
Can you see what can help us solving this issue? I’m sure you have a number of ideas in mind, we’ll talk about it in
As you can see, as simple as it can be, the Jordan curve theorem poses some problems that may be a bit out of our
reach as of now, so let’s try to find a less ideal but easier to understand solution.
Let’s now limit ourselves to convex polygons, which (again) is the most common situation.
We can take inspiration from 3D graphics, where any solid shape (and thus the polygons that make those up) are
decomposed to a bunch of triangles. Nothing stops us from doing the same and taking any polygon and decomposing
This specific triangulation is called “fan triangulation” and it is chosen for its Θ(n) (where n is the number of vertices)
execution time.
Before making our poor CPU undertake big calculations, we may want to check if there is even a possibility of a
The great majority of the lifetime of our game objects is spent not colliding with anything, so if we can easily exclude
a collision before starting complex algorithms, our game will just benefit from it.
We can take our complex polygon and give it a “bounding box”, any point that is inside such box has a possibility of
colliding with our polygon, but any point outside the bounding box surely will not collide.
Tip!
Thanks to how rectangles work, we can just use the points A and C to build a rectangle:
since they contain all 4 coordinates, we can infer B and D from them.
This is simple to achieve: we just need to loop over all the vertices and find our coordinates. The algorithm here
below:
1 s t r u c t Point {
2 // Rewritten as a memo
3 int x;
4 int y;
5 };
6
7 c l a s s Rectangle {
8 Point corner ;
9 i n t width ;
10 i n t height ;
11 // ...
12 s t a t i c Rectangle from_points ( Point topleft , Point bottomright ){
13 // ...
14 }
15 // ...
16 };
17
27 xmin = vertex [i ]. x;
28 }
29 i f ( vertex [ i ]. x > xmax ){
30 xmax = vertex [i ]. x;
31 }
32 i f ( vertex [ i ]. y < ymin ){
33 ymin = vertex [i ]. y;
34 }
35 i f ( vertex [ i ]. y > ymax ){
36 ymax = vertex [i ]. y;
37 }
38 }
39 // Now we can build the needed points for the bounding box
40 A = Point () ;
41 C = Point () ;
42 A.x = xmin ;
43 A.y = ymin ;
44 C.x = xmax ;
45 C.y = ymax ;
46 // We build our bounding box
47 boundingBox = Rectangle . from_points (A , C) ;
48 // and return it
49 r e t u r n boundingBox ;
50 }
To check if the collision “may happen”, we can just use a simple Point vs Rectangle collision check.
Finally, after all the math and preparations, we can start working towards our collision detection algorithm.
Pitfall Warning!
This algorithm works only with convex polygons that have no holes, also it probably is
not the most efficient way to check for collisions between a point and a polygon.
This is more akin to an exercise in creativity and less about “notions”: we found a
simple solution to a complex problem. Even if it is not the most efficient, it may be
“efficient enough”.
Differently from previous classes and structures, the “polygon” class will need a little more work. This is because
First of all we need an ordered list (or array) of vertices, which will be represented by points. Secondly, we need
Pitfall Warning!
You may be tempted to memorize the “triangles” that are an output of the “fan trian-
gulation”, as well as their areas. This may be a good idea if well managed, but we
will need to take care of “moving” those triangles and manage when the polygon gets
deformed: in that case all the triangle areas will have to be recalculated.
Same goes for the bounding box, which will change in size when the polygon rotates
or deforms. In this book we will try to keep the class as generic as possible (as well as
Thirdly, we need the constructor to do some math before we can use the polygon. Finally we need to integrate a
“fanning” function.
Whew… That’s a lot of work, but here’s the code for the polygon class:
3 c l a s s Polygon {
4 private :
5 Point * vertices ;
6
7 public :
8 Rectangle calculate_bounding_box () {
9 // This function calculates the bounding box
10 // -------------------------
11 // First we create and bootstrap the variables
12 i n t xmin = vertices [0]. x;
14 /*
15 * ...