Common game algorithms

Once all of the iterations are complete, then you would have a certain number of groups, each with similar shapes. The complete list of steps required to complete this problem is what is known as an algorithm. Algorithms have various traits we can use to describe them. For instance, algorithms have both time complexity and space complexity.

Time complexity describes how efficient an algorithm is relative to the size of the input it is given to work on. Space complexity describes how much memory and storage space an algorithm needs to complete the task it is assigned to do. Algorithms can be serial in nature, parallel in nature, produce exact results, or produce approximate results. Some algorithms might process data in a sequential process, meaning they are serial in nature.

Parallel algorithms, on the other hand, can break up data into smaller pieces and then work on each simultaneously. An algorithm may be exact or it can be approximate.

The exact type produces a known predictable value every time it runs. An approximate algorithm tries to find an answer that might or might not be exact. Algorithms will sometimes execute each step with an exact decision. This is known as a deterministic algorithm. An algorithm may also attempt to produce a solution using successive guesses, which become more accurate over time. This type of algorithm is known as non-deterministic. Finding the greatest common denominator of two numbers is a common task.

The greatest common denominator of two numbers is the largest integer that divides both numbers without leaving a remainder. Consider we have num1 and num2. The way the algorithm works is to divide num1 by num2 and then look at the remainder. For this, we can use the modulo operator. The Ohio State University. In programmers life algorithms and data structures is most important subject if they want to go out in the programming world and make some bucks.

Today, We will see what they do and where they are used with simplest examples. This list is prepared keeping in mind their use in competitive programming and current development practices. Sorting is the most heavily studied concept in Computer Science.

Idea is to arrange the items of a list in a specific order. Though every major programming language has built-in sorting libraries, it comes in handy if you know how they work. Depending upon requirement you may want to use any of these. More importantly one should know when and where to use them. Some examples where you can find direct application of sorting techniques include:. Binary search is used to perform a very efficient search on sorted dataset.

The time complexity is O log 2 N. Idea is to repeatedly divide in half the portion of the list that could contain the item, until we narrow it down to one possible item.

Some applications are:. Hash lookup is currently the most widely used technique to find appropriate data by key or ID. We access data by its index. Ullmann's algorithm for subgraph isomorphism solving. Determine if two graphs have isomorphic subgraphs. The maximum common subgraph isomorphism problem may be computed with a modular product graph. Compression Lossless compression algorithms Burrows-Wheeler transform.

Preprocessing useful for improving lossless compression. Data compression used by ZIP. Delta encoding. Aid to compression of data in which sequential data occurs frequently. Incremental encoding. Delta encoding applied to sequences of strings. Successor of LZ Builds a translation table from the data to compress. Is used by the GIF graphical format. LZ77 and They are both dictionary coders. Short for Lempel-Ziv-Markov chain-Algorithm. Data compression algorithm that is focused on speed.

Adaptive statistical data compression technique based on context modeling and prediction. Shannon-Fano coding. Constructs prefix codes based on a set of symbols and their probabilities. Truncated binary. An entropy encoding typically used for uniform probability distributions with a finite alphabet.

Improve binary encoding. Run-length encoding. Primary compression that replaces a sequence of same code by the number of occurences. Incremental grammar inference on a string. Progressive encoding to compress an image into a bit stream with increasing accuracy.

May be lossy compression also with better results. By Google, generic compression, efficient but slow. The name means small bread in swiss german. By Google, successor to Zopfli but faster, based on LZ 77, entropy encoding and context modeling.

Entropy encoding Coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. Huffman coding. Simple lossless compression taking advantage of relative character frequencies. Adaptive Huffman coding. Adaptive coding technique based on Huffman coding. Arithmetic coding. Advanced entropy coding. Range encoding. Same as arithmetic coding, but looked at in a slightly different way. Unary coding.

Code that represents a number n with n ones followed by a zero. Elias delta , gamma , omega coding. Universal code encoding the positive integers. Fibonacci coding. Universal code which encodes positive integers into binary code words. Golomb coding. Form of entropy coding that is optimal for alphabets following geometric distributions.

Rice coding. Lossy compression algorithms Linear predictive coding. Lossy compression by representing the spectral envelope of a digital signal of speech in compressed form. A-law algorithm. Standard companding algorithm. Mu-law algorithm. Standard analog signal compression or companding algorithm. Fractal compression. Method used to compress images using fractals. Transform coding. Type of data compression for data like audio signals or photographic images. Vector quantization.

Technique often used in lossy data compression. Wavelet compression. Form of data compression well suited for image and audio compression. Cryptography Secret key symmetric encryption Use a secret key or a pair of directly related keys for both decryption and encryption. Designed by Schneier as a general-purpose algorithm, intended as a replacement for the aging DE.

Performs transformations on data splitted in blocks, using a key. RC4 or ARC4. Tiny Encryption Algorithm. Easy to implement block cipher algorithme using some formulas. Older name for IDEA. Public key asymmetric encryption Use a pair of keys, designated as public key and private key. The public key encrypt the message, only the private key permits to decrypt it. Generate keys with prime and random numbers. Was used by US agencies, and now public domain.

Widely used in electronic commerce protocols. Use prime numbers. Diffie-Hellman Merkle key exchange or exponential key exchange. Method and algorithm to share secret over an unprotected communications channel. Used by RSA. Make use of rings of polynomials with convolution multiplications.

Message digest functions A message digest is a code resulting of the encryption of a string or data of any length, processed by a hash function. Most commonly used of the SHA set of related cryptographic hash functions.

Was designed by the NSA agency. Tiger TTH. Usually used in Tiger tree hashes. Cryptographic using pseudo-random numbers See. Shamir's secret sharing scheme. This is a formula based on polynomial interpolation. Blakley's secret sharing scheme. Is geometric in nature, the secret is a point in an m-dimensional space. Other techniques and decryption Subset sum.

Given a set of integers, does any subset sum equal zero? Used in cryptography. Shor's algorithm. Quantum algorithm able to decrypt a code based on asymetric functions such as RSA. Geometry Gift wrapping. Determining the convex hull of a set of points. Gilbert-Johnson-Keerthi distance. Determining the smallest distance between two convex shapes. Graham scan. Determining the convex hull of a set of points in the plane. Line segment intersection. Finding whether lines intersect with a sweep line algorithm.

Point in polygon. Tests whether a given point lies within a given. Polygonization of implicit surfaces. Approximate an implicit surface with a polygonal representation. Method to evaluate the distance to a point from angles to other points, whose distance is known. Search the optimal path between two nodes on a graph.

Special case of best-first search that uses heuristics to improve speed. Process to add images on walls in a video while hidden surfaces are taken into account. Computes shortest paths in a weighted graph where some of the edge weights may be negative. Graph canonization. Find a canonical form of a graph that is isomorphic to another graph.

Used in cheminformatics. Dijkstra's algorithm. Computes shortest paths in a graph with non-negative edge weights. Perturbation methods. An algorithm that computes a locally shortest paths in a graph. Solves the all pairs shortest path problem in a weighted, directed graph. Floyd's cycle-finding. Finds cycles in iterations. All pairs shortest path algorithm in sparse weighted directed graph. Hopcroft—Karp algorithm. From a bipartite graph, returns the maximum number of edges with no common endpoints.

Alternatives are breadth-first and depth-first algos. Finds a minimum spanning tree for a graph. Computes the maximum flow in a graph. Implementation of Ford-Fulkerson. Nonblocking Minimal Spanning Switch. For a telephone exchange. Spring based. Algorithm for graph drawing. Algorithm for finding a perfect matching. Coloring algorithm. Graph coloring algorithm. Nearest neighbour. Find nearest neighbour. Topological sort. Sort a directed acyclic graph in such a manner that each node comes before all nodes to which it has edges according to directions.

Tarjan's off-line least common ancestors algorithm. Compute lowest common ancestors for pairs of nodes in a tree. Graphics Bresenham's line algorithm. Uses decision variables to plots a straight line between 2 specified points. A process for coloring a picture or video in black and white, with a few strokes to mark the colors. Depixelizing Pixel Art. Smoothing algorithm that converts an image in coarse pixels into a realistic picture.

Johannes Kopf and Dani Lischinski. DDA line algorithm. Uses floating-point math to plots a straight line between 2 specified points. Flood fill. Fills a connected region with a color. There are many algorithms for contrasting photos. Xiaolin Wu's line algorithm. Line antialiasing. Painter's algorithm. Detects visible parts of a 3-dimensional scenery. Ray tracing. Realistic image rendering. Phong shading. An illumination model and an interpolation method in 3D computer graphics.

Gouraud shading. Simulate the differing effects of light and colour across the surface of a 3D object. Scanline rendering. Constructs an image by moving an imaginary line. Global illumination. Considers direct illumination and reflection from other objects. Constructing new data points such as in digital zoom.

Remove an object on a photo and rebuild the background Used by Photoshop and The Gimp. Resynthesizer tutorial. Slope-intercept algorithm. It is an implementation of the slope-intercept formula for drawing a line. Spline interpolation. Reduces error with Runge's phenomenon. Lists, arrays and trees Searching Binary search algorithm. Locates an item in a sorted list. Breadth-first search.

Traverses a graph level by level. Best-first search. Traverses a graph in the order of likely importance using a priority queue. Depth-first search. Traverses a graph branch by branch. Dictionary search. See predictive search. Disjoint-set data structure and algorithm. With for application, building a maze. Hash table. Associate keys to items in an unsorted collection, to retrieve them in a linear time. Interpolated search. Median search.

In an unordered list of numbers. Torben 's algo is slower but does not modify the input array. Predictive search. Binary like search which factors in magnitude of search term versus the high and low values in the search.

Selection algorithm. Finds the k th largest item in a list. Skip list. Splay tree. Binary tree with a function to place a node at the root and reorganize other accordingly. Uniform-cost search.

A tree search that finds the lowest cost route where costs vary. Sorting Binary tree sort. Sort of a binary tree, incremental, similar to insertion sort. Inefficient random sort of a desk card. Bubble sort. For each pair of indices, swap the items if out of order. Bucket sort. Split a list in buckets and sort them individually. Generalizes pigeonhole sort. Cocktail sort or bidirectional bubble, shaker, ripple, shuttle, happy hour sort.

Variation of bubble sort that sorts in both directions each pass through the list. Comb sort. Efficient variation of bubble sort that eliminates "turtles", the small values near the end of the list and makes use of gaps bewteen values.

Counting sort. It uses the range of numbers in the list A to create an array B of this length. Indexes in B are used to count how many elements in A have a value less than i.

Gnome sort. Similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. Convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list. Insertion sort. Determine where the current item belongs in the list of sorted ones, and insert it there. Or introspective sort.