Collisions, they're always a part of my games that I'm never happy with. Not so much the actual this sprite has hit that sprite part ( The narrowphase of the check ), but the broadphase, ie deciding which checks are needed and which we can just ignore.
Different genres require different ways to test for collisions. For a long time now I've been using grid based checks ( As far back as this old
beauty ) in arena based shoot'em ups. Simple enough, you split the screen up into overlapping sectors, and store each baddie in the sector it's occupying.
So let's say we've split the screen up into quarters, you check each baddie's position, and store it in one of the four arrays you've set aside for each sector. Then you can run through your bullets and see which sector they're in, so in theory you're only testing the baddies which are nearest to the bullet ( There's no point testing a bullet against a baddie which is on the other side of the screen ) which in an ideal world will reduce the checks by 75%. Not bad.
The problem I've always had with this is that it feels costly to maintain. I've always just cleared the sector arrays at the start of the baddie movement routines, I've never been clever enough to come up with a way to maintain it "properly". Therefore I could have baddies that have only moved a pixel or two since the last frame, there's no way they're going to have changed sectors, but I've had to treat them afresh.
That can't be good, but like I've said, I've never been able to come up with a clever way of negating that, so I've always just done it that big dumb way.
Recently quadtrees ( Check
here for a great example, and an overview by the always excellent 8bitrocket can be found
here ) and octtrees are very in vogue with Flash developers, so being a bandwagon jumper I thought I'd have a bit of that.
Again, I couldn't think of really good way to maintain the structure every frame, and it felt like you'd need a lot of objects to make it worthwhile ( Or just use it as a generic collision system for every game, but I'm not a fan of that. Collisions are a weird beast where very rarely does one hat fit all ).
One aspect that all the collision methods I mentioned above have, is shown below,
I'm going to generalise a bit here, but let's say we've drilled down into the correct sector / node / whatever. Our bullet is travelling along that path ( Pick which ever direction you feel more comfortable with, in my head it's going up and right ). Chances are it's never going to hit that baddie ( I know the baddie could in theory move enough to come into collision with it, but we're generalising for a second ).
So we've gone to quite a bit of effort to narrow down our collision checks, and then we're still running a check per bullet every frame when most of the time it's not going to hit ( Think of your accuracy rating at any game that checks such things. 75% is pretty good in a game. That means that 25% of all the bullets are going to miss, yet we're having to test 100% of the bullets a 100% of the time ).
This all felt a bit sucky in my head. A lot of cpu time spent on something that wouldn't happen.
Let's talks about "Distance Based Broadphase". I made that up, it's more than likely already been around for years with a different name and I've just happened across a similar idea, but it explains what it is pretty well.
I've approached it in a different way than how I normally set up the whole bullets / baddies stuff. Using DBB every baddie has an array of all the player bullets ( Well a linked list for speed ), and every time the player shoots that new bullet is shoved into that array.
During the baddies main loop it runs through all the bullets it has in it's array and checks it's distance to it ( The narrowphase checks are just your bog standard circle to circle collisions ). If it's distance has increased, then the bullet is moving away from the baddie, and it won't hit it.
So looking at that diagram above, lets say the bullet is flying up to the top left. The broadphase will keep checking as the distance from the bullet to the baddie is decreasing every frame, ie it's getting closer. It's possible that it could hit it, so it's worth checking.
Once the bullet goes past the sweet spot, it's moving away from the baddie. It'll never ever hit it, so we just remove it from the array and the baddie won't check for it again.
Whilst there's a possability of a collision it's worth checking, so it's not so costly ( If you're shooting at baddies from a distance then it's going to incur a cost until the bullet goes past the sweet spot, ie 'til the bullet gets to a point where it's not going to hit the baddie. The greater the distance the more the tests as it will take a while to actually get to the sweet spot ).
Going back to the first diagram, the bullet ( If moving to the top right ) is moving away from the baddie right from the start, so it's thrown away.
In effect we're checking the general direction until we get to the point of a hit, or a miss.
Now I've done some generalisation here. In real life your baddie will be flying around throwing some great shapes. For that, you just increase the size of the sweet spot to take it into account. If you have a fixed speed for a baddie you could work out exactly the sweet spot's size ( That is you'd work out if the baddie moving at it's max speed in a straight line to the bullets path how big the area to check would be ), or if you're lazy like me you just increase the size of the sweet spot by subtracting some pixels from the distance and testing it til it stops breaking.
Hopefully I've made some sense, it's proved to be quite a fair bit to explain. As always please feel free to post a comment if you have any questions or if I've got anything wrong. I'm sure I'll be editing this soon enough to clear things up.
Squize.