gbadev.org forum archive

Are there any better methods to do tile based collision detection then boundary constraints as that seems quite slow with a game of am I being naive?
_________________
[Blog] [Portfolio]

Colliding sprites with tiles is not very slow. Each time a sprite moves, check if it just crossed a tile boundary and if the new tile is 'solid', then adjust the sprite's position as appropriate.

The harder part is colliding sprites with other sprites, because the number of collision checks increases quadratically with the number of sprites on screen.

short of

Code:

for (No_sprites)
{
check collision
}

are there other ways of doing it?
_________________
[Blog] [Portfolio]

Actually sprite checks increase linearly if you don't keep checking the same ones over and over. It's like a linear sort, as opposed to bubble sort.
for(i = 0; i < sprites; i++)
for(j = i; j < sprites; j++)
ColSpriteSprite(i, j);
As long as you do your collision response (stop them from moving or whatever) on both sprites involved in a collision at the same time, there shouldn't be any diference in the result.
I've never successfully made a platformer-type collision system work though, but then again I haven't tried in a couple of years. Never could figure out how to deal with multiple collisions, where you have like 2 sprites hit, you move them apart, but that runs them into other sprites, you move those apart, that runs the original two back into eachother, etc.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

DekuTree64 wrote:

Actually sprite checks increase linearly if you don't keep checking the same ones over and over. It's like a linear sort, as opposed to bubble sort.
for(i = 0; i < sprites; i++)
for(j = i; j < sprites; j++)
ColSpriteSprite(i, j);

This is still O(n^2) and only half as fast. The key to speeding up the process is to sort the sprites by top y coordinate before you test them. Then you can break from the inner loop once sprite j's top is below sprite i's bottom. Details

Quote:

As long as you do your collision response (stop them from moving or whatever) on both sprites involved in a collision at the same time

Collision response is the hard part. Really old 8-bit games dealt with it by allowing all enemies to pass through ("alongside" in the documentation) one another and sending the player back to start after collision with an enemy.

Quote:

Never could figure out how to deal with multiple collisions, where you have like 2 sprites hit, you move them apart

Multiple collisions should clear up after a few frames if you accelerate each pair of sprites along the lines between their centers.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

tepples wrote:

This is still O(n^2) and only half as fast. The key to speeding up the process is to sort the sprites by top y coordinate before you test them. Then you can break from the inner loop once sprite j's top is below sprite i's bottom.

Not quite n^2. Actually that should be

Code:

for(i = 0; i < sprites - 1; i++)
for(j = i + 1; j < sprites; j++)
Check(i, j);

Because you don't need to check sprites against themselves, and when you get to the last one in the outer loop you've already checked it with every other one. Say you have 5 sprites, A, B, C, D and E. Here's how the loop would go:

Code:

A
check B, C, D, E
B
check C, D, E
C
check D, E
D
check E

That's only 10 checks, as opposed to 5^2=25. Definately not linear as I said before though...
And yes, Y-sorting would speed it up a whole lot. Or X-sorting if it's a more left-to-right game would probably work even better.

Quote:

Multiple collisions should clear up after a few frames if you accelerate each pair of sprites along the lines between their centers.

Yeah, it probably would. I never did get it working well enough to see if that would really be a problem, I just couldn't get it worked out in my head how it would keep from ending up with things inside of eachother.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

DekuTree64 wrote:

tepples wrote:

This is still O(n^2) and only half as fast. The key to speeding up the process is to sort the sprites by top y coordinate before you test them. Then you can break from the inner loop once sprite j's top is below sprite i's bottom.

Not quite n^2.

I said O(n^2) not n^2. I'll explain the difference next.

Quote:

Code:

for(i = 0; i < sprites - 1; i++)
for(j = i + 1; j < sprites; j++)
Check(i, j);

...
That's only 10 checks

And how many checks would it be for 100? 9+8+7+6+5+4+3+2+1 = 45 checks. More generally, for n sprites, your algorithm needs n*(n - 1)/2 checks. As n increases, this approaches a constant factor times n^2 checks. Thus, your algorithm's efficiency differs only by a small constant factor, and though you admit it's not linear, it's still quadratic.

Quote:

And yes, Y-sorting would speed it up a whole lot. Or X-sorting if it's a more left-to-right game would probably work even better.

I suggested Y-sorting because a lot of games do Y-sorting anyway to draw frontmost sprites in front of farther-back sprites. My algorithm based on Y-sorting is still quadratic as well in the worst case, but the constant factor is even smaller in the average case.

and about multiple collision response:

Quote:

I never did get it working well enough to see if that would really be a problem, I just couldn't get it worked out in my head how it would keep from ending up with things inside of eachother.

If objects keep exerting forces against each other, something has to give eventually unless they're in an enclosed space, in which case you have even worse problems that should be solved in the enemy AI layer. If you're worried about two objects completely coinciding to where you can't even push their centers apart, try jittering their coordinates.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

Thanks guys, looking back I reliesed I researched this in the summer and 'kind of forgot' that I had saved them on my computer.

yaustar == dumbass ;)

What happens when we start checking for collisions on angled platforms?
_________________
[Blog] [Portfolio]

tepples wrote:

More generally, for n sprites, your algorithm needs n*(n - 1)/2 checks. As n increases, this approaches a constant factor times n^2 checks. Thus, your algorithm's efficiency differs only by a small constant factor, and though you admit it's not linear, it's still quadratic.

I didn't get a job when in the interview I said an algorithm that would take n choose 2 cycles (an improvement over the original algorithm, which was n^2) was still geometrically bounded by n^2.

Stupid jerk... :(

Dan.

poslundc wrote:

tepples wrote:

More generally, for n sprites, your algorithm needs n*(n - 1)/2 checks. As n increases, this approaches a constant factor times n^2 checks. Thus, your algorithm's efficiency differs only by a small constant factor, and though you admit it's not linear, it's still quadratic.

I didn't get a job when in the interview I said an algorithm that would take n choose 2 cycles (an improvement over the original algorithm, which was n^2) was still geometrically bounded by n^2.

Stupid jerk... :(

Dan.

It was probably a lucky escape :)

Col

Quote:

What happens when we start checking for collisions on angled platforms?

For completely solid tiles, there's obviously a collision as soon as anything enters the tile. For slopes, a collision only occurs if something is on the solid portion of the tile.

dx = distance from left side of tile
dy = distance from top of tile

For right-upward slopes, a collision occurs when dy < dx.
For left-upward slopes, a collision occurs when dy < tile width - dx.

There also might be a special case for when the player is walking along a slope (you don't want it to block them). So when the player walks, check if they're on a slope and move them along it.

dont have to worry about moving them down the slope yet since it s a top down game :D
_________________
[Blog] [Portfolio]

This is kindof tangent to the main thread, but I'm going to post it here anyway rather than start another

>DekuTree64 said:
>Never could figure out how to deal with multiple collisions, where you
>have like 2 sprites hit, you move them apart, but that runs them into
>other sprites, you move those apart, that runs the original two back into
>eachother, etc.

I had this same problem my first several attempts at a 2d collision system; the best solution I came up with was to remove the seperation between the update of object positions and the collision testing. When you are iterating through the moving object list, check it's destination for a collision before you move on to the next object. If it collides with something, don't worry about moving the both objects, just shift the current object back to the point of the collision.

This approach is not perfect; you can't use the described method of reducing the number of collision tests, as you're testing each object as-you-go and it may collide with previously-updated objects. As long as the moving objects are kept x- or y-sorted, you can still reduce the amount of testing nessicary to something managable.

Also, you can still in rare cases come up with a situation where moving one sprite back towards it's initial position causes it to overlap an object it had already been tested against. To fix that would require either rechecking all objects every time you find a hit and push back, or to always move the offending object all the way back to their initial position. The first has a worst-case of O(n^3), and although actual performance would usually be much higher, it clearly should be avoided unless you've got cycles to burn. The second could cause objects to appear to collide without touching. However, unless object speeds are extremely high (multiple object-widths per frame), the event should be rare, and the resultant overlap slight.

It's also simply not good physics, so if realism is your goal, it's definately not the way to go. But then, if realism is your goal, GBA is a strange choice of platform.
_________________
"Only two things are infinite: the universe, and human stupidity. The first is debatable." -Albert Einstein

gbadev.org forum archive

Beginners > Methods of Collision detection

#11626 - yaustar - Tue Oct 14, 2003 10:02 pm

#11628 - sajiimori - Tue Oct 14, 2003 10:50 pm

#11631 - yaustar - Tue Oct 14, 2003 10:53 pm

#11633 - DekuTree64 - Tue Oct 14, 2003 11:24 pm

#11638 - tepples - Wed Oct 15, 2003 12:06 am

#11648 - DekuTree64 - Wed Oct 15, 2003 3:13 am

#11651 - tepples - Wed Oct 15, 2003 4:04 am

#11660 - yaustar - Wed Oct 15, 2003 1:14 pm

#11663 - poslundc - Wed Oct 15, 2003 2:50 pm

#11664 - col - Wed Oct 15, 2003 4:03 pm

#11675 - sajiimori - Wed Oct 15, 2003 6:22 pm

#11683 - yaustar - Wed Oct 15, 2003 9:33 pm

#11695 - Gopher - Thu Oct 16, 2003 1:10 am