gamedev
#define gamedev: \
I-----------------------------------------------------------------------------------\
I-----------------------------------------------------------------------------------\
I-----------------------------------------------------------------------------------\
I \
I /$$$$$$ /$$ \
I /$$__ $$ | $$ \
I | $$ \__/ /$$$$$$ /$$$$$$/$$$$ /$$$$$$ /$$$$$$$ /$$$$$$ /$$ /$$ \
I | $$ /$$$$ |____ $$| $$_ $$_ $$ /$$__ $$ /$$__ $$ /$$__ $$| $$ /$$/ \
I | $$|_ $$ /$$$$$$$| $$ \ $$ \ $$| $$$$$$$$| $$ | $$| $$$$$$$$ \ $$/$$/ \
I | $$ \ $$ /$$__ $$| $$ | $$ | $$| $$_____/| $$ | $$| $$_____/ \ $$$/ \
I | $$$$$$/| $$$$$$$| $$ | $$ | $$| $$$$$$$| $$$$$$$| $$$$$$$ \ $/ \
I \______/ \_______/|__/ |__/ |__/ \_______/ \_______/ \_______/ \_/ \
I-----------------------------------------------------------------------------------\
I-----------------------------------------------------------------------------------\
I-----------------------------------------------------------------------------------I
• graphics belong here too
• simulations belong here too
"Algorithms/Raster"
Images:
Channel:
• refers to a visible component of a pixel
• usually means a color or transparency
• the most common channel width is 8 bits { standard grayscale: (black) 0 <---> 255 (white) }
○ Types
grayscale : single channel
RGB : "Red, Green, Blue"
sRGB : "Standard Red, Green, Blue"; ISO RGB standard; 8 bit
RGBA : "Red, Green, Blue, Alpha"
CMYK : "Cyan, Magenta, Yellow, Key"; used in printing
Y'UV/YUV : naming dreamed up by the utterly deranged
|===============================|
| Common Usage | Channel |
|===============================|
| Analogue displays | YUV |
| Printers | CMYK |
| Screens | *RGB* |
| Computer vision | grayscale |
|-------------------------------|
DIP:
• "Digital Image Processing"
• any operation that manipulates an image
• quantization is the process of truncating real colors to digital values
— LoG:
• "Laplacian of Gaussian"
• edge detection algorithm
• outputs grayscale
— CLIP:
• "Contrastive Language–Image Pretraining"
• uses vectorization
• NN for describing images
— SIFT:
• "Scale-Invariant Feature Transform"
• detects key points
Color_inversion:
• each channels value is subtracted from the maximum
• if the channel width is a 2 power, bitwise-or works
Histogram:
• creating a dictionary of {channel value : number of pixels averaging}
• each pixel is iterated, the channel values are averaged after rounding,
the corresponding key is upped by one (starting from 0)
• usually displayed visually and similar to a fire-chart
— based on it its easy to tell over/under-exposure:
{
▁▁▄█ - right heavy -> OVER exposure (too much light)
█▄▁▁ - left heavy -> UNDER exposure (too little light)
}
Diffing:
MSE:
• "Mean Square Error"
• the value of each pixel is compared to the corresponding pixel
• only works with equally sized images (still, resizing is a thing, you know)
. identical: 0 <-> different: N
SSIM:
• "Structural Similarity Index"
• consideres structural information, luminance and contrast
. identical: 1 <-> different: 0
Clustering:
Isodata:
• gradually find clusters from random initial sets
Convolutional_matrix:
• dot prodroduct based
○ common matrixes
— 1 -2 -1
0 0 0
1 2 1
— 1 0 1
— 2 0 2
— 1 0 1
0.04 0.04 0.04 0.04 0.04
0.04 0.04 0.04 0.04 0.04
0.04 0.04 0.04 0.04 0.04
0.04 0.04 0.04 0.04 0.04
0.04 0.04 0.04 0.04 0.04
Kernel_based:
• "window"/"filter"
• the kernel is a matrix iterating over the image
• can be used to reduce artifact noise for computer vision
• true/false usually means the values of a binary image;
however they are arbitrary definable to colored images,
such as averaging the color values and checking for a threashold
{
┌─────────────────────┐ █X
│ │ ██
│ ███████ │
│ ██████████ │
│ ████████ │
│ ████ │
│ ██████████ │
│ █████████████ │
│ █████ █ │
│ ███ ███████ │
│ ███████████ │
│ ███████ │
│ │
└─────────────────────┘
the upper right corner of the kernel is marked, because that marks the "current pixel";
usually the middle pixel would be current one, but this highlights that its arbitrary
(and a 3x3 kernel would be too large for ascii art)
┌─────────────────────┐
│ │
│ ░██████ │
│ ░░░░██████ │
│ ░░░░░░██ │
│ ░███ │
│ ░█████████ │
│ ░░░░░░████░░░ │
│ ░████ ░ │
│ ░░█ ░████░░ │
│ ░░██████░░░ │
│ ░░░░░░░ │
│ │
└─────────────────────┘
┌─────────────────────┐
│ │
│ ██████ │
│ ██████ │
│ ██ │
│ ███ │
│ █████████ │
│ ████ │
│ ████ │
│ █ ████ │
│ ██████ │
│ │
│ │
└─────────────────────┘
┌─────────────────────┐
│ ░░░░░░░░ │
│ ░███████░░░ │
│ ██████████░░ │
│ ████████░ │
│ ░░░░░░████░ │
│ ██████████░ │
│ █████████████░ │
│ ░░░░ ░░█████░ █░ │
│ ███░░░░███████░ │
│ ███████████░ │
│ ███████░ │
│ │
└─────────────────────┘
┌─────────────────────┐
│ ████████ │
│ ███████████ │
│ ████████████ │
│ █████████ │
│ ███████████ │
│ ███████████ │
│ ██████████████ │
│ ████ ████████ ██ │
│ ███████████████ │
│ ████████████ │
│ ████████ │
│ │
└─────────────────────┘
┌─────────────────────┐
│ ░███████ │
│ ███████████ │
│ ░░░█████████ │
│ ░████████ │
│ ░██████████ │
│ ░██████████ │
│ ░░░░███████░░█ │
│ ████ ████████ ░░ │
│ ░░███████████░░ │
│ ░░███████░░░ │
│ ░░░░░░░░ │
│ │
└─────────────────────┘
┌─────────────────────┐
│ ███████ │
│ ███████████ │
│ █████████ │
│ ████████ │
│ ██████████ │
│ ██████████ │
│ ███████ █ │
│ ████ ████████ │
│ ███████████ │
│ ███████ │
│ │
│ │
└─────────────────────┘
┌─────────────────────┐
│ ░░░░░░░ │
│ ██████░░░ │
│ ██████░░ │
│ ██░░ │
│ ░░░░░░███░ │
│ █████████░ │
│ ████░ │
│ ░ ░░████░ │
│ █░░░░░████░ │
│ ██████░ │
│ │
│ │
└─────────────────────┘
┌─────────────────────┐
│ ███████ │
│ █████████ │
│ ████████ │
│ ████ │
│ ██████████ │
│ ██████████ │
│ █████ │
│ █ ███████ │
│ ███████████ │
│ ███████ │
│ │
│ │
└─────────────────────┘
}
erosion:
█X
██\
\
██ ░█
██ ██
█X
██\
\
░█ ░█
██ ██
█X
██\
\░█ ░█
██ ░█
█X
██\
\█ ░█
░█ ░░
• the kernel is filled with true values
• logical and is performed (the pixel is only true, if all pixels under the kernel is true)
dilation:
• the kernel is filled with true values
• logical or is performed (the pixel is true, if any of pixels under the kernel is true)
opeing:
dilate(erode(${Image}))
closing:
erode(dilate(${Image}))
Models: Models:
• describing 3D objects in computer readable format
• most 3D models are shell like; only the surface is defined
Poligon_mesh:
• vertices, edges and faces are used
VV:
• "Vertex-Vertex"
• vertexes and their connections are recorded
• face data is implicit
• minimalistic
• much of what will be rendered could be precomputed
+--------------------------------+
| Vertex list |
+------+----------+--------------+ v6 (0,1,1) v7 (1,1,1)
| Name | Position | Connected to | .+------+
+------+----------+--------------+ v2 (0,0,1).' | .'|
| - v0 | 0, 0, 0, | v1, v2, v4, | +------+'v3|(1,0,1)
| - v1 | 1, 0, 0, | v0, v3, v5, | | | | |
| - v2 | 0, 0, 1, | v0, v3, v6, | v4 (0,1,0)| ,+--|---+ v5 (1,1,0)
| - v3 | 1, 0, 1, | v1, v2, v7, | |.' | .'
| - v4 | 0, 1, 0, | v0, v5, v6, | +------+' v1 (1,0,0)
| - v5 | 1, 1, 0, | v1, v4, v7, | v0 (0,0,0)
| - v6 | 0, 1, 1, | v2, v4, v7, |
| - v7 | 1, 1, 1, | v3, v5, v6, |
+------+----------+--------------+
FV:
• "Face-Vertex"
• most common
• hardware support
• faces are stored with vertexes
• from a face points can be looked up,
from points neighbouring faces can be looked up
+--------------------+ +---------------------------------------+ // NOTE: this cube still has a back side
| Face List | | Vertex list | // it would be just too awkward to draw
+------+-------------+ +------+----------+---------------------+ v6 v7
| Name | Vertexes | | Name | Position | Used in | .+------+
+------+-------------+ +------+----------+---------------------+ .'f4'.f5.'|f3
| f0 | v0, v1, v2, | | - v0 | 0, 0, 0, | f0, f6, f10, f11 | v2 +------+' .| v3
| f1 | v1, v2, v3, | | - v1 | 1, 0, 0, | f0, f1, f2, f3, f10 | |'. f1 | .'|f2
| f2 | v1, v5, v7, | | - v2 | 0, 0, 1, | f0, f1, f4, f6, f7 | | '. |.' + v5
| f3 | v1, v3, v7, | | - v3 | 1, 0, 1, | f1, f3, f4, f5 | | f0 '.|'.'
| f4 | v2, v3, v6, | | - v4 | 0, 1, 0, | f6, f7, f8, f9, f11 | +------+'
| f5 | v3, v6, v7, | | - v5 | 1, 1, 0, | f2, f8, f10, f11 | v0 v1
| f6 | v0, v2, v4, | | - v6 | 0, 1, 1, | f4, f5, f7, f9 |
| f7 | v2, v4, v6, | | - v7 | 1, 1, 1, | f2, f3, f5, f8, f9 |
| f8 | v4, v5, v7, | +------+----------+---------------------+
| f9 | v4, v6, v7, |
| f10 | v0, v1, v5, |
| f11 | v0, v4, v5, |
+--------------------+
NURBS:
• "Non-Uniform Rational B-Spline"
• "the vector images of modelling"
• defines a perfectly curved surface with end points and control weights
• the weights are do NOT sit at the surface
• the curves stay very accurate and easy to predict no matter the scale
• described by precise mathematics
• very hard to work with
• mostly used in engineering software { CADs; vehicle blueprint modelling }
Constructive_solid_geometry:
• when complex objects are created from simple object by the means of bool operations
{ a sphere is subtracted from the edge of a cube }
Surface_subdivision:
• an algorithm that refines a mesh
• hard to describe shapes may be approximated easily
• recursive, the refined mesh is re-refined N times
• every iteration results in more vertexes,
complexity and compute exponentially grows
• the methodology that defines how the vertexes change is called
the refinement scheme
• a refinement scheme which perserves the original vertexes is called
an interpolation scheme
• a refinement scheme which changes the original vertexes {move/delete} is called
an approximation scheme
LODing:
• "Level Of DetailING"
• referes to the act of playing with mesh details
• has performance benefits
• object further from the viewport or moving with higher speeds can
have lower levels of detail (vertex count) as the user will not notice
{ you are playing an FPS on a crappy machine, you zoom it with your sniper to
epically own some noob and get stunned regarding how shit the far away looks
for a second }
Rendering: Rendering:
https://github.com/agvxov/softwareRenderer
• the process of displaying sprites or 3D models in 2D is called rendering
( thats by far not the only meaning it has in compsci)
• models can be pre-rendered for a performance gain
{ 8 sides of a skeleton is rendered, changing as it turns,
the player camera cannot be rotated }
• a wireframe render is a render where only the vertexes
and their connecting edges are visible { no textures added; no lighting }
Clipping:
• union operation on graphic objects
• primarily deals with determining what fits into the viewport
Cohen_shutherland:
• rectangle-line clipping
— the screen is split to regions based on bitmasks:
: LEFT = : CENTRAL : RIGHT :
: 0b0001 : 0b0000 : 0b0010 :
..................................
: :
: 0b1001 | 0b1000 | 0b1010 : TOP = 0b1000
: ---------+----------+--------- :
: 0b0001 | 0b0000 | 0b0010 : CENTRAL = 0b0000
: ---------+----------+--------- :
: 0b0101 | 0b0100 | 0b0110 : BOTTOM = 0b0100
: :
``````````````````````````````````
{
function shutherland(line):
if (is both enpoints central):
accept
elif (is both endpoints share plain):
reject
else:
shutherland(
modify_one_out_point_to_edge_intersection()
)
}
Visible_surface_determination:
• an algorithm that decides what surfaces are visible to the camera
Painters_algorithm:
• named after the painting technique of painting distant objects first,
and partially painting over them with closer objects later on
• polygons are sorted from furthest to closest and each is drawn in order
• far away polygons are usually overdrawn
• simple
• requires little memory (just a polygon list and a screen buffer)
• slow
• cyclical overlapping will fail; such as:
____ ____
\ \/ /
\ / /
\/ /
/ /\
/ / \
/ /\ \
/ / \ \
___/___/____\ \__
| \ \_|
‾/‾‾‾/‾‾‾‾‾‾‾‾\ \
/___/ \___\
• intersections will fail
Reverse_painters:
• polygins are sorted from closest to furthest and drawn in order,
with the condition that pixels may not be overwritten
• considerably faster
• suffers the same errors
Newells_algorithm:
• fixes the painters problems
• uppon overlapping splitting is done to new object
which appear in the polygon list independently
Z_buffering:
• "Z-buffering"/"dept buffering"
• a so called z-buffer is stored with pixel dept information which is used to
determine pixel overwritting
Frame Buffer Z-buffer
┌───────┬───────┬───────┬───────┐ ┌───────┬───────┬───────┬───────┐
│ pixel │ pixel │ pixel │ pixel │ │ depth │ depth │ depth │ depth │
├───────┼───────┼───────┼───────┤ ├───────┼───────┼───────┼───────┤
| pixel | pixel | pixel | pixel | | depth | depth | depth | depth |
├───────┼───────┼───────┼───────┤ ├───────┼───────┼───────┼───────┤
| pixel | pixel | pixel | pixel | | depth | depth | depth | depth |
├───────┼───────┼───────┼───────┤ ├───────┼───────┼───────┼───────┤
| pixel | pixel | pixel | pixel | | depth | depth | depth | depth |
└───────┴───────┴───────┴───────┘ └───────┴───────┴───────┴───────┘
Lighting:
• "shading"
• the process of determining how bright parts of a model should be
Static:
• brightness of textures is determined at compile time
• effitient
• no cool lighting effects can be created { dynamic day cycle change; player flashlights }
Ray_tracing:
• rays of light are simulated
• very expensive
• used to be only for animation until hardware caught up so that
video games may utalize it too
Turtle:
https://docs.python.org/3/library/turtle.html
• abstraction
— the developer controls a turtle; it can:
• turn right
• turn left
• go forward
• easy to learn
• easy to use
• easy to create complex shapes algorithmically
• high overhead
• does not scale well
• ideal for quickly creating pre-rendered media
Camera:
• common engine/renderer abstraction
• represents a view into a map or UI
• can move without affacting rendering
• multiple cameras could be utalized for rapid display context switch-ing
Map_design:
direction_of_progress:
• (usually) it should be clear to the player which way to go
• the optimal direction of progression should be clearly signalled
• lighting is often used
• in light rich environments the color is often used
Perspective:
• the types of the camera views
— first person:
• like inside someones head
• the camera rotates in place
{ Call of Duty }
— second person:
• like a camera on the shelf
• a first person like camera follows a foreign object
{ PS2 Resident Evil }
— third person:
• like a drone over someones shoulder
• the camera rotates orbitally
{ Dark Souls }
— top-down:
• like a bird-sight view
• the camera is floating above
{ Catan }
— iso-metric:
• angled
• often distorts the perspective
• often pointed at the edges of a cube-ish world
{ XCOM }
Path_finding:
Blind:
Random_backstep:
• move towards the goal
• if obstacle encountered then move randomly
• fast
• looks like a very convincing moth
• gets stuck all the time
Graph_search:
"Algorithms"
• these are specialized versions of regular
Dijkstras:
• incrementally explore each node, storing a cost value for them,
signaling where the search should continue first
• guarantees the shortest path
• slow
A_star:
• "A*"
• modified dijkstra's
• with assumptions that make it more efficient (usually)
• guarantees the shortest path
• usually faster than dijkstra's