# Collision code is creating allocations on heap every frame

I've been profiling my app trying to reduce allocations and garbage collection during gameplay.

The following code is SAT collision which i use for hill/ramp collisions, when the player is standing on a hill the profiler is saying this code is creating 5KB of Microsoft.Xna.FrameWork.Vector2[] allocations per second (88 bytes per frame).

Vector2 is a struct so I'm a little confused as to what is going on. Any help sourcing where its coming from appreciated...

The ramp collision Method (where the profiler is pointing):

/// <summary>
/// Detects and resolves the collision between two shapes
/// </summary>
private void HandleRampCollision(Shape ramp)
{
axis = new Vector2[playerShape.Axes.Length + ramp.Axes.Length];

playerShape.Axes.CopyTo(axis, 0);
ramp.Axes.CopyTo(axis, playerShape.Axes.Length);

float intervalWidth = 0;
float minimumDistance = float.MaxValue;

Vector2 resolutionAxis = Vector2.Zero;

for (int i = 0; i < axis.Length; i++)
{
// Test to see if this axis seperates shapes A and B.
if (AxisSeperatesShapes(axis[i], ramp, playerShape, out intervalWidth))
{
// We found a seperating axis! No need to carry on.
return;
}
else
{
intervalWidth *= 1.01f;

// Find the shortest distance needed to move to resolve collision.
if (intervalWidth * intervalWidth < minimumDistance * minimumDistance)
{
minimumDistance = intervalWidth;
resolutionAxis = axis[i] * minimumDistance;
}
}
}

// Make sure we are trying to push shape B
// away and not pull it into shape A.
if (resolutionAxis != Vector2.Zero)
{
isOnGround = true;
Vector2 direction;

direction = new Vector2(ramp.Center.X,
ramp.Center.Y) - playerShape.Center;

if (Vector2.Dot(direction, resolutionAxis) < 0.0f)
{
resolutionAxis = -resolutionAxis;
}

if (velocity.Y > 0 && resolutionAxis.Y > 0)
{
velocity.Y = 0;
}

if (playerShape.CanBePushed == true && ramp.CanBePushed == false)
{
playerShape.Position -= new Vector2(0, Math.Abs(resolutionAxis.Y));
}
else if (playerShape.CanBePushed == false && ramp.CanBePushed == true)
{
ramp.Position += resolutionAxis;
}
else
{
resolutionAxis /= 2.0f;
playerShape.Position -= resolutionAxis;
ramp.Position += resolutionAxis;
}

if (rampType == 1)
{
Position = new Vector2(playerShape.Position.X + (BoundingRectangle.Width), playerShape.Position.Y);
}
else if (rampType == 2)
{
Position = new Vector2(playerShape.Position.X - (BoundingRectangle.Width), playerShape.Position.Y);
}
}
}


The Axis Separates Shapes Method:

/// <summary>
/// Tests if an axis seperates two shapes.
/// </summary>
private bool AxisSeperatesShapes(Vector2 axis, Shape A, Shape B, out float intervalWidth)
{
float minA = 0, maxA = 0;
float minB = 0, maxB = 0;

A.ProjectOntoAxis(axis, out minA, out maxA);
B.ProjectOntoAxis(axis, out minB, out maxB);

if (minB > maxA || minA > maxB)
{
intervalWidth = 0;
return true;
}

float d0 = maxA - minB;
float d1 = maxB - minA;

intervalWidth = MathHelper.Min(d0, d1);
return false;
}


Shape Class (used only for hills and contains the project onto axis method):

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace NewGame
{
public class Shape
{
protected Vector2[] vertices;
protected Vector2[] temporaryVertices;
protected Vector2[] verts;

// We only need to update certain aspects of the shape if it
// has moved. So we store an old position to compare the new position to.
protected Vector2 cachedPosition = Vector2.Zero;

protected int width;
protected int height;

protected Vector2 origin = Vector2.Zero;
protected Rectangle rectangle;

public Color Color = Color.White;
public bool CanBePushed = true;

/// <summary>
/// The position of the shape.
/// </summary>
public virtual Vector2 Position { get; set; }
/// <summary>
/// The center of the shape
/// </summary>
public Vector2 Center
{
get { return origin + Position; }
}
/// <summary>
/// A rectangle containing the shape.
/// </summary>
public Rectangle Rectangle
{
get
{
return new Rectangle((int)(rectangle.X + Position.X),
(int)(rectangle.Y + Position.Y),
width,
height);
}

}

/// <summary>
/// The axis used when doing SAT tests.
/// </summary>

protected Shape()
{
Axes = new Vector2[0];
}

/// <summary>
/// Constructs a new shape.
/// </summary>
/// <param name="vertices">The vertices that will define the shape (In CW order).
/// (The shape should be created at origin and moved using Position)</param>
public Shape(Vector2[] vertices)
{
if (vertices.Length < 2)
{
throw new ArgumentException("A shape must have at least 2 vertices!");
}

// We clone the collections to avoid strange referencing issues.
this.vertices = new Vector2[vertices.Length];
this.temporaryVertices = new Vector2[vertices.Length];

Axes = new Vector2[vertices.Length];

int minX = int.MaxValue; int minY = int.MaxValue;
int maxX = int.MinValue; int maxY = int.MinValue;

for (int i = 0; i < vertices.Length; i++)
{
this.vertices[i] = vertices[i];
this.temporaryVertices[i] = vertices[i];

origin += vertices[i];

minX = (int)Math.Min(minX, vertices[i].X);
maxX = (int)Math.Max(maxX, vertices[i].X);

minY = (int)Math.Min(minY, vertices[i].Y);
maxY = (int)Math.Max(maxY, vertices[i].Y);
}

origin /= (float)(vertices.Length);

CanBePushed = true;

width = maxX - minX;
height = maxY - minY;

rectangle.X = minX;
rectangle.Y = minY;
rectangle.Width = width;
rectangle.Height = height;

CalculateProjectionAxes();
}

protected virtual void CalculateProjectionAxes()
{
int nextIndex = 0;

for (int i = 0; i < vertices.Length; i++)
{
nextIndex = i + 1;

if (nextIndex >= vertices.Length)
{
nextIndex = 0;
}

Axes[i] = Vector2.Normalize(vertices[i] - vertices[nextIndex]);
// Find the normal of the seperation axis.
Axes[i] = new Vector2(-Axes[i].Y, Axes[i].X);
}
}

public static Shape CreateRectangle(int width, int height)
{
return new Shape(new Vector2[]
{
Vector2.Zero,
new Vector2(width, 0),
new Vector2(width, height),
new Vector2(0, height),
});
}

public static Shape CreateRightTriangle(int width, int height)
{
return new Shape(new Vector2[]
{
new Vector2(width, height),  // Bottom Right Vertex
new Vector2(0, height),      // Bottom Left Vertex
new Vector2(0, 0),           // Top Left Vertex
});
}
public static Shape CreateLeftTriangle(int width, int height)
{
return new Shape(new Vector2[]
{
new Vector2(0, height),      // Bottom Left Vertex
new Vector2(width, height),  // Bottom Right Vertex
new Vector2(width, 0),       // Top Right Vertex
});
}

public static Shape CreateLeftTriangleBS(int width, int height)
{
return new Shape(new Vector2[]
{
new Vector2(0, height),  // Bottom Left Vertex
new Vector2(width, height),      // Bottom Right Vertex
new Vector2(width, height / 2),           // Top Right Vertex
});
}
public static Shape CreateLeftTriangleTS(int width, int height)
{
return new Shape(new Vector2[]
{
new Vector2(0, height / 2),      // Bottom Left Vertex
new Vector2(width, height / 2),  // Bottom Right Vertex
new Vector2(width, 0),       // Top Right Vertex
});
}

public static Shape CreateRightTriangleBS(int width, int height)
{
return new Shape(new Vector2[]
{
new Vector2(width, height),  // Bottom Right Vertex
new Vector2(0, height),      // Bottom Left Vertex
new Vector2(0, height / 2),           // Top Left Vertex
});
}

public static Shape CreateRightTriangleTS(int width, int height)
{
return new Shape(new Vector2[]
{
new Vector2(width, height / 2),  // Bottom Right Vertex
new Vector2(0, height / 2),      // Bottom Left Vertex
new Vector2(0, 0),           // Top Left Vertex
});
}

/// <summary>
/// Projects the shape onto an axis.
/// </summary>
/// <param name="axis">The axis to project the shape onto</param>
/// <param name="min">The minimum projection on the axis</param>
/// <param name="max">The maximum projection on the axis</param>
public virtual void ProjectOntoAxis(Vector2 axis, out float min, out float max)
{
verts = GetVertices();

float interval = Vector2.Dot(axis, verts[0]);
min = max = interval;

for (int i = 0; i < verts.Length; i++)
{
interval = Vector2.Dot(axis, verts[i]);

if (interval < min)
{
min = interval;
}
else if (interval > max)
{
max = interval;
}
}
}

/// <summary>
/// Returns the translated vertices of the shape.
/// </summary>
public Vector2[] GetVertices()
{
if (Vector2.DistanceSquared(cachedPosition, Position) < float.Epsilon * float.Epsilon)
{
return temporaryVertices;
}
else
{
cachedPosition = Position;

for (int i = 0; i < vertices.Length; i++)
{
temporaryVertices[i] = vertices[i] + Position;
}

return temporaryVertices;
}
}
}
}

• i'm no C# expert here but should't new do just that, allocate some memory (google searching points out to this) ? – Raxvan Dec 12 '16 at 17:17
• I create structs (Vector2 and Rectangle) all over my code in update/draw and its not allocating anything to the heap. In my experience i only need to worry about 'new' if its a class or an object etc... not structs. The code is only making allocations when a hill collision is performed. – Graham Dec 12 '16 at 17:23
• axis = new Vector2[...] that looks like an array. In any case try to avoid using new keyword in general, allocate everything that you have to during loading or once when needed. – Raxvan Dec 12 '16 at 17:38
• I just checked and Axes = new Vector2[] is only created in the shape class constructor and 'new Shape' is only called in the level & player constructors so its allocating at creation and not per frame like is happening. Whilst I agree its best to keep 'new' to a minimum it can cause more harm than good and make code unreadable if you go overboard. My assumption is that something is getting boxed in my case. – Graham Dec 12 '16 at 18:03
• Hold on, you have "axis = new Vector2[playerShape.Axes.Length + ramp.Axes.Length]" in "The ramp collision Method (where the profiler is pointing)" - it's the very first line of it. – Maximus Minimus Dec 12 '16 at 21:49

Vector2 is a struct so I'm a little confused as to what is going on. Any help sourcing where its coming from appreciated...

Vector2 is a struct, and thus a value type. However you're not allocating a Vector2, you're allocating an array of them:

axis = new Vector2[playerShape.Axes.Length + ramp.Axes.Length];


Arrays are not value types and are thus allocated on the heap.

If you can allocate this array once, at the largest possible size you'll need, and simply overwrite it every time, that may alleviate your trouble.

• This was the problem indeed. I hadn't noticed that array being created every frame since I was sure it was something in the Shape class :/ – Graham Dec 12 '16 at 23:15

Problem was caused by this line:

axis = new Vector2[playerShape.Axes.Length + ramp.Axes.Length];


I fixed it by creating a pre calculated array in the constructor for each ramp and then re-using that array.

So if a ramp has 3 vertices and the player has 4 vertices an array for that ramp type would be:

Vector2[] axis = new Vector2[7]; // Creates array pre calculated in constructor


Thanks for the comments and help all.