Caching Paths

Unity Courses Show
,
#1

The FindPath code is quite expensive and is called twice per Valid Grid Position In the MoveAction and then again when the user (or EnemyAI) decides to move. A couple of people have already suggested combining the HasPath and GetPath Length calls into a single call but, we could go a step further and cache this value.

private Dictionary<string, List<GridPosition>> pathCache = new Dictionary<string, List<GridPosition>>();

Then at the start of GetValidGridPositionList:

pathCache.Clear();

Then when we check Has Path:

List<GridPosition> pathGridPositionList = Pathfinding.Instance.FindPath(unitGridPosition, testGridPosition, out int pathLength);

                if (pathLength == 0)
                {
                    // no path found
                    continue;
                }

                int pathFindingDistanceMultiplier = 10;
                if (pathLength > maxMoveDistance * pathFindingDistanceMultiplier)
                {
                    // point is too far away
                    continue;
                }

                pathCache.Add(testGridPosition.ToString(), pathGridPositionList);

and finally in TakeAction:

List<GridPosition> pathGridPositionList;
        if (pathCache.ContainsKey(gridPosition.ToString()))
        {
            pathGridPositionList = pathCache[gridPosition.ToString()];
        } else
        {
            pathGridPositionList = Pathfinding.Instance.FindPath(unit.GetGridPosition(), gridPosition, out int pathLength);
        }

I think this can be optimised further by checking if the player or enemy has moved grid position inbetween calls to GetValidActionGridPositionList for the MoveAction.

2 Likes
#2

Update: Using the profiler I get a 4x performance boost on the Unit.Update() method just by switching the open and closed lists from Lists to Dictionaries.

3 Likes
#3

Thanks for sharing. As soon as I saw where the code was heading I was hoping caching would be addressed!

I’m going to keep this handy in case I experience performance problems as the game gets more complex.

#4

These optimisations seem really interesting but I don’t really understand where you’re putting this code in relation to what’s being done in the course - for those of us on the more beginner side, is it possible for you to elaborate a little more? Especially on how you change the open list to a dictionary, for example.

#5

HI Monkey in the FindPath method the open and closed lists can be replaced with dictionaries:

Dictionary<PathNode, PathNode> openList = new Dictionary<PathNode, PathNode>();
Dictionary<PathNode, int> closedList = new Dictionary<PathNode, int>();

These offer a much quicker look up time than lists so we can do things like:

closedList.ContainsKey(neighbourNode)

to check if a node is already on a list.

These don’t seem like a big difference and I thought myself this would be premature micro optimisation but, the profiler tells a different story. Since the bulk of this game processing time is in this function it makes a big difference.

1 Like
#6

how much of an optimization did you see?

#7

I had too much fun with this.
I started caching ALL calculated paths.

    private Dictionary<string, CalculatedPath> calculatedPathDictionary;

    private struct CalculatedPath
    {
        public int length;
        public List<GridPosition> gridPositionList;
    }

    public bool HasPath(GridPosition startGridPosition, GridPosition endGridPosition) => FindPath(startGridPosition, endGridPosition, out int pathLength) != null;

    private string CreateCalculatedDictionaryKey(GridPosition startGridPosition, GridPosition endGridPosition) => startGridPosition.ToString() + endGridPosition.ToString();

    public int GetPathLength(GridPosition startGridPosition, GridPosition endGridPosition)
    {
        if (HasPath(startGridPosition, endGridPosition))
        {
            string pathKey = CreateCalculatedDictionaryKey(startGridPosition, endGridPosition);
            return calculatedPathDictionary[pathKey].length;
        }
        Debug.Log("GetPathLength returned 0");
        return 0;
    }


    public List<GridPosition> FindPath(GridPosition startGridPosition, GridPosition endGridPosition, out int pathLength)
    {
        string calculatedDictionaryKey = CreateCalculatedDictionaryKey(startGridPosition, endGridPosition);
        if (calculatedPathDictionary.ContainsKey(calculatedDictionaryKey))
        {
            CalculatedPath calculatedPath = calculatedPathDictionary[calculatedDictionaryKey];
            pathLength = calculatedPath.length;
            return calculatedPath.gridPositionList;
        }

        // main routine here
   }

I see how there could be a memory problem when there are too many gridPositions on the level though.

Privacy & Terms