2D Collision for sprites

Started by
4 comments, last by cfrankb 13 years, 9 months ago
Well I've been working on my collision for my 2D game, so far I got bounding boxes to first check if the textures are even overlapping and then if they're it goes into my pixel collide function to check if any of the pixels are overlapping and if so then the 2 objects have collided. But my problem is it's not working properly the whole pixel side of my collision detection. And honestly at the moment I can't see where the problem is cause I've gone over it lots and rewritten it a few times and still can't workout why it's not working.

How I went about it is, when I first load my textures once I've got the texture data for my mask I then read ran a loop where if the pixel colour was bigger then 0x090909 (Red = 9, Blue = 9, Green = 9) then it meant it wasn't black (it could be a dark grey to white) so that is the info i want. Then I workout where about the pixel is in the image (pixels in the first starting from the left have x of 0, pixels in the first row starting from the bottom have y of 0) then I store that x and y value and increase the amount of pixels there are. Then when it's time to check if the pixels collide I have a loop that compares the textures offset + their pixels offset with what they collided with.

Ok I'm not sure if that is how I'm supposed to do pixel collision detection but I thought it should work, so I think there's something wrong with my code.


Here is the part that reads the textures data and creates the pixels offsets. (I know it says outline but that's because originally I was just going to make it store the images outline but then decided to make it all the image)
-(void) createOutline{	int Loop, LoopX, LoopY;	VECTOR2D *Temp;		for (outlineSize = 0, Loop = 0, LoopX = 0, LoopY = 0; Loop < (int)((texSize[0].width * texSize[0].height) * 3); Loop += 3)	{		if (LoopX == texSize[0].width)		{			LoopX = 0;			LoopY++;		}						if (*(unsigned int*)&texBytes[0][Loop] & 0x00ffffff > 592137)		{				Temp = (VECTOR2D*)realloc(outline, sizeof(VECTOR2D) * (outlineSize + 1));						if (Temp)			{				outline = Temp;				outline[outlineSize].x = (float)LoopX;				outline[outlineSize].y = (float)LoopY;				outlineSize++;			}		}		LoopX++;	}}



Here is the part that detects if the pixels have collided.
-(_Bool) pixelCollide: (VECTOR2D *)outline WithSize: (int)outlineSize AtPosition: (VECTOR2D)pos{	int Loop, Loop2;			switch (facing)	{		case Left:			for (Loop = 0; Loop < textureLeft[0].Sprite[CurrentTexture][0].outlineSize; Loop++)			{				for (Loop2 = 0; Loop2 < outlineSize; Loop2++)				{					if ((textureLeft[0].Sprite[CurrentTexture][0].outline[Loop].x + position.x == outline[Loop2].x + pos.x) && (textureLeft[0].Sprite[CurrentTexture][0].outline[Loop].y + position.y == outline[Loop2].y + pos.y))					{						m.x = outline[Loop2].x + pos.x;						m.y = outline[Loop2].y + pos.y;						return TRUE;					}				}			}			break;					case Up:			for (Loop = 0; Loop < textureUp[0].Sprite[CurrentTexture][0].outlineSize; Loop++)			{				for (Loop2 = 0; Loop2 < outlineSize; Loop2++)				{					if ((textureUp[0].Sprite[CurrentTexture][0].outline[Loop].x + position.x == outline[Loop2].x + pos.x) && (textureUp[0].Sprite[CurrentTexture][0].outline[Loop].y + position.y == outline[Loop2].y + pos.y))					{						m.x = outline[Loop2].x + pos.x;						m.y = outline[Loop2].y + pos.y;						return TRUE;					}				}			}			break;					case Right:			for (Loop = 0; Loop < textureRight[0].Sprite[CurrentTexture][0].outlineSize; Loop++)			{				for (Loop2 = 0; Loop2 < outlineSize; Loop2++)				{					if ((textureRight[0].Sprite[CurrentTexture][0].outline[Loop].x + position.x == outline[Loop2].x + pos.x) && (textureRight[0].Sprite[CurrentTexture][0].outline[Loop].y + position.y == outline[Loop2].y + pos.y))					{						m.x = outline[Loop2].x + pos.x;						m.y = outline[Loop2].y + pos.y;						return TRUE;					}				}			}			break;					case Down:			for (Loop = 0; Loop < textureDown[0].Sprite[CurrentTexture][0].outlineSize; Loop++)			{				for (Loop2 = 0; Loop2 < outlineSize; Loop2++)				{					if ((textureDown[0].Sprite[CurrentTexture][0].outline[Loop].x + position.x == outline[Loop2].x + pos.x) && (textureDown[0].Sprite[CurrentTexture][0].outline[Loop].y + position.y == outline[Loop2].y + pos.y))					{						m.x = outline[Loop2].x + pos.x;						m.y = outline[Loop2].y + pos.y;						return TRUE;					}				}			}			break;	}		return FALSE;}




Here is three examples of what's happening, for the test I'm using link texture which is the player and my badly drawn pot which is an object. The orange pixel is the pixel that has been hit. But as you can see in most cases that's wrong (well all in these examples), the player texture becomes green when it's collided too. So you can see sometimes it's saying there's a collision when there shouldn't be and sometimes and vice versa. What I've noticed is the bottom left and top right of the pot can be collided with outside of where it actually should be, and the bottom right and top left of the pot aren't colliding where they should be the player can move further inside the texture before it detects it. So yeh there's some clearly wrong going on here.





Hmm images not showing, I think I did it wrong so here's the links
Picture 1
Picture 2
Picture 3
Advertisement
That's a odd way to doing it. the concept is correct, but I'm not sure about how the textures are stored in memory. in my game, the images are on a surface, and I loop through them and check each pixel, and store them in a true bit-mask (1 bit each). What are you doing storing floats?

Anyway, here's how I go about the pixel-perfect intersection (realize this is old code, and it's using 16-bits for color, pulCopyPointer is the bit-mask):

(It doesn't show plus-signs (+) for some reason, so a large space means a plus is there :)

Here's creating the pixel definition:
        puwPointer = (UWORD *)ddsd1.lpSurface;	/* allocate the memory, zero, and copy it into it */	pulCopyPointer = (ULONG *)malloc(((ddsd1.dwHeight * ddsd1.dwWidth)/8) + 4);	memset((void *)pulCopyPointer, 0, ((ddsd1.dwHeight * ddsd1.dwWidth)/8) + 4);	for (ulY = 0; ulY < ddsd1.dwHeight; ulY++)	{		for (ulX = 0; ulX < ddsd1.dwWidth; ulX++)		{			// If it's not zero, set bit				if(*(puwPointer + ulX + (ulY * ddsd1.lPitch/2)))			{				SET(*(pulCopyPointer + (ulCount/32)), (ulCount%32));			}			ulCount++;		}	}


Here's checking the intersections:
BOOL Intersect(tScreenObject *pScreenObj1, tScreenObject *pScreenObj2){	BOOL bReturn = FALSE;	tSizeAndLoc Obj1, Obj2, RectObj1, RectObj2;	LONG lTempX, lTempY;	ULONG *pulPointer1, *pulPointer2;	ULONG ulCount1, ulCount2;	// 07/29/01 (Friday, damnit, what am I doing? Well, not drinking obviously!)	// Update to decide square or circle bounding box	// 09/20/01 Updated to check the actual bitmaps (You knew you'd have to damnit!)	Obj1 = pScreenObj1->SizeAndLoc;	Obj2 = pScreenObj2->SizeAndLoc;	// Check rectangles 1st	// Whew!	if ((Obj1.lLocX + (LONG)Obj1.ulSizeX >= Obj2.lLocX) && (Obj1.lLocX <= Obj2.lLocX + (LONG)Obj2.ulSizeX))		if ((Obj1.lLocY + (LONG)Obj1.ulSizeY >= Obj2.lLocY) && (Obj1.lLocY <= Obj2.lLocY + (LONG)Obj2.ulSizeY))		{			// 1st, check if it's a bomb (ugly, I know!)			if ((((tBullet *)pScreenObj1)->ulType == BOMB) ||				(((tBullet *)pScreenObj2)->ulType == BOMB))			{				// just return!				return (TRUE);			}			// OK, rectangles intersect, so check bitmaps			// find rectangles we should check for each object			// check each side versus other side			if (Obj1.lLocX > Obj2.lLocX)			{				RectObj1.lLocX = 0;				RectObj2.lLocX = Obj1.lLocX - Obj2.lLocX;			}			else			{				RectObj2.lLocX = 0;				RectObj1.lLocX = Obj2.lLocX - Obj1.lLocX;			}			if (GET_RIGHT(Obj1) > GET_RIGHT(Obj2))			{				RectObj1.ulSizeX = GET_RIGHT(Obj2) - MAX(Obj1.lLocX, Obj2.lLocX);				RectObj2.ulSizeX = RectObj1.ulSizeX;			}			else			{				RectObj2.ulSizeX = GET_RIGHT(Obj1) - MAX(Obj1.lLocX, Obj2.lLocX);				RectObj1.ulSizeX = RectObj2.ulSizeX;			}			if (Obj1.lLocY > Obj2.lLocY)			{				RectObj1.lLocY = 0;				RectObj2.lLocY = Obj1.lLocY - Obj2.lLocY;			}			else			{				RectObj2.lLocY = 0;				RectObj1.lLocY = Obj2.lLocY - Obj1.lLocY;			}			if (GET_BOTTOM(Obj1) > GET_BOTTOM(Obj2))			{				RectObj1.ulSizeY = GET_BOTTOM(Obj2) - MAX(Obj1.lLocY, Obj2.lLocY);				RectObj2.ulSizeY = RectObj1.ulSizeY;			}			else			{				RectObj2.ulSizeY = GET_BOTTOM(Obj1) - MAX(Obj1.lLocY, Obj2.lLocY);				RectObj1.ulSizeY = RectObj2.ulSizeY;			}						pulPointer1 = GetObjectDefinition(pScreenObj1->pucBuffer);			pulPointer2 = GetObjectDefinition(pScreenObj2->pucBuffer);			// now loop through one of em, checking the color			for (lTempY = 0; lTempY < (LONG)RectObj1.ulSizeY; lTempY++)			{				// increase count to next line				ulCount1 = (Obj1.ulSizeX * (RectObj1.lLocY + lTempY)) + RectObj1.lLocX;				ulCount2 = (Obj2.ulSizeX * (RectObj2.lLocY + lTempY)) + RectObj2.lLocX;				for (lTempX = 0; lTempX < (LONG)RectObj1.ulSizeX; lTempX++)				{					// check for not 0					if (IS_SET(*(pulPointer1 + (ulCount1/32)), (ulCount1%32)) &&						IS_SET(*(pulPointer2 + (ulCount2/32)), (ulCount2%32)))					{						bReturn = TRUE;						break;					}					ulCount1++;					ulCount2++;				}				if (bReturn)				{					break;				}			}		}	return (bReturn);}

My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

I like BeerNutts's idea of pixel collision detection but I would rather use either a 4x4 or 8x8 pixels mapping instead.

say your screen is 800 x 800 pixels. Using a 8x8 grid you would have 100 x 100 position at a byte each (~10k of memory). You could assign each position matching the player a value of 1. A bullet a value of 2. etc. As the sprites move, you would update map according.

Frank B.

--
LGCK Builder: Free Game Construction Kit:
http://cfrankb.com/lgck

Here's two links about using GPU for pixel perfect collision.
- Iliak -
[ ArcEngine: An open source .Net gaming framework ]
[ Dungeon Eye: An open source remake of Eye of the Beholder II ]
Thanks for the example BeerNutts I'll give that a try.

If I were to use a grid like what cfrankb suggested, would constantly having to update (well updating it only when needed) have a noticeable affect on performance though?

I've looked into occlusion queries to detect collision a few weeks ago, but because my goal is to make this game for the iPhone (at the moment I'm making it just for computer and when I'm finished I'll port it over) so I wasn't sure if it's supported or not. Also when I've seen it implemented (watched a few youtube videos) it seemed quite slow, and much to slow for what I want.


EDIT: I worked out what was wrong, can't believe I didn't notice it before I forgot to put brackets around the AND part of the equation in the if statement that checks if the colour is not black/very close too.

[Edited by - bottomy on July 10, 2010 10:19:38 PM]
The effect would be negligible. I tested the theory with hundreds of sprites on a pentium-133 some ten years with no visible performance penalty. Todays machines are way faster so I expect that there would be no way to overload the game cycle short of dealing with 1000s of updates a second.

--
LGCK Builder: Free Game Construction Kit:
http://cfrankb.com/lgck

This topic is closed to new replies.

Advertisement