One of the things I’ve been doing recently is improving the algorithm I use to calculate explosive damage in Jetboard Joust. I’ve mentioned this in passing before but, as I’ve spent quite some time on it throughout the course of the project, I felt it warranted a devlog entry all to itself. So here you go...
Take 1: The Range Check
The simplest way of calculating explosive damage in a game is to use a basic range check, i.e. calculate the distance of each target from the centrepoint of the explosion and if this is less than the radius of the explosion register a ‘hit’. For slightly more realism you can reduce the amount of damage done the further a target is from the centre using the inverse square law.
This method is fine in some circumstances and basically what I originally implemented in Jetboard Joust (only complicate things when necessary is pretty much the mantra I live by when it comes to coding). I didn’t feel it really cut the mustard when it came to playtesting though for a number of reasons.
1. Size Matters. As this method only uses the centrepoint of each target as reference it would distribute the same damage to a very large enemy as to a very small one, even though the large enemy had a much greater surface area exposed to the explosion. Similarly it would be possible for a large enemy to be exposed to a considerable amount of the explosion whilst its centre point was outside the damage radius and therefore not take any damage at all. As enemies vary in size tremendously in Jetboard Joust this was an issue.
2. No Protection. It did not make sense to me within the context of the game that a target on the other side of a building would not be shielded in some way from the force of the explosion, and similarly that small targets would not be shielded by larger targets. I wanted the player to have to think (to an extent) about the placing of an explosive weapon when fired into a group of targets as part of the gameplay and with this method of calculating damage the placing of explosives made very little difference.
Take 2: Mass Raycasting
My next approach was my first attempt at using raycasting to calculate explosive damage. The technique used was as follows:
Allocate a maximum damage and range to the weapon.
1. Cast a bunch of rays out from the centrepoint of the explosion. Allocate an amount of damage per ray proportional to the weapon’s overall damage.
2. For each ray, iterate through each edge of every potential target and work out the closest target to intersect (if any). Obstructions are included here.
3. If an intersection occurs, work out the ‘strength’ of the damage based on the distance of the point of intersection from the centrepoint of the explosion as a proportion of the weapon’s overall range.
4. Apply the ray damage multiplied by the strength value to the enemy
This GIF shows an example of the above method, note that the frame-rate drop is only because of the debug rendering.
On the whole this method worked pretty well. Damage done was now (roughly) proportional to the size of the target’s surface area that came into contact with the blast and targets could be shielded from the blast by obstructions and each other, making the whole system feel much more interactive dynamic. There were a couple of issues, however.
1. Fanning As rays spread out from the centre it could be possible for very small enemies to be missed entirely be explosions that had a very large blast radius. This could be remedied by simply casting more rays, but that brings me on to point 2…
2. CPU Expense I never really noticed any slowdown with this method but the amount of needless rays cast, and the fact that to improve the accuracy of the system I would have to cast yet more rays, worried me. It seemed especially wasteful on explosives fired by enemies as these really only needed to be checked against the player and obstructions.
3. Too Much Shielding Whilst having obstructions like buildings shield targets from the blast radius worked well in-game, having targets absorb 100% of blast energy was too much. With smaller enemies particularly, it seemed there needed to be some kind of ‘bleed through’ otherwise a small enemy near the centre of an explosion could absorb almost all its damage.
(2) could have been partially resolved by doing a basic range check to collect potential targets before performing the raycasting and (3) could have been resolved by ordering targets per-ray before applying damage but, with some considerable help from r/gamedev, I was able to come up with a much better solution.
Take 3: Selective Raycasting
This technique builds upon ideas that are discussed here and here. A very ‘broad brush’ description of the process is as follows:
1. Perform a basic range check to get a list of potential targets.
2. Cast a ray to each vertex of each potential target.
3. For each ray, iterate through each edge of every potential target and maintain an ordered list of those that intersect.
4. For each ray, apply damage to each intersecting target in order.
Of course, it’s a bit more complex than that in practice, particularly when it comes to calculating the damage. This is best explained with a diagram.
I’ll refer to each point that a ray intersects the edge of a target as a hitpoint. Each hitpoint is allocated an energy value. Energy starts out at 1.0 but is reduced by each target the ray intersects along the way. The amount of reduction can be set per target, so certain targets can absorb more energy than others. Remember that we are only registering the closest hitpoint on each target so each ray will only have one hitpoint per target.
I maintain a list of all hitpoints per target. Once I have iterated through all rays, so all hitpoints and their energy values have been calculated, I then iterate through each target.
For each target I sort the hitpoints by their angle from the centrepoint of the explosion, so I’m iterating through each hitpoint in a clockwise direction (could be anti-clockwise, doesn’t matter).
I calculate the angle between each hitpoint and the next one from the centrepoint of the explosion. This angle / 360˚ gives me the proportion of blast damage that should be allocated to this ‘slice’. I then take the sum of the energy value for said hitpoints and divide by two – this gives me the ‘energy’ of the blast damage for this slice. The actual damage done per slice is the blast damage value multiplied by the energy value.
Note that I don’t have to apply the inverse square law here as calculating damage done based on the angle between hitpoints means that blast damage will already decay as the target is moved further from the centrepoint of the explosion.
So, in the example diagram, the energy value for hitpoint (2) will be less than 1.0 as the ray has already passed through hitpoint (1) and absorbed some energy. Assuming for the sake of argument that the angle from the centrepoint of the explosion between points (2) and (3) is 10˚, the damage done for the ‘slice’ between hitpoints (2) and (3) will be max_damage * (10/360) * (energy(2)+energy(3))/2.0.
This method largely works but there is an issue. Consider this example image...
If the smaller target absorbed 100% of the blast’s energy then the energy value at hitpoints (2),(3),(4) and (5) would be zero which in turn means that the energy allocated to the ‘slice’ between points (1) and (2) would only be half of what it should be. The solution to this (or at least the best one I can come up with) is to also cast rays slightly to either side of each vertex, which is what I ended up doing. A similar solution is presented here. Unfortunately this triples the CPU expense but it doesn’t seem to impact performance in-game, even with lots of enemies. If performance did become an issue I could probably get away with only casting rays slightly to either side of each vertex and ignoring the ‘direct’ one.
Another key point in optimising performance is that all objects used in these calculations are recycled as described here, so there is no object allocation or garbage collection involved. I’ve found that recycling objects, particularly in memory-managed languages like Java and C#, pays off in spades when it comes to performance.
Another special case I should mention is what happens if the explosive projectile directly collides with an enemy. In this instance I found the best approach from a gameplay perspective was to allocate maximum damage at the point of impact. If the target is destroyed by the impact I remove it from the list of valid targets (so it doesn’t block the blast from anything else), whereas if it is not destroyed by the impact I leave it to absorb blast energy in the normal way.
The end result is a process that minimises CPU expense whilst also providing a rich, dynamic and pseudo-realistic gameplay experience. I can set energy absorption levels for different types of enemy, plus energy penetration levels for different types of weapon. It’s been a fairly rough road getting here (maths is not my strong point by a long chalk) but I’m pleased with the result.
The video below has a few examples of debug output showing rays cast and hitpoints followed by a few non-debug examples of explosive collisions with multiple complex colliders just to demonstrate the lack of any noticeable impact on performance.