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

Help Optimizing 2D Collision Algorithm

Started by justin12343 Sep 22, 2010 at 3:25 PM 5 replies 2.3k views
Original Post
justin12343
justin12343
I have a working 2D collision method, but it is extremely slow. I works by using a collision mask, not by using 1s and 0s, but by using a xy coordinate in a vector. Then when I check for collision, I check the bounding rects first, if they collide then I check on pixel level.

collision.h
[source lang ="cpp"]#ifndef _COLLISION_#define _COLLISION_#include "gfx_dx9.h"#include <vector>using namespace std;class object;class objectManager;struct bit{	bit( float bx, float by):x(bx),y(by){}	float x, y;};struct mask{	vector<bit*> bits;	RECT bbox;	unsigned long *pBits;}; void setObjectManager( objectManager *om);mask *create_mask( sprite *index);bool collision_check( object *a, float x, float y);bool collision_check_rect( RECT a, RECT b);#endif


collision.cpp
[source = "cpp"]#include "collision.h"#include "object.h"#include "objectManager.h"objectManager *objMan;void setObjectManager( objectManager *om){	objMan = om;}mask *create_mask( sprite *index){	mask *tmp = new mask;	tmp->bbox = index->bbox;	D3DLOCKED_RECT rect;	index->texture->LockRect( 0, ▭, NULL, D3DLOCK_READONLY);	for ( DWORD y = 0; y < index->info.Height; ++y)	{		for ( DWORD x = 0; x < index->info.Width; ++x)		{									DWORD* pBits = (DWORD*)((BYTE*)rect.pBits + y*rect.Pitch);						DWORD lastPixel = pBits[x-1];			DWORD pixel = pBits[x];			DWORD nextPixel = pBits[x+1];			if( pixel & 0xff000000 && ( ( y == 0 || lastPixel == 0x00) || ( y == index->info.Height || nextPixel == 0x00)) )			{				tmp->bits.push_back( new bit( x, y));				//tmp->pBits[y*index->bbox.right + x] = 1;			}		}	}		index->texture->UnlockRect( NULL);		return tmp;}bool collision_check( object *a, float x, float y){	mask *mask_a = a->collsion_mask;	object *b;	int line = 0;	while (line < mask_a->bbox.bottom)	{		for ( int px = 0; px <= mask_a->bbox.right; ++px)		{					if (px >= mask_a->bbox.right)			{				line+=1;			}			b = objMan->getObjectAt( a, x+px, y+line);			if (b != NULL){	break;}		}		if (b != NULL){break;}	}	if (b == NULL)	{		return false;	}	mask *mask_b = b->collsion_mask;	vector<bit*> bits_a = mask_a->bits;	vector<bit*> bits_b = mask_b->bits; 	float x1, x2, y1, y2;	x1 = floor(a->x);	y1 = floor(a->y);	x2 = floor(b->x);	y2 = floor(b->y);	RECT bbox_a = { (LONG)x1, (LONG)y1, (LONG)x+mask_a->bbox.right, (LONG)y+mask_a->bbox.bottom };	RECT bbox_b = { (LONG)x2, (LONG)y2, (LONG)x2+mask_b->bbox.right, (LONG)y2+mask_b->bbox.bottom };	bool result = false;	if (collision_check_rect( bbox_a, bbox_b))	{		for ( UINT a = 0; a < mask_a->bits.size(); ++a)			for ( UINT b = 0; b < mask_b->bits.size(); ++b)		{				float bx1, bx2, by1, by2;				bx1 = bits_a[a]->x+floor(x1);				by1 = bits_a[a]->y+floor(y1);				bx2 = bits_b->x+floor(x2);				by2 = bits_b->y+floor(y2);				if ( (bx1 == bx2) && (by1 == by2))				{					result = true;					break;				}		}			}	return result;}bool collision_check_rect( RECT a, RECT b){	bool result = false;	int x1, x2, y1, y2, w1, w2, h1, h2;	x1 = a.left;	y1 = a.top;	w1 = a.right;	h1 = a.bottom;	x2 = b.left;	y2 = b.top;	w2 = b.right;	h2 = b.bottom;	if (		(w1 > x2 && w2 > w1) ||		(x1 < w2 && x2 < x1) ||		(x1 < x2 && w1 < w2) ||		(h1 > y2 && h2 > h1) ||		(y1 < h2 && y2 <y1)		)	{		result = true;	}	return result;}


I'm not storing all the pixels in the mask, instead I got the idea of storing a outline of the image to speed it up a bit.
teqqan
teqqan
Why would you need that accurate collision detection?
I would say, use Seperated by axis theorem together with som simple initial collision detection (like circles).
justin12343
justin12343
I'm making a sonic fan game, it has a lot of slopes( not all are just squares and triangles, EX: loops and half pipes). I don't really want to do it another way unless I absolutely have to. My way here is too slow, does anyone know how to do it with the 1s and 0s and using the << , >>, & operators and such. I can't seem to find a tutorial that explains it well ( can't find one here neither).
justin12343
justin12343
I'm making a sonic fan game, it has a lot of slopes( not all are just squares and triangles, EX: loops and half pipes). I don't really want to do it another way unless I absolutely have to. My way here is too slow, does anyone know how to do it with the 1s and 0s and using the << , >>, & operators and such. I can't seem to find a tutorial that explains it well ( can't find one here neither).
Drigovas
Drigovas
So before going into how to do it, perhaps you should consider a hypothetical, to make sure what you're going after is actually what you want.

Consider the situation where there is a change in ground level of two pixels vertically. Something like this:
               x               xxxxxxxxxxxxxxxxxxxxxxxxx
Your character goes to run over it. How do they make it over? To put it in perspective, two pixels is likely too small a feature for many people to see against a busy background, and the character is likely 100+ pixels tall. And on that note, how do you represent a 'slope', or a 'triangle' in a per-pixel fashion that allows your collision detection scheme to let a player run up and down the slopes? The point is, when a player encounters a pixel-tall collision, should they climb over it, or should they stop just as if they had encountered a 100-pixel tall collision. Also, if your player moves at many pixels per frame [as is completely realistic for a sonic game], should the player be able to run straight through skinny obstructions [being completely on one side in one frame, and completely on the other side in the next frame].

These points are why games typically use geometric shapes instead of pixels. If the character is represented as an ellipsoid, the player can slide up slopes because simple dynamics calculations would allow that.

In terms of how to do per-pixel checking more efficiently, perhaps organizing your pixels into a quad tree or some such would allow you to more rapidly cull away pixel regions that will result in no collision detected. That way, you perform fewer checks.
justin12343
justin12343
Well, I don't want to get into programming quad trees, at least not right now. I came up with a idea, maybe I could calculate how much object A has collided into object B and check by using the difference in their positions. That will probably reduce how much of the masks I check at once.
WarMuuh
WarMuuh
the method you mentioned (with the 1s and 0s) is relatively easy to implement, though it is used in tilebased games...
you have tiles of length x, preferably 32, because that amount of bits can be hold of an integer (where 1s = pixels)
so a row = 1 integer...
now, you wanna test tile vs player (player is another tile)
you have to remind the offsets of the player relative to the tile..
y-offset = integer of player, you have to begin with
x-offset = somewhat like the shift-offset of every integer
then, if (ti & (pi << y-offset))>1 => collision (ti = tile-integer, pi = player-integer)
if not, test next row

this was just an example, for the right shift and y-offset, draw a picture ;)

Topic Locked

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

Sign in to reply to this topic.