MI-APH Summary

Habitica

Computer Program

• a set of instructions that can be executed by a computer

Computer Application

• computer program that helps a user to perform a task

Computer game

• a computer-controller game where players interact with objects displayed on a screen for the sake of entertainment

Mechanics

• a set of rules governing the behavior of a single game element

Story

• a sequence of events that unfolds in the game

Aesthetics

• how the game looks, sounds, tastes, feels,...

Technology

• any materials and interactions that make the game possible

• Family of game engines developed by ID software
• Id Tech 0 - the very first engine
• Every next game had more advanced technology
• Still, memory constraints sabotaged attempts to create data-heavy design

Main modules

• Game Loop - heartbeat of all games
• Scene Manager - manages objects and structures them in a scene graph
• Resource Manager - manages assets, controls a cache
• Input Manager - handles inputs (keyboard, mouse, touch, joystick, gamepad,...)
• Memory Manager - memory allocator and deallocator
• Rigidbody Engine - event-based collision detection
• Physics Engine - handles behavior of objects based on forces and impulses
• Rendering Engine - renders the game, takes care of the rendering pipeline
• Animation Engine - handles animations
• Scripting Engine - bridge between the engine and interpreted languages (JS, Lua, C#,...)
• Multimedia Engine - plays music, clips, sounds, video
• AI Engine - abstract engine for AI (path finding, states, behavioral trees, ...)
• Networking Engine - handles multipeer communication

Other modules

• GUI framework, Level Editor, Camera, Event System, World Streaming, Security, LOD, Profiler,...

• Simple, yet the most important part of the game engine
• Each turn advances the state of the game
• Sometimes it's coordinated with the platform's event loop
• Optimal time step for rendering: 60FPS = 16.6 ms per frame
• Audio is usually separated as it requires more frequent updates (~200 FPS)
• Certain systems don't need to be updated so frequently (AI)

• Provides access to all resources (assets)
• meshes, materials, shaders, animations, textures, clips, levels
• many assets are not used in their original format
• engines usually encode their resource metadata in XML files
• Resource Cache - used for faster access
• Manages lifetime of each resource
• most managers maintain some kind of registry
• Ensures that only one copy of each resource exists in memory
• resource GUID - usually path of the file, guaranteed to be unique
• Loads required resources and unloads those no longer needed
• loading is simpler than unloading
• Handles streaming

Audio pipeline

• for each 3D sound, a dry digital PCM signal must be synthesized
• distance-based attenuation - provides a sense of distance
• reverb - provides accoustics
• dry signals - arrive via an unobstructed path
• wet signals - echo (early reflections) + tail (late reverberations)
• audio buffer must be fed periodically - dropping audio is worse than dropped frames

Audio clips

• digital sound asset (MP3, OGG, WAV)
• module asset (MOD, S3M, IT, XM), not used anymore, yet it's fun to play around with them
• MIDI - sequencer-related data, nowadays mainly for recording and preprocessing

Sound cues

• collection of audio clips with metadata

Sound banks

• package of sound clips and cues

Streaming sounds

• small ring buffer for music and speech

Getting the state of the device

• polling - compare against previous state
• callbacks - handled by upper SW layer
• via a protocol (wireless device)

Devices

• keyboard, touch sensor
• one-axis controller - single analog state
• two-axis controller - mouse and joystick
• three-axis controller - accelerometer
• camera, VR lens, Azure Kinect

Dead zone

• area of a control interface that has no input effect (analog joystick)

Normalization

• axis are mapped to a Cartesian space, not a circular space
• input must be normalized

• allocates lots of small blocks of memory, each of the same size
• doesn't suffer from memory fragmentation
• entities have to be of the same size

Level loading

• used in Tomb Raider, Doom,...
• requires a loading screen
• only one game chunk is loaded at a time

Air locks

• used in Half-Life 2, Portal, Inside, new Wolfenstein,...
• larger block contains the whole scene
• smaller block represents an air lock (usually a small room/hall)
• when the player enters the are from which can neither see the previous area nor return to it, next scene is loaded

World streams

• used in open-world games: GTA, WoW, ARMA, Read Dead Redemption, Witcher,...
• the world is divided into regions
• when the player enters region B and is far enough that chunk A can no longer be seen, the engine unloads chunk A and starts loading chunk C
• LOD (level of detail) - chunks are loaded with variable granularity (only meshes)

View model

• the one represented on screen as a result of processing all other models

Networking model

• everything that has to be in sync with other models on other devices

Core model

• describes a state of a game at any point in time
• tightly coupled with networking model (if there is one)

Physics model

• all entities taking part in physical interaction

AI model

• all data that are processed by AI (navigation maps, behavioral trees,...)

• Used in 90's
• One class determines behavior of every game object
• Lots of switches and if-checks

• A unit of composition with specified interfaces and explicit context dependencies
• components are basically plug-and-play objects
• prefers composition over inheritance
• it is not about how to organize your models but how to tie them up

Monolithic

• discussed in previous chapter
• traditional OOP way
• problems with deep and wide hierarchies

Object-centric

• each game object is represented in runtime by a single class instance
• Early games: Thief: The Dark Project (1998), Dungeon Siege (2002)

Property-centric

• each game object is represented only by a unique id
• cache-friendly (components are stored contiguously in memory)
• identifiers: integer, string, hashed string,...
• early game: Deus Ex 2 (2003)

• ECS+A - Entity-component-system + attribute
• game object is just a container for data and logic
• can be easily integrated into scene graph

By modifying the container object's state

• e.g.: shared state machine
• indirect communication
• difficult to debug

By direct calls

• OP way
• fast, but increases coupling
• e.g.: group of components that are always bound together

By messaging systems

• events and commands
• each component can declare interest in relevant messages
• slower than the direct call, but that cost is negligible in all but performance-critical code
• difficult to debug, messages can fall into an infinite loop
• can be implemented via polymorphism, arrow functions,...
• e.g.: game-over event

• Components should be notified of any state change that are relevant to them
• Can be used for returning values (danger of feedback deadlock )
• Blind event forwarding - an object can forward an event to another object
• One handler - OnMessage() method, implemented in each component
• Processing can be instant or delayed
• Event Queue - pattern for batch message processing, can post events with a delay

Unicast

• a component sends a message to another component
• in most cases this can be handled by a direct call
• example: kill an object

Multicast

• a) component sends a message to specific subscribers
• b) component sends a message to all objects that meet specific criteria
• example: notify all nearby units that an enemy has entered the area
• example: a unit was destroyed -> notify everyone interested

Broadcast

• rarely used (observer pattern doesn't stick to it)
• usually for System-Entities communication
• example: level completed, game over, player died

• Avoids passing everything through the constructor
• Constructor creates an object, init method initializes it
• Objects can be initialized several times
• Objects can be allocated in-advance in a pool

• several meanings (state of the whole game, internal state of entities,...)
• in this context, it is just a member of a set, determining what actions an object may execute

// stateless, the creature will jump each frame

creatureUpdate(delta: number, absolute: number) {

  if(pressedKeys.has(KeyCode.UP)) {

    this.creature.jump();

  }

}

 

// a variable that makes certain actions possible only according to the current state

creatureUpdate(delta: number, absolute: number) {

  if(pressedKeys.has(KeyCode.UP) && this.creature.state !== STATE_JUMPING) {

    this.creature.changeState(STATE_JUMPING);

    this.creature.jump();

  }

}

• bit array that stores binary properties of game objects
• may be used for queries (e.g. find all DEAD objects)
• similar to a state machine but behaves differently
• if we maintain all flags within one single structure, we can search very fast

• marks changed objects
• can be applied to various attributes (animation, physics, transformation)
• you have to make sure to set the flag every time the state changes
• you have to keep the previous derived data in memory

Cleaning

• When the result is needed
• Avoids doing recalculation if the result is never used
• Game can freeze for expensive calculations
• At well-defined checkpoints
• less impact on user experience
• you never know, when it happens
• On the background
• You can do more redundant work
• race-condition may occur

• Builder assembles an object, factory manages the assembling
• Factory creates an object according to the parameters but with respect to the context

class UnitFactory {

 

  private pikemanBuilder: Builder; // preconfigured to build pikemans

  private musketeerBuilder: Builder; // preconfigured to build musketeers

  private archerBuilder: Builder; // preconfigured to build archers

 

  public spawnPikeman(position: Vector, faction: FactionType): GameObject {

    return this.pikeman.position(position).faction(faction).build();

  }

 

  public spawnMusketeer(position: Vector, faction: FactionType): GameObject {

    return this.musketeerBuilder.position(position).faction(faction).build();

  }

 

  public spawnArcher(position: Vector, faction: FactionType): GameObject {

    return this.archerBuilder.position(position).faction(faction).build();

  }

}

• an object holds shared data to support large number of fine-grained objects
• example: instanced rendering, geometry hashing, particle systems

• allows to reproduce any state of a game at any time
• much more complex than the save mechanism
• all game entities must have a reproducible behavior (similar to multiplayer facility)
• two main impediments: random functions and nondeterministic operations

• Solution a)
• store the state of all objects in the game - either on frame basis or at a fixed frequency
• reproduce them by modifying all objects at each frame
• Solution b)
• if the game is completely message-driven, we can store all game messages
• during the replay, forbid all components to send messages on their own
• send queued messages one by one and let them be processed

Uniform distribution

• most common distribution of random generators
• applications: noise, shuffling, one-of-many selection

Gaussian (normal) distribution

• more common in games - every characteristic has some kind of average, with individuals varying with a normal distribution
• can be calculated from a uniform generator via transformation (Box-muller algorithm)
• applications: height of trees, aiming for projectiles, average speed, physical reaction time, reload rate, refresh healing rate, critical hit

Uniform distribution

Gaussian distribution

Seed

• a hash that initializes random generators
• a good source of entropy is user input or current time

Loot

• items obtained over the gameplay (money, spells, equipment, weapons,...)

Spinning

• calling the random function on a time-frame basis without using the result
• advances the game to a difficult-to-predict place

Rarity slotting

• a method of standardization to determine rates (common, rare, epic, legendary)
• makes game events occur proportionally
• can be defined as a rarity table, calculated via weighted sum

Random encounter

• popular mechanics of RPG games (Final Fantasy, WoW, Pokémon, Golden Sun)
• the game suddenly shifts to battle mode, forcing the player to fight
• after winning the battle, the player receives a reward (skill upgrade, items, money)

• Perlin Noise - developed by Ken Perlin in 1983
• Simplex Noise - Perlin's improved noise, fewer artifacts and lower computational overhead
• both are gradient noises - we set a pseudo-random gradient at regularly spaced points in space and interpolate between them
• the noise is constructed from octaves (contribution to the signal at a particular scale)
• the signal is interpolated via a quartic function:

Oct-tree

Bounding volume

• groups objects or their parts together based on their positions and sizes
• if the object moves, so will the hierarchy
• used for physics, shape analysis, precise collision detection

Spatial data structure

• a structure that stores objects by their position
• is locked to the world
• used for range queries, neighborhood searching, rough collision detection
• the more objects we have, the more benefits we get
• Implementations
  • BSP - binary-space partitioning
  • Quad-tree - for 2D and semi-3D space
  • Oct-tree - for 3D space
  • Grid - a square grid

• hierarchical partition
• each inner node has 4 children
• it is common to have the children of same size -> we won't need to save the position vector
• overlapping objects are put it into all children they touch
• only objects in the same leaf can be in collision
• useful for outdoor scenes, where objects are placed on a landscape
• good for a small amount of objects of various sizes

• set of algorithms and principles that help autonomous agents move in a realistic manner
  by using simple forces
• designed by Craig Reynolds  in the early 90's
• Agent - a system situated within an environment, having an ability to sense that environment
• three layers of motion behavior:
  • action selection - choosing goals, strategy
  • steering - trajectory calculation
  • locomotion - way of moving, animation, articulation

• the simplest steering behavior
• a force that directs an agent toward a target position

Flee

• opposite of seek
• creates a force that steers the agent away

Arrive

• seek is not good at stopping
• arrive decelerates the agent onto the target position
• additional parameter: slowing radius

Pursuit

• agent intercepts a moving target
• predicts where the target is going to be in the future
• calls for a good prediction function

Evade

• opposite of pursuite
• the evader flees from the estimated future position

• produces a force that will give an impression of a random walking
• small random displacement is applied to the velocity vector every frame
• a circle is projected in front of the vehicle
• the vehicle is steered toward a target that moves along the perimeter
• smoothness of movement depends on three parameters:
  • circle radius, distance from the vehicle and jittering (randomness)
• the greater the radius and the distance, the stronger the force

• moves a vehicle along a set of waypoints
• the last waypoint can be reached using arrive, the others via seek
• smooth movement can be achieved using a tolerance radius or Bézier curve approximation
• very sensitive to configuration (max force, max velocity, radius,...)

Obstacle avoidance

• steers a vehicle to avoid obstacles (usually approximated by a circle)
• vehicle has a detection box - rectangular area
• two forces are calculated: lateral force and braking force

Offset pursuit

• keeps a vehicle positioned at a specified offset from a leader vehicle
• useful for battle formations

• emergent behavior, more agents/vehicles are taken into consideration
• combination of three aspects:
  • separation - steers a vehicle away from its neighborhood
  • alignment - keeps the vehicle's direction aligned with its neighbors
  • cohesion - moves a vehicle toward the center of mass of its neighbors

Vector addition and subtraction

Magnitude of a vector

• Vector - a quantity that has both a magnitude and a direction
• vector can be used to represent a point, provided that we fix the tail of the vector
  to the origin of the coordinate system
• addition and subtraction
  • vector + vector = vector
  • vector - vector = vector
  • point + vector = point
  • point - point = vector
  • point + point = undefined

• Magnitude
  • scalar representing the length of the vector
• Normalization
  • a unit vector is a vector with a magnitude of one:
• Normal vector
  • vector is normal to a surface if it is perpendicular to it
• Dot product
• Cross product
  • yields another vector that is perpendicular to two vectors

Implicit methods

• make use of quantities from the next time step
• decrease energy from the system

Semi-implicit methods

• combination of explicit and implicit methods
• very stable

Explicit methods

• make use of known quantities at each time step

Runge-Kutta family

• Euler methods, midpoint methods, RK4,...

Verlet family

• Regular Verlet
• Leapfrog Verlet
• Velocity Verlet

Body

• fundamental object in the physics scene

Rigid Body

• idealized, infinitely hard, non-deformable solid object
• physics-driven bodies - driven entirely by the simulation
• game-driven bodies - moved in a non-physical way (animations)
• fixed bodies - collision-only bodies

Soft Body

• can be deformed

Shape

• region of space described by a boundary, with a definite inside and outside (curved line, polygon, curved surface, polyhedron)

Fixture

• used to describe size, shape and material properties

Sphere

• center point and radius (4 numbers)

Capsule

• 2D: rectangle and two circles
• 3D: cylinder and two hemispherical end-caps
• representation: two points and radius

AABB

• axis-aligned bounding box
• rectangular volume (cuboid) whose faces are parallel to the axes of the coordinate system
• very efficient test for penetration
• AABB must be recalculated whenever the object rotates

SAT (separating axis theorem)

• based on collection of intersection tests
• if an axis can be found along which the projection of two convex shapes do not overlap, then the two shapes do not intersect
• for 2D: AABB 2 axes, OBB 4 axes
• for 3D: AABB 3 axes, OBB 15 axes

Other methods

• GJK, Line Sweep, Sphere test,...

• AABB in 2D: only 2 axes to check

Stepped world

• time steps vary based on occurring situation
• collision time is calculated by doing binary search in time, moving object back and forth by 1/2 steps (5 iterations is usually enough)

Continuous Collision Detection (CCD)

• uses Swept Shapes
• a new shape is formed by the motion of the original one
• rotating shapes may result in shapes that aren't convex

• a collection of point masses that obeys certain physical laws
• can model complex fuzzy shapes and dynamics
• heavily used Flyweight pattern (array of positions, velocities, group lists)
• particles are not only moving points! Even a tree may become a particle!

Applications

• fluids
• visual effects
• flocks
• rendered trails (plants)
• soft bodies (flag, cloth)

Basic model

1. generate new particles
2. assign individual attributes
3. extinguish dead particles
4. move and transform particles according to their dynamic attributes
5. render meshes

Euler angles

• Pitch, Yaw, Roll
• simple, small size (3 floats), intuitive nature
• the order in which the rotations are performed matters
• gimbal lock issue - when a 90-degree rotation causes one of the three principal axes to collapse onto another principal axis

Axis + angle

• axis of rotation plus a scalar for the angle of rotation
• intiutive and compact
• rotations cannot be easily interpolated
• rotations cannot be applied to vectors directly

Model space

• origin is usually placed at a central location (center of mass)
• axes are aligned to natural direction of the model (e.g. a nose of an animal)

World space

• fixed coordinate space, in which the positions, orientations and scales of all objects in the game world are expressed

View/Camera space

• coordinate frame fixed to the camera
• space origin is placed at the focal point of the camera
• OpenGL: camera faces toward negative

Clip space

• a rectangular prism extending from -1 to 1 (OpenGL)

View/screen space

• a region of the screen used to display a portion of the final image

• View volume - region of space the camera can see
• Frustum - the shape of view volume for perspective projection
• Rectangular prism - the shape of view volume for orthographic projection
• Field of view (FOV) - the angle between the top and bottom of the 2D surface on which the world will be projected

Perspective projection

Orthographic projection

Stop-motion animation

• predefined set of images/sprites
• simple and intuitive, but impossible to re-define without changing the assets

Keyframed animation

• keyframes contain values (position, color, modifier,...) at given point of time
• intermediate frames are interpolated

Sprite animation

Skeletal 2D

Skeletal 3D

Vertex

Linear interpolation

• for 1D values (time, sound)

Bilinear interpolation

• on a rectilinear 2D grid
• for 2D values (images, textures)
• Q - known points (closest pixels)
• P - desired point

Trilinear interpolation

• on a regular 3D grid
• for 3D values (mipmaps)

Z-Fighting

Vertex

• primarily a point in 3D space with  coordinates
• attributes: position vector, normal, color,  coordinates, skinning weights

Fragment

• a sample-sized segment of a rasterized primitive
• its size depends on sampling method

Texture

• a piece of bitmap that is applied to a model

Occlusion

• rendering two triangles that overlap each other
• Z-Fighting issue
• solution: more precise depth buffer

Culling

• process of removing triangles that aren't facing the camera
• frustum culling, portals, anti-portals,...

• programs that run on the video card in order to perform a variety of specialized functions (lighting, effects, post-processing, even physics or AI)

Vertex shader

• input is vertex, output is transformed vertex

Geometry shader (optional)

• input is n-vertex primitive, output is zero or more primitives

Tessellation shader (optional)

• input is primitive, output is subdivided primitive

Pixel/fragment shader

• input is fragment, output is color, depth value, stencil value

Compute shader

• shader that run outside of the rendering pipeline
• used for massively parallel GPGPU computing

Waypoint-based

• level designer places waypoints that are later linked up

Mesh-based

• created from a polygonal representation of the environment's floor
• describes walkable areas

Grid-based

• created by superimposing a grid over a game environment
• traversability flag indicates whether the cell is traversable or not
• connection geometries: tile, octile, hex
• reflecting environmental changes = recalculation of the traversability flag

• improved Dijkstra by an estimate of the cost to the target from each node
• Cost , where  is the cost-so-far and  is the heuristic estimate
• Heuristics: Euclidean, Manhattan, adaptive (penalty for direction change)
  • Manhattan distance will work if almost no obstacles appear

• Improvements
  • preprocess the map, calculate universal paths
  • mark tiles which cannot lead anywhere as dead-ends
  • limit the search space

• breadth-first search ignores costs
• Dijkstra ignores position of the target
• A* takes into account both of them

• IF-THIS-THEN-THAT approach
• AI behavior is completely hardcoded
• simple, easy to debug, easy to extend if programmed properly
• human player should behave as the developers expect
• good scripting behavior must cover a large amount of situations

• the oldest and most commonly used formalism to model game AIs
• useful for an entity whose behavior changes based on an internal state that can be divided
  into small number of distinct options
• each game entity can be in exactly one of a finite number of states at any time

• Definition
  • quadruple
  •  is a finite, non-empty set of states
  •  is a finite set of inputs
  •  is the state-transition function
  •  is an initial state,
• can be implemented via polymorphism or a state transition table
• unmanageable for large complex systems, leading to transition explosion

• also known as statecharts
• each state can have a superstate or a substate
• groups of states share transitions
• usually implemented as a stack
  • push a low-level state on the stack when enter
  • pop and move to the next state when finished

• tree of hierarchical nodes that control decision making process
• originate from gaming industry around 2004 (Halo 2)
• combine elements from both Scripting and HFSMs
• there is no standardized formalization

• inner nodes lead to appropriate leaves best suited to the situation
• depth-first traversal, starting with the root node
• each executed behavior passes back and returns a status
  • SUCCESS, FAILURE, RUNNING, (SUSPENDED)

Bot

• an intelligent artificial player emulating a human player
• used mainly to describe AI in FPS game

NPC

• non-playable character - doesn't play the game but rather interacts with the player

Planning

• a formalized process of searching for sequence of actions to satisfy a goal

Supervised learning

• works just like learning at schools
• for certain input there is a correct output the algorithm has to learn

Unsupervised learning

• the output cannot be categorized as being either correct or false
• the algorithm learns patterns instead

Reinforcement learning

• an agent must learn the best possible output by using trial and error
• for each action chosen the agent obtains a feedback

• a grid over the game environment
• maintains probability for each grid cell
• probability represents the likelihood of an opponent presence
• when the opponent is not visible, the probabilities from the previous occupancy cells are propagated along the edges to neighboring cells

• used in RTS
• the value at any coordinate is the damage that the enemy can inflict
• updating is done through iterating the list of known enemies
• can be easily integrated into pathfinding

• Example: combat units bypass enemy defensive structure in order to attack their infrastructure

• more generalized than threat maps
• helps the AI to make better decisions by providing useful information
  • situation summary (borders, enemy presence)
  • statistics summary (number of visits, number of assaults)
  • future predictions
• Example: number of units killed during last strike

• centers on the idea of goals as desirable world states
• each action has a set of conditions it can satisfy, as well as a set of preconditions that
  must be true in order to be satisfied
• originally implemented for F.E.A.R (2005)
• two stages: select a relevant goal and attempt to fulfill that goal

Script

• a piece of code that performs a specific task
• originally, scripts were simple languages for punch-cards processing

Scripting language

• common definition: a scripting language is a high-level language that can be interpreted by another program at runtime
• it is more about an environment than the language itself - even C/C++ can be considered as a scripting language if loaded by an interpreter
• C# is compiled into byte-code that is interpreted at runtime by .NET, yet most people don't consider it as a scripting language

Common characteristics

• economy of expression
• flexible dynamic typing
• easy access to other programs

• the engine needs to communicate with the scripting part - provided by bridges
  • JNI (Java - C++)
  • P/Invoke (.NET - C++)
  • LuaBridge (Lua - C++)
  • Dukbind (Duktape JS - C++)

• bridge is a performance bottleneck, especially for per-frame calls
• more scripting languages -> more bridges to maintain
• crossing the boundary between C++ and the script is slow while marshalling a large amount of data

• Marshalling
  • transforming the memory representation of an object between two domains (different programming languages)
• Semantic gap
  • descriptive difference of an object in various representations (relational database, object-oriented structure)

• single-screen multiplayer
• split-screen multiplayer
• networked multiplayer
• MMOG

• the main objective: how to synchronize several universes
• all clients have to achieve a certain degree of synchrony
• there is no (known) real-world picture for this type of problem

• impact on the game design - game model, animation engine, sound engine, vehicle model, AI engine, physics,...

• implement multiplayer features into a single-player game is a painful task
• converting a multiplayer game into a single-player game is trivial

• Naive approach: transfer a complete game state repeatedly to all clients
• Most common approach: transfer a minimal subset of a game state that is required to reconstruct the complete information
• Topologies: peer-to-peer, client-server

• each device exchanges data with each other in a fully connected graph
• used in Doom, early Command & Conquer, Age of Empires, Starcraft
• given  peers, each peer must have  connections ->  in total
• methods: single master, partial authority, full replication

•  devices,  connections
• server must handle  more messages per second
• server quickly becomes the bottleneck (lack of power and bandwidth)
• it is quite clear which code runs on a server machine
• Dedicated server - only runs the game state and communicates
• Listen server - server is an active participant in the game itself

• the act of transmitting a state of an object from one device to another
• each object must be uniquely identified (network ID)
• the network message usually consists of a type of an object and all parameters required to construct this object on all machines

Interpolation/extrapolation

• smoothens out incoming values by interpolating to them

Deterministic prediction

• runs simulated code, masks latency and keeps the client's state in sync

Dead reckoning

• non-deterministic prediction
• client uses the last known state of an object to extrapolate future state

Server-side rewind

• the server buffers object positions for several frames to match the client's view when processing instant events