Collision detection in 3D for obstacles, sword fighting... [Archive]

Firlefanz

14-11-2006, 08:11 AM

Hello,

I need a collision detection for mainly 2 purposes:
- when the player is walking he should not walk 'through' obstacles
- when the player beats I want to know which monster(s) are hit

It is for a 3D kind of medieval RPG Action Game developed with DanJetX.

All my meshes are stored in a Engine based on a TList.

I have a very basic collision detection working a a circle's radius, taken and altered from a sample from Dan:

function TForm1.boundcollide(spriteself: TDJXEngineItem): boolean;
var i: integer;
colSpr: TDJXEngineItem;
ColPt: TD3DXVector2;
tmpVec: TD3DXVector2;
ndist: Double;
begin
//Collision with other sprites
//do not be alarmed by the complexity of the
//calculations, they are really simple
//once you take a closer look;)
result:=false;
for i:=0 to Engine.Count-1 do begin
ndist:=distance_dbl(spriteself.x,spriteself.z,0,En gine.Sprites[i].X,Engine.Sprites[i].Z,0);
if (Engine.Sprites[i]<>spriteself) and (ndist<Innomsprite(spriteself).nRadius+Innomsprite(Engine .Sprites[i]).nRadius+1)
then begin
colSpr:=Engine.Sprites[i];
//Player schl?§gt
if (spriteself.name='spieler') and (meshplayer(spriteself).status=schlag1) then begin
if (colspr.name='innom') and (meshinnom(colspr).status<>schmerz) then begin
meshinnom(colspr).nanimpos:=0;
meshinnom(colspr).status:=schmerz;
meshinnom(colspr).hit(meshplayer(spriteself).nhitp ower);
end;
end;
//Innom schl?§gt
if (spriteself.name='innom') and (meshinnom(spriteself).status<>schlag1) and (meshinnom(spriteself).status<>schmerz) then begin
if (colspr.name='bauer') then begin
meshinnom(spriteself).nanimpos:=0;
meshinnom(spriteself).status:=schlag1;
meshbauer(colspr).hit(meshinnom(spriteself).nhitpo wer);
end;
if (colspr.name='spieler') then begin
meshinnom(spriteself).nanimpos:=0;
meshinnom(spriteself).status:=schlag1;
meshplayer(colspr).hit(meshinnom(spriteself).nhitp ower);
end;
end;
if (Engine.Sprites[i]<>spriteself) and (ndist<Innomsprite(spriteself).nRadius+Innomsprite(Engine .Sprites[i]).nRadius)
then begin
result:=true;
colSpr:=Engine.Sprites[i];
ColPt:=D3DXVector2((spriteself.X+colSpr.X)/2,(spriteself.z+colSpr.z)/2);
tmpVec:=D3DXVector2(spriteself.X - colSpr.X,spriteself.z - colSpr.z);
D3DXVec2Normalize(tmpVec, tmpVec);
if innomsprite(spriteself).bolmovable then begin
if innomsprite(ColSpr).bolmovable then begin
spriteself.x:=ColPt.x + tmpVec.x * innomsprite(spriteself).nRadius;
spriteself.z:=ColPt.y + tmpVec.y * innomsprite(spriteself).nRadius;
end
else begin
spriteself.x := ColSpr.x + tmpVec.x * innomsprite(ColSpr).nRadius + tmpVec.x * innomsprite(spriteself).nRadius;
spriteself.z := ColSpr.z + tmpVec.y * innomsprite(ColSpr).nRadius + tmpVec.y * innomsprite(spriteself).nRadius;
end;
end;
end;
{ if innomsprite(ColSpr).bolmovable then begin
if innomsprite(spriteself).bolmovable then begin
ColSpr.x := ColPt.x - tmpVec.x * innomsprite(ColSpr).nRadius;
ColSpr.z := ColPt.y - tmpVec.y * innomsprite(ColSpr).nRadius;
end
else begin
ColSpr.x := spriteself.x - tmpVec.x * innomsprite(spriteself).nRadius - tmpVec.x * innomsprite(ColSpr).nRadius;
ColSpr.z := spriteself.z - tmpVec.y * innomsprite(spriteself).nRadius - tmpVec.y * innomsprite(ColSpr).nRadius;
end;
end; }
exit;
end;
end;
end;

One problem is it only works with circles, so this is bad when it comes to fences and walls etc. So I need another case for rectangle collisions?

The other problem is, 'spieler' means player, 'innom' is the monster, 'bauer' is a villagers and each of them has a nrotatey variable beween -pi and pi which direction the person faces.
Now when many monsters surround the player, one gets hits but not the one in the right direction, it may also be one standing behind the player...

I am not experienced with that, can somebody help me out, how do you guys do this?

Thanks,
Firle

grudzio

14-11-2006, 05:01 PM

Now when many monsters surround the player, one gets hits but not the one in the right direction, it may also be one standing behind the player...

Store the direction the player is facing as a vector. It can be made from facing angle

vDir := vector(cos(angle,0,sin(angle));

To find out if player faces the monster first calculate vector v between player and monster positions. Then calculate the dot product of v and players direction. If it is greater than zero than monster is in front of a player otherwise monster is behind.

This method gives you information if the monster is behind or in front of the player. The monster can be in front of the player but outside players
viewing field (too far ont he right or left). To check this further tests are needed. An example

I am assuming that player has 90 degree field of view.
\ front /
\ /
\ /
left ---P --- right
/ \
/ \
/ back \

v := Monster.Pos - Player.Pos;
d := dotProduct(Player.Dir,v);
if d > 0 then begin //the monster over the vertical line on the picture
d := ArcCos(d);
if (d < pi/4) or (d > 3*pi/4) then //player is in the front area

As for collisons with obstacles you need bounding rectangles. You can do collision in two passes. First with static objects based on rectangles and second with monsters based on circles.

Hope you find it usefull.

Firlefanz

15-11-2006, 07:31 AM

Hello grudzio,

thanks a lot for this very useful info and explanations!

I'll try that, looks very good to me, just what I need I guess.

Thanks a lot! :D

Firlefanz

Firlefanz

15-11-2006, 01:20 PM

One question about this explanation:

vdir is : TD3DXVector3 right?

v and d are single or double, right?

What is Monster.Pos and Player.Pos?

I have x,y,z Position variable for each of them.

Is it also a TD3DXVector3 with X,Y,Z?

Thanks,
firle

Huehnerschaender

15-11-2006, 02:57 PM

Yes it is.

The Dotproduct of 2 Vectors (in your case TD3DXVector3) gives a float value.

The ArcCos of this value gives the angle (in radians), in which the 2 points are positioned to each other.

DotProduct =

function DotProduct(const a, b: TPoint3): Real;
begin
Result:= (a.x * b.x) + (a.y * b.y) + (a.z * b.z);
end;

grudzio

15-11-2006, 03:11 PM

Player.Pos and Monster.Pos are 3D vectors (TD3DXVector3) and describe world position of player and monster. They are composed of x,y,z variables you use currently.

Player.Dir is also TD3DXVector3 describing orientation of the player (or monster). It can be made from nrotatey variable you have

Player.Dir := MakeTD3DXVector3( cos(nrotatey), 0, sin(nrotatey));

If you store nrotatey in angles dont forget to change it to radians before you pass it to sin and cos functions.

vDir is also a TD3DXVector3 but in my example it is replaced by Player.Dir.

v is also a TD3DXVector3. So in the line
v := Monster.Pos - Player.Pos;
"-" means vector subtraction.

d is a scalar value (single or double).

I am sorry for the confusion. I hope it is more clear now.

I just noticed that it is already anwsered. I am so sloooow typer :( .

grudzio

15-11-2006, 03:21 PM

Just one more thing. Like Huehnerschaender already said, the dotProduct(v1,v2) returns an cosine of an angle between vectors v1 and v2. So it can be used to determine if player is facing monster. This can be usefull if you want the attacks to give more damage if made from side or behind.

Firlefanz

15-11-2006, 04:00 PM

Looks very good. Thank you both for those explantions, I will try that later and be back with more questions or let you know if it worked. :wink:

Firle

Firlefanz

16-11-2006, 07:30 AM

Hello,

yesterday I build a new routine for fighting collisions.
But something is wrong with it, when I am in the radius of the monster, in some position I hit it never, in another position I hit it always no matter how I rotate.

I guess I did something wrong here.

function TForm1.fightcollide(spriteself: TDJXEngineItem): boolean;
var i: integer;
colSpr: TDJXEngineItem;
ColPt: TD3DXVector2;
tmpVec: TD3DXVector2;
ndist,nrot: Double;
vdir,v: TD3DXVector3;
d: single;
begin
result:=false;
nrot:=degtorad(spriteself.nrotatey);
vDir := D3DXVector3(cos(nrot),0,sin(nrot));
for i:=0 to Engine.Count-1 do begin
ndist:=distance_dbl(spriteself.x,spriteself.z,0,En gine.Sprites[i].X,Engine.Sprites[i].Z,0);
if (Engine.Sprites[i]<>spriteself)
and (ndist<Innomsprite(spriteself).nRadius*2+Innomsprite(Engi ne.Sprites[i]).nRadius*2)
then begin
colSpr:=Engine.Sprites[i];
//Player hits Monster
if (spriteself.name='spieler') and (meshplayer(spriteself).status=schlag1) then begin
if (colspr.name='innom') and (meshinnom(colspr).status<>schmerz) then begin
D3DXVec3Subtract(v,D3DXVector3(colspr.X,colspr.Y,c olspr.Z),D3DXVector3(spriteself.X,spriteself.Y,spr iteself.Z));
d:= (v.x * vdir.x) + (v.z * vdir.z);
d := ArcCos(d);
//if (d <pi> 3*pi/4) then begin //player is in the front area
if (d <pi> 2*pi/3) then begin //player is in the front area
meshinnom(colspr).nanimpos:=0;
meshinnom(colspr).status:=schmerz;
meshinnom(colspr).hit(meshplayer(spriteself).nhitp ower);
end;
end;
end;
end;
end;
end;

Player is here spriteself, the monster is here the Engine item ColSpr.
I just changed the angle a bit for testing purposes but still the same, it depends on the position not on the rotation right now.

My rotation is a bit strange. When turning around I decrease it, I start at 0, at around -7 I am rotatet one time etc, at -14 two times.

When I render with -nrotatey-pi/2 for Y Rotation it is alright.
So much to my nrotateY. :D

Firle

Firlefanz

16-11-2006, 07:34 AM

Hey, the code format does strange things, the line is

...I cannot post it even with quote etc it always get changed

:evil:
Very angry! Cannot post the code!

When posting it it gets changed eached time, even with quote!

if (d <pi> 2*pi/3) then begin //player is in the front area

Firle

grudzio

16-11-2006, 07:45 AM

I have missed one important thing. The dotProduct(v1,v2) returns an cosine of an angle between vectors v1 and v2 when v1 and v2 are normalised. So before calculating dot product normalize both vectors.

Sorry about that.

About rotations. You have mixed somewhere radians and degrees.
7 is allmost equal to 2*pi = 6.28 - full 360 degree turn.

To get the < and > chars check the "Disable HTML in this post" option.

Firlefanz

16-11-2006, 09:58 AM

Hello grudzio,

thanks a lot again :)

I'll try that when I am home.

Firle

WILL

16-11-2006, 03:13 PM

Hey Eric, try posting with HTML disabled. sometimes the > and < characters are assumed to be tags.

Firlefanz

16-11-2006, 03:27 PM

Yes, grudzio also told me, thanks for the clue.

Just a funny picture, me in 3D, this will be one of our playable heroes:

http://www.ericbehme.de/phpBB2/files/pic_681.jpg

Firle

grudzio

16-11-2006, 06:13 PM

Nice picture :D

Huehnerschaender

16-11-2006, 07:00 PM

Nice underwear :) :)

grudzio, one question:

I also need a function which tells me the position of two points in height (The same as before but for higher and lower on terrain).

Can you help me with it?

Greetings,
Dirk

grudzio

16-11-2006, 09:53 PM

I am not sure if I understand you correctly. Do you want to check if the object A is behind or in front of object B and they are on different heights?

If so, just ignore the Y coordinate (height) or set it equal to zero.

v := ObjectB.Pos - ObjectA.Pos;
v.y := 0;
normalize(v);
dir := ObjectA.Dir;
dir.y := 0;
normalize(dir);
d := dotProduct(v,dir);

Huehnerschaender

16-11-2006, 10:02 PM

This tells me if an object is left or right of my viewing direction.
I need to know if it is over or under my view direction. So I cannot ignore y, because y stores height and thats exactly what I need. The angle between my height and the height of object xy.

I use this functionality for a check if object is in my frustrum. Then I decide if I draw it or not. I know how to check if the object is left or right of me and if it is out of my angle of view I don't draw it.

To speed up things now, I also want to know if it is over or under the camera view. That's what I need the function for.

Greetings,
Dirk

grudzio

16-11-2006, 11:03 PM

Now I understand :D .

First check if the object is in front of the camera. (like in my post above).
If the test is passed then:
1. calculate vector between object and camera position:

v := Object.Pos - Camera.Pos;

2. Project v on the camera direction:

oz := dotProduct(v,camera.Dir);

3. Test if object is over or under camera view:

//Pascal does not have tangent function
tan := sin(CameraViewAngle*0.5) / cos(CameraViewAngle*0.5);

if (v.y < oz*tan) and (v.y > -oz*tan) then
// object is visible

In 3. I assume that camera is not rotated along z axis.

Just in case here is a link to a good general Frustum Culling tutorial
http://www.lighthouse3d.com/opengl/viewfrustum/index.php?intro.

Huehnerschaender

17-11-2006, 01:17 AM

Thank you very much. I will try it tomorrow....

Firlefanz

17-11-2006, 07:35 AM

Nice underwear lol :D

The guy gets a breast plate armor and trousers, both can be changed, the boots are directly on the mesh and stay. There will be 4 different chars with own textures, special moves and abilities (correct word?).

So one last Question (I hope):
This helped me a lot.
Now it seems to work if I have the monster exactly in front or, and this is the problem exactly in the back :roll: :wink:

function TForm1.fightcollide(spriteself: TDJXEngineItem): boolean;
var i: integer;
colSpr: TDJXEngineItem;
ColPt: TD3DXVector2;
tmpVec: TD3DXVector2;
ndist,nrot: Double;
vdir,v: TD3DXVector3;
d: single;
begin
result:=false;
//nrot:=degtorad(spriteself.nrotatey);
nrot:=spriteself.nrotatey;
vDir := D3DXVector3(cos(nrot),0,sin(nrot));
for i:=0 to Engine.Count-1 do begin
ndist:=distance_dbl(spriteself.x,spriteself.z,0,En gine.Sprites[i].X,Engine.Sprites[i].Z,0);
if (Engine.Sprites[i]<>spriteself)
and (ndist<Innomsprite(spriteself).nRadius*2+Innomsprite(Engi ne.Sprites[i]).nRadius*2)
then begin
colSpr:=Engine.Sprites[i];
//Player hits Monster
if (spriteself.name='spieler') and (meshplayer(spriteself).status=schlag1) then begin
if (colspr.name='innom') and (meshinnom(colspr).status<>schmerz) then begin
D3DXVec3Subtract(v,D3DXVector3(colspr.X,colspr.Y,c olspr.Z),D3DXVector3(spriteself.X,spriteself.Y,spr iteself.Z));
D3DXVec3Normalize(vdir, vdir );
D3DXVec3Normalize(v,v);
d:= (v.x * vdir.x) + (v.z * vdir.z);
d := ArcCos(d);
if (d < pi/5) or (d > 5*pi/6) then begin //player is in the front area
meshinnom(colspr).nanimpos:=0;
meshinnom(colspr).status:=schmerz;
meshinnom(colspr).hit(meshplayer(spriteself).nhitp ower);
end;
end;
end;
end;
end;
end;

Disabling html....done :twisted:

Thanks a lot guys, this helps me a lot!

Firle

Huehnerschaender

17-11-2006, 08:23 AM

you "forgot" to check if d is greater than 0. only then the monster is in front of you. if d is negative then it is behind you. look at the first sample from grudizio.

greetings,
dirk

Firlefanz

17-11-2006, 08:33 AM

Now I got the idea.

This will be very cool for straight hit and 'swinging' hit lol.

Perfect, thanks! (need to write some comments now)

This helped me a lot, great stuff, thank you both :salute:

grudzio

17-11-2006, 11:51 PM

Huehnerschaender:

The third step - checking if object is below or above camera wiev should be changed to this

// CameraXAngle is the rotation angle along X axis
oy := v.y*cos(CameraXAngle);
//Pascal does not have tangent function
tan := sin(CameraViewAngle*0.5) / cos(CameraViewAngle*0.5);

if (oy < oz*tan) and (oy > -oz*tan) then
// object is visible

Now it works if camera looks up or down.

Huehnerschaender

18-11-2006, 07:43 AM

Thanks grudzio.

I will try it out as soon as possible.

Btw, my version of pascal (BDS 2005/2006) has a tan function included in math.pas.

Greetings,
Dirk