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?
Adding complexity to explosion checks
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.
Special Cases
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:
Explosion cube-mapping
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 😉
Taking Initiative 
In a past game, I used the following idea:
the explosion is materialized via 2 spheres centered at the explosion point, one with radius R and one with radius R+dR. That defines a shell of thickness dR. Each frame, the inner sphere is grown to the size of the outer one, an the outer sphere is grown by dR again, repeated until you hit the maxRadius of the explosion.
each frame you look for new actors inside that shell and maintain a list of already hit actors so you can prevent spamming some objects after they have been hit once (or not, depending on the weapon design: grenade vs. napalm grenade etc 🙂
then for each actors that potentially need to be damaged, you can line-check from the explosion center to some relevant points on the actors, typically bones like head, torso or shoulders, hips, etc … the more bone, the more accuracy you’ll obviously get, at the expence of CPU usage. Conceptually this is some kind of rough approximation of raytracing the explosion shell. And you culd surely reduce the length of the line-checks by clamping them inside the inner-outer spheres so they would always be ~dR long.
and becaus you can flag the collision geometry, you can easily line trace through some objects so that the shockwave propagates (and maybe dampens) through them.
That being said, using the GPU and maybe occlusion queries to render a local “envmap” (dual-paraboloids?) of the explosion is an interesting approach !
You could render the depth on a cubemap or dual-paraboloid when the explosion happens. Then each frame and for each potential hit actor, you render it and reuse the depth information you already have (assuming no moving occluders…) and use the occlusion query tu see if you hit that actor or not …
I’m just wondering if the cost of the rendering would make it prohibitive. If explosion dont occur very frequently it could work but in the case of numerous simulataneous explosions, memory for the cube map storage also becomes an issue in addition to the rendering costs.
Thanks for the reply Marc, so line checking is a pretty standard technique. I’m assuming some degree of error is acceptable with regards to explosion hit checks.
Do you think that my silly rendering idea would even be feasible, the computational cost can be quite high. The nice thing about the line checks and your moving sphere idea is that you automatically distribute the cost of the line checks over several frames. It’s quite elegant 😉
I think the rendering idea you suggest could work indeed and couls potentially be not too expensive if you:
– use dual-paraboloids instead of cubemaps (rendering the scene x2 instead of x6 or x4 if you don’t care about vertical propagation)
– use occlusion query so you don’t have to readback the rendered buffer
– use collision geometry or lowest lod so the vertex count stays low
– use rigid-skinned boxes for representing characters
A side artifact is that with a GPU solution, you might get extra frame of latency on the result, or at least have to take good care of the rendering/gameplay synchronisation if you don’t want to stall the rendering pipeline too often.
yeh in most cases (standard realistic’ish fps’s) vertical checks wont be necessary but even if they are an extra paraboloid should cover it. Worst case 3 renders, at a low resolution and using low LOD meshes.
Maybe instead of rendering the character meshes, the bounding boxes of the game objects could be rendered instead? that should be significantly faster than rendering the actual meshes!
With all the special effects of the explosion, and everything else going on a few milliseconds of delay on the damage dealing may be acceptable.
What about the octtree data structure? Check the radius of the affected blast, and look into these nodes in the tree?
Nice post, and some nice brainstorming there.
Marc is correct: the gpu typically runs 1 frame behind the cpu (more if you’re triple buffering). Ergo, results are typically only obtainable in the next frame. This is probably ok if you’re running at 60Hz (ie. 16ms latency), but if you’re running slower then it might suck. Reading back the gpu-produced cubemap/dual-parabaloid map would add additional latency.
My thoughts:
Firstly, discovering the set of objects in the blast radius needs some acceleration data structure. This will give you information to make better decisions.
Round-robin the CPU intersection tests will add additional latency, but allow you to distribute ray-cast time over multiple frames. This may not be too bad though because explosions will have a natural latency (Little Boy blast generated winds of around 620 mph). If you do this, sort the set of objects from closest to furthest so if it is noticed, it just looks like blast latency.
Using the CPU technique by default and switching to the gpu techniques might also be plausible if you determine the set of objects in the blast radius is more than some threshold and the cost of one technique scales faster than the cost of another technique with respect to no. of objects. Your mileage may vary though, so this would need empirical study to determine these thresholds and the value of such a technique. It may also vary depending on scene, which makes it difficult to tune, although a brute-force preprocessing algorithm that regularly samples your scene can easily discover these thresholds per scene or per area within the scene.
GPU technique could be done on a per cube-map face basis (or quadrant basis, depending on whether you cast +Y/-Y faces too), depending on number of objects in each quadrant.
If player is in proximity to an explosion and in a position to observe the accuracy, switch to high-quality technique otherwise switch to a cheaper technique (1 ray cast per object?)- really, how will they know? You might only want to do this for player initiated explosions to minimize lower-accuracy frustration.
If player is in proximity of the blast radius, they will be subject to the concussive effects. Some games enable a slow-motion/ringing-in-ears bit that will reduce the perceived blast latency, so would allow round-robining to go less noticed.
Game designers can also reduce the cost by reducing blast radius, and ensuring the set of objects in a highly occluded area is not dense.
Thanks for the detailed reply Justin, I’m starting to see that latency is probably going to be the biggest problem with the GPU based approach.
You would definately need to extend the explosion outwards over time but as Marc said, we can generate the cubemap/paraboloid map at the start of the explosion and simply reuse it over the course of the explosion. I feel that it would be more accurate than simply cheating by using a player proximity check.
Often when I play an FPS, I’d lob a grenade at one target then run and engage targets in the opposite direction. I’d hate to suddenly cross a magical threshold and have my grenade be ineffective due to a raycast failure. Again if performance is critical then maybe thats simply unavoidable.
I would be very keen to see a study on this problem. In fact I think this problem would make a pretty awesome honors/masters project.
Game dev – the eternal balancing act 😉
Oops, just read what I wrote and it’s not what I meant at all 🙂
When I said :
“You might only want to do this for player initiated explosions to minimize lower-accuracy frustration”
I actually meant “enemy initiated”. ie.
“You might want to do only high-accuracy for player initiated explosions, so players can’t be frustrated with lower-accuracy results from their direct actions”
This was mainly an optimization suggestion for a situation where you might have carpet/mortar bombing happening at a far distance from the player, but don’t necessarily want those to be really expensive due to the sheer number of explosions that are happening. I hope that was better.
FYI, I’ve found a lot of gamedev/optimization is “cheating”. It’s the player experience that matters and anything you can do to minimize performance/stuttering problems will help to prevent player frustration 😉
Hmm I was just thinking – if you were to implement a deferred rendering engine with a geometry buffer…
Could you position a point light at the explosion’s center, and cast a shadow – either into your G-Buffer, or into a separate map, and use that to mask the G-Buffer when sampling it for object IDs (or however you identify objects in your buffer)?
This might also save processing time, since you may want to have your explosion cast light and shadow anyways.
To let the explosion affect actors/objects through certain geometry (deciding this based on material might be beneficial too, say an explosion wont be blocked by cardboard, but it will be blocked by concrete) could then possibly be handled by transparency.
Just a few thoughts, I don’t know if this would be practical at all.
thats actually a really good idea, I wasnt thinking about the rendering of the explosion at all! You’re right in that you’d probably want to generate some light through the explosion. In that case like you said we can generate the explosion map at rendering but we still then have the problem of latency as Justin and Marc mentioned.
I also have no idea whether any of the techniques discussed with the exception of the ray casting would actually be feasible. I’m going to try and find some time to try and do a brief demo of it and see how it goes.
I vaguely remember reading about KillZone 2 using precalculated cover maps which where basically low resolution cube maps of sorts which where (automatically?) placed all over the map.
This would then be used for AI to determine if a particular place would provide enough cover and if they could see the player or not (I think).
So I was thinking, it might be possible to use a system like this in reverse, to determine if an explosion can ‘see’ you. That should be pretty cheap.
Thanks for the info!! Though I’m thinking that even if you have the cover cube maps it doesnt solve the problem of ensuring the explosion affects a player even if only like 20% of his body is sticking out.
That being said, it just occured to me that in most cases AI agents will take cover in a fixed manner, they wont be half exposed or semi in-cover. So in that regard the hit check technique may actually be perfectly fine. Though in the situation where agents are in motion and an explosion goes off then we’re back to square one.
I am very keen to learn more about the Killzone cubemaps, any chacne you can remember where you read about it?
Well it would be an approximation, and if you place more ‘cover’ samples in the map it should be reasonably accurate, at least to a point where you would have an extremely hard time determining the difference between this and it being 100% accurate.
As for the link, I read it here:
http://aigamedev.com/insider/coverage/waypoint-cover-maps/
The issue isnt so much the cover map resolution but rather how to check whether an agent is visible or not using the cover map.
I dont know anything regarding cover maps but I’m thinking that the end result might be similar to the idea of rendering the scene from the view of the explosion. Which makes me wonder how useful a cover map would be from a different view than the explosion? Like I said I dont know anything about cover maps so I’m thinking out loud 🙂