Game Engines

Planning & Design

​

​

​

(please email me at pdiffenderfer@gmail.com with any criticisms)

How to Plan & Design a Game Engine

Game Engines are complicated and like all complicated projects it's best we understand the problem space, the decisions we need to make, and the different solutions available.

We must choose which components of a game engine we want, which features we want per component, and which designs we want to undertake to build the components.

Core Components of a Game Engine

* = components often required to create a game engine

​

• AI (objects that have behavior)
• Animation (anything that moves)
• Asset Management*
• Audio*
• Core* (game state, memory, data structures)
• Entity* (sprites, characters, meshes)
• Entity Management*
• Event System
• Files & Streams (parsing & writing data places)
• Game Loop*
• Input* (keys, mouse, controllers, sensors)

• Math* (vectors, matrices, & shapes)
• Multithreading
• Networking
• Particle Effects
• Physics
• Rendering* (graphics, scenes, cameras, windows)
• Screens* (menu, loading, gameplay)
• Scripting System
• System Integration
• User Interface

Secondary Components of a Game Engine

** = components broken out into their own because multiple components depend on them

​

​

• Debugging Utilities
• Easing** (animation velocity)
• Game Patching & DLC
• Gaming Services (score boards, authentication servers, profile saving, match-making services)
• Localization (multilanguage support)
• Maps (tiles, hex, heightmap, platforms, converting between screen points and map locations)
• Paths** (lines & curves)
• Profiles (game state, achievements, preferences)
• Spatial Database (index and query entities in space)
• Tasks (break up processing into pieces that can be ran asynchronously)
• Tools
• Types (expose game objects to debugging, networking, file system, and tool components)

Example Organization

Implementation & Design Considerations

• Which Language [& Framework]?
• Which Graphics Library?
• Graphics library agnostic?
• Which Dimensions? (2D, 3D, isometric)
• Dimension agnostic, all 3D, or separate classes for 2D & 3D?
• Which Components?
• Any 3rd Party Libraries?
• Behind a facade to swap out implementations?
• Cross-platform?
• Components should operate on an interface to abstract the platform specific code
• Input, Audio, Multithreading, Files & Streams, Asset Management, Networking, Memory

Structure of Presentation

• What do we want to build?
• For each core component
• Define basic responsibilities
• List possible features / implementations
• Pros & Cons
• What designs / solutions are available?
• For each component
• For each feature
• Discuss solutions
• Pros & Cons
• Our Game Engine Design

What do we want to build?

AI

Responsibilities

• Add behavior and intelligence to actors.
• Managing state & transitions of an actor.
• Helping actors traverse their environment.
• Finding a path
• Following a path
• Avoiding collisions
• Group movement
• Control how much processing time is spent per frame by queueing tasks (see Tasks component)

Sub-Components

• State Machine
• Finite
• Fuzzy
• Path Finding
• Steering Behaviors

AI > State Machines > Finite

Responsibilities

• Manage the state of an actor
• Handle transitions between states
• Handle multiple transitions (which one to apply)
• Prioritized
• Random Selection

Features

• Conditions
• Evaluates to true or false
• Compound (and, or, not, xor)
• Require N true/falses in a row before true
• Transitions
• If condition is true, go to state
• Prioritized transitions
• Random transitions
• Transition from given state or any to a specific state
• Periodic condition evaluation

​

AI > State Machines > Fuzzy

Responsibilities

• Manage the states of an actor
• Each state can be active to some degree

Features

• Conditions
• Evaluates between 0.0 and 1.0
• Compound (min, max, avg)
• Running average
• States
• State is active based on condition
• Periodic condition evaluation

​

​

AI > Path Finding

Responsibilities

• Given a "map" and two "points" on the map, return a path between the points
• Map and points don't need to represent physical values
• The path returned should be the best available for the given actor
• Control how much processing time is spent per frame by queueing tasks (see Tasks component)

Features

• Nodes & Edges
• Have a constant or dynamic cost
• Can only be traversed by certain actors
• Heuristics
• Estimates cost from current node to target
• Path simplification & optimization
• Path caching
• Dynamic path evaluation & recalculation
• Node traversability changes
• Partial & incremental path calculation
• Hierarchical pathfinding (a tree of graphs)

​

AI > Steering Behaviors

Responsibilities

• Add realistic movement to actors in their environment
• Adjusts movement behavior based on the state of the actor

Features

• Target an object, position, future position, offset to another target
• Filter which targets are seen based on proximity, field of view, & object type
• Constrain actor movement (believability)
• Steering behavior
• To, Away, Arrive, Wander, Follow, Path,
• Cohesion, Separation, Alignment
• Compound behaviors
• Prioritized
• State Machine uses actor state
• Context uses concept of good and bad forces

​

Animation

Responsibilities

• Change one or more properties of an entity from one set of values to another set of values through a path of points
• Sprite animations
• Skeletal animations
• Camera zooming, movement, shaking, etc
• Color, scaling, rotation, alpha, etc

Features

• Generic Animation System
• Play, Pause, Resume, Queue, Seek, Reverse
• Partial Animations
• Transitioning
• Animation Blending
• Additive Animations
• Sequential Animations
• Constraints
• Spring & Physical Forces
• Linear, Curved, Disjoint, and Combo paths
• Keyframe Animations
• Animation Events
• Multi-input Animations

Asset Management

Responsibilities

• Loading an asset (texture, animation, model, font, etc) from any source
• Embedded, file system, http, zip file, database
• Converting assets from raw format into game friendly structures
• Control how much processing time is spent per frame by queueing tasks (see Tasks component)

Features

• Live asset reloading
• Custom sources
• Custom format
• Caching
• Asynchronous loading
• Bundles
• Context
• Ensures only assets the game currently needs are loaded - releases unneeded assets
• One or more contexts can be active at a time

Audio

Responsibilities

• Loads and streams audio files
• Handles system limitations by ensuring most appropriate sounds are playing
• Manage the state and volume of sounds based on game state

Features

• Play, pause, resume, mute, stop, repeat, fade
• Stereo playback based on position of sound
• Volume adjustment based on obstacles
• Sound effects based on environment surface
• Uses a state Machine
• Prioritized sounds when the system is limited by concurrent sound instances
• By type, distance, volume, etc
• Maximum instances per sound
• Sound banks which choose a sound to play based on probability
• Mass actions on sound instances based on flags (IN_WORLD, UI, AMBIENCE, etc)

Core

Responsibilities

• Basic structures and utilities

​

Features

• Game State
• Timing and drawing data
• Memory
• Pooling / caching
• Pointers / Handles
• Data Structures
• Lists, Stacks, Queues, Trees
• Primitives & Objects
• Interfaces
• Clone, Factory, Bufferable
• Bitset Utilities

Debugging Utilities

Responsibilities

• Assist developer in finding and fixing bugs and poor performance
• Handles the "real-time" requirements a game has with the requirements to be able to inspect code & values

Features

• Live Graphs
• Based on 1 or more round-robin databases that track data points
• Memory, networking, profiling data
• Profiling
• Nested profiling is tracked
• Console
• Displays game activity and accepts commands
• Verbosity setting
• Channels
• Multithreading concurrent access detection
• Trying to write and read a shared resource at the same time
• Snapshots
• Take singular or multiple frame snapshots of the state of the game and display or log them
• Multiple snapshots can be aggregated

Easing

Responsibilities

• Provide functions for controlling the velocity of an animation

Features

• Easing
• Single argument function which takes a delta and returns a new delta
• Ex: linear, elastic, ease, cubic, quartic, sine
• Easing Type
• Double argument factory which takes a delta and an easing function and generates a new easing function
• Ex: in, out, reverse, ping-pong, back, in-out
• Easing Scale
• Double argument factory which takes a scalar value and easing function and generates a new easing function
• Parses easing expression strings into Easings

Entity

Responsibilities

• Provides interfaces for game objects which can be updated, drawn, hidden, disabled, expires, etc
• Provides a base set of game objects

Features

• Templates
• Describe an entities shared values (available animations, effects, etc)
• Sprite
• Basic, Rotated, Animated, Tiled, Physics
• Character
• Skeletal Animations
• Mesh
• Static, Dynamic, Animated

Entity Management

Responsibilities

• Efficiently update and render the entities in the game
• Only update entities that need it
• Only render entities that are visible
• Store entities in some traversable structure
• Handle entity removal/expiration and insertion/addition efficiently
• Time efficiency
• Memory efficiency (pooling)

Implementations

• Simple data structures
• Managed arrays, auto-pruning lists, linked lists, trees, layers of lists
• Entity Component System
• Components of an entity are stored coherently in memory for quick updating
• Systems iterate over all entities with components X, Y, and Z
• Entities don't need to really exist as an object, only as an identifier
• Scene Graph
• Tree of nodes where a node and its descendants could be invisible to the user and efficiently ignored
• Mixed System

Event System

Responsibilities

• Simple and decoupled communication between different components in a game
• Can handle any number of subscribers listening for an event
• Allows events to pass metadata to subscribers
• Events can be binded to other components
• UI can trigger events
• Events can be sent to a server via networking

Features

• Immediate or delayed event triggering
• Some events could interfere with update logic and should be queued and batch ran
• Subscribers can have priority and can ignore events temporarily or forever
• Event propagation can be stopped by a subscriber

Files & Streams

Responsibilities

• Provide functionality for serializing and deserializing game objects to and from one or more formats
• Offers compression and decompression functionality

Features

• Format-agnostic
• The same code could read and write to multiple formats (JSON, XML, binary, etc)
• Reflection based translation
• Some languages offer automatic translation
• Compress/decompress binary data
• Useful for networking
• Map between discriminators and translators
• Discriminator is a string like "vector" which is stored in data to know what to create
• Map between data types and translators

Game Loop

Responsibilities

• Determines when updating and rendering need to occur
• Provides timing information to update logic on time elapsed since last update
• Provides interpolation data to rendering logic when the game is set to render more than update (i.e. fixed updates per second)

Implementations

• Variable
• Every iteration performs an update and render, no maximum rate (fps)
• Interpolated
• Updates at a fixed rate but draws every iteration and sends interpolation data to rendering for frames between updates
• Fixed
• Updates and renders have their own rate, any extra time is spent "sleeping" the thread

Game Patches & DLC

Responsibilities

• Contacts the server and determines which files are out of date and handles downloading and installing
• Contacts the server about new files available and downloads and installs them

Features

• Resource registry with timestamp or hashes
• Client and resource server both have registries for game and each DLC
• Registries have their own hash and timestamp for quick patch checking
• Separate servers store files with their timestamps or hashes and can be securely downloaded

Gaming Services

Responsibilities

• Allows a game to connect to servers which add social and competitive value

Services

• Scoreboards / Leaderboards
• Social Platform Integration
• Facebook, Google+
• User Authentication & Management
• Profile Sync
• See Profiles component

Input

Responsibilities

• Convert raw input data from devices (mouse, keyboard, controllers, accelerometer, etc) into a platform independent API
• Provide input state access or input state change listeners (or both)

Features

• One or more contexts can be active
• A context has mappings between input and actions
• Actions can be called on key up, key press, key down, or the entire duration of a state change
• Actions can be binded to an event system
• Inputs can provide a value on a range (mouse, joysticks, accelerometer)
• Inputs have triggering ranges and filtering
• Input combinations (Ctrl + A)
• Gesture Detection (U U D D L R L R B A)

Localization

Responsibilities

• Provides support for toggling between different localizations:
• Multi-language
• Date formats
• Number/currency formats
• Units of measurement
• Algorithms
• Different locales could implement game logic differently

Features

• Localizations are stored in files containing
• Map of key to text
• Date formats
• Number formats
• Primary units of measurement
• Algorithm information
• Formatted text which contains functions for translating dates, numbers, and between units

Maps

Responsibilities

• Render a section of a map based on the camera
• Provide information about the map to other components
• Traversability (AI > Path Finding)
• Objects to add to Physics
• Convert between screen coordinates and map coordinates
• Trigger map events based on mouse
• Provide invisible map objects that the player can interact with
• Trigger areas could trigger events

Implementations

• Heightmap
• Tilemap
• Used in top-down and platformers
• Hexmap
• Isometric
• Sectioned
• Maps broken up into pieces for minimizing memory usage and the number of entities to update & simulate physics

Math

Responsibilities

• Provides data structures and algorithms necessary for 2D and 3D games
• Primitives
• Geometries
• Springs
• Plotting / Raytracing
• Distance Calculators
• Provides common non-spatial mathematical functions and utilities
• Random Number Generation
• Noise
• Probability Map

Features

• Dimension agnostic structures and algorithms, separate 2D and 3D, or just a singular dimension
• Primitives
• Vector, Point, Matrix, Color, Quaternion, Ranges
• Geometry
• Bounds, Rectangle, Sphere, Line, Plane, Segment, Polygon
• Springs
• Linear & distance (Euclidean and Manhattan)

Multithreading

Responsibilities

• Allow the game code to be broken up into individual tasks that can be executed in multiple threads
• Provide utilities for ensuring threads are NOT reading and writing to a resource at the same time
• Provide information about how much time it takes from task queue, to start, to end, to finishing on the main thread. This may help determine where multithreading doesn't make sense.

Features

• Thread Manager
• Sleep time between tasks
• Target tasks per second/minute
• Max number of threads
• Successful tasks ready to be finished
• Extra threads can be created for large tasks

Networking

Responsibilities

• Provide a nearly seamless experience playing the game with other people
• Handles slow connections
• Converts messages or RPC into bytes to be written to packets
• Allow a client to download resources async
• Provide functionality for creating user servers, matchmaking servers, and game servers

Features

• Connect to any number of servers
• Setup multiple channels to control congestion
• A channel has a priority, whether or not the messages need to be ordered, and whether or not messages need to be reliably sent
• Messages can be cancelled, have their own priority, have a time they need to be sent by, and a number of times we can try to send it again
• A packet has a maximum size so lower priority messages are queued for later
• Each endpoint has a send rate in FPS

Networking > Client

Responsibilities

• Communicates with one or more servers
• Authentication
• Updates
• Matchmaking
• Gameplay
• Can act as a dummy terminal sending commands to the server and predicting the outcome OR acts authoritatively and sends game state to server OR cooperates with other clients in a deterministic simulation (common for RTS)
• Manages actor events sent from server (create, update, delete)

Features

• State-based validation of messages sent from server
• Command oriented (authoritative server)
• Client collects commands (inputs) and sends them to server, server responds with game state updates
• Client-side prediction simulates what the server might send and the client handles corrections if any are required
• State oriented (authoritative client)
• Client sends the game state and the server can validate it to a degree - then passes it along to the other clients

Networking > Gameplay Server

Responsibilities

• Receives and validates messages sent by clients
• Messages can represent commands, actor state, variables, functions (RPC)
• Behaves as the authority of the game state or a passive validator
• Keeps track of the last X game states to validate past messages
• Manages all actors that exist in game and need to be synced with the clients
• Determines which messages need to be passed to each client to minimize the amount of data sent out

Features

• State-based validation of messages sent from client
• Validate commands / states sent by client
• Logical and based on game state history
• Command oriented (authoritative server)
• Server processes inputs and updates local game state
• State oriented (authoritative client)
• Server can validate the state sent and broadcast it to clients
• Each client has a list of relevant actors
• Based on vision, hearing, recent
• LOD actor state communication
• Full, partial, sounds, none

Particle Effects

Responsibilities

• Spawns and animates particles
• Determines which particle systems should be rendered
• Efficiently handles the rapid creation and destruction of particles and how that affects memory usage and fragmentation

Features

• Entity Component Facade
• Deterministic Behavior
• Burst particle system
• Burst size, frequency, particle life, etc
• Trail effects
• Emitter listener defines initial state and final states
• Emitter modifier actively animates the particles
• Particle system AABB for occlusion tests
• Particle ordering for 3D systems

Paths

Responsibilities

• Using one or more points, generates a point with a delta value between 0.0 and 1.0
• Points can be anything (vector, angle, etc)
• Used for motion, sprite animation (frames), skeletal animation, animation transitioning, particle animation, etc

Implementations

• Point
• Single point
• Linear
• Interpolates between a set of points (tween, linear, keyframe)
• Curved
• A path that goes through the starting and ending points and maybe points in between (cubic, quadratic, spline, catmull-rom, etc)
• Disjoint
• Multiple points without interpolation
• Combo
• Multiple paths
• Sub
• Small section of another path

Physics

Responsibilities

• Simulate
• Rigidly body collisions & resolution
• External forces
• Motors
• Constraints
• Triggers events
• Collisions
• Motor or constraint sensors
• Keep track of collision data (contact points and normals)

Features

• Shapes
• Single Geometry
• Compound
• Motors
• Constraints
• Events
• Collision Data
• Generic Facade
• Deterministic

Profiles

Responsibilities

• Provides a way to save player preferences, saved game states, and any achievements.

Features

• One or more profiles
• Profiles synced with user gaming service
• Profile has:
• Preferences
• Achievements / trophies
• Game state saving & loading
• Custom data

Rendering

Responsibilities

• Creates windows, scenes, and cameras
• Determines which entities are visible and need to be rendered
• Handles interpolation between entity states when there are more rendering calls than updates
• Decouples the graphics library from the game logic
• Useful for multi platform support and networked games

Features

• Scene Graph
• Decoupled Rendering System
• Each entity has a view which maps to a rendering implementation loaded at startup
• Graphics library agnostic rendering
• Shaders, Vertex Buffers, Fullscreen Post Processing Effects, Textures, Surfaces, Meshes, Sprites, Immediate Mode Rendering (Graphics), Fonts
• One or more monitors, one or more windows, one or more views per window
• A view renders a scene from a camera's perspective

Screens

Responsibilities

• Manage screens and transitions
• Screens handle their own input
• Screens require certain assets to be loaded before rendering
• Screens draw their own scene and update their own entities
• Events can trigger screen transitioning
• UI can trigger events

Features

• Screen Manager
• Handles current screen and all subscreens
• Handles asset loading
• Triggers events around screen transitioning
• Commonly used screens
• Loading (Assets)
• Video
• Animation (Logos, Credits)

Scripting System

Responsibilities

• Allows a secondary uncompiled language to handle game logic
• Loads and executes the scripts on command or on schedule while passing the necessary inputs
• Scripts have access to variables and functions in game
• Enables a game to be moddable

Features

• Script Schedules
• Determines if and when one or more scripts are ran during gameplay
• Script Groups
• Live Script Reloading
• Easier Game Logic updating with patches
• Tiered Variable Scopes
• Global
• Group
• Function
• Parameter
• Memoized Scripts
• Save & Restore Scopes (save/load game)

​

Spatial Database

Responsibilities

• Indexes objects in space based on their position and geometry
• Can be queried for all objects intersecting/contained in a geometry
• Handles spatial entity position updates

Features

• Querying
• Intersection
• Containment
• K-nearest-neighbor
• Ray tracing
• Continuous Querying
• Notify of changes in query result
• Collision Callbacks
• Implementations
• Grid
• Binary Tree
• Quadtree / Octree
• Sweep and Prune
• Kd-tree

System Integration

Responsibilities

• Provides system information to the developer
• Memory, number of CPUs, OS
• Record videos and screenshots
• Provides system-specific support for the following components:
• Rendering
• Input
• Files & Streams
• Profiles

Features

• Operating system information
• Screenshots & GIFs

Tasks

Responsibilities

• Allow the game code to be broken up into individual tasks and be executed based on priority
• Run tasks within a time frame to ensure a consistent frame rate / user experience

Features

• Tasks
• Priority
• Time constraints
• Status (pending, running, canceled, success, failure, finished)
• Submitted, starting, & completion time
• Task chains and groups
• Task Manager
• Runs tasks within time frame
• Keeps tasks ordered based on priority

Tools

Responsibilities

• Assist the developer in creating, converting, and organizing assets
• Assets in the most appropriate format results in quicker load time
• Provide some basic functionality so the developer can create their own tools that integrate with their code base

Tools

• Script editor
• Particle system editor
• UI editor
• Map editor
• Animation editor
• Character editor
• Asset converter
• World editor
• Combination of previous tools
• Import and place assets in a map
• Organize entities in scene graph
• Set entity properties
• Test out game

User Interface

Responsibilities

• Provides controls that can be utilized with the mouse, keys, or a controller
• Provides skin-able controls and a default skin so tools can easily be created
• Controls can be skinned based on state (default, focused, selected, hover, etc)
• Loads controls from an asset or build them programmatically
• Handles ordering, what controls are focused, where input is triggered, how input events propagate or bubble

Controls

• Inputs
• Text, dropdowns, checkboxes, radios, etc
• Actions
• Button, toggle button
• Containers
• Lists, menus, toolbars, dialogs, sidebar
• Text
• Labels, scrollable text, tooltips
• Layouts
• Absolute positioning, responsive, stacking, grids, tables

Types

Features

• Get properties
• primitive types
• collection types that can be iterated
• some properties are read-only
• some properties are virtual
• Given a root value & type and a path get or the value at the end of the path

Responsibilities

• Expose game object properties and types and associated metadata
• Provides an avenue to inspect and record the state of any number of objects in a way the developer can extend.
• Can be used by editors and other tools to modify game state or setup game state live.
• Can be used by serialization/deserialization to convert objects into formats like XML & JSON
• Can be used by networking system to encode types into smallest number of bits as possible.

What designs / solutions are available?