What's your method of collision detection?
lin lin

I usaully just check to see if the object is on the screen, then if it is, while it's been drawn, I push the player back to the boarders of the object if the player was inside the area in that particular frame. Is this method too slow? Because if I had alot of objects on the screen I would have 30-100 if's for each frame only for collision detection.

1 more thing. Collision detection is pretty easy when there's no diaginal boarders. What if there is?

It sounds like you're doing bounding box collision, that's one of(if not the) fasted methods since it's the simplest.

Dustin Dettmer

My collision detection algorithm depends on the application. One time i experimented with pixel perfect with automatic slope detection. It was pretty cool, except that it was a little slow and sometimes let you jump through walls...

Anyway I'd stick with your basic bounding box collision detection and simply avoid diagonal surfaces. A simple trick you can do for 'slopes' is to make them staircases and add code that automatically 'jumps up' walls that are small enough. If you've ever run up stairs in Mario, or walked over walls in World of Warcraft you'll know what I mean.

Anything more advanced requires a bit of math. Past this point the amount of work for very little payoff becomes very high.

X-G
Quote:

It sounds like you're doing bounding box collision, that's one of(if not the) fasted methods since it's the simplest.

What are you smoking? Sphere-sphere (or sphere-point) collision is about a million times simpler and faster than bounding box collision.

Dustin Dettmer

I think conceptually bounding box is simpler. Especially for people who haven't studied trig.

lin lin

I been in cal for 3 years now. I know my math. Just never really applied it to my programming. So what's this bid of math your talking about? Can you give me a bit detail?

For example you ever see the objects in diablo 2? Your character tends to run around them. I wonder if it's box collsion or they using something else.

Lucid Nightmare

Bounding box and sphere point are both simple, basic and primitive at the same time but pretty useful at most times and a good way to start especially if u are a learner...

Zaphos
Quote:

Sphere-sphere (or sphere-point) collision is about a million times simpler and faster than bounding box collision.

(is this just hyperbole, or are you assuming the bounding boxes may be rotated, or ... ?)
Raises the question: is lin lin dealing with a 3D space, or a 2D space? I'm assuming 2D.

Anyway, 'off the cuff', bounding box looks like:
given rectangle a and rectangle b:

```if (fabs(a.center_x - b.center_x) < (a.width + b.width)/2.0f
&& fabs(a.center_y - b.center_y) < (a.height + b.height)/2.0f)
collide(a, b);
```

Circle-circle looks like:
given circle a and circle b:

```float dx = a.x - b.x;
float dy = a.y - b.y;
if (dx*dx+dy*dy < rsum*rsum)
collide(a,b);
```

Diablo 2 is not a game I've actually played, but given that they use what seemed like auto-generated isometric tile maps, I imagine they check the relevant elements of a tile map to check for collision. To allow a character to run around them, I imagine they use a path-finding algorithm (such as a*).

edit:

Quote:

Because if I had alot of objects on the screen I would have 30-100 if's for each frame only for collision detection.

If you have lots of objects on the screen, and you are, for each object, iterating through the other objects ... you may want to partition the objects based on their location in screen space. By making a list of all objects in a "region" of screen space, then only checking for collisions between objects in the same or adjacent regions, you can skip a lot of collision checks.
In my most hackish pseudocode:

 1 for (object i in all objects) { // for each object in the main object list 2 objects_list[i.x/REGION_WIDTH][i.y/REGION_HEIGHT].add(i); // add it to a matrix of object lists 3 } 4 5 for (int x in objects_list) { // for each column in the matrix 6 for (int y in objects_list[x]) { // for each column in the matrix 7 for (object i in objects_list[x][y]) { // for each object in this entry 8 for (int xd = 0; xd <= 1; xd++) { // the adjacent entries x-wise 9 if (x+xd >= objects_list.size()) // if we're not out of bounds 10 continue; 11 for (int yd = 0; yd <= 1; yd++) { // for the adjacent entries y-wise 12 if (y+yd >= objects_list[x].size()) // if we're not out of bounds 13 continue; 14 for (object j in objects_list[x][y]) { // for each object in the list 15 if (test_intersect(i, j)) // check for intersection 16 handle_collision(i, j); // handles collisions as needed 17 } 18 } 19 } 20 } 21 } 22 }

(in a proper implementation, you could ensure it doesn't redundantly check against objects in its own box, as well ... but this is just pseudocode to illustrate the concept.)

lin lin

What's this about Dot-Product collision detection I hear about? Anyone know? I know te forumla but I don't know how it can be used for collision detection on a specific vector.

Zaphos

Well, I'm not sure what specific algorithm you've heard about. There's a pretty straightforward test for convex polygon intersection written up here and it uses dot products. Seems like a nice one, to me.

One straightforward application of the dot product to collision that comes to mind is one for collision response -- by dotting the incoming-velocity vector with the normal vector of the surface you've hit, then taking vel-2*dotprod*normal as your new velocity, you bounce reasonably off the surface (since you've 'reflected' your velocity vector about the surface). Take out the factor of 2, and you slide along the surface ...

Hmm, and the simplest application which is actually a collision test: if you want to have a wall of infinite length, take a vector which is normal to the wall, and a vector which is (your_pos - a_point_on_the_wall), and dot them. If the result changes sign from one frame to the next, you have crossed the wall between those frames.

Sirocco
Quote:

What are you smoking? Sphere-sphere (or sphere-point) collision is about a million times simpler and faster than bounding box collision.

For the vast majority of my projects, sphere-point detection works very well. You do a straightforward distance check between two points, and if the distance is < x you know something has invaded the object's personal space The whole rectangular bounding box works as well, but in reality many sprites have a more rounded shape than a square one; yet I'll concede that in most cases your favored approach relies on personal taste more than anything.

vixinu

Sounds to mee that point -poit, or sphere-sphere or whatever is good for not-rectangular. How exactly do you measure distances?

Zaphos
Quote:

How exactly do you measure distances?

Using the Pythagorean theorem.

I thought you would use the distance formula to check the distance between 2 points?

Indeterminatus
Quote:

Using the Pythagorean theorem.

Quote:

I thought you would use the distance formula to check the distance between 2 points?

There's no difference. The Pythagorean theorem can be used for distance calculation, thus, it passes as "distance formula".

Jonatan Hedborg

people have already said it, but here it is anyway;
Normaly, distance = sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) )
if distance is less than the sum of the radiuses, they are overlapping.
The only problem is that sqrt is very (!) slow, so instead you do it like this;

```if( ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)) < (p1.radius+p2.radius)*(p1.radius+p2.radius) ) do_overlap_stuff()
```

Untested code etc... But thats the basics of it.
There is some optimization to be made from storing the radius of object squared instead of normal.

EDIT: correction, see bellow.

Zaphos

To state it explicitly, the pythagorean formula will say that the distance, d, between points p1 and p2, has this relationship:
d^2 = (p1.x - p2.x)^2 + (p1.y - p2.y)^2

The distance formula, then, is:
d = sqrt( (p1.x - p2.x)^2 + (p1.y - p2.y)^2 )

If you merely wish to do a collision check, it is sensible to omit the sqrt and check if (p1.x - p2.x)^2 + (p1.y - p2.y)^2 < (radius1 + radius2)^2, since computing the sqrt is expensive and does not change the result of this comparison.

(Edit: Ah, I wrote this at the same time as (and so without seeing) the post immediately above this. Please exuse the redundancy.)

Jonatan Hedborg

I may be wrong, but i think the radiuses should be squared seperatly.
Also, please remember that there is no power-of operator that i know of. ^ is ... xor?
Just so any newbies don't come running back

Zaphos

Yes, the ^ was not intended to be read as literal C code, in which it would be an xor, but rather as a power operator.

The radii should be squared after summation, not before. You might demonstrate it to yourself like this: given two centers of circles, which are distance d apart, how can we make the circles touch? If you visualize this, it should be apparent that we may give as much of d as we like to one radius, and the rest to the other, and the circles will still touch. The only thing we need to concern ourselves with is the sum of the radii equalling d.

Jonatan Hedborg

Ah yes, that seems to make sense

lin lin

All this seems to be for 3d except the box and sphere detection. I been using both upto this point and it works fine. It's just I wish there were more advanced methods which involves more math and less checks. I am not going into 3d yet.

Zaphos
Quote:

All this seems to be for 3d except the box and sphere detection.

Er, what's "All this" referring to? No techniques which are specific to 3D have been mentioned at all, except perhaps the trivial extension of the circle collision detection to sphere collision detection.
If there's something you don't understand, or which you imagine to be specific to 3D-space, please point it out specifically.

Audric
linlin said:

I push the player back to the borders of the object if the player was inside the area in that particular frame. Is this method too slow? (...)

Pushing the player back requires a wild guess about where it came from :/
I've tried another method, it works nicely for a platformer: I check if the intended move for current frame is possible - If it's not, I clip the movement to the possible segment.
Ex: player attempts a "x += 5" during this logical step: I check if the right edge of the player's bounding box can do this move without being blocked. If only a 2 pixel move was possible, I move the character only 2 pixels and flag it so it can react to the event.

Speedwise, with this method I need only tests for moving objects, once per frame of movement. I also test it only against objects classes that might block it (bullets don't block each other, so no need to prevent their overlap)

Zaphos
Quote:

Pushing the player back requires a wild guess about where it came from :/

Only if you don't record where it came from.

Audric

Diablo 2 has diamond-shaped tiles, each one is composed of 16 sub-tiles (4x4), still diamond-shaped, and each sub-tile has flags for "blocks player", "blocks non-flying", "blocks projectiles", etc.
No idea how precise their collision checking is, though.

Zaphos said:

Only if you don't record where it came from.

So you solve collision by "slowly backstep, stopping as soon as the character is not in collision with anything, OR when it reaches its initial position (whichever comes first)" ?
This usually works but objects which are fast and small (projectiles) cause 2 problems:

1 - it can still miss some collisions entirely. Like the Mancubus fireballs in Doom 2, they were given a small collision size so the player could dodge them easily, but with their speed they can cross thin walls.

2 - even if a collision is detected, it may backtrack to a wrong position (too short and possibly unreachable) like:

```       +-----+
LION  |     |    // lion is going right at a speed of 10 characters per frame
+-----+

+-----+
|   LION   // collision detected with right wall of cage, backtracked to:
+-----+

+-----+
| LION|    // caged! how did it get in there?
+-----+
```

IMO, the simplest way to find the correct limit in every case is to.. go forward until you reach it!

Zaphos
Quote:

So you solve collision by "slowly backstep, stopping as soon as the character is not in collision with anything, OR when it reaches its initial position (whichever comes first)" ?

Well, you might want to do a binary search instead of that. Or you could just push the player out in that direction, eg, by giving them an impulse of force.

Quote:

This usually works but objects which are fast and small (projectiles) cause 2 problems:

Those cases could be worked about by, for example, using a polygon based collision detection, and checking for a collision between the polygon-which-encompasses-the-lion's-path and the environment. Or by testing for collision at fixed-length intervals along the path between the found-collision and the starting point (which may be larger than the forward step-size). Or those cases might simply not be important, depending on the game & such.

Quote:

IMO, the simplest way to find the correct limit in every case is to.. go forward until you reach it!

The main issue with this is that it can be slow. There are situations in which other methods would be preferred. Of course, what one should use depends on the game & target system & so on.

Trezker

First you just check if a collision has occured at all. This should be done as fast as possible.

If a collision occurs, do a proper process of getting the results right.
Since collisions are quite rare, there really shouldn't be many collisions every frame, it doesn't matter much how fast the function is.

Audric

Objects which push each other complicate things..
player pushing a boulder,
floating platform carrying the player

Also, a gravity-affected object resting on the floor has a permanent collision with scenery. If the collision stops, it's a new event: a fall.

Simon Parzer

I use a tile-per-tile collision detection, as my current project is tilebased. Simple enough: Check the movement values for the current object, if the next tile in movement is "walkable", move the object, otherwise don't.