Distance based broadphase collisions

Ok, let's start this off with a caveat. I actually came up with this approach and named it, but there's no way on earth that I was the first to do it, there's got to be an existing routine which works the same way with a proper name, it's just the law of coding.

Whatever you do, someone else has already done it, and better. Like The Simpsons.

Let's start with a screen shot, it's easier to talk around that.

You never want to be in this situation in real life.

Typical shooter, a ton of bullets to check against the player.

Now a common approach is to split the screen into overlapping sectors, figure out which sector the player is in, then just check all the bullets in that sector. Hey presto, a lot less checks.

The approach we took made each bullet a little more autonomous, rather than check it’s current sector and update an array / list / whatever each bullet runs a distance check to the player ( The blog title gave that away a little didn’t it ).

We’re going to back track a little,

The arrow shows the bullets direction, so we can see it’s moving away from the player. At a certain point, due to the bullets speed and the players maximum speed, that bullet is never ever going to hit the player. And that’s the basics of what we’re doing.

In a shooter the vast majority of the time a bullet is not going to be deadly to the player, so let’s cull those checks out to save time.

To break that down into something useful, we give each bullet a max distance value when it’s first shot, a silly high value. Every couple of frames ( When running at the magic 60fps you can be a little naughty and not bothering running everything every frame. Movement yes, that’s the whole point of 60fps, but internal checks, we can cheat a little there. Let’s just keep that our secret though ) we check the distance to the player.

If that distance has decreased then we’re moving towards the player, we’re still a valid kill shot, so carry on. If the distance has increased, hmmm, we’re moving away so let’s run that distance check a little less often and see what happens. At a certain point the distance is going to be so great that it’s never going to hit the player ( This is the fiddly bit which requires testing. We were a little liberal with it as this is for an iPad game so touch controls don’t allow the same level of control as you’d get with, well, any other form of input really, so we made the cut off point a little bit sooner than perhaps you would normally ).

Once we know the bullet isn’t going to hit the player, cool, we can run our really reduced main loop on it where it just checks for going off screen, really nice and light. And that will be for the majority of bullets on screen at any one time.

This clip should help explain it a little better

Grey bullets are either not checking against the player, or running reduced checks. Where a bullet turns red it means it's close enough to bother testing. And yes, I regret setting the bullets to red as they're displayed in washed out YouTube red.

Now say your game has a turret that aims at the player, this is probably going to be more work than it’s worth, the shot is going to be on target, but in something like DN8 [ The game featured in the grabs ] where the baddies are quite happy shooting every which way in a show of glowing force, it’s a large saving.

But aren’t distance checks expensive ? Obviously we’re going to drop the whole square root part of our circle to circle checks ( We’re not being pixel perfect as, well, that’s insane isn’t it. We’re not making a platformer ) but there’s still a cost involved.

Yes, but for the fine part of the collision phase we need the distance anyway, and remember we’re not running these every frame. You can increase the number of checks as the bullet gets closer, but with a silly number of bullets on screen you want to give the player every chance ( Player bullet hit boxes have been bigger than needed, whilst the player collision box has been smaller, for ever now because we all know that the player likes to feel like they’ve been lucky, even if we’ve rigged that luck for them ).

If you’d like to see this in action ( Here it comes ) DN8 Pulse is now up on the appStore ( I knew it, the self promoting sting in this tail ) for iPad 2 or newer, right here:

https://itunes.apple.com/us/app/dn8-pulse-bullet-hell/id878639479?ls=1&mt=8

Please feel free to fire over any questions in the comments, and if anyone knows the real term for this collision approach please share it, as I refuse to believe I actually invented something.

Thanks for reading.

Squize.