Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1401678 Posts in 67940 Topics- by 61496 Members - Latest Member: Lankar5

July 07, 2022, 12:06:50 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)2D collision detection with shapes
Pages: [1]
Print
Author Topic: 2D collision detection with shapes  (Read 6629 times)
Robotacon
Pixelhead
Level 3
******


Story mode


View Profile
« on: February 12, 2008, 09:02:21 AM »

Hi guys,
I feel like a complete rookie asking a question about collision detection but I'd like to hear what your experience is on this. (Also writing posts is kind of therapeutic)

I have a 2D platform game where all objects have a collision map. I figured that it's better to test on a consistent map than having pixel perfect collision detection on every animated frame.

Here's an example spritesheet:


And here's the collision map:

There is one hit area for crawling and one for crouching and one for everything else.

Now, is this a normal way to solve the collision detection problem? This works fine at the moment but now I'm going to implement a ledge hanging algorithm. My plan for this is to add a couple of green pixels on the right-most hit area that only is checked for when the player is jumping so that I know if he's in grabbing distance.

Come to think of it I've got a bunch of other problems too. If you look at the crawling hit map it's possible to hang by the edge of your feet if you crawl out far enough off an edge. I've solved that with some patchy code that will force you into kneeling but I would like to have a more generic solution for this.

While writing I figure that perhaps I should use a green color the G channel for areas that can support the character. Like this...



That way I can make sure that the character is not balancing too far off an edge and I can check for hanging on a ledge.

Anyone else got any useful tips?

EDIT:
I'm going to use yellow for pixels that both support the character and can be hit for damage. The R channel will be used for hit detection against enemies while the G channel will be used for checking if the character is standing or hanging on something.

EDIT:
Fixed the second hit map
« Last Edit: February 12, 2008, 09:21:52 AM by robotacon » Logged
Saint
Level 3
***



View Profile WWW
« Reply #1 on: February 12, 2008, 09:33:29 AM »

Hmm, i prefer to use primitives for collision detection as they require less data, are more scalable and usually faster to test, and give you more accurate information about the collision taking place (normal, penetration depth etc).

Just some input. If you're going with bitmap testing, you may be able to use bitmasks instead of actual pixels to speed up testing.
Logged
Robotacon
Pixelhead
Level 3
******


Story mode


View Profile
« Reply #2 on: February 12, 2008, 09:56:11 AM »

The game reads png resources and transforms them internally to bitmasks.
I'm not testing against bitmaps. Currently each hit mask takes 1 bit per pixel, I'm thinking about expanding that to 2 bits per pixel.

The language barrier stopped me from realizing I should use the word Mask instead of the word Map.

However, I'm interested in what you mean by...
Quote
more accurate information about the collision taking place (normal, penetration depth etc).

/ Robo
Logged
Saint
Level 3
***



View Profile WWW
« Reply #3 on: February 12, 2008, 10:33:15 AM »

...

I mean that when using primitives you have a lot more information about the shape of objects. If you do SAT or DJK tests, you can get accurate collision manifolds and normals as well as the penetration depth without complicating the function too much, and you can do this on a per-frame basis. Primitives can also be rotated or scaled without precision loss (other than that of floating-point precision).

A per-pixel test won't tell you about these things. If you are mindful of how you define occlusion you can of course approximate what results you need with the help of the previous frame position, so if you feel this is enough there's no reason to delve into something more complex.
Logged
Ivan
Owl Country
Level 10
*


alright, let's see what we can see


View Profile
« Reply #4 on: February 12, 2008, 11:50:37 AM »

I agree. I don't see what you could possibly gain by having those extra few pixels that you get in a per-pixel collision mask. A rectangle collision box (or boxes) would be much much faster.
Logged

http://polycode.org/ - Free, cross-platform, open-source engine.
Robotacon
Pixelhead
Level 3
******


Story mode


View Profile
« Reply #5 on: February 12, 2008, 01:33:25 PM »

I see your point now and I'll consider it.
I'm not too fond of rectangular collision tests but since I was planing to have multi player support later on perhaps that's needed anyhow.
 
Also I see great potential for sloped backgrounds and what not.

I'm still interested in alternative solutions.

EDIT:
I guess I can live with something corresponding to this:

Thanks for pointing out the absurdity of having a hit mask.
« Last Edit: February 12, 2008, 01:52:58 PM by robotacon » Logged
Golds
Loves Juno
Level 9
*


Juno sucks


View Profile WWW
« Reply #6 on: February 13, 2008, 02:05:20 AM »

When testing things like projectile hits in a 2d game, having a collision mask is nice.  It all depends on how in-depth you want your physics to be.
Logged

@doomlaser, mark johns
Robotacon
Pixelhead
Level 3
******


Story mode


View Profile
« Reply #7 on: February 13, 2008, 05:19:42 AM »

Why are collision masks nice/better for projectile hits?

Now I'm rewriteing my engine representing everything with boxes.
Logged
rodhyde
Level 0
*


View Profile
« Reply #8 on: February 13, 2008, 06:19:38 AM »

Why are collision masks nice/better for projectile hits?

Now I'm rewriteing my engine representing everything with boxes.

If an object's hit box is smaller than the object's visible appearance then a rectangle is just fine.

If, however, your hit box is a bounding rectangle around the entire object then unless the object is pretty much rectangular there will be parts of it that your collision system will flag as being in collision, even though what is drawn doesn't look like a collision, leading to complaints of dodgy collision detection.

--- Rod
Logged
Robotacon
Pixelhead
Level 3
******


Story mode


View Profile
« Reply #9 on: February 13, 2008, 11:08:07 AM »

Yeah, that's why I was using a bitmask in the first place.

Hm...
Perhaps I'll use rectangular areas for testing against static map-elements and most enemies and have pixel perfect testing (against the actual sprites) for projectiles.

Thanks everyone that find time to reply on this topic.
Logged
moi
Level 10
*****


DILF SANTA


View Profile WWW
« Reply #10 on: February 13, 2008, 11:20:32 AM »

In most cases, rectangular or ellipsoid collision is sufficient, if you really need complex shapes, you could set up a system that would store an array of points forming a polygon and check collision with the shape (not difficult for convex shapes, and concave shapes could be treated as ensembles of convex shapes).
Another even simpler idea is to check on several simple boxes (or ellipsoids).
Logged

subsystems   subsystems   subsystems
ravuya
Level 7
**


Yip yip yip yip yip


View Profile WWW
« Reply #11 on: February 13, 2008, 02:12:05 PM »

You can always do the simpler rectangular check first, to see if there's even a chance of it hitting, and then do the more expensive per-pixel check.

Trivially discarding collision checks is the key to performance.
Logged

MekanikDestructiwKommando
Level 3
***


Let's ROCK!


View Profile
« Reply #12 on: May 12, 2008, 01:56:31 AM »

Once you get the rectangles compared, how do you do pixel perfect tests in your code? What is the logic behind this I mean.. I am wondering.  Cool
Logged

Quote
There have always been interactive experiences that go beyond entertainment.  For example, if mafia games are too fun for you, then you can always join the mafia.
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic