Sign in to follow this  

What algorithm and data structure for collision detection?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this