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

Popular posts from this blog

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 away of growing an existing memory allocation in place. In C this is provided by the realloc function, but there's no equivalent in the std::allocator interfa…

OpenGL ES and occlusion queries

This is a follow-up to my earlier post "WebGL doesn't have query objects".

Since I wrote that post, the situation has changed a bit. It's still true to say that WebGL doesn't have query objects, but the underlying reason - that OpenGL ES doesn't - is no longer true.

For OpenGL ES 2.0, there's an extension which provides basic query functionality: EXT_occlusion_query_boolean (which seems to have been based on ARB_occlusion_query2 from regular OpenGL). For OpenGL ES 3.0, the functionality from that extension appears to have been adopted into the standard. The extension provides two query types, both of which set a boolean value to indicate whether any pixels passed the depth and stencil tests.

While this is progress, unfortunately it's still not sufficient to implement the pixel accurate collision detection method I described in an earlier post. For that purpose it's not enough to know whether any pixels passed the tests; you want to know whether al…

Octree node identifiers

Let's say we have an octree and we want to come up with a unique integer that can identify any node in the tree - including interior nodes, not just leaf nodes. Let's also say that the octree has a maximum depth no greater than 9 levels, i.e. the level containing the leaf nodes divides space into 512 parts along each axis.

The encoding The morton encoding of a node's i,j,k coordinates within the tree lets us identify a node uniquely if we already know it's depth. Without knowing the depth, there's no way to differentiate between cells at different depths in the tree. For example, the node at depth 1 with coords 0,0,0 has exactly the same morton encoding as the node at depth 2 with coords 0,0,0.

We can fix this by appending the depth of the node to the morton encoding. If we have an octree of depth 9 then we need up to 27 bits for the morton encoding and 4 bits for the depth, which still fits nicely into a 32-bit integer. We'll shift the morton code up so that i…