Near-Pixel 2D collision using point lists

Published on: 2024-07-09 19:09:10

In this article, I'll describe the method I'm using in my own game projects. It breaks down as this:
  1. For each pixel in the image add its local space coordinate to the CollisionMap; a list of points.
  2. Then we prune the list, removing the points deeply embedded inside the map, as other points in the outer edges would test for collision before reaching these anyway.

   public class CollisionMap
   {
       private static Dictionary precalculatedMaps = new Dictionary();

       [JsonIgnore]
       public int[,] Map { get; private set; }

       public CollisionMap(Texture2D texture)
       {
           // Check if we have precalculated the collision map for this texture
           if (!precalculatedMaps.ContainsKey(texture.Name))
           {
               this.Map = GenerateCollisionMap(texture, 24, 24);
               precalculatedMaps[texture.Name] = this;
           } else
           {
               this.Map = precalculatedMaps[texture.Name].Map;
           }
       }

       public int GetValueAt(int x, int y)
       {
           return Map[x, y];
       }

       //alternatively: private static int[,] GenerateCollisionMap(Color[] colorData, int collisionMapWidth, int collisionMapHeight)
       private static int[,] GenerateCollisionMap(Texture2D texture, int collisionMapWidth, int collisionMapHeight)
       {
           int[,] tempMap = new int[collisionMapWidth, collisionMapHeight];
           Color[] colorData = new Color[texture.Width * texture.Height];
           texture.GetData(colorData);

           // First pass to create the basic map
           for (int n = 0; n < colorData.Length; n++)
           {
               int x = n % texture.Width;
               int y = n / texture.Width;
               int mx = x * collisionMapWidth / texture.Width;
               int my = y * collisionMapWidth / texture.Height;
               bool mapClear = tempMap[mx, my] == 0;
               bool alphaMapVisible = colorData[n].A > 200;
               if (mapClear && alphaMapVisible)
               {
                   tempMap[mx, my] = 1;
               }
           }

           // Second pass to remove points that are embedded at least 3 points deep 
           // as collision is bound to trigger before reaching them anyway
           int[,] prunedMap = new int[collisionMapWidth, collisionMapWidth];

           // number of pixels needs to be surrounding to qualify removal. 
           // Padding of 4 means 4-pixel neighbours in all directions.
           int padding = 4; 
           for (int x = padding; x < collisionMapWidth - padding; x++)
           {
               for (int y = padding; y < collisionMapWidth - padding; y++)
               {
                   int sum = 0;
                   for (int tx = x - padding; tx <= x + padding; tx++)
                   {
                       for (int ty = y - padding; ty <= y + padding; ty++)
                       {
                           sum += tempMap[tx, ty];
                       }
                   }

                   // if the sum of this is (1+2*padding)*(1+2*padding) then we know that this point is deeply embedded and can be removed
                   prunedMap[x, y] = (sum == (1 + 2 * padding) * (1 + 2 * padding)) ? 0 : tempMap[x, y];
               }
           }

           return prunedMap;
       }
   }