Skip to main content
GameDev.net gamedev.net
🔒 Locked

Collision detection using Sector

Started by jonathanc Apr 17, 2009 at 10:41 AM 24 replies 3.1k views
Original Post
jonathanc
jonathanc
Hi, I am working on a simple FPS game and currently thinking about a simple way to implement collision detection (or how the enemy detects the player and vice versa). It's a game for the visually impaired so there's no camera/graphics at all. Just sound cues. First criteria is that the enemy/player has to be within a certain distance from each other. This is easy as I used the Bounding Circle method to detect if the collide. Second bit is a bit tough for me. Both my enemy and player have orientation vectors. Currently I am only making them 2D thus a (0, 1)[1 is max] vector would mean the player/enemy is facing north. Do keep in mind though that the orientation vector could also be a float like [0.024, -0.987] etc depending on which quadrant the view is facing. I want them to "detect" each other when the first criteria is true and also when they are facing each other. Now, if player has orientation vector of (0,1) and enemy of (0, -1) would mean they are facing each other. This is easy enough but I also want a certain angle as well. So I want them to face each other and maybe have certain angles too, for example a 45 FoV. So thats around 22.5 degrees each side of the exact opposite orientation vectors. I looked at Sectors (Area = 1/2 * radius * PI) but I am not sure how should I apply it here. Should I just apply the orientation vector (and position vector) then calculate a Sector (instead of Bounding Cirle) at that position? The radius could just be a preset value of the enemy's tracking range and the player's maximum view range etc. Just wondering if this is the correct method of implementing this. The game I am creating is mostly Audio based (Direct3D) so I am using Sound Cones (which I think would work great with this idea). Basically what I need is a "Bounding Sector" Collision detection I guess? What I have now is just a simple Bounding Circle and that works but its weird to have the zombie attacking you when he is facing the other way. Any ideas/suggestions would be appreciated! edit: sorry bout double post... was lagging and I clicked back and refreshed. [Edited by - jonathanc on April 17, 2009 10:57:32 AM]
Zakwayda
Zakwayda
Basically, you want to perform a 'field of view' check, which is pretty straightforward.

The test reduces to finding the angle between the forward vector and the vector to the target, and checking to see if the magnitude of the angle is below the given threshold (the threshold will typically be half of the desired field of view).

To find the unsigned angle between two vectors in 2-d:
float unsigned_angle(vector2 a, vector2 b){    return abs(atan2(perp_dot(a,b), dot(a,b)));}
The field-of-view check can then be written like this:
bool check_fov(vector2 pos, vector2 forward, float fov, vector2 target){    return unsigned_angle(forward, target - pos) < fov / 2;}
Not compiled or tested, but I'm pretty sure I got that right.
jonathanc
jonathanc
Edited reply. I found this out from Googling:

float perp_dot (vec2 v1, vec2 v2){	D3DXVECTOR2 v1_d3d (v1.x, v1.y);	D3DXVECTOR2 v2_d3d (v2.x, v2.y);	vec2 v1_perp = perp (v1);	D3DXVECTOR2 v1_d3d_perp (v1_perp.x, v1_perp.y);	return D3DXVec2Dot (&v1_d3d_perp, &v2_d3d);}


I guess this is correct in your case as well?

Few questions though so I hope you could kindly help out:

1) 
    return abs(atan2(perp_dot(a,b), dot(a,b)));

this returns value in radians if I am not mistaken? So must I reformat it to degrees here since I will declare the FoV in degrees?

2) By magnitude of the FoV do you mean the radius of the sector aka how far the FoV extends? I would be needing to control the distance as well. I know how to do this via bounding circle method but not so sure about this current method.


So for example, lets say if player is at position (0,0) and has a FoV of 45 degrees facing orientation vector (0,1). The enemy is at position (1,0) same FoV but is facing orientation vector (0,1) as well. This means that the enemy's back will be facing the player hence he shouldn't "see" the player to react (test returning negative for enemy). But the player sees the enemy assuming the radius of his FoV puts the enemy's position inside the FoV. (check for player returns positive). I will basically run the collision check for player and enemy since there are conditions where the enemy "sees" the player but the player doesn't see the enemy or vice versa depending on orientation.

Sorry for the long questions but any help would be welcomed! Thanks!

[Edited by - jonathanc on April 17, 2009 12:51:25 PM]
Zakwayda
Zakwayda
Quote:
this returns value in radians if I am not mistaken? So must I reformat it to degrees here since I will declare the FoV in degrees?
Yes, you'll need to perform any necessary degrees<->radians conversions. If you're programming in C or C++, atan() will return the angle in radians, so you'll need to convert the result to degrees if that's how your field of view is represented.
Quote:
2) By magnitude of the FoV do you mean the radius of the sector aka how far the FoV extends? I would be needing to control the distance as well. I know how to do this via bounding circle method but not so sure about this current method.
By magnitude I just mean the absolute value. Also, it was actually the absolute value of the angle between the forward vector and the vector to the target that I was referring to, not the absolute value of the field of view (which wouldn't be of much use, of course, since the field of view is always positive).

So no, it doesn't have anything to do with the view distance or query radius. As for how to perform the range check, the answer is simply to perform the bounding circle test first (which you already know how to do), and then perform the FOV check to see if the target is in the object's field of view. In other words, they're two separate things (the code I posted doesn't do a range check of any sort - it's intended to be used in addition to the bounding circle test, not in place of it).
Quote:
So for example, lets say if player is at position (0,0) and has a FoV of 45 degrees facing orientation vector (0,1). The enemy is at position (1,0) same FoV but is facing orientation vector (0,1) as well.
Are you sure you didn't mean '0, 1' for the enemy position? If so, your example makes sense (as written though, it doesn't seem to work out as you described).
jonathanc
jonathanc
Hi jyk,

Thanks for your reply. I have worked out most of the stuff and it looks like its working.

Quote:
Are you sure you didn't mean '0, 1' for the enemy position? If so, your example makes sense (as written though, it doesn't seem to work out as you described).


Yes, I meant 0,1. Sorry about the mistake. However, I do notice a small bug.

Lets imagine this:
Player pos (0,0) Player orient (0,1) Player radius (1)Enemy pos (0,3) Enemy orient (0,1) Enemy radius(1)


So at start there's no bounding circle. I start to move the player forward (+Z) 1 unit to pos (0,1) the bounding circle test will return pos but fov will return neg. So enemy won't attack. (but player able to attack ofc). I move the player to pos (0,4). The enemy remains stationary at all time.

Now, please correct me if I am wrong but enemy should be start to attack me at this position? The enemy doesn't seem to be doing anything in this case. The bounding circle+fov only works if enemy has orientation (0,-1) at start.

Any clues as to why? I do the test per every frame.
Zakwayda
Zakwayda
There are a few things I don't quite understand about your example:
Quote:
Lets imagine this:
Player pos (0,0) Player orient (0,1) Player radius (1)Enemy pos (0,3) Enemy orient (0,1) Enemy radius(1)
So at start there's no bounding circle.
What do you mean by 'there's no bounding circle'? Do you just mean that the bounding circle test returns negative for both entities?
Quote:
I start to move the player forward (+Z) 1 unit to pos (0,1) the bounding circle test will return pos but fov will return neg.
Are you talking about the player here, or the enemy? If it's the player, the FOV test should return positive. Also, I would think the bounding circle test for both would return negative here (since neither entity is within the bounding circle of the other).
Quote:
So enemy won't attack. (but player able to attack ofc). I move the player to pos (0,4). The enemy remains stationary at all time.

Now, please correct me if I am wrong but enemy should be start to attack me at this position? The enemy doesn't seem to be doing anything in this case. The bounding circle+fov only works if enemy has orientation (0,-1) at start.
Are the moves discrete, or continuous? That is, is the player moved instantaneously from position 0,1 to position 0,4, or does the player move smoothly from one position to the other over several updates?

If the move is instantaneous (i.e. discrete), then the bounding circle test for the enemy could easily fail when the player is at 0,4 (due to numerical imprecision). If it's continuous, then the enemy should detect the player when the player moves past the point 0,3.

In any case, if the test isn't working as you expect, perhaps you could post your code (be sure to include both the bounding circle and FOV portions). It's a simple algorithm, so if there are any errors they should be pretty easy to spot.
jonathanc
jonathanc
Quote:

What do you mean by 'there's no bounding circle'? Do you just mean that the bounding circle test returns negative for both entities?


Yes sorry for not clarifying. I mean that if I test the player with the enemy using the bounding circle function it returns negative, hence it doesn't test the fov at this stage.

Quote:
Are you talking about the player here, or the enemy? If it's the player, the FOV test should return positive. Also, I would think the bounding circle test for both would return negative here (since neither entity is within the bounding circle of the other).


At the moment the enemy doesn't move and would always be at the same initial orientation when it was created. The only moving entity at the moment is the player. He is free to move on the ZX plane and also change orientation about this plane.
Now to the confusing bit here :D I modified slightly your FoV test. This is the prototype of my check_fov function :

bool Player::check_fov(CVector2 Zombiepos, CVector2 zombieOrient, float zombiefov, CVector2 playerPos)

as you can see, the player is actually the "target" here. The rest of the terms in the function is rather self explanatory.

This is then the prototype of the complete collision detection function (to check if the zombie will attack the player exclusively)

bool Player::Attacked(float x, float z, float r, CVector2 Tarpos, CVector2 TarOrient, float tarFOV ){		if(BoundingCircle(x, z, r)) //within range (player can attack but zombie will depend if it is facing player	{				if(check_fov(Tarpos, TarOrient, DEG2RAD(tarFOV), target) )		{			return true; // check if within zombie fov target = player ZX pos in this case, as a CVector2 type		}		return false;			}	return false;}


Ignore the bad coding practice here please. x, z, r are the X-pos, Z-pos and the radius for the zombie entity.
Sorry again for being incoherent but could you please have a look to see if I have done anything wrong here?

Quote:
Are the moves discrete, or continuous? That is, is the player moved instantaneously from position 0,1 to position 0,4, or does the player move smoothly from one position to the other over several updates?

If the move is instantaneous (i.e. discrete), then the bounding circle test for the enemy could easily fail when the player is at 0,4 (due to numerical imprecision). If it's continuous, then the enemy should detect the player when the player moves past the point 0,3.

In any case, if the test isn't working as you expect, perhaps you could post your code (be sure to include both the bounding circle and FOV portions). It's a simple algorithm, so if there are any errors they should be pretty easy to spot.


The moves are continous. I check for keyboard input every frame and moves a certain unit when the check returns positive. I hope the code posted here are adequate. Please kindly let me know if you need more.

Again, thanks for your help.

edit: Posted my Bounding Circle function as well just in case there's some mistake in it.
bool Player::BoundingCircle(float x, float z, float r){	float xsq, zsq, rsq, temp;		D3DVECTOR postemp;	player->GetPosition(&postemp);		xsq = pow((x-postemp.x), 2);	zsq = pow((z-postemp.z), 2);	rsq = pow((r + REACH), 2);	temp = (xsq + zsq);	return (temp < rsq); // collision	}

Zakwayda
Zakwayda
Can you post the code for check_fov()?
jonathanc
jonathanc
Quote:
Original post by jyk
Can you post the code for check_fov()?


Sure , here you go :

bool Player::check_fov(CVector2 Zombiepos, CVector2 zombieOrient, float zombiefov, CVector2 playerPos){    return unsigned_angle(zombieOrient, vec_sub(Get2Dpos() , Zombiepos)) < zombiefov / 2; //zombiefov here is still in degrees though (45 / 60 etc) not sure if thats right	}CVector2 Player::Get2Dpos(){	D3DVECTOR temp;	player->GetPosition(&temp);	return CVector2(temp.x, temp.y);}CVector2 vec_sub(CVector2 v1, CVector2 v2){	return CVector2 (v1.x - v2.x, v1.y - v2.y);}


Sorry for the late reply, sometimes the forums would just time-out for me and says Page Not Found.
Zakwayda
Zakwayda
Sorry, I probably should have been more specific. In order to try and diagnose the problem, I really need to see all the code. In this case, I need to see unsigned_angle() and any support functions it calls that you have written.

Again, if there's an error, I'm sure it'll be easy to spot, but without seeing all the code I can really only guess as to the cause of the problem.
jonathanc
jonathanc
whoops , forgot about unsigned_angle

here it is:

float Player::unsigned_angle(CVector2 a, CVector2 b){    return abs(atan2(perp_dot(a,b), vec_dot(a,b)));}//and the vector functions called :CVector2 perp (CVector2 v){	return CVector2 (-v.y, v.x);}float vec_dot (CVector2 v1, CVector2 v2){	D3DXVECTOR2 v1_d3d (v1.x, v1.y);	D3DXVECTOR2 v2_d3d (v2.x, v2.y);	return D3DXVec2Dot (&v1_d3d, &v2_d3d);}float perp_dot (CVector2 v1, CVector2 v2){	D3DXVECTOR2 v1_d3d (v1.x, v1.y);	D3DXVECTOR2 v2_d3d (v2.x, v2.y);	CVector2 v1_perp = perp (v1);	D3DXVECTOR2 v1_d3d_perp (v1_perp.x, v1_perp.y);	return D3DXVec2Dot (&v1_d3d_perp, &v2_d3d);}class CVector2{public:	float x;	float y;	friend float vec_dot (CVector2 v1, CVector2 v2);	friend float perp_dot (CVector2 v1, CVector2 v2);	friend CVector2 vec_sub(CVector2 v1, CVector2 v2);	CVector2 perp (CVector2 v);	CVector2 (float x_in, float y_in)	{		x = x_in;		y = y_in;	}};


Should be all I hope. It's a bit messy because I am cut and pasting from all over the place :P
Zakwayda
Zakwayda
I haven't looked over all the code yet, but the first thing I see is that unsigned_angle() returns the angle in radians (assuming C++), but it looks like you're comparing it to an angle in degrees. I'd start by fixing this, and see if that solves the problem.
jonathanc
jonathanc
Hmm, well spotted. And yes, I'm programming in C++. Was a bit tired last night when coding this. Ive made the following changes:

bool Player::check_fov(CVector2 Zombiepos, CVector2 zombieOrient, float zombiefov, CVector2 playerPos){	   // return unsigned_angle(zombieOrient, vec_sub(Get2Dpos() , Zombiepos)) < zombiefov / 2;	return unsigned_angle(zombieOrient, vec_sub(Get2Dpos() , Zombiepos)) < DEG2RAD(zombiefov) / 2;	}//with the following defines:#define PI 3.141592#define DEG2RAD(x) (x * (PI / 180.0f))


Will try to do some testing now

[Edited by - jonathanc on April 18, 2009 3:36:16 PM]
jonathanc
jonathanc
Right, test results:

Player starts @ (0,0). I set his orientation locked to (0,1) so this means he will head dead north. His radius is set as 1.

Test 1:
Zombie positioned @ (0,3) Orientation set to (0, -1). Radius is 1. (Zombie will never move nor change orientation)

My bool Player::Attacked(float x, float z, float r, CVector2 Tarpos, CVector2 TarOrient, float tarFOV ) function returns positive @ around (0,1.1).

I guess this is normal as the player is both in the bounding circle range and also the zombie is facing him.

Test 2:
Zombie same position but Orientation set to (0, 1). Player starts back (0,0). Player moves in the same direction as Test 1.

No collision happens whatsoever. Shouldn't Player::Attacked return positive the player goes beyond (0, 3) ? This means the zone where the player will be attacked.

Conclusion
So far it seems that Player::Attacked only works if zombie if facing towards the player. Haven't tested other variables though such as different zombie positions and orientations.
However, I think that this test should be successful since its the most basic test for this case.

[Edited by - jonathanc on April 18, 2009 4:46:16 PM]
Zakwayda
Zakwayda
Yes, if the zombie is at 0,3 and facing north (0,1), and if the player starts at 0,0 and moves north, then the test should return true once the player has passed the position 0,3.

I'll look at the code a little more, but in the meantime, I recommend doing some debugging. Start by positioning the player at, say, 0,3.5, and run the app. The easiest way to see what's going on would probably be to step through the program in the debugger, if the tools you're using offer this feature. If not, and if you have a console of some sort available, add debug output that indicates what exactly is happening.

What you want to determine is where and why the test is failing. Is the bounding circle test returning false? Or the FOV test? If the latter, why? What is the computed angle between the zombie's forward direction vector and the vector to the player? (In your test case, it should be around zero.) What value is it being compared to? Is the field of view that's passed in correct? And so on.

If I spot anything else in the code that looks suspect though, I'll let you know.
Zakwayda
Zakwayda
Just a couple additional comments after looking over the code a little more.

I would double-check again that you're handling degree-radian conversions correctly. I suggested that perhaps you were comparing radians to degrees in your FOV test function because you had a comment to that effect there, but I also see that you're converting the field of view argument to radians when you call that function. Anyway, make sure you're not missing any conversions anywhere, or converting more than once (e.g. converting degrees to radians, and then converting to radians again, which will give you garbage).

From a debugging standpoint, it might be easier if you worked with degrees consistently (for math library functions such as atan2 that return an angle in radians, just convert the return value to degrees immediately before doing anything with it). This might make it easier to confirm the correctness of the computed values at a glance.

Beyond that, the code is currently a little hard to follow, so without really digging into it I can't really tell what's happening where. This is mostly due to variable and function naming, and general code organization. It's probably clear enough to you (since you wrote it!), but it's probably still worth double-checking to make sure that you're working with the right data (e.g. player position, zombie position, zombie field of view, etc.) in the right places.
jonathanc
jonathanc
Aye I know its pretty messy because there's a lot of other code here and there and I didn't paste the complete class (which would be VERY long :P )

I have a separate console window to output my printf for debugging purposes.
AllocConsole();	freopen("CONOUT$", "wb", stdout);
and I am using VS2005 and trying my best to debug things

Hmm, about the conversion, should I just convert the return of 
float Player::unsigned_angle(CVector2 a, CVector2 b){    return abs(atan2(perp_dot(a,b), vec_dot(a,b)));}

so that it will return a value in degrees? For example: 
return RAD2DEG(abs(atan2(perp_dot(a,b), vec_dot(a,b))));


edit: Will attempt to explain the code out a little :P
bool Player::Attacked(float x, float z, float r, CVector2 Tarpos, CVector2 TarOrient, float tarFOV )

is basically the star of the show. It's called every frame and compared to all the alive zombies (not so efficient I know:P) which at the moment is just one. Zombies like the player have 3 important stats, their pos (ZXplane), their orientation(0-1 range on the ZX plane) and lastly the radius (for bounding circle computation). At the present, the zombies don't move/turn at all.

Float x,z in this function is the zombie's pos, float r is the zombie's radius. Tarpos means the zombie's position again as CVector2 type, TarOrient is the zombie's orientation (0,1 etc etc) and the fov is the zombie's FoV in degrees.

Player::Attacked first test for Bounding Circle comparing the player's current pos and the zombies. If that passes , it will then test for fov using 
bool Player::check_fov(CVector2 Zombiepos, CVector2 zombieOrient, float zombiefov, CVector2 playerPos)

This is basicallly the code that you showed me earlier except I use the player as the "target" here. If that passes as well Player::Attacked will return positive. It will return false in all other circumstances. Player::Attack is specifically just used to see if the player is attacked by zombies.
Zombiepos = the zombie's position, zombieOrient = the zombie's orientation, zombiefov = zombie's fov. Yeah I know the naming conventions are very confusing and probably the code is not efficiently or well written but I am just trying to keep things simple and of course make it work :P

Hmm I hope that cleared things up a bit .Will do further testing but its all numbers at the moment and as you probably know I am not so good with numbers :(
This is a game for the visually impaired so there's no graphics to compare or debug with.

Zakwayda
Zakwayda
Quote:
Hmm, about the conversion, should I just convert the return of 
float Player::unsigned_angle(CVector2 a, CVector2 b){    return abs(atan2(perp_dot(a,b), vec_dot(a,b)));}

so that it will return a value in degrees? For example: 
return RAD2DEG(abs(atan2(perp_dot(a,b), vec_dot(a,b))));
Yes, that would work. The key though is consistency - just remember that if you miss a conversion, or if you inadvertently compare a value in degrees to a value in radians, the results will be incorrect in most cases and your program will not behave as you expect.

A reasonable approach would be to work with degrees consistently within your program, and then only perform conversions when interfacing with C/C++ math library functions (like in your example above).
jonathanc
jonathanc
Hey , made a lil edit on the previous post to clear things up a bit.

I made the changes to the return and it seems to still have the same impact as before so I reckon the conversion is not the issue here. Perhaps a way I apply some function , such as the check_fov which I did make some changes from what you have suggested. I probably didn't get the direction vectors (orientation vectors) right...
Zakwayda
Zakwayda
One small tip: just because the final game won't incorporate graphics doesn't mean you can't create a graphical representation for debugging purposes.

If you don't have any support in place for graphics though, it may or may not be worth the trouble to add such support. (It depends on the scope of the project, I suppose - if the eventual scope of the simulation will be significantly greater than a player and a few zombies, spending a day or two getting some debug graphics in place might very well pay off in terms of development time saved.)

Since at the moment you don't have any graphical debug output, I would just suggest that you not take the correctness of any of your data for granted; for example, the direction vectors themselves could be incorrect, as you mentioned.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.