Auf das Thema antworten  [ 1 Beitrag ] 
Tutorial: 2D Pixel Collison Detection for XNA 

Is this code usefull?
Du kannst eine Option auswählen

Ergebnis anzeigen

Tutorial: 2D Pixel Collison Detection for XNA 
Autor Nachricht
Administrator
Benutzeravatar

Registriert: Sa 15. Dez 2012, 19:15
Beiträge: 137
Wohnort: Karlsruhe
Mit Zitat antworten
Tutorial: 2D Pixel Collison Detection for XNA

Hey folks!

This tutorial is about 2D pixel collision detection for XNA. The feature keys of this solution are efficiency and easy to understand code flow. You can use this solution as a template for every project. It is easy to expand and to modify. To test the code, I made a Visual Studio Solution wich you can download right here.

Use the keys F1 to F12 to switch the collision object, the arrow-keys to move the selected object and press left control and the arrow-keys to move the object more smoothly.
The orange object is the selected one. If there is no orange object, it intersects with another one. The red objects are the A-Objects in the collision, the blue objects are the B-Objects in the collision. The lime rectangles are the intersection rectangles for the pixel collision. You can use the border collision - which is more efficent - for any texture which has rectangle shape parts only.


Screenshot of the test:
Bild


How it works
The static method CollisionObject.CheckForCollisions(IEnumerable<CollisionObject>, bool) returns a list with a tuple of the two collision objects which collide. The methods need a enumerable list with the collision objects and a bool, if you want to use pixel collision. Such a list can be a generic list (List<CollisionObject>) or a array of CollisionObject. You have, for the pixel collision, to set the static, readonly byte CollisionAlpha. If it is 255 (Default), there is no collision, if the alpha value of one of the object has on the intersecting pixel not a 100% opacity.

A CollisionObject needs a texture and the information, if the more efficent way of boder collision can be used. Use it for textures with rectangle shape parts only! The star is not qualified. If you also specify a width and a height, the Bounds of the CollisionObject are modified. But this overloaded method is for a complete filled rectangle only. The texture will resize to the Bounds on drawing.

This is the CollisionObject class:
Code:
 
public class CollisionObject : IComparable<CollisionObject>
{
        public static List<Rectangle> Intersection = new List<Rectangle>(12);
 
        private static int _idCounter = 0;
        public readonly int ID;
        public Texture2D Texture { get; private set; }
        private Color[] colors;
        public Rectangle Bounds { get; private set; }
        public Point Location
        {
                get { return Bounds.Location; }
                set
                {
                        Bounds = new Rectangle(value.X, value.Y, Bounds.Width, Bounds.Height);
                        Program.GameScreen.StarPositionsChanged = true;
                }
        }
        public int Left
        {
                get { return Bounds.Left; }
                set
                {
                        Bounds = new Rectangle(value, Bounds.Top, Bounds.Width, Bounds.Height);
                        Program.GameScreen.StarPositionsChanged = true;
                }
        }
        public int Top
        {
                get { return Bounds.Top; }
                set
                {
                        Bounds = new Rectangle(Bounds.Left, value, Bounds.Width, Bounds.Height);
                        Program.GameScreen.StarPositionsChanged = true;
                }
        }
        public bool UseBorderCollision { get; private set; }
       
        public Color Tint { get; set; }
       
        public CollisionObject(Texture2D texture, bool useBorderCollision) {...}
        public CollisionObject(Texture2D texture, bool useBorderCollision, int width, int height) {...}
       
        public void SetTexture(Texture2D texture, bool useBorderCollision) {...}
        public void SetTexture(Texture2D texture, bool useBorderCollision, int width, int height) {...}
       
        public virtual void Draw(SpriteBatch sprite) {...}
       
        public override string ToString() {...}
       
        public static readonly byte CollisionAlpha = 255;
        public static List<Tuple<CollisionObject, CollisionObject>>
            CheckForCollisions(IEnumerable<CollisionObject> collisionObjects, bool usePixelCollision) {...}
       
        public static bool operator <(CollisionObject a, CollisionObject b) { return a.Bounds.Left < b.Bounds.Left; }
        public static bool operator >(CollisionObject a, CollisionObject b) { return a.Bounds.Left > b.Bounds.Left; }
        int IComparable<CollisionObject>.CompareTo(CollisionObject other) {...}
       
}
 


The method CheckForCollisions will return the collitions:
Code:
 
public static List<Tuple<CollisionObject, CollisionObject>> CheckForCollisions(IEnumerable<CollisionObject> collisionObjects, bool usePixelCollision)
{
        List<Tuple<CollisionObject, CollisionObject>> collisions = new List<Tuple<CollisionObject, CollisionObject>>();
        Intersection.Clear();
 
        List<CollisionObject> objectList = new List<CollisionObject>(collisionObjects);
        objectList.Sort();
        CollisionObject objA, objB;
        int count = objectList.Count;
        Rectangle colRecA;
        Point offsetB;
        for (int ixA = 0; ixA < count; ixA++)
                for (int ixB = ixA + 1; ixB < count; ixB++)
                {
                        objA = objectList[ixA]; objB = objectList[ixB];
                        if (objA.Equals(objB)) continue;
 
                        if (objB.Bounds.Left > objA.Bounds.Right) break;    // objB and all subsequent are too far right
                        if (objB.Bounds.Right < objA.Bounds.Left) continue; // objB is too far left
                        if (objB.Bounds.Bottom < objA.Bounds.Top) continue; // objB is too far above
                        if (objB.Bounds.Top > objA.Bounds.Bottom) continue; // objB is too far below
 
                        // Rectangle collision!
                        if (!usePixelCollision) { collisions.Add(new Tuple<CollisionObject, CollisionObject>(objA, objB)); continue; }
 
 
                        if (objA.Bounds.Top > objB.Bounds.Top)
                        {
                                colRecA = new Rectangle(objB.Bounds.Left - objA.Bounds.Left, 0,
                                        objA.Bounds.Right - objB.Bounds.Left, objB.Bounds.Bottom - objA.Bounds.Top);
                                offsetB = new Point(0, objA.Bounds.Top - objB.Bounds.Top);
                        }
                        else
                        {
                                colRecA = new Rectangle(objB.Bounds.Left - objA.Bounds.Left, objB.Bounds.Top - objA.Bounds.Top,
                                        objA.Bounds.Right - objB.Bounds.Left, objA.Bounds.Bottom - objB.Bounds.Top);
                                offsetB = new Point(0, 0);
                        }
                        Intersection.Add(new Rectangle(colRecA.X + objA.Bounds.Left, colRecA.Y + objA.Bounds.Y, colRecA.Width, colRecA.Height));
 
                        // Detect pixel collision
                        if (colRecA.Height == 0 || colRecA.Width == 0) continue;
                        if (objA.UseBorderCollision &amp;&amp; objB.UseBorderCollision)
                        {
                                // Checking the border of the intercept rectangle - sorted by computational expense
 
                                // upper border
                                int indexOffsetA = colRecA.X + colRecA.Y * objA.Texture.Width, indexOffsetB = offsetB.X + offsetB.Y * objB.Texture.Width;
                                for (int x = 0; x < colRecA.Width; x++)
                                        if (objA.colors[indexOffsetA + x].A >= CollisionAlpha &amp;&amp;
                                                objB.colors[indexOffsetB + x].A >= CollisionAlpha)
                                                goto Collision;
 
                                // lower border
                                indexOffsetA = colRecA.X + (colRecA.Y + colRecA.Height - 1) * objA.Texture.Width;
                                indexOffsetB = offsetB.X + (offsetB.Y + colRecA.Height - 1) * objB.Texture.Width;
                                for (int x = 0; x < colRecA.Width; x++)
                                        if (objA.colors[indexOffsetA + x].A >= CollisionAlpha &amp;&amp;
                                                objB.colors[indexOffsetB + x].A >= CollisionAlpha)
                                                goto Collision;
 
                                // left border
                                for (int y = 0; y < colRecA.Height; y++)
                                        if (objA.colors[y * objA.Texture.Width].A >= CollisionAlpha &amp;&amp;
                                                objB.colors[y * objB.Texture.Width].A >= CollisionAlpha)
                                                goto Collision;
 
                                // right border
                                for (int y = 0; y < colRecA.Height; y++)
                                        if (objA.colors[colRecA.X + y * objA.Texture.Width].A >= CollisionAlpha &amp;&amp;
                                                objB.colors[offsetB.X + y * objB.Texture.Width].A >= CollisionAlpha)
                                                goto Collision;
                        }
                        else
                        {
                                // checking the whole rectangle
                                int indexOffsetA, indexOffsetB; // storing the offset in the color array for less compute intensive multiplications
                                for (int y = 0; y < colRecA.Height; y++)
                                {
                                        indexOffsetA = colRecA.X + (colRecA.Y + y) * objA.Texture.Width;
                                        indexOffsetB = offsetB.X + (offsetB.Y + y) * objB.Texture.Width;
                                        for (int x = 0; x < colRecA.Width; x++)
                                        {
                                                if (objA.colors[indexOffsetA + x].A >= CollisionAlpha &amp;&amp;
                                                        objB.colors[indexOffsetB + x].A >= CollisionAlpha)
                                                        goto Collision;
                                        }
                                }
 
                                //for (int x = 0; x < colRec.Width; x++)
                                //    for (int y = 0; y < colRec.Height; y++)
                                //        if (a.colors[colRec.X + x + (colRec.Y + y) * a.Texture.Width].A >= CollisionAlpha &amp;&amp;
                                //            b.colors[offset.X + x + (offset.Y + y) * b.Texture.Width].A >= CollisionAlpha)
                                //        {
                                //            collision = true; break;
                                //        }
                        }
 
                        continue;
                Collision: collisions.Add(new Tuple<CollisionObject, CollisionObject>(objA, objB));
                }
 
        return collisions;
}
 

After the deklaration of the collisions list for the results, the list for the green intersection boxes are cleared. Than I declare the objectList and sort it. This can be done, because the class CollisionObject implements the interface IEnumerable<CollisionObject> which is implicit integrated by the method IComparable<CollisionObject>.CompareTo(CollisionObject). Such a comparer method can return three results. If the object is smaler than the other, than it has to return a number, smaller than 0. If the object has the same size/value/whatever, the method returns 0 or else a number bigger than 0 (the object is bigger than the other). It is not nessesary to implement the operator < and >. There is also no sence to check for the Y-value or something else. Futher details on this later.

The next variables are declared before the loop starting, in order to avoid multiply memory reservation.

Eyery object have to check a collision with eyery other object. Really? Lets check this on an example:
  • A {X:50 Y:50 Width:30 Height:100}
  • B {X:60 Y:90 Width:30 Height:100}
  • C {X:75 Y:60 Width:30 Height:100}
  • D {X:100 Y:50 Width:30 Height:100}
  • E {X:150 Y:50 Width:30 Height:100}
This list is sorted by the X value of the objects. To let it easy - it's also the order of their names. If we want to check eyery object with every object, than we could do it like this:
Code:
 
// bad solution!
foreach(CollisionObject a in objectList)
     foreach(CollisionObject b in objectList)
          {
               // checking for collision
          }
 

This would work, but it would end into 25 checks:
A-A, A-B, A-C, A-D, A-E, B-A, B-B, B-C, B-D, B-E, C-A, C-B, C-C, C-D, C-E, D-A, D-B, D-C, D-D, D-E, E-A, E-B, E-C, E-D, E-E.
Every object is checked with eyery other object twice plus twice with itself. This is why I use the Index and check for this combinations only:
A-B, A-C, A-D, A-E, B-C, B-D, B-E, C-D, C-E, D-E
This results in just 10 checks. And my code can more!

The two CollisionObject, which have to be checked, have the local name objA and objB. If they are equal, the loop will continue with the next entry. In the next step, you will see the magic of an sorted list: If objB is too far right, then all subsequent objects are also too far right - so I can break the inner loop. This will result in this 8 checks: A-B, A-C, A-D, B-C, B-D, C-D, C-E, D-E. Consider the amount of checks which can be saved with much more objects. The costs are the checks for the sorting of the list, but this should be done very efficent and fast.

There are three other possibilities to miss an intersection: objB is too far left/above or below. But as you can see B has a Y of 90 and C a Y of 60. The 90 of B can not say anything of the Y of the following. And the sorting by Y after sorting by X is not possible, if the X value of both objects are not the same. So we have to continue to the next entry. But the first break will save us a lot of calculations.

Rectangle collision
At this point, there is a rectangle collision. If the pixel collision is not wanted, than we add the result and continue with the next entry. Otherwise we have to calculate the intersection. You can see this rectangle (colRecA) as a lime colored rectangle in the example picture above. We have to translate the intersection area to the texture area of the object objA and objB. The intersection on the texture on object objA begins at X and Y of colRecA and has its width and height. The intersection on the texture of the object objB starts at the X and Y value of the point offsetB.

The static List<Rectangle> holds the intersection rectangle to draw it in the example. You'll may not need it in your projects.

Detect pixel collision
The test, if the width or heigth of colRec is 0 is a funny kind of a thing. It happens, when the two objects are overlapping by one pixel. But I can not just increase the width and height of the intersection rectangle - this would result in an error.

If both of the objects have rectangle shape parts only, than we can use a shortcut. We check just the border of the intersection rectangle and not eyery pixel. This will save a lot. But it works not for textures with diagonal shape parts or stuff like that. The checking order is sorted by the computational expense. Note: Multiplications are not as nice as additions.

If one of the texture can not be checked the short way, we have to check every single pixel of the intersection rectangle. As you can see, I have swap the x and the y coordinate to save multiplications. The commented block below is an old solution without goto. There are many haters of using goto, but this is an good example for how it can be very usefull. I can break two loops at one time and jump to the code below where Collision stands. To avoid execution if there is no collision, I have to use continue in front of it.


How I use it in the example

Code:
 
private void CheckForCollisions()
{
        foreach (CollisionObject star in Stars) star.Tint = Color.White;
        SelectedStar.Tint = SelectedStarColor;
 
        foreach (Tuple<CollisionObject, CollisionObject> collision in CollisionObject.CheckForCollisions(Stars, true))
        {
                collision.Item1.Tint = Color.Red;
                collision.Item2.Tint = Color.Blue;
        }
 
        StarPositionsChanged = false;
}
 

This method is called in the Update method if the boolean StarPositionsChanged is true. It becomes true, if the position of a CollisionObject has changed. So I have to check for collisions not 60 times a secound even there was no movement. I would recommand this for your projects as well.

So... Do you have any questions left? Write! :)


Greetings,
Magony

_________________
Bei Fragen, Lob, Kritik, Vorschläge, hilfreiche Hinweise oder Alternativvorschläge: Beitrag, neues Thema oder PN.
Für Dinge die diskutiert werden sollten, bitte neues Thema im jeweiligen Forum.
Wenn du nicht weißt wohin: Forum Unsortiert.


So 23. Mär 2014, 14:44
Diesen Beitrag melden
Profil Website besuchen
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Auf das Thema antworten   [ 1 Beitrag ] 

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste


Du darfst neue Themen in diesem Forum erstellen.
Du darfst Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software
Deutsche Übersetzung durch phpBB.de

Impressum