collision detection of cannon balls with wall and target

Question

I am seeking a good algorithm detecting if a moving ball is touching either a static wall or a static target. A classic Firing game logic. Anyone seen a good algorithm other than just loop them all?

EDIT: i have no idea which is the best solution, BSP tree or grid based calculation, but my implementation will be on javascript and controlling moving objects in canvas. and the cannon ball will be destroyed if it hit on something, so i think each fired cannon ball need one BSP tree

Answer 1

Since you already know the location of the static object, you can encode its location into a BSP or kd-tree. Then, as the location of the ball moves, you track the object's location in the BSP or kd-tree and only compare against objects within the same nodes of the tree.

The overall idea is to build up a binary tree before you start doing your tests. This data structure makes it much easier to locate 'nearby' objects -- since you are cutting down the number of objects you test for collision, you speed up the detection overall.

Answer 2

I agree that wickedchicken's idea is the best. I'm just suggesting another approach all the same.

What I did when I was coding a similar game (years ago) was to partition the playing area into a N*N grid. Now, to check whether a collision occurs, I just checked with only those objects that were in the same grid square as the ball or in any of the 8 squares adjacent to that square. Carefully choosing the value of N can make this pretty fast.

Of course, this only gives good results if all the objects are distributed more or less evenly across the playing area. But at the time this approach looked easier to me than coding a more complex data structure (I was still in high school and just learning programming).

Answer 3

Since the wall/target are not moving, you are not comparing the balls for collisions with each other (right?), and you must loop through every ball every frame anyways to move it, you would be best to just check every ball for collision every frame (if the collision is complex, you can filter by approximate distance).

This will run faster and be easier to write than keeping a BSP tree.