Collision detection

I am doing a project where there开发者_运维问答 is a room filled with objects with different shapes.

I am drawing the room in paint, being the picture all white and painting all the walls/obstacles red.

I am drawing each movable object in a different file, also using paint.

Now, I load both the map of the room and the objects as matrix of 1's and 0's to my program. I have one matrix for the first, and another matrix for each of the objects I load on the room.

The object will be able to move freely in the room, moving by any distance, any angle, and being allowed to rotate itself. How should I go about devising a method that allows me to rotate the object by any angle and still being able to detect collisions? What I mean is that if the object could just go up, down, left and right, I could just check both the matrix to see if they "overlap" any of the 1's. But if I want to rotate the object, let's say, by 10º, I can't see how I can convert that to a matrix and check it against the wall's matrix.

Should I drop the matrix representation and create mathematical regions and deal with this as we deal with it in IR^2 calculus, with some library? Wouldn't it be pretty expensive in computation terms?

What is a simple method to do this? It doesn't need to be a top notch method, but I am using it for a complex algorithm and I wouldn't want to be losing too much computing time at each iteration with this.

This likely won't completely answer your question, but it may help. When I was doing collision detection in a small game I was writing, I would have a collision 'hit box' surrounding the object as well as a more complex detection method. You don't have to use the complex method until the two hit boxes overlap, and then you only have to calculate collision for the two objects, rather than every object to every other object in space.

I did a similar thing years ago. Each object of my 3D scene was composed of basic wall/floor/ceiling object patterns. Each object was a mesh with his own bounding sphere. Then I first tested my camera's bouding sphere against each object's bounding sphere for detecting collision, and if they collided I performed a more precise collision test (mesh/sphere).

It was fast enough (Duron 600 MHz) and it was really easy to implement.

For your scenario, you seem to have a lot of dynamic objects (I only had the camera in my project, as a moving object) so it might help to have some kind of space partitioning techniques like BSP-trees of quadtrees.

I suggest approximating both bodies as spheres (collision capsule) with radius R1 and R2.

If this is the case, you'll need to account for:

1 - The radius of the two bodies. In this case the enemy will be a point of radius 0 and the bullet will have radius getBulletSize();

2 - The velocity of the bullet and the enemy during the animation frame is between 0<=t<=1.

The case of the collision will occur when |r1 + r2| < d, where d is the distance between both bodies centre of mass.

d is given as P(t) - Q(t), Q and P are the centre of mass of both objects. P(t) = P0 + Vpt. Q(t) = Q0 + Vqt.

Vp = P1 - P0; Vq = Q1 - Q0;

=> d = P(t) - Q(t)

Solving for the case (R1 + R2)^2 = (P(t) - Q(t))^2 will produce the time of collision. Don't be scared of this formulae! It solves to a simple second order polynomial of which the quadratic formula will solve for t. If B^2 > 0 in the formulae, first time of surface collision occurs when the time is a minimum!

Collision Cases:

Occurs if:

1) 0 <= t <= 1.

Preliminary Check:

2) minimum d (derivative of radius condition = 0) must be < R1 + R2

You can also enhance this by creating a bounding volume hierarchy of the object mesh with a leaf density (number of primitives per cell) condition. The initial collision tests would then iterate from root down to handle over approximation due to the capsule order.