3
\$\begingroup\$

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?

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ 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/… \$\endgroup\$
    – House
    Oct 13, 2012 at 17:13
  • 1
    \$\begingroup\$ I couldn't understand them. They are two advanced for me. \$\endgroup\$
    – Sri Harsha Chilakapati
    Oct 13, 2012 at 17:16

1 Answer 1

Reset to default
10
\$\begingroup\$

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).

enter image description here

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.

Improve this answer
\$\endgroup\$
4
  • 3
    \$\begingroup\$ +1 this is an easy and the fastest solution. Not that speed is important with only so few objects. \$\endgroup\$
    – Markus von Broady
    Oct 13, 2012 at 17:27
  • \$\begingroup\$ Updating the entire 2d-array every frame is even expensive, isn't it? \$\endgroup\$
    – Sri Harsha Chilakapati
    Oct 13, 2012 at 17:28
  • \$\begingroup\$ 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. \$\endgroup\$
    – AturSams
    Oct 13, 2012 at 17:34
  • \$\begingroup\$ 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. \$\endgroup\$
    – Markus von Broady
    Oct 14, 2012 at 7:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .