# What algorithm and data structure for collision detection?

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

## Recommended Posts

Hello, I have a very simple program that has a bunch of objects with X, Y coordinates. They have a couple of other features but lets simplify and just say they have a position, gender (male or female) and can be married or single. Anyway, i am creating my objects and storing them in a list with C#. Its just the list that comes with the .Net framework. What i need to do is go through the list, and see if any objects are within 5 units of each other then test to see if they are single and of opposite sex. I just had a for loop within a for loop that compares each object with every other object in the list. As you can imagine, it gets really slow when the lists get bigger as the algorithm is O(n2). I cant for the life of me think how to make it faster than O(n2). The only thing i can come up with is to make a list of single males and a list of single females then compare each object in the smallers lists with each other. However, this is still O(n2) and just reduces list sizes which enables me to get a larger population but still slows down just a bit later. Does anyone have any ideas on how i can store my objects for fast comparison each cycle? Any ideas would be greatly appreciated. Thanks :)

##### Share on other sites
This is my whole 2d collision detection system
struct sEntityPos{	sEntityPos()	{		x = 0;		y = 0;	}	sEntityPos(float a,float b)	{		x = a;		y = b;	}	float x,y;};enum eEntityDirection{	E_UP,	E_DOWN,	E_LEFT,	E_RIGHT,	E_NONE};bool CScreen::CanMove(sEntityPos Pos,eEntityDirection Direction){	if(Direction == E_LEFT)Pos.x -= 4;	else if(Direction == E_RIGHT)Pos.x += 4;	else if(Direction == E_UP)Pos.y += 4;	else if(Direction == E_DOWN)Pos.y -= 4;	int PlayerColX1 = (int)Pos.x/32;	int PlayerColY1 = (int)(Pos.y-44)/32;	int PlayerColX2 = (int)(Pos.x+28)/32;	int PlayerColY2 = (int)((Pos.y+28)-44)/32;	switch(Direction)	{	case E_LEFT:		if(m_Screens[m_iActiveScreen].Tiles[PlayerColX1][PlayerColY1].GetBaseEntityType() == E_COLLIDABLE && m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY1].GetEntityPos().x)		{			return false;		}		if(m_Screens[m_iActiveScreen].Tiles[PlayerColX1][PlayerColY2].GetBaseEntityType() == E_COLLIDABLE)		{			return false;		}		break;	case E_RIGHT:		if(m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY1].GetBaseEntityType() == E_COLLIDABLE)		{			return false;		}		if(m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY2].GetBaseEntityType() == E_COLLIDABLE)		{			return false;		}		break;	case E_DOWN:		if(Pos.x < m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY1].GetEntityPos().x && m_Screens[m_iActiveScreen].Tiles[PlayerColX1][PlayerColY1].GetBaseEntityType() == E_COLLIDABLE && m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY1].GetEntityPos().x && m_Screens[m_iActiveScreen].Tiles[PlayerColX1][PlayerColY1].IsTransparent() == false)		{			return false;		}		else		{			if(m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY1].GetBaseEntityType() == E_COLLIDABLE && m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY1].GetEntityPos().x && m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY1].IsTransparent() == false)			{				return false;			}		}		break;	case E_UP:		if(m_Screens[m_iActiveScreen].Tiles[PlayerColX1][PlayerColY2].GetBaseEntityType() == E_COLLIDABLE)		{			return false;		}		if(m_Screens[m_iActiveScreen].Tiles[PlayerColX2][PlayerColY2].GetBaseEntityType() == E_COLLIDABLE)		{			return false;		}		break;	};	return true;}

Hope that helps

##### Share on other sites
Quote:
 Does anyone have any ideas on how i can store my objects for fast comparison each cycle?

1. 1
2. 2
3. 3
4. 4
Rutin
18
5. 5

• 13
• 14
• 9
• 9
• 9
• ### Forum Statistics

• Total Topics
632927
• Total Posts
3009247
• ### Who's Online (See full list)

There are no registered users currently online

×