1 of 89

Game Engines

Intro + Foundations

Faculty of Mathematics and Physics

Charles University

10^th March 2022

Karel Vlachovský (based on Jakub Gemrot’s presentation)

Based on “Game Engine Architectures”

and “Game Design Patterns” books

and various inet resources

2 of 89

Game Engine�Roadmap

Various parts of a game engine architecture

focus on foundations (unique topic in the context of game dev)

Other parts

Gameplay, AI, animations, etc. - already discussed

Game Engine specific topics

Memory
Asset streaming
Timing
Jobs

3 of 89

Game Engine�Why?

WHY DO YOU NEED�(3^rd party) GAME ENGINE?

4 of 89

Game Engine�Why?

The problem

We choose particular GE for feature X
Later find that we need feature Y
But our GE is not prepared / cranky support for Y => workaround it a lot

This lecture

Get impression, what GE may consist of
Some tricks and technicalities of GE

The result

Compiling a list of questions to be answered when assessing particular GE for your game production

5 of 89

Game Engine�Why?

You are single indie

Who wants to make, e.g., 3D game and want all those nice shadows and post-processing effects

You are studio (10, 20, more people)

Who wants multiple people collaborating on a single game

In both case, you want to speed things up

The question is, would this particular Game Engine speed up your work?

6 of 89

Game Engine�What?

WHAT IS GAME ENGINE?

7 of 89

Game Engine�What?

Set of tools for easing game production

Integrated game development environment
Console tools for automating pipeline
Game agnostic (== extensible + reusable)

Feature rich
Data driven

Multi-platform

We can characterize game engines, and they are quite a few, actually a lot of them, as a set of tools for easing game production.

You might see them through prism of their editors, but during development you might actually need console tools as well

for automating your pipeline, like for instance automatic compilation and builds that you can distribute to your testers

on daily basis. But it is true that their biggest feature is usually an integrated game development environment paired

with some IDE for coding, which might sometimes be even integrated in the engine itself.

You probably expect game engine to be also game agnostic. Meaning extensible and reusable. Thought that might not always be the case

as it depends on what features and of what quality the engine is integrating.

Multiplatformity is a must today of course. Even indies are trying to target as many platforms as they can to reach broader audience.

8 of 89

Game Engine�What?

Games themselves resemble kind of engine

Due to iterative development
Think of it as a moddable game

Different aesthetics
Different storyline

Multi-platform

The problem is, that many games, once built, resembles some kind of engine because iterative development and remaking of bits here and there

is part of all game development so each game can be to a certain degrees modded to create a game of different esthetics or different storyline.

So each game and engine can be put on a hypothetical timeline where on the left side we have so rigid implementation that it cannot

Be easily changed and on the right side, we have the holy grail of game engines, something so flexible that it can be effectively used

for creating lightweight 2D platform to full-fledged 3D MMOs.

Interesting is then comparison between Quake II or III engine, Unreal Engine 4 and Unity. Each quite different, but Quake is for first-person

shooters while Unreal Engine was also built for first-person shooters originally, whereas Unity is more in game-agnostic part. But as development

of UE4 continues, it is getting more and more general.

9 of 89

Game Engine�What?

HOW DO GAME ENGINE DIFFER FROM �A FRAMEWORK OR A MIDDLEWARE?

10 of 89

Game Framework / Middleware�What?

Set of tools for easing some part of game production

No integrated development environment

Mostly oriented on programmers (set of libraries and console tools)

“One to a few subsystem(s)”
Not necessarily data driven
Not necessarily multi-platform
Middleware is not having own „execution loop“

11 of 89

Game Engine�For whom?

WHOSE WORK GAME ENGINE MUST SUPPORT?

12 of 89

Game Engine�For whom?

Game Engines are used from many perspectives

Engineers (have to efficiently code)
Artists (have to efficiently create the content)
Game designers (have to efficiently iterate ideas)

They work in tandem using Game Engine as an integrator of their work

Before diving into an engine architecture there is important remark about the different kinds of people who are working

with a game engine. That’s because game engine is not here only to support the game, but the work of game makers as well.

That is, game engine contains a lot of tools and code that is actually irrelevant to the game itself, but which is extremely

important during the game production. The program that runs the game can then be run with just a subset of the whole

game engine code base.

How easy is to work with the code base, import new content, script new game mechanics is very important aspect of

every game engine as the game can never be designed using waterfall scheme. Interactivity must be directly experienced

and is very hard if not impossible to fathom. Therefore the engine must support iterative development and ease the

cycle of designing, coding, assembling and playtesting as much as possible.

So you have engineers who need to code efficiently, artists who need to create and integrate content as fast as possible

and game designers that need to efficienty iterate their ideas. Game engine can be then seen as an integrator of their work.

13 of 89

Game Engine�For whom?

Game engine must not place excessive overhead onto create-run-play-test iterations (waterfall does not work in gamedev), which must be as short as possible

Import new content
Script new game mechanics
Immediately test in the game

Before diving into an engine architecture there is important remark about the different kinds of people who are working

with a game engine. That’s because game engine is not here only to support the game, but the work of game makers as well.

That is, game engine contains a lot of tools and code that is actually irrelevant to the game itself, but which is extremely

important during the game production. The program that runs the game can then be run with just a subset of the whole

game engine code base.

How easy is to work with the code base, import new content, script new game mechanics is very important aspect of

every game engine as the game can never be designed using waterfall scheme. Interactivity must be directly experienced

and is very hard if not impossible to fathom. Therefore the engine must support iterative development and ease the

cycle of designing, coding, assembling and playtesting as much as possible.

So you have engineers who need to code efficiently, artists who need to create and integrate content as fast as possible

and game designers that need to efficienty iterate their ideas. Game engine can be then seen as an integrator of their work.

14 of 89

Game Engine�What for?

WHAT FEATURES MUST GAME ENGINE PROVIDE TO GAMES?

15 of 89

Game Engine�What for?

Different genres => different needs
Killer feature for one game can be useless for other
GE should allow extensions

16 of 89

Game Engine�What for?

FPS / RPG

Large 3D worlds
Responsive camera
Weaponry/Magic
Minimal character model
High-fidelity animation
Small-scale multiplayer

Platformers

Dynamic environment
Puzzle-like elements
Third-person (+ complex camera movement)

Fighting games

Rich-set of fighting animations
Accurate hit detection
Complex user input
Single arena only

17 of 89

Game Engine�What for?

Racing games

Tricks for distance object rendering
Track divided into reusable sectors
Third-person (+ complex camera movement)

RTS

Hordes of low-res units
Terrain
Adjustable environment (buildings at least)
Various UIs
“Point-and-click”

MMOG

Scalable networking subsystem

18 of 89

Game Engine�What for?

RULE OF THE THUMB

First describe the game you want to create
Assess skills of your team
Then choose a game engine or a framework that would support the game as well as your team-work the best. Use it yourself first!

19 of 89

Game Engine�Architecture Overview

GAME ENGINE ARCHITECTURE OVERVIEW

20 of 89

Game Engine�Architecture Overview – Game Specific

Game engine architecture can be simply described as huge.

From a certain perspective game engines are like operating systems;

And many consoles were not more than “game loaders” in the past.

But that’s actually hard to see, when all you observe is the top of the pyramid,

the actual game.

So here we start on the top with game-specific layer each game has and each game

needs to adapt heavily. Game specific subsystems are always developed for each game separately.

You can see them as game business logic in a sense. You need to declare and implement

all the items, weapons, vehicles, puzzles, AI, camera movement, eye candies specifically

for each game. But that’s not all.

One real-world example. Warhorse Studios decided to use CryEngine back when

they were starting to work on KC:D. … But AI subsystem of CryEngine was implemented

for first-person shooters. So all NPCs were meant to be rather shortlived. Now contrast

it with open-world RPG such as KC:D where you need villagers to have their lives.

And so, whole AI subsystem of CryEngine was replaced, completely.

21 of 89

Game Engine�Architecture Overview – Game Specific

Each game has and needs to adapt heavily
The core of game business logic
Tailored specifically for each game

22 of 89

Game Engine�Architecture Overview – Game Specific

Real-world example:

Warhorse Studios decided to use CryEngine for KC:D
AI subsystem of CE designed for FPS

Short-lived NPCs
Villagers in the open-world RPG needed to live their lives

The whole AI subsystem of CE was completely replaced

23 of 89

Game Engine�Architecture Overview – Game “Agnostic” Layer

24 of 89

Game Engine�Architecture Overview – Foundations

25 of 89

Game Engine�Architecture Overview – Platform Level

26 of 89

Game Engine�Platform Independence Layer

Game Engine ~ OS

Own “language”, “memory management”, “threading / synchronization primitives”, …

27 of 89

Game Engine�Platform Independence Layer

Game Engine ~ OS

Often replaces standard C/C++ libraries and abstracts them with their own model
Own language => Hard to replace a single box here
Adding another 3^rd party middleware SDK => wrapping into primitives the rest of the engine understands

However, a clash of versions of utility libraries (like SDL) that are integrated deep within the middleware can be a huge pain

That’s why I have labeled Game Engines as operating systems of their own kind, because they have to have strong Platform Independence Layer

and their custom Core Systems, which are then shaping the rest of the code base.

In order to work with them, you have to speak their languages. That is, game engines either embraces but more often replaces various standard C/C++ libraries

and abstracts them with their own model. Everything above those systems then speaks a custom game engine proprietary language and that’s why it is typically

hard to replace a single box within this architecture. If you would like to bring another 3^rd party middleware SDK to the game, you have to first wrap it into primitives the rest of the engine understands, and only after then you can use them. More complex interface your middleware has, more complex the integration will be; the worst

what can happen is the clash of versions of various utility libraries like Boost or STL that are typically integrated deep within middleware and if middleware is not

designed the way that they are replaceable (by having own independence layer!), it might be even practically unfeasible due to the excessive effort you will have to invest into such an adaptation. That’s why it is a big decision choosing a certain game engine as your weapon of choice. You wanted to use them just

for simple 2D sidescroller and export it to multiple platforms, but you might encounter glitches along the way that might be hard to solve.

28 of 89

Game Engine�Tools <-> Engine Integration

Independent

Built-in

29 of 89

Game Engine�As an Integrator

GAME ENGINE AS AN INTEGRATOR OF WORK

30 of 89

Game Engine�Asset Pipeline

GE should provide ways for the integration with other tools
Every import/export (or even update) should happen automatically or with “one-click”
Asset Conditioning Pipeline:

“Devel data” vs. “Cooked data”

Resource database

TXT + SCM / SQL

That’s because when producing a game, even as indie, you will be dealing with

something that is called asset pipeline. That is, how are you going to be authoring

content for your game. Game engine and its editor are final integrators and consumers

of results of other tools like 3D modeling and animation tools like 3DMax, Maya, Blender,

or procedural assets like Houdini. Ideally, you would like your engine to be loading changes automatically

and the holy grail is to work in 3^rd party editor and have your changes being propagated

to your game during runtime.

On the other note, but still in the same park of the asset pipeline, you might need sometimes

to work with development data, which are of poor quality. The problem is that loading

times for scenes with quality models and animations are high… and if ALL you want to

test are gameplay triggers, you do not need that fancy graphics.

31 of 89

Game Engine�Resource Management

How assets are loaded, processed, adapted, thrown away (not only) during runtime
The path of the asset (Asset Conditioning Pipeline)

Digital Content Creation (DCC) tool

-> Resource Exporter (exports out of DCC)

-> Resource Compiler (adapts for GE)

-> Resource Linker (creates composite packages)

- e.g., character consists of a model, skeleton, rig,

textures and animations

32 of 89

Game Engine�Resource Management

Assets have dependencies

Asset Conditioning Pipeline must be driven by rules

Whenever some asset changes, it may imply rebuild of multiple assets

Dependencies must be tracked during life-time

To provide automatic load / unload

There can be internal (within file) as well as external dependencies (multiple files)

33 of 89

Game Engine�Resource Management

Resource Manager Responsibilities

Each asset is loaded only once within the memory

Auto loads/unloads when required/no longer needed

Manages the memory
Handles streaming

34 of 89

Game Engine�Resource Management

Loading assets

Map: GUID -> Resource
Very slow operation, may not happen during gameplay

Either you have load everything at once at the beginning of the level
Or do it asynchronously in the background (streaming) to prepare for streaming in another world chunk

35 of 89

Game Engine�Architecture Overview

A FEW COMPONENTS…

36 of 89

Game Engine�Core

Assertions

Game Engines are always adjusted during the game production – they are “in development” state

Math

Extremely important for space-efficient network protocols
Developers of Factorio had to write their own math library because of subtle differences in complex math operations between different HW

Otherwise the differences piled up and deviated the simulation in the end

Memory management

new / delete operators are slow

Like assertions, why they are important? Why should I care? Well during the development, your game specific layer

will be changing a lot. Without assertions, things will be breaking on a whim. You need to specify checks that

will be removed during the final build for speed ups, true, but during development that can save you from headaches.

Or math, you might have thought that math is solved things. Well, you might get surprised to receive different results

based on platform your game might be run on. Guys from the Factorio game has written their own math library

exactly because of this. They found out that their simulation deviates on various platforms, which is weird as the codebase

was the same. What they found out were subtle differences in more complex operations like square roots, trigonometry

and such, which pile up and caused the simulation to deviate in the end. A bugger for multiplayer that should work

between different platforms as well. There you want to rely on the simulation being the same as it allows you to replicate

less stuff over the wire allowing for shorter latency.

Or memory management. Is that supposed to be a work for operating system? Well yes and no. The thing is that new and

delete operators are slow. Anything that relies on OS services is slow in general, and you do not have a control over it.

Which is bad if you are trying to run a game, that is a real-time simulation.

37 of 89

Game Engine�Core

Resource manager

Engineer – Artist – Game Designer meeting point
Different quality of assets given the target platform

You really don’t want to have a duplicated scene for different platform

Build - automatically flagging used resources that should be included
Many bugs are data-induced ~ should be runtime fixable

Swapping assets during runtime should be allowed

38 of 89

Game Engine�Rendering Engine

Multiple layers

Graphics Device Interface
Low-level renderer

Primitives, Material system, Dynamic lightning, Camera, Viewport

Scene Graph / Culling

Ideally “spatial subdivision” agnostic (SG customizable)

Visual effects

Particles, decals, light mapping, dynamic shadows, HDR, FSAA, etc.

Front end / HUD (2D)

Then of course renderer. Game needs to be visual nowadays, you won’t get much attention with text-based

games. Apart from 3D rendering and 2D rendering there is one component you should pay attention to

and that is a scene graph and its culling. When framerate is dropping for your scene good chances are

you’re rendering too many triangles. Of course complexity of shaders may be troublesome as well but usually

your models are huge as well as your scenes. Well for models we have level of details. If a model is far away from

the camera, we replace it with low-poly model or a billboard really. But what if your scene is simply composed

of too many objects? Than it is the best to know, which game objects need to be rendered and which not.

Open-world has it hard but for corrido games or dungeons, you might need to be hinting the renderer that there

are some parts it does not need to be considering at all! Because they cannot be seen. So called scene graph culling.

And for that reason, you might want an engine that allows you to customize this feature as it heavily depends on

kind of scenes you will be creating.

39 of 89

Game Engine�Other components

Audio
Network
Physics
Animation
AI
Scripting
Event System
Profiling
Game subsystems

40 of 89

Game Engine�As Soft Real-time System

GAME ENGINE AS A SOFT REAL-TIME SYSTEM

And why you typically do not want to reinvent them…

41 of 89

Game Engine�As Soft Real-time System

GAME ENGINE MESSAGING SYSTEM

How do subsystems communicate?

42 of 89

Game Engine�As Soft Real-time System

http://www.gamasutra.com/blogs/MichaelKissner/20151027/257369/Writing_a_Game_Engine_from_Scratch__Part_1_Messaging.php

43 of 89

Game Engine�As Soft Real-time System

=>

http://www.gamasutra.com/blogs/MichaelKissner/20151027/257369/Writing_a_Game_Engine_from_Scratch__Part_1_Messaging.php

However, it does not need to be like this. Instead you might want subsystems to be communicating via some form

form of messages or events. One can learn from various remote procedure calls mechanism but essentially the idea

is not to call subsystems directly but be sending requests or reacting to events broadcast by those systems. One way

to implement this is via generic message bus to which you can send requests like “Play sound now” or “Create new

scene entity” or propagate events like “Player wants to shoot” or “Another frame was rendered”. If you do this,

what you will get is a message bus that can log what is happening in the system. I.e., by just observing the messages on the bus

you can reconstruct what has been happening in your game, which is a great tool for debugging complex scenarios.

Moreover, you can start sending ad-hoc messages via console during runtime to observe behavior of your subsystems

under various conditions, another plus for the debugging.

44 of 89

Game Engine�As Soft Real-time System

LOW-LEVEL OPTIMIZATIONS

45 of 89

Game Engine�As Soft Real-time System

Optimizations are the key to higher frame rates
Shift of the paradigms

Sequential => Parallel
CPU is expensive, Memory is cheap => CPU is cheap, Memory is expensive

46 of 89

Game Engine�As Soft Real-time System

Reality is complex nowadays

Intuition does not help:

Fewer instructions == faster code

NOPE

Data is faster than computation

NOPE

Computation is faster than data

NOPE

=> You have to profile, always

47 of 89

Game Engine�As Soft Real-time System

CPU Cores have multi-level cache + are pipelined

48 of 89

Game Engine�As Soft Real-time System

Code dependencies (and branching) + cache misses produce stalls

=> accessing a[++i] can be worse than a[i++]

49 of 89

Game Engine�As Soft Real-time System

Example of improved code

uint32_t digits10(uint64_t v) {

uint32_t result = 1;

for (;;) {

if (v < 10) return result;

v /= 10U;

result += 1;

}

Can we do better? …

50 of 89

Game Engine�As Soft Real-time System

Example of improved code

uint32_t digits10(uint64_t v) {

uint32_t result = 1;

for (;;) {

if (v < 10) return result;

if (v < 100) return result + 1;

if (v < 1000) return result + 2;

if (v < 10000) return result + 3;

// Skip ahead by 4 orders of magnitude

v /= 10000U;

result += 4;

}

More comparisons and additions, fewer /= … roughly 5x times faster
This is not exactly loop unrolling; or we can say that this is smart loop unrolling that cannot be done automatically as we’re performing the division only once!

51 of 89

Game Engine�As Soft Real-time System

More examples:

52 of 89

Game Engine�Low-level Systems

MEMORY MANAGEMENT

53 of 89

Game Engine�As Soft Real-time System

CPU Cores have multi-level cache

54 of 89

Game Engine�As Soft Real-time System

There are some numbers you should have in mind

[2016]

1ns = 10²x => 100 ns = 10²x => 10µs = 10²x => 1ms

55 of 89

Game Engine�As Soft Real-time System

There are some numbers you should have in mind

[2020]

1ns = 10²x => 100 ns = 10²x => 10µs = 10²x => 1ms

56 of 89

Game Engine�Memory Management

malloc and new are slow

Context switch to kernel-mode

=> Avoid dynamic allocation completely

Continuous memory access is the key

Cache misses may tear your time complexity (e.g., >20x slower)

=> Align your data correctly on every level

57 of 89

Game Engine�Memory Management – Avoiding Dyn. Alloc.

Provide custom memory manager

Allocate the memory at the beginning

Receive large byte*

Manage by yourself

Different strategies: stack-based (single/double side), pool allocators (different games favor different strategies)
Yes, become the master of your own memory ☺

58 of 89

Game Engine�Memory Management – Avoiding Dyn. Alloc.

Own memory management => Own containers
(Dynamic) Array
Linked list
Stack
Queue
BinaryTree
…
… good libraries allows you to supply your own memory manager

59 of 89

Game Engine�Memory Management – Aligning Data Struct.

The Problem

struct InefficientPacking

{

U32 mU1; // 32 bits

F32 mF2; // 32 bits

U8 mB3; // 8 bits

I32 mI4; // 32 bits

bool mB5; // 8 bits

char* mP6; // 32 bits

};

Compiler will not

optimize this!

Because of efficient

CPU Read/Write (CPU works

only with properly aligned data).

60 of 89

Game Engine�Memory Management – Aligning Data Struct.

When CPU is reading memory, it fetches usually more then required (HW dependent but ~64 bytes)

struct InefficientAccess

{

U32 a; // 32 bits

char[512] txt; // 512*8bits

U32 b; // 32 bits

};

Accessing a and b in a single expression => 2 cache misses

https://akkadia.org/drepper/cpumemory.pdf

61 of 89

Game Engine�Memory Management – Aligning Data Struct.

More on memory and CPU

https://akkadia.org/drepper/cpumemory.pdf

62 of 89

Game Engine�Low-level Systems

STRING HANDLING

63 of 89

Game Engine�String Handling

Strings are human-readable representations of a number

enemy-tank-01 better than 20146
… but also slow (allocation, compare, copy, …)

Different kinds of strings

Unique identifiers
Debugging text
Game text (requires localization)

64 of 89

Game Engine�String Handling

String as Unique Id

Use MACRO to translate strings into numbers

No debugging support but fastest

int id = TEXT(“tank-01”)

Combinable hashing functions: djb2 and FNV-1a

TEXT(“tank”) + TEXT(“-01”) == TEXT(“tank-01”

Use map to translate between string and id

Bi-directional for debugging

Wrap it into a small object

Each unique string has own object instance
ID always present at the inspected place

65 of 89

Game Engine�String Handling

String as Unique Id

Have the best of both worlds!

Define custom types ID and macros for creating and manipulating those IDs, e.g. TEXT(...). And then, depending on the build type (devel vs. ship), include different implementations!

66 of 89

Game Engine�String Handling

String as Game Text and localization

Database of texts

Database chosen according to the language

Keys are Unique String Ids

=> No plain text ever used within the code

67 of 89

Game Engine�Loops

GAME ENGINE LOOPS

do { play the game }

while (ExitNotRequested())

At the beginning of the lecture, we said that game engines and frameworks differ from middlewares by implementing a game loop design pattern.

I.e. an endless while cycle that is broken only by a request to terminate the game and thus the game engine itself.

Why it is this distinction important? That’s because you need to maintain some coherency of subsystem execution, you need to order their

updates as they may depend on the results of each other work. Now how you could do that if a middleware is having its own closed update loop

running in a separate thread you have no control over? You probably cannot. Therefore, middlewares are not having their own loops

and offers just an entry point update method that you are ought to call from your game loop.

As usual, there are a few approaches how this rather simple idea can be implemented and as usual, in the end, it is not that simple at all.

68 of 89

Game Engine�Loops

The movement is the illusion of many frames per second
So every engine has (at least) its “render loop”
In general, game engines have “game loop”s running on various frequencies
There are multiple “loop” architectures

As you already know, a movement on the screen is the illusion of presenting many frames per second.

Biologically speaking, we humans are sampling the reality with limited frames per second so after a certain

threshold, we start perceiving fast things as moving continuously. Do not be mistaken with old saying that 24 or 25 FPS

is enough. You can surely spot a difference between 25FPS on 100Hz monitor and 100FPS. But in general,

anything above 30FPS is acceptable by many.

Every game engine therefore has at least a render loop, that is trying to run either as fast as possible or with some

kind of a cap like 60FPS. But rendering is not the only subsystem game engines have. You need to read input,

you need to update physics, you need to update AI, you need to update simulation, etc. And not all those

subsystems need to work every frame. Like AI is sufficient to update 10 times per second for high fidelity

results. Or some systems cannot tick with variable framerate, like physics, which needs to be fixed-step in order

to lower their sort of non-determinism.

In the end, all subsystem loops will be somehow realized in the context of within one master game loop.

69 of 89

Game Engine�Loops

GAME ENGINE LOOPS

SINGLE THREADED

70 of 89

Game Engine�Loops – Simple Pong Example

void main() // Pong

{

initGame();

while (true) // game loop

{

readHumanInterfaceDevices();

if (quitButtonPressed()) break; // exit the game loop

movePaddles();

moveBall();

collideAndBounceBall();

if (ballImpactedSide(LEFT_PLAYER))

{

incremenentScore(RIGHT_PLAYER);

resetBall();

}

else if (ballImpactedSide(RIGHT_PLAYER))

{

incrementScore(LEFT_PLAYER);

resetBall();

}

renderPlayfield();

}

71 of 89

Game Engine�Loops – Simple Pong Example

void main() // ENGINE

{

initEngineAndLoadData();

while (true) // game loop

{

inputSystem.Update ();

if (isExit()) break; // exit the game

physics.tick();

gameplay.tick();

rendering.tick();

}

destroyEngine();

}

72 of 89

Game Engine�Loops – Windows Loop

Window Message Pump

while (true)

{

// Service any and all pending Windows messages.

MSG msg;

while (PeekMessage(&msg, NULL, 0, 0) > 0)

{

TranslateMessage(&msg);

DispatchMessage(&msg);

}

// No more Windows messages to process -- run one

// iteration of our "real" game loop.

RunOneIterationOfGameLoop();

}

73 of 89

Game Engine�Loops – Callback-Driven

Callback-Driven Loop (OGRE example)

while (true)

{

for (each frameListener)

{

frameListener.frameStarted();

}

renderCurrentScene();

for (each frameListener)

{

frameListener.frameEnded();

}

finalizeSceneAndSwapBuffers();

}

74 of 89

Game Engine�Loops – Event-Driven

Event-Driven Loop

Event system at the heart
Callbacks mimicked by periodic events that are allowed to be posted to the future

At the end of the event I schedule a new one

75 of 89

Game Engine�Loops

GAME ENGINE LOOPS

MULTI-THREADED

76 of 89

Game Engine�Loops

All systems are multi-core nowadays (even cell phones…)
It would be a waste not to utilize it…

One must be aware of the concrete architecture you are coding for

Sony PS3 was a bit exotic, now things are more standardized…

77 of 89

Game Engine�Loops

XBOX360

Sony Playstation 3

[PS3]

The PS3’s main CPU is called the Power Processing Unit (PPU). It is a

PowerPC processor, much like the ones found in the Xbox 360. In addition

to this central processor, the PS3 has six coprocessors known as Synergistic

Processing Units (SPUs). These coprocessors are based around the PowerPC

instruction set, but they have been streamlined for maximum hardware simplicity

and maximum performance.

The GPU on the PS3, known as the RSX, has a dedicated 256 MiB of video

RAM. The PPU has access to 256 MiB of system RAM. In addition, each SPU

has a dedicated high-speed 256 KiB RAM area called its local store (LS). Local

store memory performs about as efficiently as an L1 cache, making the SPUs

blindingly fast.

The three cores and the GPU share a unified 512 MiB pool of

RAM, which can be used for executable code, application data, textures, video

RAM—you name it.

The SPUs never read directly from main RAM. Instead, a direct memory

access (DMA) controller allows blocks of data to be copied back and forth

between system RAM and the SPUs’ local stores. These data transfers happen

in parallel, so both the PPU and SPUs can be doing useful calculations while

they wait for data to arrive.

XBox360, on the other hand, has more regular PC-like architecture.

Having three cores with shared 1MiB L2 cache and 512 MB of GDD3

RAM shared also with GPU.

78 of 89

Game Engine�Loops

Sony Playstation 4

XBOX One

However, programming for PS3 was a nightmare. The architecture was so different

and new, it gave programmers headaches from endless nights because

Moving data back and forth between PPU and SPU was not easy task.

PS4 thus reverted to more standard architecture which is more or less similar

To Xbox one.

The PS4’s eight-core Jaguar CPU is a high-performance computing device.

Yes, it runs at a slower clock rate than the PS3’s PPU and SPUs (1.6 GHz as

opposed to 3.2 GHz). But it makes up for this by including hardware that

makes less-than-optimal code (in other words, pretty much all game code that

hasn’t been manually downcoded to assembly language!) run much faster

than it would on the PS3. For example, the Jaguar supports advanced branch

prediction circuitry, which can correctly recognize all sorts of common branching

patterns in your code. This means a lot fewer pipeline stalls in “branchy”

code. At the end of the day, what this means to game programmers is that

they can focus their efforts more on making great games and less on trying to

rearrange their source code to eliminate branches in an effort to buy back lost

performance.

XBOX One architecture is very similar, there are differences but they are not

that much noticeable.

79 of 89

Game Engine�Loops

Fork-Join Loop

First attempt to make a game-engine multi-threaded
Parallelize only (suitable) parts of previously single-threaded loop that are CPU intensive

80 of 89

Game Engine�Loops

Thread-per subsystem

Subsystems invoked from the main thread as required
There are still blind-spots
E.g. Unity 3D (sort of)

81 of 89

Game Engine�Loops

Job model

Advocated in PS3 with SPURS library
Jobs are fine-grained and can be distributed between as many cores as one have
Whenever main thread has nothing to do, it crunches jobs as well!
E.g. Unreal Engine 4

The holy grail of multi-threaded loop model is job model. Originally advocated in PS3

however the time was not right back then. Job model differs largely from the thread

per subsystem model that you only have main scheduler thread and job thread.

You are constantly creating a directed graph of jobs, which defines dependencies

to each other, having the scheduler thread figuring out their ordering a dispatching

them for execution to job thread. Even more, if the main thread has nothing to do,

it crunches jobs as well. In theory, it works well, in practice it is difficult to achieve

The right amount of separation between jobs and split them into smaller chunks so

big long running jobs did not create blank spots as others job that depends on them

need to wait for their single thread exectuion.

This approach is used a lot by UE4.

82 of 89

Game Engine�Loops

Single Job model

Function pointer
Operates on some data
Each job mustn’t perform race condition

Criteria for a job:

Can be executed in isolation
Little data sharing, independent from other jobs
Self-contained
Cleanup their own initialization (like memory allocation)
No dependency on external code sequences
Can be pretty small, no problem with hundreds of jobs a frame

Performance Consideration

Align jobs according to their work, otherwise false sharing may occur

83 of 89

Game Engine�Loops

Example Job

Function pointer
Operates on some data
Each job mustn’t perform race condition

Performance Consideration

Align jobs according to their work, otherwise false sharing may occur

84 of 89

Game Engine�Loops

False Sharing

Hard to detect!
Each core writes to a different variables
BUT, those variables share the “cache line”
Cores are racing for ownership of the cache line => stalls

85 of 89

Game Engine�Data-oriented design

DATA ORIENTED DESIGN

Source: https://gamedevelopment.tutsplus.com/articles/what-is-data-oriented-game-engine-design--cms-21052

Source: https://www.youtube.com/watch?time_continue=4&v=yy8jQgmhbAU

86 of 89

Game Engine�Data-oriented design

“Object-oriented programming is [...] both anti-modular and anti-parallel by its very nature, and hence unsuitable for a modern CS curriculum.”

Robert Harper, a professor at Carnegie Mellon University

Thread synchronization over objects even though you are working with one field causing unnecessary lock contention
Violating cache locality (object references other objects elsewhere on the heap)

87 of 89

Game Engine�Data-oriented design

Looks like a fork&join model, in theory can be jobified and streamlined.

/ Entity-Component-System (ECS)

The idea is to see the gameplay code as system operating over some data. Hence the name data-oriented design

as opposed to object-oriented design. In this approach you do not model your entities with objects

but rather with a number or a set of numbers, which points to arrays of components the entity is formed with.

The trick is, that those arrays are created so they are easily digestible by so-called systems, which ought to be

be performing gameplay updates. Like for instance solving spreading of fire by having a flammable component

And fire system that crunches propagation of the flame across the array of flammable components.

The trick is that we will always be iterating over the consecutive array of elements which are going to be small

thus keeping CPU caches happy yielding big performance improvements.

88 of 89

Game Engine�Thanks you for you attention!

THAT’S IT FOR TODAY!

89 of 89

Game Engine�Thanks you for you attention!

Some interesting stuff:

Naughty Dog Multithreaded Loop Thoughts

Redesigning Game Engine in Bungee

Multi-threading Practices

Game Engine Architecture Club (YouTube)

Data-oriented Game Engine Design

OOP is Dead (YouTube)

GPU Programming for Video Games

How to Recognize Good Middleware