What algorithm and data structure for collision detection?
Author
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 :)
This is my whole 2d collision detection system
Hope that helps
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
