🔒 Locked

2D collision checking query

Started by Ging Nov 23, 2003 at 6:59 PM 1 replies 750+ views

Original Post

Nov 23, 2003 at 6:59 PM

I''ve been hunting around for a decent collision algorithm for something I''m working on in my spare time away from uni. It''s heading towards a basic predator / prey simulator. I''ve got a 640 x 480 window with 400 particles bouncing around with random movement. I''ve got them bouncing off the edges (easy enough bit of trig to reverse their angle when they hit a certain x / y co-ord) but I want them to be able to tell when they''ve hit each other, so I can start to simulate the predatorial aspect of the design. The program solely uses SDL for drawing and input. The particles are 4 x 4 pixel squares. red for prey, green for predators. My current thinking is to have a grid of 16 x 16 squares set up, each holding a vector of the current contents. So I can just check the grid squares with predators in for collision rather than checking every single particle each frame. (I tried that when I first started, it managed about 5 hits in 2 minutes of run time!) I''ve only got a the psuedo code written up for the grid system, I would just like to know if anyone could think of a better way of reducing the overhead on the collision checking before I implement it! Thanks for any help, Ging

logic monkey

Nov 23, 2003 at 10:32 PM

I think it might be faster just to have an array of predators and one of prey and for each predator check if any of the prey are colliding.
I''m not sure of the overhead of checking grid like you want to do but it feel like it would be more expensive. It sounds like you would have to figure out who is in each square, what type of particle they are and then find if they collide.

Seems like extra work but I may be overlooking something.

SelethD

Nov 24, 2003 at 1:02 AM

Im not sure if this would be too much overhead, it invoves checking the coordinates of where an object will be when it moves next.

Each object is 4x4, so bread you screen 640x480 into 4x4 squares
it would be 160 x 120 use an array

int collisonGrid[160][120];

these are the steps to follow when drawing each object

//start object drawing loop
step 1
erase object number from collision grid by placing a -1 at location object.x>>2, object.y>>2
collisionGrid[object.x>>2][object.y>>2] = (-1);

step 2
set objects new coordinates depending on vector, and speed, whatever

step 3
check collison grid at objects new coordinates
if ((collisionGrid[object.x>>2][object.y>>2] != (-1))
//collided with another object
get the identity of the object
objecthit = collisionGrid[object.x>>2][object.y>>2];

step 4
you can work the collision when you find it(for example, change the direction of current object, and objecthit) or store in a list for processing after all object have moved

if a hit did happen, put current object back to coordinates as was before translated in step 2
so that no two objects are ever at the same spot on the grid

step 5
put objects id back on collision grid
collisionGrid[object.x>>2][object.y>>2] = objectnumber

//end object drawing loop

Hope this helps, if not maybe it will lead you in a good direction.
Sorry im not too good at making more sense.

SelethD

Topic Locked

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