Per color collision is really expensive - can my approach be improved?

Question

I've been working on adding a color based collision component which takes a list of colors and checks to see if an object is colliding with any of them. However, the operation seems to be extremely expensive, even though I am only colliding 2 objects. I think something is wrong with my TestCollision method but, I can't find the error.

    public List<Color> Colors = new List<Color>();
    private Texture2D _texture;
    public Texture2D Texture
    {
        get { return _texture; }
        set 
        {
            _texture = value;
            ColorData = _texture.GetData();
        }
    }
    public Color[,] ColorData { get; private set; }

    public PerColorCollision(Entity e, string name) : base(e, name)
    {
        ColorsColliedWith = new List<Color>();
    }

    public PerColorCollision(Entity e, string name, Texture2D texture) : base(e, name)
    {
        Texture = texture;
        ColorsColliedWith = new List<Color>();
    }

    public List<Color> ColorsColliedWith { get; private set; }

      public override bool TestCollision(Entity e)
    {

        if (BoundingBox.Intersects(e.GetComponent<Collision>().BoundingBox))
        {
            PerColorCollision ppc = e.GetComponent<PerColorCollision>();


            //Get the area of intersection
            var intersection = new Rectangle();
            intersection.Y = Math.Max(BoundingBox.Top, ppc.BoundingBox.Top);
            intersection.Height = Math.Min(BoundingBox.Bottom, ppc.BoundingBox.Bottom) -
                                  intersection.Y;
            intersection.X = Math.Max(BoundingBox.Left, ppc.BoundingBox.Left);
            intersection.Width = Math.Min(BoundingBox.Right, ppc.BoundingBox.Right) -
                                 intersection.X;



            foreach (var color in Colors)
            {
                for (int y = intersection.Y; y < intersection.Bottom; y++)
                {
                    for (int x = intersection.X; x < intersection.Right; x++)
                    {
                        //We subtract our bounding boxes to set the position back to relative, since the area of intersection would be the at the absolute positions
                        Color color1 = ColorData[(x - BoundingBox.Left), (y - BoundingBox.Top)];
                        Color color2 =
                            ppc.ColorData[
                                (x - ppc.BoundingBox.Left),
                                (y - ppc.BoundingBox.Top)];
                        if (color1.A != 0 && color2 == color)
                        {
                            ColorsColliedWith.Add(color);
                            break;
                        }
                    }
                    if (ColorsColliedWith.Contains(color))
                        break;
                }
            }
        }

        if (ColorsColliedWith.Count > 0)
            return true;
        return false;
    }

    public override void Update()
    {
        ColorsColliedWith.Clear();
        base.Update();
    }

In the base.Update it runs the TestCollision method against all of the partners in Collision.Partners. Is there any other optimization that I can do?

Answer 1

Color based per pixel collision is very expensive, but I assume you have a good reason for not going for something like combining 2d boxes/circles or SAT which can only do convex shapes.

The main things you can do to speed things up are lessening your number checks and/or lessening the time a check takes. The former you've already done about as well as you can for per pixel collision so we'll focus on the latter.

Currently for an intersected area, you make a check for the intersecting width * the intersecting height * the number of individual colors being checked for. Even with only a couple objects to check collision between, that's going to add up very fast.

The first thing would be to greatly reduce the GetComponent's called. As is you're getting three things from your Entity every pixel a number of times equal to the number of colors you're checking for! Pulling out of an array is quick, like you're doing with color1, but when you have to go get the array, left, and top every time you're going to find yourself burning a lot of unnecessary cycles. Unless the component is moving while you are in this loop, you know the left and top of the bounding box will remain constant. The array also shouldn't change unless the sprite is changing on another thread somehow while you're in this loop. Instead of getting them every time, get them at the top and store them in variables, then use those variables to get color 2 just like how you're doing for color1.

At this point you should test your code out again as this is probably going to be your biggest gain. However, there is always more optimization you can do. What really matters is how much you need, but if at this point the collision is not acceptable for your needs, then continue on down.

One very quick thing that may or may not gain you much is the Contains check you are doing once per row. Contains isn't the most optimal way to early out of the second loop, considering any situation that triggers the break in the inner loop will trigger the outer and that's the only place it changes within. It will only ever (in this function anyway) get one thing added to it before it breaks out so it shouldn't really be too costly. But if you've got more things in it, doing that repeatedly is going to add up somewhat. You can probably replace it with something as simple as a boolean you turn true when you find a match should you want to/have no reason not to axe it.

From here there are other things you can do, but they start to get to be more of a pain to implement. Other areas to look at would be stopping checking colors themselves, thus bringing 4 compares down to 1; and/or limiting yourself to a finite pallet (allowing you to pull various constant time shenanigans).

If you were to have something like a 256 color pallet for instance, you could store a second array of the sprite with which of those 256 indices it's color falls on. Each one would be a single byte keeping the size fairly small. From there you'd just have to do what you're currently doing with that array instead of the actual colors, which would keep you from having to check the RGBA values independently.

If you wanted to do this without giving up color variations, you could use a method to hash the RGBA values down to a total 0-255. While each number in that case would represent a range of colors instead of a single one, depending on your needs such may prove sufficient.

If you could get your number of discrete colors for purposes of collision down to something like 32 or 64, you could even use bit flags to check for all the colors you're looking for in a single check no matter how many you seek...

In all these cases keep in mind that you should only optimize until it works sufficiently for your purposes. There will nearly always be more you can do to optimize, given what tradeoffs you're willing to make. Such is a trap to be avoided, as you usually get diminishing returns quickly. If you use System.Diagnostics.Stopwatch you can time sections of your code which is excellent for figuring out what part of your code is actually causing issue. Few things are worse than spending a bunch of time and heartache making a section run really tight only to find that it still has to wait on other bottlenecks which are taking far longer.

Answer 2

Your worst case test at the moment is where there's no collision at all, so I'd concentrate on that first. For example maybe you know from your map data approximately where the edge of the road is and can test to see if you're close to the edge without looking at pixels? Maybe if all 4 corners of the car are on the road then you don't need to test the rest of it?

I suspect nesting those loops differently will help significantly in many cases too. Most notably if you're colliding with the last colour in the array then you'll have to check the whole rectangle several times to find that out currently. Moving the outer loop round the colours to be the inner loop would speed things up significantly there.

You also may (or may not) find that swapping the nesting of the x and y loops will help. I'm not sure what the memory layout of arrays in C# is, so you'll have to profile to see which is best.

You could also pre-process the car sprites to find a reduced bounding box that only covers the opaque pixels.