Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
September 1, 2014
arrowPress Releases
September 1, 2014
PR Newswire
View All
View All     Submit Event





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Distance based broadphase collisions
by Richard Myles on 06/09/14 09:47:00 am   Featured Blogs

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

 

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.

Some bullets...

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,

Try and find a good looking clipart arrow. Impossible.

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.


Related Jobs

Zindagi Games
Zindagi Games — Camarillo, California, United States
[09.01.14]

Software Engineer
Zindagi Games
Zindagi Games — Camarillo, California, United States
[09.01.14]

Lead/Senior Designer
Retro Studios - Nintendo
Retro Studios - Nintendo — Austin, Texas, United States
[09.01.14]

RETRO STUDIOS - Level 3 Engineer
N-Fusion Interactive
N-Fusion Interactive — Manalapan, New Jersey, United States
[09.01.14]

Unity 3D Game Programmer






Comments


Chris Dias
profile image
I barely noticed the difference between the grey & red bullets. I think it would have been better if you changed the opacity of the grey bullets or just erased them entirely.

Richard Myles
profile image
Yeah, it wasn't my greatest plan on reflection, I should have done as you said, but hopefully it doesn't distract from the article too much.

Kevin Fishburne
profile image
The underlying logic of setting the update rates of systems (or individual elements of a system) by examining their relevance to gameplay is pretty solid. The applications extend far beyond bullet collision checks. Sorta like "don't draw shit that's outside the screen", or "don't calculate sound effects outside of earshot". Making the code mind-numblingly efficient also helps, of course.

Richard Myles
profile image
Exactly that mate. That's the one advantage of going for 60fps ( Compared to the million painful disadvantages ) you can get away with skipping frames for various things a lot more.
Simple things like staggering a score update so it only refreshes every couple of frames ( When needed ) all really help spread the load.
Having variable update rates on various different systems, that takes some balancing, but if you're making your frame rate king then it's worth the pain.

Kevin Fishburne
profile image
It's also useful for server backends for MMOs. The one I'm working on manages tens of thousands of trees and plants, thousands of animals and even grows the grass. Maintaining 10 network FPS for players with real-time twitch movement and combat requires those environmental systems to take a back-seat.

The ironic thing about this article, for me, is that I just started work on a shoot 'em up a few days ago. Must be fate. :)

Dennis Gustafsson
profile image
Am I missing something here, or isn't the actual collision check against the player also just a distance check in this case? Doing a simple circle collision (distance check) for the player against all bullets should be virtually for free on a modern device, even with thousands of bullets.

Richard Myles
profile image
I think it all depends on both the device, and the language / VM you're using.
Personally I think it's worth the effort to cull say a 100 bullet checks down to 20 rather than just brute forcing through all a 100 every frame, if the game play allows it of course.

Scott Lembcke
profile image
This is *exactly* the example I make to people where a broadphase doesn't help and may even be worse. You are colliding many objects against just one object, so it's a linear number of checks to begin with. Since your culling step can't be better than O(n) and anything you do is going to involve at least computing a change in position, it can't really be faster than a squared distance check. You also can't really extrapolate this idea to provide temporal coherence for a spatial index either.

Dave Hoskins
profile image
I would have laid a course grid over the play area and put all objects into it like pixel buckets.
That way you only have to check the local buckets for object collisions, none of this mathematics malarkey!

*edit* Plus, 'dropping the square root' doesn't make it less accurate at all, you just check against the square of the object's size instead.

Richard Myles
profile image
In reverse order, d'oh, you're totally right about my square root comment. I'll be happy if that's the only dumb error in there.

With regards the grid, I did briefly touch on it, as it is normally how I would do it. The disadvantage as I saw it was it would be a case of both managing the bullets current grid sector and then testing the bullet > player collision, as opposed to the approach I covered you only have that one distance check.
Also you still have to manage the bullets in their grid even if they're never going to hit the player as they move from grid sector to grid sector, unless you cull them ( via a distance or direction check ) when they can't possibly be a threat anymore.

I know that's kinda splitting hairs a little, and I've just realised it's very difficult to reply without sounding overly defensive :)

Dave Hoskins
profile image
If it's only the player that can get hit then that's fair enough. If it was more complex then the number of checks would go up exponentially.
And I suppose if you know the bullet's speed is constant you don't need to check again until after set time of the bullet's speed plus the maximum player's speed! :)


none
 
Comment: