2D Collision masks for handling slopes

Question

I've been looking at the example at: http://create.msdn.com/en-US/education/catalog/tutorial/collision_2d_perpixel and am trying to figure out how to adjust the sprite once a collision has been detected. As David suggested at Sidescroller variable terrain heightmap for walking/collision, I made a few sensor points (feet, sides, bottom center, etc.) and can easily detect when these points actually collide with non-transparent portions of a second texture (simple slope). I'm having trouble with the algorithm of how I would actually adjust the sprite position based on a collision.

Say I detect a collision with the slope at the sprite's right foot. How can I scan the slope texture data to find the Y position to place the sprite's foot so it is no longer inside the slope? The way it is stored as a 1D array in the example is a bit confusing, should I try to store the data as a 2D array instead? For test purposes, I'm thinking of just using the slope texture alpha itself as a primitive and easy collision mask (no grass bits or anything besides a simple non-linear slope). Then, as in the example, I find the coordinates of any collisions between the slope texture and the sprite's sensors and mark these special sensor collisions as having occurred. Finally, in the case of moving up a slope, I would scan for the first transparent pixel above (in the texture's Ys at that X) the right foot collision point and set that as the new height of the sprite.

I'm a little unclear also on when I should make these adjustments. Collisions are checked on every game.update() so would I quickly change the position of the sprite before the next update is called?

I also noticed several people mention that it's best to separate collision checks horizontally and vertically, why is that exactly?

Open to any suggestions if this is an inefficient or inaccurate way of handling this.

I wish MSDN had provided an example of something like this, I didn't know it would be so much more complex than NES Mario style pure box platforming!

Answer 1

Basic approach

Querying the texture directly might be slow so I would probably store the collision mask separately. The format in which you store it is not that relevant. I don't see any problem with storing it as a 2D array as you mentioned. Something like this for instance would be enough:

// Use bool or byte to save space
bool[,] collisionMask = new bool[TileWidth, TileHeight]; 

At load-time I would create all of the mask arrays from the alpha channel of the tile textures but only once for each type of tile. In other words, do not store this information inside each individual tile, but store it in the tileset instead.

As for scanning for the correct position for the character to stand on, I would just do it the brute-force way - query the mask at the same position as your foot sensor sensor, and then move up pixel by pixel until you find a non-blocked one. Then move your character up by that same amount.

Since tiles probably won't be too big, I don't think there will be much of a performance problem with this simple approach.

But it's possible to simplify it in some cases

Depending on the variability of your tiles it's possible that you could simplify the way you store your information a lot. For instance if your tiles always start from the bottom and don't have holes in them you could store their collision masks as a single one dimensional height map array:

// Essentially an height map for the tile type
byte[] collisionMask = new byte[TileWidth];

Or if they don't always start from the bottom but still don't have holes or multiple "islands" you could store it as:

// Use Point.X for bottom height and Point.Y for top height
Point[] collisionMask = new Point[TileWidth];

So it all depends on how complex you want your tiles to be.

When to move the character

I'm a little unclear also on when I should make these adjustments. Collisions are checked on every game.update() so would I quickly change the position of the sprite before the next update is called?

Yep. First you move your character. Then you have the collision detection phase, and finally the collision response phase. That's essentially what you'll be doing by moving the character up outside the tile.

Separate axis handling

I also noticed several people mention that it's best to separate collision checks horizontally and vertically, why is that exactly?

That's not really much of a problem here because your foot sensor collision response will always be moving the character up. You'll be handling collisions with walls separately anyway, using the middle sensor.

I've made this picture for another question but I'll repost it here for context:

Basically if you move diagonally all at once, it can create an ambiguity where the algorithm needs to guess in which direction it should push out of the tile. It's possible to make it intelligent enough to always use the correct direction, but it's easier to just handle movement in each axis separately, as there's no ambiguity that way.

Answer 2

I haven't used XNA and I also haven't thoroughly read your topic, but anyway.

They way I did it (in AS3, but that doesn't matter) is to get the vector of the slope.

Say you want a 45 degrees slope. To get the vector, you just do this:

the slope's X - the character's X = the character's Y

So, y=(slope.y-tileHeight/2)+slope.x(+tile width/2)-x(+character width/2)

and then compensate the character's height, so -charHeight/2

and for mirrored slopes, you do this:

y=x-slope.x+tileWidth/2

Do you get the basic idea? So, the closer the character gets to the right or left side of a slope, how higher the character gets. I find this method a lot more reliable than checking for pixels. Though there is one problem with this, you'll have to make all the angles individually. Not sure if that's a problem for you...

If you still don't get it, don't be afraid to ask!