Gaming Your Way

May contain nuts.

Distance Based Broadphase

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.


Comments (7) -

  • tonypa

    8/28/2008 7:50:58 PM |

    um, if I were to solve it, I would either calculate exact time of collision (when you know speeds of 2 objects) and then you can skip all collision tests until enough time has past or always sort the bullets array (by distance to the ship) so you only check for first bullet in the list meaning until first bullet is far away then other bullets are all even further.

  • Squize

    8/28/2008 8:37:56 PM |

    Hey mate, nice to see you around here.

    I was thinking about ray-casting, to see if the baddie would ever intersect the bullets trajectory, but I figured with the baddie moving in God only knows what direction and speed it could be a lot of extra maths for nothing ( ie, the bullet still doesn't hit the baddie ).
    I'm really not up to speed on all things vector, but I'm guessing for pre-calculating the exact collision time both objects would have to be moving in a constant speed / direction ?

    In some games of course that would be ideal, Bust-a-move springs to mind, but for the arena based shooter I've worked on this for I don't think it'd fit.

    The bullet sorting is a nice idea, I remember I did it way back on my port of Delta ( What I consider my first ever Flash game, even though I gave up after the first 3 levels ), but that was a horizontal shooter so it was much easier. If the bullets are either vertical or horizontal that works a treat, but I've gone all 360 on this one.

    One area I was thinking of playing with re: DBB is to work out the distance, and then just use that as a counter ( So a simple count=distance/speed ) and skip testing again until that counter is 0.
    In theory that would save a lot more checks, although there would need to be some sort of safety margin to account for the baddie moving ( count=distance/(speed*2) ), but by then we could miss the bullet hitting the sweet spot, so although we'll have skipped some costly checks it may be for a further expense ( ie the bullet check would be running, albeit in a reduced form for want of a better term, longer than it's needed ).

    When I get chance I'll run some tests on this through the profiler. It does feel [ Code wise ] a lot quicker than the old sector based code, the actual loop is quite minimal, although with 50+ baddies and 20+ bullets it could still be pushing things.

    Thanks for the feedback, if you have any more don't keep it to yourself :)

  • Jeff

    8/29/2008 5:41:46 AM |

    Squize, I like this method a lot. It seems pretty doable and maybe a lot easier than a QuadTree (or use both). How are you implementing a linked list in AS3 for the bullet array? I have thought about that approach, but I always come back to a bullet array in my main gameLoop class and a reference to it in the enemy classes. The collisionCheck event fires off and the enemy objects receive it and then reference the gameLoop for the current bullet list. I'm sure a better programmer can come up with a splendid way of doing the same thing. Maybe a linked list is the ticket.

  • tonypa

    8/29/2008 8:02:08 AM |

    Yes, finding exact time of collision can become complicated once both objects change direction and/or velocity, like when they are affected by multiple forces. But in such cases your DBB idea can fail too. Bullet may be curving around the baddie, moving away at first but coming back to it from behind. If I understood the idea correctly, once its removed from baddie list, it is considered to be never hitting it again.

    The problems could also arise when the baddie itself is moving which means you are recalculating the sweet spot coordinates at every frame. For example lets suppose bullet and baddie move in same direction but bullet has slower speed then baddie. Now if bullet is shot in front of baddie, after some time the baddie may reach it but collision is never checked because bullet is not in its list (it moved away when it was shot).

  • Squize

    8/29/2008 11:51:07 AM |

    Hey Jeff.

    The linked list is from here:

    How I used to do it was the bulletHandler would have an array of active bullets, and then the same class would just loop through the bullets testing against the baddies ( Or the baddieHandler would just grab a copy of that array and work with it there ), with this way, each baddie instance has it's own copy that it updates itself ( So if it's ignoring a bullet it deletes it from it's own private array [ / Linked list ]. When the player shoots a bullet, that new bullet instance is sent over to each baddie so it can add it to it's list ).

    So in effect I'm only using a linked list for speed rather than any real need to use it to manage the data.

    Doing it this way, and taking a stupid example, say you have 40 baddies on the left of the screen and you're facing right and shoot. Each baddie would recieve info on that bullet and check for it. After a couple of frames each baddie will realise the bullets not going to hit them and just ignore it. Going back to this over the top example, if you carried on facing right and fired a 100 shots at once, it still wouldn't be very costly.

  • Squize

    8/29/2008 12:09:29 PM |

    Yeah Tony there are problems with it, it's not a catch all system. For the game I'm using this for I was going to treat the homing missiles as a special case as they won't travel on a straight line and would therefore break this.

    As to a baddie moving towards a bullet moving towards it ( If I've read you right ), the sweet spot is technically 1 point, but I test for a circle around it, so there is a sanity check, otherwise it would fail a lot with both objects moving.
    The sweet spot is the closest point between the two objects. Let's say A is moving towards B. Every frame we test the distance. So long as that distance is decreasing then we're moving towards it still. We then store that new distance ( let's call it prevDistance ), as it's the shortest possible between A and B. There will come a point when the distance > prevDistance and then that's when we've passed the sweet spot ( ie, the sweet spot would have been the previous frame, it's when we're closest to the baddie ).

    Once it's past that point ( And outside of our additional sanity check ) it's not going to hit the baddie, it's gone too far.

    The trick is more working out the sanity check, which I touched on in the blog post ( But didn't explain at all well ). It depends on the game type, and in theory you could have a shoot'em up where the baddies fly in really mental attack waves where they're always arcing around the screen. In a case like that it's possible that the baddie could arc away from the bullet far enough that the bullet is thrown away, and then fly back into the bullets path ( Only for it to miss it due to it being ignored ). And that's where you have to tweak the size of the sanity check.
    The bigger that check, ie the bigger the radius of the circle in which we forgive the bullet for not moving closer to the baddie, the more costly the test.

    If I get chance I may post a debug version of my game up here and it should make it easier to visualise.

  • Dark Vyper

    8/29/2008 5:35:54 PM |

    My brain hurts :(

Comments are closed