Pixel perfect collision with mirrored textures and 'lines'

Windows
1

Hi,

I’m trying to do pixel perfect collision and found a helpful tutorial from Riemers here and here. Basically, the Pixel Data of each texture is read into an array, and then matrices are used to determine which pixels occupy the same space and to honor rotation and scaling. Then it is checked if both pixels at that space are non-transparent to find a collision…

What I still don’t get is, how do I check pixel collision when the sprites are not only rotated/scaled, but also flipped horizontally (SpriteEffects.FlipHorizontally) and/or vertically (SpriteEffects.FlipVertically).

And how do I check collisions with a line, where a 1x1 pixel texture is drawn to a target rectangle with the length and rotation that the resulting line should have?

If you know an answer, please describe it as detailled as possible and as easy-to-understand as possible… I’m still a total beginner.

2

You can see the flipping as a combination of translation (depending on where the origin of your texture is) and scale. If your origin is in the middle of the texture you only need to scale to get the flip effect. That means if your sprite is flipped horizontally you just have to multiply the x-component of the scale that goes into the matrix by -1. A vertical flip is the same as multiplying the y-component of your scale by -1 (IF your origin is in the middle). Note that the origin only has to be in the middle in the component you’re mirroring around e.g. if you only flip around x the origin has to be in the middle in its x-component, but not necessarily in its y-component. If you’re working with matrices it’s easiest to have the origin in the center anyway. Now if the origin is for example in the upper left and you flip along x, you’d have to translate it by the width of the texture first so the result will be in the same place as just flipping with the origin in the center. In that case the creation of the matrix would look like this

matrix = [translation_so_origin_is_in_center *] scale_with_flipping_included * rotation * translation

I hope that gives you some intuition as to how to solve this :slight_smile:

You could render the line to a RenderTarget and then use the same technique as above where you treat the rendertarget with the line on it like another texture, though if the line is long you’ll check way too many pixels. That would be easiest though, since you can treat you’re lines like any other texture when doing collision detection. An optimization would be to use Bresenham’s line algorithm to figure out which pixels the line occupies and store those coordinates in the line, then iterate over them to check for collision, comparing the coordinates to see if they match. Though your line then behaves differently from other object when you check for collision, which can be a pain. You could also use maths to calculate any intersections. If you define your line by a begin and end point you can figure out its equation y = m*x + b (you should remember this from maths class). You can then check if a pixel is on it by filling in x and y and checking if it’s close to zero (because a point is on the line if it fits the equation and you can bring over y to the other side to get m*x + b - y = 0, meaning that that will hold for a point that is on the line). You don’t want to check for exact equality but have some tolerance =>

public bool OnLine(float x, float y) 
{
    return Math.Abs(this.m * x + this.b - y) < this.tolerance;
}

This function assumes you checked against the bounding rectangle of the line segment first, so it doesn’t check if the point is within the bounds.

I know this isn’t very detailed on all options, but let me know what method you’re going for and I can clarify if necessary :slight_smile:

3

Hm… I don’t really get it… also, I use spritesheets, and different-sized target rectangles for scaling. How do I implement that when I want to do pixel-perfect collision checks?

Aren’t there ANY pre-made functions for this that I could just use (or already-working examples), instead of ‘inventing the wheel’ altogether?

4

Nobody out there who can explain this step-by-step for a NOOB ? Did you all start with MonoGame already having a degree in Algebra and Geometry?

5

It’s probably easiest if you setup the arrays in which you store collision data per sprite. Either that or you have to figure out the mapping from the sprite to the sheet and deal with only taking into account the area of that specific sprite in the sheet, which is a lot more complicated.

MonoGame is just a framework, there’s some collision detection code in there, but not per pixel. There might be code for this somewhere, but “inventing the wheel” is part of working with MonoGame. It’s what makes it fun IMHO :slightly_smiling:

Pixel perfect collision with rotated and scaled sprites is really not an easy problem to solve… You’ll have to do some maths to figure it out. You could make this way easier by using rectangles and/or circles to define the bounding area of your sprites. That’s how most people do it. You can approximate pretty much any silhoutte with a combination of rectangles and circles. If your sprites have really complicated shapes, you could also use polygons, but that complicates the collision detection again. I personally don’t really like using pixel-perfect collision detection and I wouldn’t even attempt it if my sprites where rotated and scaled. Bounding boxes/circles are just way easier to work with and in almost all cases do the trick just as well.

6

There is no easy or efficient solution to this. I do not know of any game in the history of games that does pixel-perfect collision with rotated, flipped and/or scaled sprites. All collision systems I have seen have been approximate representations of the world they simulate. They use boxes, circles, spheres and other simple primitives to make it look good enough, calculate fast enough, and most of all, be fun for the player.

It’s not that we don’t want to share. It’s that we just don’t do what you are asking us for.

7

I had to write functions for a compiler I wrote that did pixel perfect collision detection for rotated,sceled sprites plus with added effects amongst other things. The gist of the code is here PNG Non-Transparent Pixel Collision Detection?

8

Hi Absolute_Beginner!

Take a look at this repo here. It contains code for pixel-perfect collision along with some explanation why you shouldn’t use it.
I tried to expand the readme.md in order to explain the algorithm and why one shouldn’t use it.

If you want to limit your collision-candidates in the first place, try this. It has an extensive readme.md as well concentrating on broad-phase collision detection.
Or keep an eye on MonoGame.Extended. They are planning extended collision features and are currently working on it.

If you have additional questions, feel free to PM as well.

cu,
Psilo

9

Hm… let’s try a different approach.

I got the code described here and here and here … basically, as far as I understand it, the color data of both images is copied into 2d arrays, then two transformation matrices are created to take rotation and scaling into account, and then the pixels are compared based on those matrices.

This indeed seems to work, even with rotated and scaled sprites (no matter how scaled or rotated both images are, as long each image has equal scaling in x AND y direction) … however, when an image uses a scaling that is not equal in length an height, then the collision does NOT work correctly anymore.

Example: I draw an image like

spriteBatch.Draw(sprite, new Vector2(pos_x, pos_y), null, Color.White, rotation, origin, new Vector2 (scale + 0.5f, scale + 1.2f), SpriteEffects.None, 0f);

and create a matching matrix like

Matrix sprite_matrix = Matrix.CreateTranslation(-origin.X, -origin.Y, 0) *
Matrix.CreateRotationZ(rotation) *
Matrix.CreateScale(scale + 0.5f, scale + 1.2f, 1.0f) *
Matrix.CreateTranslation(pos_x, pos_y, 0) *
Matrix.Identity;

both with different scaling in x and y direction (e.g. ‘scale + 0.5f’ horizontally and ‘scale + 1.2f’ vertically as used above), and when I test collision with another image, this does not work right… but when scaling in x and y direction is the same (e.g. scale + 05.f horizontally and scale + 0.5f vertically), it does work.

I thought that’s what the matrices do, translate between different rotation and different scaling? Can anyone tell me what I’m doing wrong, and how I can change it so scaling with different values for x and y will work too?

10

I’m sorry I didn’t reply immediately.
I have some things going on at home, but I will try your code and come back with a suggestion / bugfix.
Thx.

11

Hmmm.
Curious.
I’ve tested the code here using this modification in the call of the spikeBall-constructor:

spikeyBallSprite = new Sprite(spikeyBallTexture)
{
    Position = new Vector2(400, 340),
// the next line is new and scales the ball asymmetrically.
    Scale = new Vector2(.8f, 1.4f)
};

and it works like one would expect.
Go ahead, clone the repo and see for yourself. It’s line 78 in the file Game1.cs.

I think your ‘mistake’ is that you rotate before scaling the object when creating the matrix, but you just draw scaled in the spriteBatch-call. And that would be a translate-scale-rotate instead.

Like that:

SCALE(1.4f, 1f) -> ROTATE(45)

ROTATE(45) -> SCALE(1.4f, 1f)

So when you switch the two lines you’re probably fine.

But I saw in another thread that you’ve gone for another approach that’s better in all respects.

cu & have fun,
Psilo

12

@throbax: I don’t understand what you mean with ‘you just draw scaled in the spriteBatch-call’, but switching the two lines indeed did the trick. Now per-pixel collision works perfectly even with differently-scaled sprites.

My hero! :wink:

This also means that Riemer’s XNA Collision Tutorial is wrong with its matrix creation example in that point…

My other approach is trying to put Bounding Boxes around the important parts of a rotating sprite… however, I haven’t fully found out yet how to check for a collision when the boxes get rotated…

I’m a newbie, and understand things best from WORKING code examples. However, most of the examples require XNA Game Studio to be installed, or are ‘incompatible with your version of Visual Studio’, or aren’t really documented, or whatever. But as long as I’m not able to master the most fundamental basics (which includes collision detection), there is no way to even think of starting to program any game.

13

I just meant that you did it like in the second diagram (in the creation of the transformation matrix), but the call to SpriteBatch.Draw() does the thing in the first diagram.
By switching the two lines in your matrix-creation code you adjusted the matrix to do the same as in the first diagram.
That’s why it works.

Also thanks blush
and no problem.

If you need further advice, just pm.