In a recent technical interview I got asked the following question: “if an explosion occurs i.e. from a grenade, how would you determine which characters in the game are affected”. This was a question that I couldnt answer at the time which annoyed the hell out of me and it’s been sitting in the back of my head for the last few weeks. So I decided to discuss it (and my proposed solution) on my blog as an “academic” exercise. I would really appreciate any feedback or comments on this discussion. This is far from being a solved problem for me and while my solution may potentially work quite well, there may be a simpler technique available which I don’t know about.
Coming back to the question. Well the naive answer to that question is to simply do a collision detection check with the explosion area of effect/blast radius (sphere) and any nearby characters’ bounding boxes. Now what about the scenario depicted in the below figure?
Obviously the crouched soldier should not be damaged by the explosion right? Ironically, a lot of games dont actually take that into account and simple leave explosions hit checks as described above, so you’ll be hit by a grenade irrespective of where you are or what you’re behind just as long as you are within the blast radius.
Lets just consider for moment, how standard hit checks are done for ranged weapons. There are two popular techniques, the first being the insta-hit technique. The inst-hit technique basically casts a ray in the aimed direction of the character’s weapon. Intersect tests are then conducted between the ray and any possible characters in the general direction of the ray. If a collision is detected with a character, then that character is damaged. If multiple character intersections are detected then based on whether the projectile can go through multiple characters or not either the closest interesected character is damaged or all intersected characters are damaged.
The second common technique is one where an actual projectile is spawned when a weapon is fired and the projectile is moved along a flight path each frame. A standard collision detection check is run on the projectile each frame and if a collision with a damageable object is detected, then that object is damaged. Once again if the projectile can pass through object addition logic is needed to handle that case.
For an explosion things are a little different, all entities within the blast radius are damaged at the same time. So why did I discuss weapon hit checks then, well because my initial (idiotic) idea regarding handling of explosions was to somehow use instahit rays to determine whether characters are affected by explosions or not.
When an explosion occurs the first thing thats necessary is to limit the number of objects that may be affected by it before checking whether there is any actual effect on them. We can do this by using a blast radius sphere and constructing a list of all objects within the sphere or that intersect sphere. By narrowing down the number of possible objects, we’ve reduced the complexity of the problem quite significantly.
Unfortunately, we’re still in the same situation, how do we determine if a character is hit by an explosion? My initial idea was to perform a reverse hit check from a character to the explosion. If a ray is sent from the character’s conter of mass (or the center of the character’s bounding box) to the explosion without intersecting anything then that character is affected by the explosion. This means that in the situation shown above, the explosion would only affect the unobstructed character. So problem solved?
Well, NO! The problem is most certainly not solved.
In all the cases shown above, the reverse hit check would fail when in fact the character should take damage from the explosion. So like an idiot I figured, why not simply increase the number of hit check origin points? If I send rays from the character’s head, torso, arms and legs then that should help. Sure that would probably fix things for most cases (though there still may occur a cases that all the rays are blocked and yet the character should still be damaged) but it also introduces a further complexity problem. It may not be an issue doing 6 intersection tests for a single character but with each additional character within the explosion radius, the number of intersection tests that need to be performed increases. Then what about other destructible objects that arent characters, they need specially defined ray origin points and so on… This whole system quickly becomes unwieldy, hence my labelling of it as idiotic.
Trying ensure that a character is always hit by an explosion through an intersection test is a bad, bad idea as you will never be able to spawn enough rays to ensure perfect accuracy and still maintain good performance.
Now I do tend to muck about with graphics programming to some degree so it occured to me that I could just do a combination of environment mapping and the ancient openGL picking technique. Environment mapping is a technique to simulate reflections on reflective surfaces such as spheres. The technique basically consists of rendering the scene from the viewpoint of the reflective object then mapping that result to the surface of the object as a texture.
In the case of a reflective sphere, the scene is rendered six times, once for each face of a cube map. Technically only the faces of the cube map facing the viewer need to be rendered but just bear with me. Once each view has been rendered to the cube map, the cube map is mapped to the surface of the sphere.
Now the openGL picking technique is also quite straightforward, in addition to each scene object being rendered to the render target, each scene object is rendered to a seperate buffer (texture) which has the same dimensions as the render target, lets call it the picking buffer cause I cant remember the actual name offhand, except now instead of a color for each pixel of an object, an object id is stored. This means that we now know which pixels in the render target each object occupies and when we select a pixel in the render target we can directly return the object ID (from the corresponding texel in the picking buffer).
So how is this useful for explosions, well consider the below figure:
What if we render the scene using only the objects that may possibly be affected by the explosion (the list we created initially) from the view point of the explosion. Then just as with the openGL picking technique, we dont render any material or color values but rather just the object IDs. We only store the object IDs of damageable objects, objects that are invulnerable do not get written to the explosion-view (cant think of a better name) buffer. When combined with depth testing our final buffer will simply contain the explosion-visible silhouettes of all damageable objects. Now if we iterate over the buffer we can easily construct a list of objects which should be affected by the explosion.
The downsides of this technique are that we will need to render the scene multiple times since the explosion’s blast radius is spherical (view volumes 1 to 4 in the above figure) which may come at quite a high cost. This can be ameliorated in several ways, the first being to reduce the size of the buffer containing the explosion-view, we dont need a high level of detail for each object in the final image, we just need to know if the objects are visible. Secondly since the level of detail can be quite low, we can probably get away with only render the lowest LOD meshes for each object further reducing the cost of the technique.
The only problem with this technique is that the explosion will not travel through damageable objects (and damaging objects behind them) I’m sure with some more brainstorming a solution to that can be found as well.
UPDATE: It just occured to me that if I only stored the depth of the closest invulnerable object to the explosion then I can bit-pack all damageable object ID that lie infront of the invulnerable object into the cubemap’s RGBA channels.
Anyways so that was a random blog post on a a problem thats been bugging me. I would really appreciate some feedback regarding other solutions to this, I’m pretty sure that I’ve ended up reinventing the wheel here and that there exist slightly more elegant solutions to the problem. If so, please please please let me know 😉