Archived

This topic is now archived and is closed to further replies.

DVazanias

collision detection method

Recommended Posts

I am aiming to set up a virtual grid of sections over my world so that i can cut down on the number of objects checked during collision detection. Therefore i only have to check the objects in the same section as the player''s object. However i am struggling with the code to set this up. I tried making a cSection class and a cGrid class. Each section keeps a list of all objects inside it and the grid keeps track of the positions of all the sections So there is a list of sections in the grid and a list of objects in each section. First of all does that sound like a goo way of implementing it? Second how do i get the objects to tell the sections which section it should be in? Thirdly the reason for doing it this way is so that i don''t have to loop through every object to check which section it is in and that i only have to look at the section data - i don''t think i am managing this though Please could someone provide me with a code sample on how to do this. I am struggling. Also is using a vector a good way of doing a linked list for this kind of thing? (e.g. tracking the objects in a section is done through a vectorObjList

Share this post


Link to post
Share on other sites
The way I did it was to create a grid of spaces like you, but to only consider changing the grid of an object when it moves. You can vert simply set up a list of if..else statements to check the direction of movement and then test the objects position against the next grid plane/box in that direction.

Share this post


Link to post
Share on other sites
umm....so say if they move right check the section they are in and the one that is right of them. How would i set up the code to handle knowing which grid section is to the right?

If i give each section a id number that acts as reference then if i know that you''re in section 2 then section 3 is to the right. And i could check that if the width of the grid is 5 and 5 high for example, i could do a divide by 5 on each section and if it doesn''t equal 1 it is not the last section. Therefore i could do this:

if(MoveRight)
{
//check if we are in last section
//if we are not then update position
if(CurrentSecionID/GridWidth != 1)
{
UpdatePos(Sect[CurrentSectionID+1],Obj);
}
}

and then updatepos would do this:

void UpdatePos(cSection &theSection, cObject Obj)
{
if((Obj->x > theSection->left) &&
(Obj->x < theSection->right) )
//then check y values

//if it satisfies all the if statements then the object
//has moved to a new section so update section info

theSection->ObjList.push_back(Obj);

//and remove from old section
}

Is that what you mean? I think that would work, hopefully you can follow my code/pseudo code. So to summarise i check section i am in, check next section, if i have moved and it isnt the last section check that after moving if i am now in the next section, if so update object list for that section, if i am not dont update.

Share this post


Link to post
Share on other sites
Yeah that about sums it up. One thing to note though - objects are rarely one pixel in size...

...Once you make the move, and find that it has moved into the next grid, compare how far into the grid section it has moved, if this distance is greater than the objects radius, then it is completely in the new grid. If it''s smaller than the radius, it''s in both grid squares. You''ll need to keep an ''oldGrid'' variable to track situations where it enters one grid square and remains in the previous one still (overlapping both). then you can set the oldGrid variable to the new grid square ID ONLY when it is entirely within the new grid square. Might need to use an array of oldGrid variables if you''re working in 3d.

If you are working in 3d then this means it is possible for an object to exist in up to 8 grid squares. Having never tried a grid square list of objects idea, (my current game being small enough to allow me to use a loop through all the enemies) I''m not sure how fast it will run. Although faster than doing collision checks for each enemy, I''m a bit concerned that if you make your grid size too small, the objects will be moving grid squares all the time, and the list altering of each grid square will begin to slow it down. Just something to keep an eye on....

Share this post


Link to post
Share on other sites