# Collision detection using Sector

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

## Recommended Posts

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]

##### Share on other sites
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.

##### Share on other sites
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]

##### Share on other sites
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).

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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	}

##### Share on other sites
Can you post the code for check_fov()?

##### Share on other sites
Quote:
 Original post by jykCan 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.

##### Share on other sites
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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 11
• 15
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
634151
• Total Posts
3015825
×