Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

Games Dev 2 Cheat Sheet (DRAFT) by

Games Dev 2 fsdafdsfdsdfsfdsfdsfd

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Influence Map

Influence Map
Way of viewing the distri­bution of control over a map.
 
Grid out the world and provide a numerical estimate of the influence of every unit on the cell it is in and its neighh­bouring cells.
 
Influence diminishes over distance.
 
The influence of all units in the game are summed in order to generate an influence map which is a repres­ent­ation of influence and location which can be used for strategic analysis.
 
An example can be using the euclidean distance to calculate influence on each square­/cell. influence = 0.5distance
 
Calcul­ation is done for every unit with positive values used for friendly units and negative for enemies.
Front line
Line that can be traces at the edge of positive and negative cells.
Concen­tration of forces
The areas with the highest positive values are where the influence of the friendly forces are strongest.
Maths
The influence falls off over distance which can be linear or expone­ntial with distance. Influence is repres­ented by the type of weapons for example. ie a sword is less powerful than a gun
 
Because inflen­uence never reaches 0, use a cut off point for very small values to avoid unnece­ssary calcul­ations.
Desira­bility
A weighted sum which would change accord­ingly to the context or type of decision.
Time & distance
Even though influence diminishes over distance it can still have an impact on decisions taken by other units far away
Time & probab­ility
Can suggest how we use influence maps to represent potential actions
Interp­reting Results
Influence state decision such as combat want to choose acell in which enemy is weak but in which we are strong
 
Examine the distance of units to the front-line both friendly and enemy which can help indicate areas to which we should be paying special attention to.
Terrain
Can increase or decrease the propag­ation of influence according to terrain. e.g. take obstacles into account

Trees

Decision Trees
A decision tree is way of repres­enting knowledge.
 
A decision tree is a way of using inputs to predict future outputs.
 
It is a classi­fic­ation method, decision trees learn from examples using induct­ions. They can deal with uncert­ainty. thye dont use ranges because of large numbers of branching altern­atives.
Sequence
Execute the first node that has not yet succeeded. Keep executing a task until it returns a success. Any failure in the sequence is a failure overall. Fix or continue to next sequence.
Selector
Selects one child node to execute. Could be random or some sort of control mechanism.
Decorator
Single child node. Allows for other types of operation such as repeti­tion, filter or an inventor.
ID3 algorithms
Note: Look at Tree PP for method

Production Systems

Knowledge Repres­ent­ation
Knowledge is repres­ent­ation and the methods for manipu­lating it
Procedural Knowledge
Is operat­ional ie what to do when
 
Most common method is production rules
 
Production Rules
New knowledge is derived using various reasoning mechan­isms. IF AND THEN
 
A deductive argument can only bring out what is already implicit in it premises but can give rise to questions.
 
Reasoning is carried out by an interp­reter
 
2 methods: forward chaining from assertions and backward chaining from hypotheses

Blackboard Model

Blackboard Model
Is a decision making method.
 
Problems and all workings out are written on the blackb­oard.
 
The insight is that a collective unders­tanding of a problem may be better than an individual unders­tan­ding.
 
May be more efficient to have many experts each with a partial unders­tading of a problem than one expert that has a full unders­tan­ding.
Specia­lists
No specialist unders­tands the whole problem
 
Component that can operate on the data written p on the blackb­oard. The area of expertise of each specialist is narrow. A specialist may indicatate a relevance value indicating how they can deal with the problem.
 
No commun­ication allowed between experts. Everything goes through the medium of the blackb­oard.
Arbiter
Selects which of the specia­lists to execute
Archit­ecture
2 types of archit­ecture
 
A) Multiple specia­lists each with their own area of expiertie. It is assumed that only one specialist at a time will be dealing with a specific problem.
 
B) Specia­lists with overla­pping areas of expertise. More than 1 specialist can signal relevance. More than one specialist can deal with a problem at a time.
Charac­ter­istics
Blackboard offers flexib­ility
 
Order of reasoning not pre-de­ter­mined
 
At any given point that most relevant specialist will be selected
 
Specia­lists can act in a variety of ways like requesting more data etc.
 
A specialist need not know how its assertions or signals are going to be used.
 
The specialist is only concerned with fulfilling a request.

Entity IDs And Commun­ication

Forms of Entity Identi­fic­ation:
Pointers, Names, Entity UIDs (Evaluate these)
Entity Pointe­rs(­pro­s/cons)
Problems occur when entities are destroyed. For example when an entity high up in the chain dies, therefore, making the pointer invalid. Can lead to exceptions
Entity UIDs(U­nique Identifier
+ Holds a UID instead of a pointer
 
+ Uses a function to safely convert into pointer
 
+ An error is returned when resource doesn't exist. A lot easier to handle than invalid pointers.
 
+ Hash tables are used which provide efficency. Keys are converted into integers.
 
- Collisions can occur in hash tables
Entity Messaging
Better to send messages to entities than to use getters and setters
 
+ Entities only need to know messaging types
 
+ Can make intera­ctions more complex, by having replies for example.
 
Need a system messenger class. Avoid using new and delete. Use statics
 
- Finding the position of another entity can be clumsy
 
- There is latency between responses
 
+ Entity UIDs can be converted to pointers to access generic or commonly used data
 
+ Could implement an Immedi­ate­Message function where message is sent directly to entity and return value is response

Tools Progra­mming

Tool Chain
Sequence of tools needed to convert raw assets through to usable game data.

Camera Projec­tio­n/P­icking

Model Space
Entity's mesh is defined in its own local coordinate system
World Space
Transf­orming a model in the world
World Matrix
Transf­orming model from model space to world space with a matrix.
Camera Space
The scene as view from the camera's position.
View Matrix
Transf­orm­ation from world space to camera space is done with the view matrix.
Camera to Viewport space
Project camera space into 2D.
 
This is done with the projection matrix
Projection Details
Near clip distance is from camera position to viewport.
 
Far clip distance is furthest we can see from camera position.
 
FOV - field of view

Compon­ent­-Based Entities

Problems with OO
Tight couping between parent and child. Features of parents affect or limit the features of children
 
Hierar­chies are static, games need more flexib­ility
 
Multiple inheri­tance can be use but causes confusion
Compon­ent­-based Archit­ecture
Entity holds a dynamic list of components
 
Each component has an update function called when entity is updated
 
Messages to entity passed to each component. e.g. health component reacts to a damage message
 
Send messages to compon­ent­s/e­ntities within the same entity
 
+Litte coupling between components
 
+Easy to add/remove functi­onality
 
+Simple to concep­tualise
 
+Easily built from script­/data files
 
-Much more message passing
 
-May be too flexible
 

Concurrent Progra­mming

Concurrent Program
Simult­ane­ously executes multiple intera­cting comput­ational tasks. Not the same as parallel program
Proces­ses­/th­reads
The tasks may be separate programs or a set of proces­ses­/th­reads created by a single program.
 
Focus of concurrent progra­mming is the intera­ction between tasks and the coordi­nation of shared resoruces.
Parallel Progra­mming
Simult­ane­ously exutes a single task across several processors
Processes
A program is just a passive set of instuc­tions whereas a process is an active instance of a program, acually being executed
 
Each process has a distinct set of resources. A section of memory (RAM, cache). System Resources. Security settings (perms), processor state
Threads
A program may in turn contain several threads of execution
 
Threads conatin process resources Look Above ^^
 
Processes can be single threaded or multi-­thr­eaded
 
Multi-­thr­eaded can be more efficent if done right
 
Multi-­thr­eaded processes are more efficient than multi-­process programs due to less setup and commun­ication since threads share resources.
Data Coordi­nation
Major issue with concurrent is preventing concurrent processes from interf­ering with eachother.
Resource Coordi­nation
Preventing sharing of resources from interf­ering. e.g. One process rewrites content of the file while another is in the process of reading it.
Race Conditions
2 processes racing to complete their task first
 
A flaw in a concurrent system where the exact sequence or timing of events affects the output.
 
Hard to track down due to shared data/r­eso­urces being accesses almost simult­ane­ously.
Locking
A resource, piece of data or section of code can be locked to a single process or thread.
Critical Section
A section of code that can only be accessed by a single thread at a time.. The section of code is aasumed to be accesing data that needs careful synchr­oni­sation. Only locks code not data.
Mutex
An object that can only be owned by a single thread on a single process at a time.
Semaphore
An obkect that can be held by up to N threads simult­ane­ously. Section can be shared by a few processes but not an unlimited number, which limits the number resources that can be opened simult­ane­ously.
Timers
Can pause a thread until a certain time or repeatedly wake/sleep a thread.
Blocking
When a thread or process is prevented from accessing data or executing code due to synchr­oni­sation object is said to be blocked.
 
When a thread is blocked wait for the code/data to become available by allowing the thread to stall (sleep) , which loses the advantages of concur­rency. And can add a timeout to help limit how long to wait. Or simply skip the task that requires the blocked data/code
Deadlocks
When 2 threads try to lock 2 resources they stall waiting for eachother causing a deadlock and each thread will wait forever for the other. Can only be resoved by better synchr­oni­sation of objects. ie associate a single mutex to the ownership of any part of the group.

Text-based Game Data

Hard-c­oding
Embedding of data in program code
 
- Requires recomp­ilation to change data which can be slow for large project.
 
- Cannot be done at runtime
 
To improve this we can use data files.
 
+ Hard coded data is stored in a text format which means it is human readab­le/­wri­table.
 
Text based data will need to be parsed at run-time.
Binary data files
Can help in large data sets as it's quicker to parse but they're not human readable
Issues with Text-based data
Slower than using hard-c­oding
 
Text need more storage than binary
 
Need good test cases to have good text valida­tion.
 
Additional code develo­pment required
XML (eXten­sible Mark-up Language
Structured data
 
Not a progra­mming language
 
Stream­-or­iented parsing - Uses callbacks as tags that are opened and closed
 
Tree-t­rav­ersal parsing - Reads entire document and passes back as a complete hierar­chical structure
XML Disadv­antages
The redundancy of syntax causes higher storage making parsing take longer.
 
XML is less readable compared to other text-based document formats such as JSON. XML doesn't support arrays.
 
XML files are usually larger due to being verbose therefore it totally depends on who is writing it.
 
Advantages XML
XML is platform and progra­mming language indepe­ndent therfore can be used by any system and supports hardware and software change.
 
Support Unicode and intern­ational encoding standard for use with different languages and scripts.
 
The data stored and transp­orted using XML can be changed at any point of time without affecting the data presented. XML allows validation using DTD and Schema. This validation ensures that the XML document is free from any syntax error.
 
XML simpli­fie­sdata sharing between various systems because of its platform indepe­ndent nature.

Planning

STRIPS (Stanford Research Institute Problem Solver)
 
Formal language that assumes that all conditions not stated to be true are false
 
Planning is a process of divising a sequence of actions to achieve a goal.
 
Pathfi­nding is an example of planning
 
Uses actions, states and goals
 
In language can be expressed as logical statements like At(B). They can be combined like At(door) AND holdin­g(key)
 
Actions can be specified in terms of precon­dit­ions. Like Move(A, B), Precon­dit­ions: At(A), Postco­ndi­tions: not At(A), At(B)
 
Precon­dition = entry state
 
Postco­ndition = exit state

Finite State Machines (FSM)

FSMS model states, transi­tions and actions
Probab­listic FSM
Describe any FSM which includes probab­ilities
 
Probab­ilities are placed on transi­tions out of states
 
Can have an output state which has a probab­ility associated with it.
 
Multiple output states with probab­ility scores used to select between them
 
Probab­ilities could be fixed or could change over time. Can extend probab­ilities in lots of ways e.g. trigger functions.
Stack-­(based FSM)
Track past states using a stack
 
Stacks are pushed on and popped off the stack at transi­tions. This means that an agent can be interr­upted and later return to a previous state.
 
Stack based FSM can produce a simple FSM than a standard FSM but not always approp­riate tor return to a previous state.
Hierac­rchical FSM
A state may link to another FSM or set of FSMs
 
Transition from a state leads to a brand new FSM. Use the stack to store the initiating state.
 
If control is passed down the hierarchy then the new FSM starts at its own initial state. Allow you to identify and separate out behaviour or tasks. Helps reduce size and complexity of a FSM
 
Record the original state and any associated data because control may pass back at some point.
 
- May lead to code re-use since a task could be used in several different situations
 
To avoid code repitition allow the re-use of FSMs.
 
The hierarchy of states can produce behaviour unique to an agent even if states are shared with other agents.
 
It is possible to swap FSMs in and out.
 
This can be done with any one of the FSM layers.
 
Hence an agent could exhibit different implem­ent­ations of a task in different situat­ions, e.g. different combat FSMs.
 
A state could have sub states
 
This can bypass the need to have a new FSM but avoid doing it too much or else it can lead to the FSM becoming broken.
Subsum­ption FSM
Intell­igent behaviour can be built from a collection of simple machines.
 
Decompose complex behaviour into simple modules, operations or tasks.
 
The modules are implem­ented as layers of FSMs
 
Thje layers of FSMs all operate at the same time.
 
Lower layers deal with short-term goals and higher layers deal with long-term goals.
 
Lower layers have priority

Entity Update and Rendering

Entity Update
Each entity has its own update function
 
Can be called every frame or less frequently
 
Reciev­es/­pro­cesses messages
 
Send messages
 
Decision making
 
+ Entity behaviour and state collected together
 
+Easy to maintain
 
+ Easier to comprehend behaviour
 
- Overall game behaviour is distri­buted, can get unexpected intera­ction
 
- Messaging between entities can be long-w­inded
Scene Update
In the TL-Engine a single global update function is used
 
Can become bloate­d/hard to maintain
 
No attempt to encaps­ulate behaviour
 
Using entity­-based update still uses Scene Update to do certain global update work
 
+ Global function easy to work with
 
- Model state tends to become a set of globals
Entity Rendering
Each entity gets its own render function. A function that's called every frame to update animat­ions, positions, textures etc.
Pre/Post Rendering
Called for entities before and after the main rendering calls. E.g. Calcul­ating camera view matrix
Dot Product Formula
X.T = |X||T|­cos(B)
 

Scripting for Games

Why Scripting
Ease of develo­pment - Less prone to erros and less intricate
 
Much easier to change and test
 
No recomp­ila­tion, change at runtime
 
Think about Unity - Use scripts to control entiti­es(game objects) player as an example
Scripting (pros/­cons)
- Perfor­mance - Scriping language often interp­reted. Can be 10x slower than C++
 
- No control of memory management can cause issues
 
- Limited tool support
 
- Hard to spot errors
 
- Need to write interface to our c++
 
Don't necces­sarly need to use scripting languages
 
Consider language based on perfor­mance needs and memory footprint, feature set etc.
Python
Portable, interp­reted, OO progra­mming language
 
Dynami­cally typed
 
Automatic garbage collection
 
Blocks are defined by indent­ation
Lua
Lightw­eight scrupting language
 
Not OO
 
Small/­Simple feature set
 
Small memory
 
Small but powerful feature set
 
Dynami­cally typed
 
Only one kind of data structure - the table
 
Simple integr­ation with C API
 
Less high level than Python
 
Rather niche language outside games
 
Better perfor­mance, less memory use
 
Simple interface for C and C++
 
Lends itself well to game entity scripting
 
Interf­acing LUa with C++ is fairly simple since Lua is itself a C program and has a direct C API.

Cellular Automata

Cellular Automata
Are machines which model problems as a set of discrete cells.
Game of Life
John Conway
 
Uses a 2D grid as a map to lay out the actions of the game.
 
Binary cells used to represent entities on the map with either alive or empty where empty is dead.
 
Each cell only considers its 8 neighb­ouring cells: orthogonal and diagonal
 
All cells are examined simult­ane­ously
 
Each cell considered in its own right.
Game of life rules
A live cell with less than two live neighbours dies. Analogous to loneliness or underp­opu­lation. A live cell with more than three live neighbours dies. Analogous to overpo­ulation or crowding. A live cell with two or three live neighbours survives. It becomes part of the next generation of cells. An empty cell with three neighbours becomes a live cell.
 
Need to seed the system with alive cells to start the game otherwise nothing happens.
Rules
1. A live cell with less than two live neighbours dies. Analogous to loneliness or underp­opu­lation. A live cell with more than three live neighbours dies. Analogous to overpo­ulation or crowding. A live cell with two or three live neighbours survives. It becomes part of the next generation of cells. An empty cell with three neighbours becomes a live cell.
 
2. A live cell with more than three live neighbours dies. Analogous to overpo­ulation or crowding.
 
3. A live cell with two or three live neighbours survives. It becomes part of the next generation of cells.
 
4. An empty cell with three neighbours becomes a live cell.
 
Refer to lecture powerpoint for game of life examples

Terrain Analysis

Applic­ability
Wide variety of approa­ches. From Team based games, squads, enemy AI, moving into cover, adopting to a good firing position etc.
Specific Requir­ements for terrain analysis
Repres­ent­ation of terrain
 
Reason about that repres­ent­ation
 
Difficult to generalise
 
Typically custom built
 
General points can be made
Initial Analysis
Need to decide the attributes being used in the reasoning. Cannot recognise a choke point unless you hae already decided that these are of use to your game.
Waypoints
Reasoning using waypoints
 
Need a repres­ent­ation of the world.
 
For each waypoint calculate its offensive and defensive value
 
Direct­ional inform­ation needed
 
Can take various factors into consid­eration including cover, lack of target etc.
Static and Dynamic - Prepro­cessing
Some static analysis is compar­atively easy. Hills shore etc.
 
This can be pre-pr­ocessed
 
More difficult with dynamic terrain though
Clustering
A strategory game needs to be able to recognise dynamic areas like towns and forests.
 
The region is complex. Better to convert into convex hull.
Convex Hulls
Easy to reason with.
 
eed to know what points are inside the convex hull.
Choke points
Use an influence that can grow.Each region is surrounded by a uniform area. Arny areas that overlap are considered to be choke points.
 
Choke points can be extended to show where to hide. This is done by tracing along the edge of a region going away from the choke point until there is no direct line of sight to the choke point.
 
Influence maps have been used for terrain analysis to identify locations such as resource points, building routes for attack or staging areas for attack.
Cover behind objects
Simplest case is single opponent firing at you and you track a line of sight to the edges of the object. Any point in between the two edge points is in cover. Can be used for multiple opponents. Perfect location for cover can be calculated by calcul­ating the centre of gravity of the object. Assume that the object is 2D and that mass is evenly distri­buted.
 
Simply trace a line from centre to oppoent or opponents

Resource Management

Resour­ce/­Asset
Any file that is loaded and used by elements in the game
Asset Management
PRogra­mming involved in loading and working with asset files
Resource Template
Template that stores the inform­ation about the assets in the game.
Resource loading issues
System automa­tically loads all the level resources at setup time. No hard coding
 
Repeat­ition of resource loading. Therefore, need to identify resources that have already loaded.
 
Could load resources on demand when entity is needed
Shared Resources
Find if resource has already been loaded. Can serach the entire list but may be slow
 
Use hash map instead for efficency. Could use UIDs like with entities.
Resource Destru­ction
Could destroy all objects at the end of level
 
Could destroy exlicitly so each entity has a delete function.
Track Resources
Track resources and delete them when they're not being used.
Smart Pointers
Pointer that manages its own memory and atomat­ically detect the reference count which is increa­sed­/de­creased according to the reference count.
Reference count issues
If reference count reaches 0 they are deleted and may need to be used later on
 
Reloading can cause stutter in game, which we want to avoid.
 
To deal with this issue we can store a single persistent reference throughout the game.

Turing Machine

Turing Aproach
Turing defined a class of abstract machines now called Turing Machines
 
Turing is breaking maths down to its most basic operat­ions.
Turing Machine
Recasts this idea as a machine he supposes can perform all of the functions that the man does.
 
Turing defined a class of of abstract machines now called Turing Machines.
 
A mathem­atical model of comput­ation that defines an abstract machine which manipu­lates symbols on a strip of tape according to a table of rows.
Relevance to computers
Turing machines can do recurs­ions, add and do functions. You can create any mathem­atical operation we know about using these basic operat­ions.
Universal TM
A basic TM can compute only one particular function. Where Universal TM is one which can simulate any other machine.
Turing's Thesis
The definition of comput­ation is "­som­ething which can be done by TM".
Church
Demons­trated that any comput­ation can be done using Lambda calculus.
Issues with TM
The halting problem: the determ­ination of whether a TM will come to a halt given a particular program. Disproof by showing a contra­ction. It posits the existence of a program to solve the Halting Problem and then demons­trates that it would lead to a contra­dic­tion.
Proof
Testing proves in general halting problem cannot be solved. The reason is that it gives rise to an inherent contra­dic­tion.
Humans
Human minds might be Universal TMS as it has been argued that a Universal TM should in principle be capable of intell­igence.
Real computers
Universal TM is comparable to real computer. Anything that a real computer can compute a TM can compute. It is easier to describe certain algorithms using a TM than using a real computer.
 
Universal TM are unbounded with infinite space, where computers are bounded both time and space are limited. TM express algorithms in general terms where as a real computer needs to consider other things such as precision and error condit­ions.
 
A TM uses a sequential tape. A real computer uses registers and random access storage. TMs do not model concur­rency easily i.e. different tasks performing at the same time.