# Making an efficient collision detection system

I'm very new to game development (just started 3 months ago) and I'm learning through creating a game engine. It's located here. In terms of collision, I know only brute-force detection, in which case, the game slows down if there are a number of objects. So my question is How should I program the collisions?

I want them to happen automatically for every object and call the object's `collision(GObject other)` method on each collision.

Are there any new algorithms which can make this fast? If so, can anybody shed some light on this topic?

-
There are lots of other collision detection efficiency questions on the site. Did you not find what you were looking for in those? gamedev.stackexchange.com/questions/tagged/… – Byte56 Oct 13 '12 at 17:13
I couldn't understand them. They are two advanced for me. – Sri Harsha Chilakapati Oct 13 '12 at 17:16

## 1 Answer

I have seen your game samples. In this specific case I would use a grid. Divide the game screen into squares. Create a 2D-Array representing the game screen squares and containing reference to the game objects inside each square (2d array of object lists).

Check for collisions between all the objects that are inside the same squares (that can collide with one another). An average sized object can be in up to four squares at most.

Update the 2d-array every time you move an object. The object 'remembers' in which squares it is, so you only need to update 8 squares at most even if the object teleports away.

It is one of the best solutions as far as average running time goes because you only need to update once per-object and in most cases, you only need to check for collision once or less per-object. For instance in the space shooter, you would only be checking spaceships that are in the same square with a bullet.

-
+1 this is an easy and the fastest solution. Not that speed is important with only so few objects. – Markus von Broady Oct 13 '12 at 17:27
Updating the entire 2d-array every frame is even expensive, isn't it? – Sri Harsha Chilakapati Oct 13 '12 at 17:28
You only update once if an object has moved. You do not update the entire array and only keep check on squares where objects exist currently. It is O(n) which means it is the best deal you can get. (cheapest) Did you understand the part where the object remembers it's squares? That means you only need to run a collision test once per object on average if the game environment is not very dense. – zehelvion Oct 13 '12 at 17:34
I thought I'd add, that if all enemy ships move lined as it seems on the picture, for additional optimization you could fix the ships on the grid, and move the grid (offsets) instead. – Markus von Broady Oct 14 '12 at 7:47