Sign in to follow this  
ChazH

Algorithms

Recommended Posts

Hello, I am currently trying to prepare a list of game programming algorithms used commonly for a reference sheet. Anyone have any suggestions of algorithms that should be added or where I can find a good list of algorithms. Example. Dot Product vector1 U = (Ux, Uy, Uz) Vector2 V = (Vx, Vy, Vz) U * V = UxVx + UyVy + UzVz Thanks, Chaz [Edited by - ChazH on December 28, 2009 10:53:17 AM]

Share this post


Link to post
Share on other sites
Yeah look up:

Maths:
Matrix functions (multiplication, addition that sort of thin)
Vector functions (Crossproduct, dot product, inverse, addition, magnitude, normalize)
Quaternions functions (Crossproduct, dot product, inverse, addition, magnitude, conjugate, normalize)

Algorithms, or thins that don't fit into math section nicely:
A* (A-Star)
Quaternion rotations
Matrix rotations
Matrix skew
SLERP (spherical linear Interpolation, tied to Quaternions)
Inverse kinematics (Very much maths, but more than pure math functions)
Flat shading
Gaurad shading (I think I splet that wrong)
Texture mapping (Very large topic there)
Phong shading
raycasting

That should et you off, just start reading through wikipedia.

Share this post


Link to post
Share on other sites
Don't forget:
Sorting
Searching

Randomizing
Repetitive Functions (oscillators, springs, etc.)
Chaotic Functions

Probability Distributions


There are a tonne of "common" functions/algorithms used that are all very specific to different subsystems.
Interpolation, collision, transformations( compression, filtering, FFT, tone-maping, lookup-tables, etc.), memory allocation, task scheduling, level-of-detail scaling, etc.

Share this post


Link to post
Share on other sites
Data structures and the algorithms related to them are also important, such as

Linked List
Dictionary, Hash Table, ...
Tree, Binary Search Tree, Red-Black Tree, and so on
Quadtree, Octree, etc...
Stack
Heap (the data structure)
Graphs
...

And some other things you could look into are

Binary Space Partitioning
Finite State Machines
Intersections (such as intersections of lines, spheres, cylinders, triangles, cubes, ...)
...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this