Useful Algorithms for Game Design

This thread will be for posting useful algorithms and techniques that can help improve your games in many ways. If you have anything you would like to add, please post it here.

Quadtrees: An algorithm to split up an area into quadrants. It allows collision detection to only check for collisions with objects in the same quadrant, and reduces the number of objects the collision detection algorithm needs to check. There are many uses for it, many listed on this Wikipedia page. Quadrants can also be subdivided into sub-quadrants.
Quadtrees work like this:
-Split the Screen into 4 Quadrants.
-Split each Quadrant into 4 more Quadrants.
-Continue splitting until the Quadrants are small enough for you.
-Determine which objects are in which quadrants.
-When doing collision detection(or whatever), only check for collisions(or whatever) with objects in the same quadrants.
This reduces the numbers of objects that you need to check for collisions with significantly. Especially if there are lots of tiles that need to be checked.

Bounding Box Collisions: Checking for collisions between two or more objects based on a Rectangular outline. They are very simple, but not very accurate. Here's how they work.
-For every object of the first type...
--For every object of the second type...
---Create a Rectangle around the border of object 1
---Create a Rectangle around the border of object 2
---If bottom of Rect1 < top of Rect2
---Or if top of Rect1 > bottom of Rect2
---Or if right of Rect1 < bottom of Rect2
---Or if left of Rect1 > right of Rect2
----There is no collision
---Otherwise, there is a collision
This will reduce time used to check for collisions by only checking boxes, instead of Pixel-by-Pixel. A 3D version can be created by adding more checks.

Circular Collisions: Checking for Collisions between two objects based on their distance from each other. This will be simple. We'll just check if the distance between the two "circles" is less than the sum of their radii.
-For every object of the first type...
--For every object of the second type...
---Set a maxdistance variable to the sum the the radii of objects 1 and 2.
---Find the true distance between the objects by using the Pythagorean theorem(distance = sqrt((y2-y1)^2 + (x2-x1)^2)).
---If the true distance is less than the maxdistance, there is a collision.
---Otherwise, there is no collision.
This reduces the need for expensive pixel-perfect algorithms by giving you a quick and easy pixel-perfect circular formula. A 3D version can be made by extending the Pythagorean theorem.

This post has been edited by OniLink10 on Oct 25 2009, 06:21 PM

If you can post an example for us average people, that would be fine

maybe you should post a couple you know about so people get ideas of what's useful for games

i doubt quadtrees and processor-conserving algorithms are useful to your run-of-the-mill m***, tbh

sigh

i still don't get it

they are when you have to write your own collisions ****!

Added Bounding Box Collisions. A simplified Pixel-by-Pixel(Pixel-Perfect) collision algorithm is coming soon.

Circular collisions have been added.

Run-of-the-mill m***s write their own collisions ****?

I'm proud of you guys!

how about non-axis-aligned bounding box collisions, and extending your circular collision example to handle potentially rotated ellipses

This post has been edited by Xgoff on Oct 25 2009, 06:31 PM