Memory Optimization #6
Description
Thank you for this project. It's really great. I'm using it in my Never Split the Party game.
Unfortunately, it's doing a ton of unnecessary memory allocation. Something like 30k of memory for each path find in my usage. With several enemies updating their paths often it was often allocating 150k per frame!
Here's how I optimized it.
Change Point from a class to a struct. Value types are allocated on stack instead of heap. They also do better in arrays since there's no reference operation.
In PathFinding._ImpFindPath make openSet and closedSet static and just clear them instead of recreating them. That makes them non-thread safe but I'm not doing anything fancy with threads I don't think.
Changed Grid.GetNeighbours to be an IEnumerable.
`
///
/// Get all the neighbors of a given tile in the grid.
///
/// Node to get neighbors for.
/// List of node neighbors.
public IEnumerable GetNeighbours(Node node, Pathfinding.DistanceType distanceType)
{
int x = 0, y = 0;
switch (distanceType)
{
case Pathfinding.DistanceType.Manhattan:
y = 0;
for (x = -1; x <= 1; ++x)
{
var neighbor = AddNodeNeighbour(x, y, node);
if (neighbor != null)
yield return neighbor;
}
x = 0;
for (y = -1; y <= 1; ++y)
{
var neighbor = AddNodeNeighbour(x, y, node);
if (neighbor != null)
yield return neighbor;
}
break;
case Pathfinding.DistanceType.Euclidean:
for (x = -1; x <= 1; x++)
{
for (y = -1; y <= 1; y++)
{
var neighbor = AddNodeNeighbour(x, y, node);
if (neighbor != null)
yield return neighbor;
}
}
break;
}
}
/// <summary>
/// Adds the node neighbour.
/// </summary>
/// <returns><c>true</c>, if node neighbour was added, <c>false</c> otherwise.</returns>
/// <param name="x">The x coordinate.</param>
/// <param name="y">The y coordinate.</param>
/// <param name="node">Node.</param>
/// <param name="neighbours">Neighbours.</param>
Node AddNodeNeighbour(int x, int y, Node node)
{
if (x == 0 && y == 0)
return null;
int checkX = node.gridX + x;
int checkY = node.gridY + y;
if (checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)
{
return nodes[checkX, checkY];
}
return null;
}
`
I might convert _ImpFindPath to be an IEnumerable as well.