PDA

View Full Version : Help: Collision detection, I don't know how to set it up




slooksterPSV
Jun 3, 2006, 06:30 PM
Ok I'm totally lost with collision detection, I'm absolutely an idiot when it comes to it, if anyone knows anything about it or wants to see the code I'm trying to make work, let me know, I cannot figure out how to do collision detection.



Eraserhead
Jun 6, 2006, 06:20 AM
Please give the code and the language and i'm sure people can help...

Palad1
Jun 6, 2006, 07:18 AM
Are you working in 2D or 3D?

in 2d, a fairly simple solution used to detect collisions in the viewing area is to keep a second screen buffer where each pixel value is an index of the object.

So you have
1/ the screen buffer filled with rgb values
2/ the collision buffer filled with entities ID

Cheers,
Palad1

pdpfilms
Jun 6, 2006, 10:12 AM
I must say, I'm very pleased MacRumors now has a specific Programming section. Because I have absolutely no idea what you're talking about.

bobber205
Jun 6, 2006, 10:44 AM
Are you working in 2D or 3D?

in 2d, a fairly simple solution used to detect collisions in the viewing area is to keep a second screen buffer where each pixel value is an index of the object.

So you have
1/ the screen buffer filled with rgb values
2/ the collision buffer filled with entities ID

Cheers,
Palad1

I've done that before and that's definitely the way to go.
Some languages that have built in collision detection do it that way too (REALbasic maybe?)

SC68Cal
Jun 6, 2006, 11:08 AM
I must say, I'm very pleased MacRumors now has a specific Programming section. Because I have absolutely no idea what you're talking about.

the best way to describe collision detection is in one of the programs I made for a class in VB.net.

basically you had a character, and when you clicked on an enemy, a fireball was created and would home in on the enemy, collision detection was used to determine when the fireball actually "hit" the enemy and would cause the enemy to dissapear.

slooksterPSV
Jun 6, 2006, 11:32 AM
Since I don't have it figured out, I'm using C++ and SDL as the SDK/API. I was able to use source code from another person with their permission on how to detect collisions. But I still need to learn how to do it.

savar
Jun 6, 2006, 11:33 AM
Ok I'm totally lost with collision detection, I'm absolutely an idiot when it comes to it, if anyone knows anything about it or wants to see the code I'm trying to make work, let me know, I cannot figure out how to do collision detection.

Hey, you're the guy writing the RPG, right? There's two basic approaches: approximate and exact.

You can do approximate collision detection by drawing shapes (circles, squares, abitrary polygons, etc.) around your sprites, and then using geometry in pair-wise comparisons to see which ones overlap. (Circle is the easiest by the way, because it takes only one comparison: distance(p1,p2) < radius1 + radius2.) This approach is good only for a few sprites, because by taking each pair the collision function runs in (approximately) exponential time. But if you only have a few sprites (20-40 maybe), this is pretty doable.

The other way is to do pixel-level collision detection, which provides exact collision detection. Like somebody else said, you can keep a separate bitmap (aka occupancy map) where you record what parts of the screen are already full. You could also do collision detection in your drawing routine, if you draw the sprites in a separate layer and then composite them onto the background.

Fukui
Jun 6, 2006, 11:38 AM
Since I don't have it figured out, I'm using C++ and SDL as the SDK/API. I was able to use source code from another person with their permission on how to detect collisions. But I still need to learn how to do it.
List of rectangles , cycle through the list of rectangles, if any rectangle is within/touching another, its collided... I did a primitive one using NSContainsRect() and NSIntersectsRect() and other simple rectangle methods. The more tricky part is "what to do when they do collide."

Its not too hard.

slooksterPSV
Jun 6, 2006, 11:52 AM
I think I get it!
if the point x of the character greater than or equal to the point x of the object and (actually XAND) if the point x of the character is less than or equal to the point x + the width - 1 of the object of the object then:

if ((player.x >= object.x) && (player.x <= object.x + object.w - 1))
{
...


Then check the y values the very same way.

if ( (player.y >= object.y) && (player.y <= object.y + object.h - 1) )
{
return true;
}
}
return false;

Otherwise there was no collision.

EDIT: But there are multiple collisions you have to check so that's not the full way.

slooksterPSV
Jun 6, 2006, 11:56 AM
Here's the code that I was allowed to use from Aaron Cox:
I removed it just in case he doesn't want it posted.

MarkCollette
Jun 8, 2006, 04:49 PM
A true collision happens when to objects share the same space at the same time. The calculations get more complex, the more dimensions you're modelling. Some suggestions here are effectively optimisations on that.

For the object buffer (each pixel point has a pointer to the object), if they are drawn on the same space they have collided. But take care, objects can collide without ever visually overlapping. Take for example two objects on the X axis, moving towards each other rapidly. Depending on how rapidly you render those objects, they may not be drawn while they overlap.

For the rectangle clipping, it's actually only an early-out calculation. That is to say, two objects have not collided if their bounding box (or sphere) have not collided. But just because the boxes have collided doesn't mean the objects have, if they're shaped in any way differently than a box :) For example, you might make a sprite, and use transparency for the parts of the image that do not correspond to the object. Then one object touching that transparent part does not constitute a collision.

Ok, so we'll check collisions in the physics modelling thread, and not the rendering thread, and we'll use the proper math to calculate a true collision, but even then that timing issue still remains, depending on the granularity of our timeslices. It's actually the same problem as before. The two objects are moving together rapidly, A goes at 50 meters per second east and B goes at 50 meters per second west. Even if each occupies 1 meter of space, that's 50 timeslices per second that we have to check for a collision. And then we have the problem that no object can go faster than the CPU can crunch collisions.

The solution is to calculate collisions along a swathe (my term). That is, when A is going 50m/s East, A is cutting a swathe between two points, and we have to see if B's swathe collides with that. And then do collision detection over that time interval.


Here's A, B at time 0:
A B

time 1:
A B

time 2:
A B

time 3:
A B

time 4:
B A


So, the collision happenned inbetween timeslices 3 and 4. In all the other timeslices, A's swathe and B's swathe did not have a collision potential. One can accomplish this by using a bounding box that encompasses not just the object, but every space it will hold in the next timeslice.


Here's A, B at time 0:
A--| |--B

time 1:
A--| |--B

time 2:
A--| |--B

time 3:
A|-|B

time 4:
|--B A--|


Things get very complicated when calculating exactly what touches first. Most games just have the objects bounce away or blow up, but you might want so see if the person stabbed or punched the other object in the head or knee.

So they key is to know what level of precision you need for your specific game, code up the specific routines for collisions, etc., and then add in optimisations to speed stuff up. Some optimisations will make other ones redundant, but that's part of the learning process. Plus it helps for debugging the new stuff.

superbovine
Jun 8, 2006, 06:03 PM
Ok I'm totally lost with collision detection, I'm absolutely an idiot when it comes to it, if anyone knows anything about it or wants to see the code I'm trying to make work, let me know, I cannot figure out how to do collision detection.

FYI: when you say collision detection in the computer science world, please specify what you are talking about because collision detection in networking is way different than graphics.

Why don't you just google or read your text? It isn't that hard to read up on collision detection. although, if you were writing it in opengl there would be a ton of examples as well.

MarkCollette
Jun 8, 2006, 08:56 PM
FYI: when you say collision detection in the computer science world, please specify what you are talking about because collision detection in networking is way different than graphics.

Wow, I totally missed that one.

slooksterPSV
Jun 8, 2006, 09:47 PM
Yeah its Graphics, I mentioned it in like Post #13 or sommat. Anyways I'm going to just post this one here. Does anyone know how to do scrolling? http://lazyfooproductions.com/SDL_tutorials/index.php has some great tutorials, but I need to re-write half if not more of my code to make it work like this person has made it work. The tiles are being invoked and drawn by themselves to the screen.

Is there anyway I can draw what was on one bitmap to another bitmap and blit what coordinates of it I want? I tride doing this, but alas it failed:
SDL_Surface* temp = NULL;
...
//blit the surface to an arbitrary bitmap (instead of the screen) and blit only what parts are defined as in the SDL_Rect.

Ok so that's barely any code, but how can I blit from one bitmap to another? Instead of one bitmap to screen?

savar
Jun 8, 2006, 11:52 PM
A true collision happens when to objects share the same space at the same time. The calculations get more complex, the more dimensions you're modelling. Some suggestions here are effectively optimisations on that.

For the object buffer (each pixel point has a pointer to the object), if they are drawn on the same space they have collided. But take care, objects can collide without ever visually overlapping. Take for example two objects on the X axis, moving towards each other rapidly. Depending on how rapidly you render those objects, they may not be drawn while they overlap.

This is a very interesting post. Where have you implemented a physics model like this? In a game or some kind of scientific app?

Catfish_Man
Jun 9, 2006, 12:46 PM
Everything you never wanted to know about implementing 2D collision detection and physics engines: http://www.harveycartel.org/metanet/tutorials.html

slooksterPSV
Jun 9, 2006, 12:56 PM
Everything you never wanted to know about implementing 2D collision detection and physics engines: http://www.harveycartel.org/metanet/tutorials.html
OMGosh, that helps sooooooo much, now I just need help with my scrolling - I made a new post for it and included my source in a 4.7MB file.
http://forums.macrumors.com/showthread.php?t=207776

MarkCollette
Jun 9, 2006, 02:48 PM
This is a very interesting post. Where have you implemented a physics model like this? In a game or some kind of scientific app?

My friend Tony Swain implemented a whole graphics API/animation API/game engine in Java, which we've heavily discussed. Of course we've both read up on it too.

Edit: Plus, I haven't implemented the first couple of solutions described, but was rather summarising other people's suggestions in this thread, while noting some limitations. Which is why I wouldn't use those approaches :)