Memory Optimization

[Bryan-Legend]

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.

[Bryan-Legend]

Whoops. Looks like I'm actually using the code from here: https://github.com/RonenNess/UnityUtils/tree/master/Controls/PathFinding/2dTileBasedPathFinding

Which explains the mystery point class.

[live627]

make openSet and closedSet static and just clear them instead of recreating them

But wouldn't that then create a race condition if multiple agents request a path at the same time?

[Bryan-Legend]

make openSet and closedSet static and just clear them instead of recreating them

But wouldn't that then create a race condition if multiple agents request a path at the same time?

Maybe, but in Unity the user game code is all single threaded and .net has protections against collections being modified. It would throw instead of freeze.