Near-Pixel 2D collision using point lists
Work-in-progress as I'm creating the blog site while adding the content
In this article, I'll describe the method I'm using in my own game projects.
It breaks down as this:
- For each pixel in the image add its local space coordinate to the CollisionMap; a list of points.
- 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.
- When testing for collisions between two entities, we then compare the distance of the points against each other's maps.
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;
}
}