As has been noted in several posts, the Movement calculations in our system can be rather expensive, enough to slow the system down, and create noteable pauses when we move on a tile.
Much of this is due to repeated calls to our PathFinding.
For example: Our pathfinding is called for each potential move tiles once to determine if there is a path, and again to determine the length of that path.
Within MoveAction, we currenntly have these checks to Pathfinding for each tile being tested:
if (!Pathfinding.Instance.IsWalkableGridPosition(testGridPosition))
{
continue;
}
if (!Pathfinding.Instance.HasPath(unitGridPosition, testGridPosition))
{
continue;
}
int pathfindingDistanceMultiplier = 10;
if (Pathfinding.Instance.GetPathLength(unitGridPosition, testGridPosition) > maxMoveDistance * pathfindingDistanceMultiplier)
{
// Path length is too long
continue;
}
Now the first call is relatively cheap, and simply polls the Pathfinding to lookup the grid position in question and return it’s status as unwalkable…
the second call, on the other hand, causes us to calculate a path to the testGridPosition…
and the third call causes us to do this again…
We could put all three of these things into one call to PathFinding with a couple of quick changes to the start of Pathfinding.FindPath:
///After getting endNode from the gridSystem
if (!endNode.IsWalkable())
{
pathLength=Int32.MaxValue;
return null;
}
///Rest of Pathfinding method until the end, after no path has been found:
pathLength=Int32.MaxValue;
return null;
Now at this point, we don’t need the first two checks in MoveAction, because they will be factored into the result of GetPathLength. If the path is not walkable, the returned length will be Int32.MaxValue, a value so large, it will fail the length test. If the system can’t find a path, again that length will be Int32.MaxValue. This means we only need
int pathfindingDistanceMultiplier = 10;
if (Pathfinding.Instance.GetPathLength(unitGridPosition, testGridPosition) > maxMoveDistance * pathfindingDistanceMultiplier)
{
// Path length is too long
continue;
}
With that optimization out of the way, we’re still calculating a path again when we click to move. I’m of the mind that for any given tile, a path should only be calculated once, and once only. How can we achieve this in the most efficient way possible?
My solution is to cache calculated paths within the PathNodes themselves.
This will require some small changes in a few spots…
We’ll start in PathNode… we need a List of GridPositions that is the most recently cached path, and we need a getter and setter:
private List<GridPosition> cachedPath = new List<GridPosition>();
public void SetCachedPath(List<GridPosition> path) => cachedPath = path;
public List<GridPosition> GetCachedPath() => cachedPath;
Now in PathFinding, we need to set this CachedPath when we return a path. The best place for this is at the end of CalculatePath, where we breadcrumb our way from the end position back to the start position, and then reverse the list to return to the finder:
List<GridPosition> gridPositionList = new List<GridPosition>();
foreach (PathNode pathNode in pathNodeList)
{
gridPositionList.Add(pathNode.GetGridPosition());
}
endNode.SetCachedPath(gridPositionList);
return gridPositionList;
Ideally, we should never be asking for a cached path unless it’s been properly added to the IsValidGridPositionList, so strictly speaking we shouldn’t need to clear the cached paths between unit turns. We can, however, do so. Here are two methods, one if you are using a single floor, and another for multi-floor to clear all cached positions:
public void ClearAllCachedPathsSingleFloor()
{
if(gridSystem==null) return; //prevents race conditions
for(int x=0;x<width;x++)
{
for (int z = 0; z < height; z++)
{
GetNode(x,z).SetCachedPath(new List<GridPosition>());
}
}
}
public void ClearAllCachedPathsMultiFloor()
{
if (gridSystemList == null) return; //prevents race conditions
for (int floor = 0;floor<floorAmount;floor++)
{
for (int x=0;x < width;x++)
{
for (int z = 0; z < height; z++)
{
GetNode(x,z,floor).SetCachedPath(new List<GridPosition>());
}
}
}
}
You can call the appropriate method in UnitActionSystem when the SelectedUnit changes. The system appears to work just fine with or without this clearing of the caches due to the changes made in MoveAction.
Next, we’ll need a way to get the Cached Path…
Again, in Pathfinding.cs:
public List<GridPosition> GetCachedPath(GridPosition position)
{
if (!IsWalkableGridPosition(position)) return new List<GridPosition>();
return GetNode(position.x, position.z, position.floor).GetCachedPath();
}
If you’re single floor, return the position.floor.
Finally, in MoveAction, where we’ll actually use the Path, we’ll get our list from GetCachedPath instead of Finding a new path:
List<GridPosition>
pathGridPositionList = //Pathfinding.Instance.FindPath(unit.GetGridPosition(), gridPosition, out int pathLength);
Pathfinding.Instance.GetCachedPath(gridPosition);
And that’s it. We are now calling Pathfinding on any given position once per the Unit selecting MoveAction.