Collision Detection in Frames

[LostTime77]

Hello everybody! I'm not new to the forums, I look at them often, however I post very little. I have a question on simple collision detection between two rectangles. I currently do not care about how one can test for a collision, I simply care about the redrawing aspect of two objects projected to collide.


So I have two rectangles, on a collision course. Their height, width , and y positions are exactly the same, the only thing that changes is their x position. I define the change in position for the left rectangle as 3 pixels (arbitrary number) added to x every frame of the animation. The left rectangle moves along to the right while the right rectangle is stationary (for the purpose of the logic, the right rectangle doesn't need to be moving). I know how basic collision detections works. Say we have a point defined by x + 50, which pertains to the top left corner of the left rectangle plus 50 for the width of that same rectangle. So i can write something such as if(x + 50 == top left corner of stationary rectangle). This is all fine and dandy BUT what happens if the top left corner of my rectangle is 51 pixels away from the top left corner of my right rectangle? so the change in x for the collision to occur would have to be 1 pixel for the test to check true. However my change in x is defined as 3 pixels... so on the next frame my top left corner of the left rectangle is 48 pixels away from the top right corner of the right rectangle. The collision test failed and now since my rectangle is 50 pixels wide, it is now penetrating the right rectangle and just decides to keep on moving every frame. I know simple solutions can be made such as if(x + 50 >= top left corner of right rect), blah blah. These are solutions I do not want. I want pixel perfect collision AND I also want the drawing of the rectangle to be fluent through the animation.


What I have tried so far that has seen the most success is adding my velocity vector (3) to x + 50 and then seeing if that pokes through the top left corner of the right rectangle (if(x + 50 + dx > top left corner of right rect)), THEN iterating through all the possible values of dx for(i = 0; i < dx; i++) --> if(x + 50 + i == top left corner right rect) then the change in x for that frame is equal to i. This makes it so that the left box arrives at the exact position of the right rectangle for the next frame and regular detection prevails. However the problem with this is that it changes the speed of my velocity vector for that frame, which is an incorrect solution.
I know I am missing something and have been doing a lot of reading online about collision detection and animation, but those articles seem to fail to provide me with the information I seek. I do not care to know how collisions are detected, but rather how animations are redrawn so pixel perfect detection can be made. I will let the actual detecting be a surprise when I actually care to learn those advanced methods.


PS. my frame rate is 60 fps. I have experimented with changing frame rates in accordance to the velocity vectors. However this is also to no avail. Eventually, this all will be integrated into a simple gravity, collision detection physics engine over the long haul. If such solutions involve calculus or physics equations (obviously) I would prefer them.


I hope I have explained my problem well enough.

 

[Markbnj]

You can't have pixel-perfect collision detection if you don't test every pixel . That doesn't mean you have to test one pixel per frame, but as you found out an algorithm that relies on two vertices of the colliding objects inhabiting the same point at the time the test is performed is going to fail for some rate of movement greater than 1 pixel per frame.

I'm no expert on collision detection, but I can tell you there's been a _ton_ of stuff written about it over the last twenty years. If I were just grabbing stuff off the top shelf of my head I would say look at either path projection (over the three pixels of movement in your example the point of the vertice in object 1 traversed a line; did that line intersect part of object 2?), or bounds testing (is any point of object 1 inside object 2 right now?).

 

[AdaptiveBrainMatter]

I'm not sure what you're trying to accomplish here, but for your overall goal, I would suggest using a velocity measured in pixels/second, rather than what appears to be pixels/frame. Also, it seems to me that you want to have fairly accurate collision results, this will require a pixel perfect collision detection algorithm, of which there are plenty for box-box collisions. If you've already got a good collision detection algorithm, it appears to me that you've already got everything you need to complete your project.

 

[LostTime77]

Thanks for the responses.

See, the problem I am running into is that im using a timer to adjust the frame rate. It is java so I am creating the timer then using the actionPerformed function to call a repaint and to also update the screen position for each frame. If I use pixels per second, say 497 pixels per second, I have to convert to pixels / millisecond. So 497/1000 is .5 pixels per millisecond, so then multiply by my frame rate value (16ms for 60 frames or so/sec) and I get 7.9 something. There is not a problem with me finding the next position for the frame because I can make a variable int and have it round. Now, since the screen automatically updates by (7) pixels per frame, my block does not pass through all the intermediate integer values up to that 7, so how in the world can you detect an accurate collision if my collision routine is continuous and outside this actionPerformed function? Ok so I implement the collision detection in the actionPerformed so it gets checked after or before it adds 7 to my position. My routine has now determined that 7 pixels (the line that the block would traverse) pokes through the edge of my second block. Ok now what? I still need the block to move 5 pixels since its 5 pixels away from the second block but my update is 7 pixels/frame. What now? 5 pixels away, no problem! I just make the block move 5 pixels on the next frame. This in itself present a problem because my block is now not moving my specified speed but a different speed for that frame. I'm wondering, is this the way to do it?

 

[AdaptiveBrainMatter]

Ok, I think I see what you're doing now. You're updating the position of the box on the next frame. I don't know why you do it that way, seems to me it adds extra work. But yeah, what you've got is basically the way you've got to do it. Using your example where Box A moves 7 pixels/frame and Box B is stationary, so Box A hits Box B in 5 pixels, moving Box A just 5 pixels would be the proper response, wouldn't it? I mean, in reality, if I run at 6 feet per second towards a brick wall, with the wall only 3 feet away, in merely half a second, I would hit that wall, however, if the smallest time slice is 1 second, you have to say that for that last second, I was moving at 3 feet per second. To achieve acceptably smooth animation, you would usually just pick a really small time slice, one that's too small for humans to notice. After all, if you slow video down, what appears smooth at full speed will appear choppy. An example of this would be those high-speed video's of bullets going through apples or other fruit.

 

[Atheus]

Originally posted by: LostTime77
Now, since the screen automatically updates by (7) pixels per frame, my block does not pass through all the intermediate integer values up to that 7, so how in the world can you detect an accurate collision if my collision routine is continuous and outside this actionPerformed function?

If I remember right - you check for collisions this 'frame', then if there are any, go back in time to find the first one. You sort of split/integrate the time interval and run the algorithm until you close in on a value. Then you resolve that collision and use the trajectory of the affected objects in later calculation.

This sounds processor intesive because it is.

BTW this:

http://www.harveycartel.org/me...torials/tutorialA.html (Separating Axis Theorem)

is the algorithm I used when I wrote my java game engine. That page doesn't give you everything you need but there's a good paper around with all the math layed out.

 

[LostTime77]

Ah yes, SAT. That has come up many times in my reading, and that particular article. This information is good, and eventually I will implement the SAT to detect collisions, however I just needed to get it straight how collision responses worked in reference to animation. Basically the method I had was on track, see if the velocity vector pokes through the second block, if it does then find how far it pokes through, then set the current position change to be this value. I can see this working for a bitmask pixel perfect detection system and also SAT. Basically project the bitmask, if there's a collision find how far then on the next frame move the object that 'how far' length.

Thanks for the input guys.

 

[LostTime77]

Ok so... after some experimenting and some work with threads I think I may have come up with a solution that I'm comfortable with based on the previous posts. Basically, I use a thread and have that thread sleep an amount of time based on my fps value. Secondly on each frame we do a collision detection. We check if the velocity vector pokes through the second object, and if it does figure out how far and how much the first object needs to be to collide into the second object. After, we convert this distance value into a relative frame rate value, maintaining the ratio of desired frames. So if my dx is 7 pixels / frame, and the distance the object needs to travel is 5 pixels, I do distance (5) / 7 pixels per frame all multiplied by my fps value (16ms for 60fps) and get the time in milliseconds that it will take the object to collide. I then set the thread to sleep this amount of time, repaint using the new distance, and viola, the block collides in the exact position I want it to, and it maintains the speed that it was going at.

I really appreciate all the comments that helped me come to this realization. Thanks guys