Skip to main content

Quick and easy collision detection


This is a neat little trick I found a few months ago, which I thought was worth documenting.

If you're making a 2D sprite based game and want a quick and easy way to do collision detection between the player sprite and the enemy sprites, you can use an OpenGL occlusion query.

First of all, start an occlusion query, draw the player's sprite into an empty buffer, then end the query. The result will give you the total number of pixels in the sprite. Then, on every frame:

  1. Draw all the enemy sprites at the same depth.
  2. Start the occlusion query.
  3. Draw the player sprite behind the enemy sprites.
  4. End the query and get the result.
If the number of pixels drawn from the player is less than the total, they've collided with an enemy.

The beauty of this is that it's pixel-accurate and essentially zero cost. The downside is that occlusion query support isn't available in OpenGL ES or WebGL yet, so it won't work there.

Comments

Post a Comment

Popular posts from this blog

Triangle bounding boxes in a single byte

Just thought of a way to store the bounding box for a single triangle in only one byte. It's not really practical or something you'd ever really want to use, but what the hell. Assume we have some kind of indexed mesh structure with a list of vertex positions and a list of triangle indices:   struct Mesh {     std::vector<vec3> verts;     std::vector<uvec3> triangles;   }; We can find the bounding box of a triangle by taking the min and max of all three vertices:   vec3 Mesh::lowerBound(uint32_t tri) const {     vec3 v0 = verts[triangles[tri].x];     vec3 v1 = verts[triangles[tri].y];     vec3 v2 = verts[triangles[tri].z];     return min(min(v0, v1), v2);   }   vec3 Mesh::upperBound(uint32_t tri) const {     vec3 v0 = verts[triangles[tri].x];     vec3 v1 = verts[triangles[tri].y];     vec3 v2 = verts[triangles[tri].z];     return ...
2 comments
Read more

How to outperform std::vector in 1 easy step

Everyone who's familiar with C++ knows that you should avoid resizing a std::vector inside a loop wherever possible. The reasoning's pretty obvious: the memory allocated for the vector doubles in size each time it fills up and that doubling is a costly operation. Have you ever wondered why it's so costly though? It's tempting to assume that because implementations of the STL have been around for so long that they must be pretty efficient. It turns out that's a bad assumption because the problem, in this case, is the standard itself: specifically, the allocator interface. The allocator interface provides two methods that obtain and release memory: allocate allocates uninitialized storage (public member function) deallocate deallocates storage (public member function) (taken from this page ). What's missing is a   way of growing an existing memory allocation in place. In C this is provided by the realloc function, but there's no equiva...
2 comments
Read more

WebGL doesn't have query objects.

WebGL doesn't support query objects yet. There's not even an extension for them. It's a bit of an oversight, but stems from the fact that they aren't in OpenGL ES 2.0 (which WebGL is based on) either. Queries are useful for a number of things. Timer queries can be used to extract detailed profiling information about your rendering. Occlusion queries can be used for culling objects before they're drawn (especially useful if you have an expensive fragment shader). And so on. This is a nuisance for me because I was using an occlusion query to perform fast pixel-accurate collision detection for my c++ game Schroedinger's Cat . Now that I'm attempting to port the game to WebGL, I need to find an alternative approach. Update: I've written a follow-up to this post:  OpenGL ES and occlusion queries .
2 comments
Read more