# Quake 3 collisions

This topic is 4143 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ive got a fully working Q3 renderer up and running in XNA and wanted to try to get some collision going. I looked about on tih forum and didnt find much, so I knocked this up
Vector3 CheckCollision(Vector3 position, Vector3 velocity)
{
BSPLeaf leaf = DetermineCurrentLeaf();

for (int j = 0; j < leaf.n_leafbrushes; j++)
{
BSPLeafBrush leafBrush = LeafBrush[leaf.leafbrush + j];
BSPBrush brush = Brush[leafBrush.brush];
for (int k = 0; k < brush.n_brushsides; k++)
{
int plane = BrushSide[brush.brushside + k].plane;
float dot = Vector3.Dot(position-velocity, Plane[plane].normal) - (Plane[plane].dist);
dot = Math.Abs(dot);
if (dot <5)
{

velocity = new Vector3((float)Math.Acos(Plane[plane].normal.X)*velocity.X,
(float)Math.Acos(Plane[plane].normal.Y) * velocity.Y,
(float)Math.Acos(Plane[plane].normal.Z) * velocity.Z);
}

}
}
position =position- velocity;

return position;

}

Now I should point out now that my maths isnt great, so theres probably lots to pick apart here! Now What i seem to get it I collide against most some of the rendered walls as i expect, but also hit a few impassible ones too. Basically I get down to the plane level of the BSP (I assume I'm doing it correctly), and then dot the new position against the plane. If it is <5 (the radius of my bounding sphere), then I alter the velocity to the ACos of the normal of the plane. The reason for this is that if the normal of the plane is 0,1,0 then acos of that would be 90,0,90 which would indicate that i cant move in the Y direction. So 1: Does anyone know how to avoid the invisible planes (ie the ons that dont have walls or floors) 2: Is there anything anyone can suggest as being obviosly wrong above. I mean it seems to work ok, but I'm open for critisism - but please remember that my maths isnt the greatest, so if you respond with "You should dot the quadrangle of the perpendicular hypotenuse, and then pass that to a Logarithmic algorithm", I may ask for help interpretting it! Cheers (PS the above code is c# - not that it should make too much difference to anyone) Neil

##### Share on other sites
Check this tutorial, it explains exactly what you need to do.

As a sumary, what you do is trace a ray from your initial (current) position to your (desired) final position thru the BSP to find the first collision if any, then move acordingly.

If you look at the Quake 3 source, the code is in code/qcommon/cm_trace.c, the magic begins with the CM_Trace function.

##### Share on other sites
I actually tried that code, but couldnt get it to work properly. I didnt manage to get wall collsions working, but not floor collision. I downloaded the Q3 source earlier, but i was a little overwhelmed- your link to where to find the code should be most helpful.

N

##### Share on other sites
Quote:
 Original post by thedoI actually tried that code, but couldnt get it to work properly. I didnt manage to get wall collsions working, but not floor collision. I downloaded the Q3 source earlier, but i was a little overwhelmed- your link to where to find the code should be most helpful. N

I got mine working after careful study of the Quake 3 source, I am not sure if your problems came from errors in the paper or errors in your implementation, but yes, I'll agree that the paper by itself does not sufice, and I think it does have some subtle errors, nevertheless its a good start on understanding how the code works.

In any case, finding the current leaf, which seems to be what you are doing, is a step for rendering, not collision detection.

##### Share on other sites
Thanks for the info. Ive converted the source to VS2005 poject and its compiling now - I'm not planning on running it right now, but just using VS to allow me to navigate the structures more easily than Textpad.

Cheers

N

##### Share on other sites
Well, what a long morning of trying to understand code.

I finally got something running - I basically managed to get by by always assuming a bounding sphere, and converting the following methods

CM_Trace, CM_PositionTest, CM_TraceThroughLeaf, CM_TraceThroughBrush, CM_TraceThroughTree, CM_TestInLeaf and CM_TestBoxInBrush, and CM_BoxLeafNums_r.

I'm at a bit of a loss why it does so much work when there is no velocity - I'd assume that if you havetnt moved that the game could assume that you were in a valid area and just let you keep the position, but apparently not - can anyone shed any light?

As per usual, Its not perfect - probably due to parts ive incorrectly translated - as i still havea couple of walls i can walk thorugh and some invisible walls still. Still no collision with the floor either - should there be?

Anyways, thanks for the help so far!

N

##### Share on other sites
Quote:
 Original post by thedoI'm at a bit of a loss why it does so much work when there is no velocity - I'd assume that if you havetnt moved that the game could assume that you were in a valid area and just let you keep the position, but apparently not - can anyone shed any light?

There is always velocity, remember Gravity? its the LAW you know [smile].

Quote:
 Original post by thedoAs per usual, Its not perfect - probably due to parts ive incorrectly translated - as i still havea couple of walls i can walk thorugh and some invisible walls still. Still no collision with the floor either - should there be?Anyways, thanks for the help so far!N

Perhaps its due to the fact that you're not applying the acceleration due to gravity?

Cheers!

##### Share on other sites
Well, the trace method takes a start point and an endpoint, so i was doing something like

Vector3 position = cameraPosition; //Gotten though inverting the view and getting the translation
Vector3 newPosition = position+velocity;

my velocity would be say, 0,-0.1,0 - which means that the endpoint isnt equal to the startpoint. I know a linear velocity for gravity isnt exactly realistic, but hey, I'd rather make it realistic once its working! This also in this case doesnt really explain why so much work is done when the endpoint==startpoint as this doesnt actually happen!

N

##### Share on other sites
Quote:
 Original post by thedoWell, the trace method takes a start point and an endpoint, so i was doing something likeVector3 position = cameraPosition; //Gotten though inverting the view and getting the translationVector3 newPosition = position+velocity;my velocity would be say, 0,-0.1,0 - which means that the endpoint isnt equal to the startpoint. I know a linear velocity for gravity isnt exactly realistic, but hey, I'd rather make it realistic once its working! This also in this case doesnt really explain why so much work is done when the endpoint==startpoint as this doesnt actually happen!N

ok, 2 observations, one is that your position should really be the center of the character axis alligned box, or the center of its bounding sphere if you are using spheres, this is because the algorithm expects ths to be the case (IE, it uses a radius to determine the bounding volume of the character), the camera position would usually be offset as to be close to he eyes of the model, you may be setting the camera position to be the center of the bounding volume, in such case, just keep it in consideration for later.

the second observation is that the scale on Quake 3 BSPs is 32 units per meter, which means a velocity of -0.1 for gravity is almost neglectible unless you are scalling everything acordingly, try using a bigger number even if right now its a static value and remember gravity on earth has an acceleration of 9.81 m/s² or 32.2 ft/s².

##### Share on other sites
The reason i chose such a small number was to ensure I actually hit the plane and wasnt going through fully in 1 frame. I'm pretty sure I'm doing something wrong somewhere (obviously), however its just pretty hard to debug it as i can only test "virtually" - ie other than getting no feedback from hitting the ground its pretty hard to determine why without stepping through a *lot* of times!

N

##### Share on other sites
Quote:
 Original post by thedoThe reason i chose such a small number was to ensure I actually hit the plane and wasnt going through fully in 1 frame. I'm pretty sure I'm doing something wrong somewhere (obviously), however its just pretty hard to debug it as i can only test "virtually" - ie other than getting no feedback from hitting the ground its pretty hard to determine why without stepping through a *lot* of times!Cheers for your advice!N

You shouldnt worry about tunneling, the algorithm takes care of it, remember, conceptualy it doesnt "teleport" the character from start to end, it moves it along the segment descrived by the start/end points stoping if it finds an obstacle before reaching the end, just make sure you begin the simulation with the character in a non-colliding state, perhaps a unit or two over the floor instead of actually hitting it.