Collision Detection Hint please

[exor674]

I am having some issues with figuring out collision detection.
pX and pY is the top-left corner of the player, and sX and sY is the top-left of what I'm tring to collide with.
Both objects are 8x8 square, and I want to be able to detect entering the object from any point.
This is really CLOSE but detects if I just "brush the object" and I want to be at least 1 or 2 pixels in.
I tried something (s[XY]+2 and s[XY]+6 instead of s[XY] and s[XY]+8 {excuse my regexesque notation there}) but that just made it really finicky and miss most legal collisions.

Code: Select all

if ( (pX   >= sX && pX   <= sX+8 && pY   >= sY && pY   <= sY+8) || // top left
     (pX+8 >= sX && pX+8 <= sX+8 && pY   >= sY && pY   <= sY+8) || // top right
     (pX   >= sX && pX   <= sX+8 && pY+8 >= sY && pY+8 <= sY+8) || // bottom left
     (pX+8 >= sX && pX+8 <= sX+8 && pY+8 >= sY && pY+8 <= sY+8)) { // bottom right
          // collided
}

Someone wanna give me a shove in the right direction, or am I way off track?

[avansc]

have you considered using some better collision formulas?

Code: Select all

bool SimCol::pointInSphere(float sX, float sY, float sR, float x, float y)
{
	float dist = (sX - x)*(sX - x) + (sY - y)*(sY - y);
	if(dist < sR*sR)
		return true;
	return false;
}

bool SimCol::lineInter(line &AB, line &CD)
{
	if(((CD.y2 - CD.y1)*(AB.x2 - AB.x1) - (CD.x2 - CD.x1)*(AB.y2 - AB.y1)) == 0)
		return false;

	if(((CD.y2 - CD.y1)*(AB.x2 - AB.x1) - (CD.x2 - CD.x1)*(AB.y2 - AB.y1)) != 0)
	{
		if(((((CD.x2 - CD.x1)*(AB.y1 - CD.y1) - (CD.y2 - CD.y1)*(AB.x1 - CD.x1))/
				((CD.y2 - CD.y1)*(AB.x2 - AB.x1) - (CD.x2 - CD.x1)*(AB.y2 - AB.y1))) > 0) && ((((CD.x2 - CD.x1)*(AB.y1 - CD.y1) - (CD.y2 - CD.y1)*(AB.x1 - CD.x1))/
				((CD.y2 - CD.y1)*(AB.x2 - AB.x1) - (CD.x2 - CD.x1)*(AB.y2 - AB.y1))) < 1))
		{
			if((((AB.x2 - AB.x1)*(AB.y1 - CD.y1) - (AB.y2 - AB.y1)*(AB.x1 - CD.x1))/
				((CD.y2 - CD.y1)*(AB.x2 - AB.x1) - (CD.x2 - CD.x1)*(AB.y2 - AB.y1)) > 0) && (((AB.x2 - AB.x1)*(AB.y1 - CD.y1) - (AB.y2 - AB.y1)*(AB.x1 - CD.x1))/
				((CD.y2 - CD.y1)*(AB.x2 - AB.x1) - (CD.x2 - CD.x1)*(AB.y2 - AB.y1)) < 1))
			{
				return true;
			}
		}
	}

	return false;
}

bool SimCol::lineInSphere(float sX, float sY, float sR, line &AB)
{
	if(this->pointInSphere(sX, sY, sR, AB.x1, AB.y1))
		return true;
	if(this->pointInSphere(sX, sY, sR, AB.x2, AB.y2))
		return true;

	float dx = AB.x2 - AB.x1;
	float dy = AB.y2 - AB.y1;
	float d = dx*dx + dy*dy;
	float D = (AB.x1 - sX)*(AB.y2 - sY) - (AB.x2 - sX)*(AB.y1 - sY);
	float delta = ((sR*sR) * d) - (D*D);

	float sgn = 0;
	float dyP = dy;

	if(dyP<0)
		dyP = -1 *dyP;

	if(dy < 0)
	{
		sgn = -1;
	}else{
		sgn = 1;
	}

	if(((sR*sR) * (((AB.x2 - AB.x1)*(AB.x2 - AB.x1)) + ((AB.y2 - AB.y1)*(AB.y2 - AB.y1)))) - (((AB.x1 - sX)*(AB.y2 - sY) - (AB.x2 - sX)*(AB.y1 - sY))*((AB.x1 - sX)*(AB.y2 - sY) - (AB.x2 - sX)*(AB.y1 - sY))) >= 1)
	{
		if(((D*dy + sgn * dx * sqrt(sR*sR*d - D*D)) / d) >= AB.x1 && ((D*dy + sgn * dx * sqrt(sR*sR*d - D*D)) / d) <= AB.x2)
			return true;
		if(((D*dy + sgn * dx * sqrt(sR*sR*d - D*D)) / d) >= AB.x2 && ((D*dy + sgn * dx * sqrt(sR*sR*d - D*D)) / d) <= AB.x1)
			return true;
	}

	return false;
}

[exor674]

Code: Select all

if ( (pX   >= sX+2 && pX   <= sX+6 && pY   >= sY+2 && pY   <= sY+6) || // top left
     (pX+8 >= sX+2 && pX+8 <= sX+6 && pY   >= sY+2 && pY   <= sY+6) || // top right
     (pX   >= sX+2 && pX   <= sX+6 && pY+8 >= sY+2 && pY+8 <= sY+6) || // bottom left
     (pX+8 >= sX+2 && pX+8 <= sX+6 && pY+8 >= sY+2 && pY+8 <= sY+6)) { // bottom right
          // collided
}

Only thing I can think of is to do it with the PLAYER location instead so its

Code: Select all

if ( (pX+2 >= sX && pX+2 <= sX+8 && pY+2 >= sY && pY+2 <= sY+8) || // top left
     (pX+6 >= sX && pX+6 <= sX+8 && pY+2 >= sY && pY+2 <= sY+8) || // top right
     (pX+2 >= sX && pX+2 <= sX+8 && pY+6 >= sY && pY+6 <= sY+8) || // bottom left
     (pX+6 >= sX && pX+6 <= sX+8 && pY+6 >= sY && pY+6 <= sY+8)) { // bottom right
          // collided
}

but I think that'll miss a few legal collisions too: pX == sX && pY == sY+2 for example
but I really can't test my new idea or mess with it much more as I have to zoom off to class... Bah!

[bugmenot]

You are on the right track but your implementation is off. Lets assume you want a 1 pixel 'brush'?

Code: Select all

// Work out the actual collision's top left hand corner, not the graphics
int newPX = pX + 1;
int newPY = pY + 1;
int newSX = sX + 1;
int newSY = sY + 1;

// The collision box size is now 6 not 8 (1 pixel on each side)
const int COLLISION_BOX_SIZE = 6;

Now you have the values needed for the collision box inside graphic, centred properly.

[bugmenot]

have you considered using some better collision formulas?

Code: Select all

// code deleted

The OP is doing simple box box collision, he/she really doesn't need anything more complicated.

[avansc]

have you considered using some better collision formulas?

Code: Select all

// code deleted

The OP is doing simple box box collision, he/she really doesn't need anything more complicated.

i understand that. but it does not leave much room for expandability.
what if in 2 months he/she wants to have collisions on shapes that aren't square, or perhaps squares that are rotated.
also bearing that he can still use his code for that, and just keep the code i provided if the need ever arise. deleting code
seems a bit harsh. but whatever.

[bugmenot]

i understand that. but it does not leave much room for expandability.
what if in 2 months he/she wants to have collisions on shapes that aren't square, or perhaps squares that are rotated.
also bearing that he can still use his code for that, and just keep the code i provided if the need ever arise. deleting code
seems a bit harsh. but whatever.

If the OP wants to do other collisions then fine, he can use the code you posted. The problem that the OP posted is to do with getting the box collision code working the way he wanted and your post didn't help the user solve the problem or at worst, confuse them further by throwing more code at them.

Now, if you posted a more flexible version of the box collision code, taking into account of 'soft' boundaries, that would be much different and gives the OP a start in his collision utility functions which if he needs to expand, he can do at a later stage.

[avansc]

i understand that. but it does not leave much room for expandability.
what if in 2 months he/she wants to have collisions on shapes that aren't square, or perhaps squares that are rotated.
also bearing that he can still use his code for that, and just keep the code i provided if the need ever arise. deleting code
seems a bit harsh. but whatever.

If the OP wants to do other collisions then fine, he can use the code you posted. The problem that the OP posted is to do with getting the box collision code working the way he wanted and your post didn't help the user solve the problem or at worst, confuse them further by throwing more code at them.

Now, if you posted a more flexible version of the box collision code, taking into account of 'soft' boundaries, that would be much different and gives the OP a start in his collision utility functions which if he needs to expand, he can do at a later stage.

okay.

OP, have you considered going about this the way that the originals did?
that is, reduce your code to just test for a point in a box. (which is easy and fast, and also makes it alot easier to do soft collisions)

what they did was this.

take the width/2 and hight/2 of the one box, and add it to the box that will be tested agains.
now is a very simple test to see if the point is in the box. and you can add and subtract a constant depending on if you wanted sov collisions.



bugmenot, does that still bug you?

[bugmenot]

bugmenot, does that still bug you?

Better. Remember you are dealing with beginners most of the time so solving problems that don't exist yet for them is more likely to hinder/confuse them unless you provide them with an explanation.

So posting the previous post first and then going "Oh, here are some other collision algorithms that you may find handy in the future' solves the original problem and provides a reference point to any potential problems/questions in the future.

[MarauderIIC]

Better. Remember you are dealing with beginners most of the time so solving problems that don't exist yet for them is more likely to hinder/confuse them unless you provide them with an explanation.

I agree here: usually posting something that's over somebody's head makes them go, "oh okay..." and then they solve it somewhere else on their own, which may or may not be the best way. I admit that I too am usually guilty of posting something too complicated :P

[exor674]

...

okay.

OP, have you considered going about this the way that the originals did?
that is, reduce your code to just test for a point in a box. (which is easy and fast, and also makes it alot easier to do soft collisions)

what they did was this.

take the width/2 and hight/2 of the one box, and add it to the box that will be tested agains.
now is a very simple test to see if the point is in the box. and you can add and subtract a constant depending on if you wanted sov collisions.

I think I got it!

Code: Select all

int pX = player.x() + 4;
int pY = player.y() + 4;
int sX = item.x() + 4;
int sY = item.y() + 4;

int collBoundry = 7; // 4 px from middle of player to edge, 3px from middle of to edge with 1px 'brush'
if ((pX > sX-collBoundry && pY > sY-collBoundry) && (pX < sX+collBoundry && pY < sY+collBoundry)) {
     // collide
}

I should really have getters for the width/height but not in the mood to add that right now.
Seems to work properly in all conditions I can test... seems like I need to get slightly further in on a corner but it's not like I have to go to a different POINT on the target now to have it count.

And for the record, I was considering doing something more complex, but the only thing I could think of was get the distance between the two middles, and the only way I know to get distance involved square roots -- and as this is a game for a handheld, I'm a little limited on cycles and I don't want to be doing a square root or three every frame. But box collision works perfectly for this case, so I really don't need anything more complex.

I actually am glad you suggested those better formulas so I can have them handy if I need to do collisions on something with a few more cycles to toss around.

[avansc]

hey, there is a way of getting around the sqrt problem.

you can just compart your distace before you sqrt it, to x*x of that value, that should be alot faster if i recall.
im sure bugmenot could say for sure.

Code: Select all

bool physics::particleInForce(particle *p, force *f)
{
	float dist = (f->x - p->x)*(f->x - p->x) + (f->y - p->y)*(f->y - p->y);
	if(dist < f->r*f->r)
		return true;
	return false;
}

[bugmenot]

As long as you are looking for a relative distance rather then exact, you can remove the sqrt by doing what avansc said which makes the algorithm much faster.

[eatcomics]

I admit that I too am usually guilty of posting something too complicated :P

nonsense marauder, I enjoy your scarce posts.