A Pathfinding Coroutine

Unity Courses Show
,
#1

NOTE: This refactor is incomplete, and testing has yielded some critical issues. Further edits to follow, but it hit after midnight, so further edits will need to wait till at least tomorrow

A few students have inquired about ways of making the current pathfinding system introduced by @CodeMonkey faster, or at least a bit more responsive…

While there are a number of good A* pathfinding projects out there, I thought I’d take a crack at making a system that, while not technically faster, will allow the game to continue to be responsive as each character determines it’s moves (or for player characters as possible moves are displayed.

The first thing I determined is that we often find ourselves calculating several different paths… for example, when a player’s unit is selected, we go through each tile and determine if it has a valid path within the number of movement units or not. This can be lessened by only selecting units to test within a valid distance, but no matter if its 3x3 units or the whole grid, while the path is being calculated, the system is unresponsive. This is because Unity (outside of DOTS/ECS) runs on a single thread. This means that while the path is calculating, no other Updates can occur. You can see when this happens that the entire game freezes for a moment while paths are calculated and in the AI the best move is tallied…

In Unity, we can use Coroutines to perform tasks in the background while the game continues to run. There are some caveats, as Coroutines are actually running on the same thread as the game, so it’s important that Coroutines use discreet amounts of time slices to ensure that the game continues running as normal.

There are two ways we could go about this pathfinding… we could make all of the methods that allow us to calculate actions and AI into coroutines, as well as the pathfinding algorythm itself, so as the AI, for example, builds up the list of possible actions, we could do this in a coroutine and movements can be calculated as the decisions are being considered. The other possibility is to front load the pathfinding calculations and cache them, which would happen when the unit selection has changed. This method would use a coroutine to calculate every single destination with reference to the current unit’s position. This is the approach I intend to show with this post:

First, we need to make a small modification to the PathNode, which is where we will be storing our path information.

    private List<GridPosition> pathToStart = new List<GridPosition>();
    private int pathLength;

    public List<GridPosition> PathToTile => pathToStart;

    public void SetPathToStart(List<GridPosition> newPath)
    {
        pathToStart = newPath;
    }

    public void SetPathLength(int length) => pathLength = length;

    public int GetPathLength() => pathLength;

This is where we’ll be storing the path from the given location to the current start position, which is the GridPosition of the active unit.

We’ll be setting this in a special IEnumerator SeedAllPaths method, but we’ll get to that shortly.

The next thing we’ll need to do is to convert our FindPath method to a coroutine…
What I did was copy the FindPath method and make modifications from there.

FindPathAsync() 
    private IEnumerator FindPathAsync(GridPosition startGridPosition, GridPosition endGridPosition, System.Action<List<GridPosition>> result)
    {
        List<PathNode> openList = new List<PathNode>();
        List<PathNode> closedList = new List<PathNode>();

        PathNode startNode = gridSystem.GetGridObject(startGridPosition);
        PathNode endNode = gridSystem.GetGridObject(endGridPosition);
        openList.Add(startNode);

        for (int x = 0; x < gridSystem.GetWidth(); x++)
        {
            for (int z = 0; z < gridSystem.GetHeight(); z++)
            {
                GridPosition gridPosition = new GridPosition(x, z);
                PathNode pathNode = gridSystem.GetGridObject(gridPosition);

                pathNode.SetGCost(int.MaxValue);
                pathNode.SetHCost(0);
                pathNode.CalculateFCost();
                pathNode.ResetCameFromPathNode();
            }
        }

        startNode.SetGCost(0);
        startNode.SetHCost(CalculateDistance(startGridPosition, endGridPosition));
        startNode.CalculateFCost();

        while (openList.Count > 0)
        {
            PathNode currentNode = GetLowestFCostPathNode(openList);

            if (currentNode == endNode)
            {
                endNode.SetPathLength(endNode.GetFCost());
                result.Invoke(CalculatePath(endNode));
                yield break;
            }

            openList.Remove(currentNode);
            closedList.Add(currentNode);

            foreach (PathNode neighbourNode in GetNeighbourList(currentNode))
            {
                if (closedList.Contains(neighbourNode))
                {
                    continue;
                }

                if (!neighbourNode.IsWalkable())
                {
                    closedList.Add(neighbourNode);
                    continue;
                }

                int tentativeGCost = 
                    currentNode.GetGCost() + CalculateDistance(currentNode.GetGridPosition(), neighbourNode.GetGridPosition());

                if (tentativeGCost < neighbourNode.GetGCost())
                {
                    neighbourNode.SetCameFromPathNode(currentNode);
                    neighbourNode.SetGCost(tentativeGCost);
                    neighbourNode.SetHCost(CalculateDistance(neighbourNode.GetGridPosition(), endGridPosition));
                    neighbourNode.CalculateFCost();

                    if (!openList.Contains(neighbourNode))
                    {
                        openList.Add(neighbourNode);
                    }
                }

                yield return null;
            }
        }
        result?.Invoke(new List<GridPosition>());
    }

So let’s go over the high points of the changes: First of all is the method header…

private IEnumerator FindPathAsync(GridPosition startGridPosition, GridPosition endGridPosition, System.Action<List<GridPosition>> result)

This one is quite the mouthful. The type is an IEnumerator. This is how Unity handles coroutines, by making them an IEnumerator, with the yield return statements giving control back to the system. We have the startGridPosition and endGridPosition from the original method, plus a callback. The callback is for a delegate that accepts a List<GridPosition> as it’s only argument… Whether we find a path or don’t find a path, a List<GridPosition> will be returned by this function. Even in the event that there is no path, a List will be returned, it will just be empty.

Things actually stay pretty normal until we get to the finding of the end node. If we find the end node, then we invoke the method from the header:

            if (currentNode == endNode)
            {
                endNode.SetPathLength(endNode.GetFCost());
                result?.Invoke(CalculatePath(endNode));
                yield break;
            }

So what we’re doing is that we’re calling the specified delegate, and passing to that delegate the result of CalculatePath(endNode); This will make a bit more sense later. The yield break instruction simply exits the coroutine. We’re also storing the pathlength in the node itself so we can retrieve it if needed.

The last instruction in the foreach loop

yield return null;

tells the system to go back to what it was doing until the next frame. This has two effects…

  • It takes a bit longer to calculate all the paths, because we keep yield breaking
  • The system does not stall, appearing not to be responsive.

Now at the end of the method, if we still haven’t actually found a path to the tile, then we invoke the result with a new List<GridPosition>().

Why do we do this? So that we never had a null result. The inventor of the null once described the null as his Billion Dollar Mistake. Personally, I think he was underselling the value of the time wasted and damage done by null pointers over the years. A simple solution to avoiding null results is to return a new List of whatever result you’re looking for, and if the list is empty, then no action will be taken in a foreach loop.

Ok, so all of this was to get us to the point that we’re ready to seed our PathNodes… This is the method that is going to seed each PathNode with a path from that node to the Starting point (if it exists).

    public IEnumerator SeedAllPaths(GridPosition startPosition, System.Action callback)
    {
        
        for(int x=0;x<gridSystem.GetWidth();x++)
        for (int z = 0; z < gridSystem.GetHeight(); z++)
        {
            var currentObject = gridSystem.GetGridObject(new GridPosition(x, z));
            if(startPosition == currentObject.GetGridPosition()) 
            {
                 currentObject.SetPathToStart(new List<GridPosition>());
                 continue;
            }
            yield return FindPathAsync(startPosition, currentObject.GetGridPosition(), currentObject.SetPathToStart);
        }
        callback?.Invoke();
    }

This method will be called when the UnitActionSystem has changed characters, and will seed the map. We’ll get to the use case for this in a few moments. It works by cycling through each Pathnode on the map and creating a path to that node, storing the result in the PathNode. Whe it’s done, each Pathnode will have a list of the path to get to it, or an empty list if it isn’t reachable.
The secret sauce to this is in the yield return line:

yield return FindPathAsync(startPosition, currentObject.GetGridPosition(), currentObject.SetPathToStart);

What this does is pause execution of this coroutine until the FindPathAsync coroutine has done it’s job. Note that we’re passing it the SetPathToStart of the currentObject that we’re checking. This is what ensures that each object will have a valid List in it’s possession.

Some more methods we’ll be needing:

    public List<GridPosition> GetPath(GridPosition startPosition)
    {
        if (gridSystem.IsValidGridPosition(startPosition))
        {
            return gridSystem.GetGridObject(startPosition).PathToStart;
        }
        return new List<GridPosition>();
    }

    public bool HasPath(GridPosition endGridPosition)
    {
        return gridSystem.GetGridObject(endGridPosition).PathToStart.Count > 0;
    }

    public int GetPathLength(GridPosition endGridPosition) => gridSystem.GetGridObject(endGridPosition).GetPathLength();
#2

Now for the “How will this work, anyways?” question. We’ve got a way to find all the paths asyncronously, but how do we use this information once it’s obtained?

We’re going to start by making a change in the SetSelectedUnit() method in UnitActionSystem

      private void SetSelectedUnit(Unit unit)
    {
        selectedUnit = unit;
        StartCoroutine(SeedAllPaths(unit.GetGridPosition(), OnCalculateAllPathsComplete));

    }

    private IEnumerator SeedAllPaths(GridPosition gridPosition, System.Action callback)
    {
        while (Pathfinding.Instance == null)
        {
            yield return null;
        }
        yield return Pathfinding.Instance.SeedAllPaths(gridPosition, callback);
    }

    private void OnCalculateAllPathsComplete()
    {
        SetSelectedAction(selectedUnit.GetAction<MoveAction>());

        OnSelectedUnitChanged?.Invoke(this, EventArgs.Empty);
    }

Now what we’ve done here is delay telling the rest of the objects that the selected unit has changed until after the path has been calculated. We’ve started a coroutine, and at the end of that Coroutine, OnCalculateAllPathsComplete() will be called. Here’s the deal: While that pathfinding is running, nothing else is happening in the game, but the animations themselves will still continue running… When calculating paths without a coroutine, especially when calculating complex AI decisions, the Update and Animators aren’t running, everything is held up until all of these calculations are complete. Even worse, when we have multiple actions available, we’ll calculate the same set of paths multiple times! You may be

So we’ve handled when the player selects a unit, but we also need to handle when the AI cycles through it’s units. For that, we’ll need a bit of rebranding in our AI…
We’re going to add a Queue and a current unit, and some similar logic to what we used above to try to get some actions going:

    private Queue<Unit> enemyUnits = new Queue<Unit>();
    private Unit currentUnit = null;

    void InitEnemyUnitsQueue()
    {
        enemyUnits.Clear();
        foreach (Unit unit in UnitManager.Instance.GetEnemyUnitList())
        {
            enemyUnits.Enqueue(unit);
        }
    }
    void TryNextEnemyUnit()
    {
        if (enemyUnits.Count == 0)
        {
            state = State.WaitingForEnemyTurn;
            TurnSystem.Instance.NextTurn();
        }
        currentUnit = enemyUnits.Dequeue();
        state =  State.Busy;
        StartCoroutine(Pathfinding.Instance.SeedAllPaths(currentUnit.GetGridPosition(), CalculatePathComplete));
    }

    void CalculatePathComplete()
    {
        if (!TryTakeEnemyAIAction(currentUnit, CalculatePathComplete))
        {
            SetStateTakingTurn();
        }
    }

So what this is doing is when the Enemy is handed the turn, the queue is built from the current available units. Our Update will now call TryNextEnemyUnit() when the timer has expired, which will seed the paths and then when done seeding the path will attempt to take an action. If the action is valid, then CalculatePathComplete will run again until the unit is out of valid actions. If no action was found, then we go back to the taking turn state, which will call the next unit.

This means that our Statemachine in Update has been simplified a little:

        switch (state)
        {
            case State.WaitingForEnemyTurn:
                break;
            case State.TakingTurn:
                timer -= Time.deltaTime;
                if (timer <= 0f)
                {
                    TryNextEnemyUnit();
                }
                break;
            case State.Busy:
                break;
        }

Since the TryNextEnemyState will be handling turning over the turn when we’re out of units, we don’t need to worry about handing off to the TurnManager.

So this gets us only 2/3rds of the way there, and what’s next will probably be a bit mind blowing… because now we have to use that path information in our Actions rather than calculating path information again.

#3

We’re going to start in MoveAction:

Let’s start with something simple: The actual TakeAction method. I’ve only made one modification:

    public override void TakeAction(GridPosition gridPosition, Action onActionComplete)
    {
        //List<GridPosition> pathGridPositionList = Pathfinding.Instance.FindPath(unit.GetGridPosition(), gridPosition, out int pathLength);
        List<GridPosition> pathGridPositionList = Pathfinding.Instance.GetPath(gridPosition);
        currentPositionIndex = 0;
        positionList = new List<Vector3>();

        foreach (GridPosition pathGridPosition in pathGridPositionList)
        {
            positionList.Add(LevelGrid.Instance.GetWorldPosition(pathGridPosition));
        }

        OnStartMoving?.Invoke(this, EventArgs.Empty);

        ActionStart(onActionComplete);
    }

Since, by the time we get to TakeAction, we know that all PathNodes have a path back to the start position, and the start position must be the unit position, we only have to get the path back from the Pathfinding. The pathLength is inconsequential, we’re not using it here.

We only need a couple of minor changes in the GetValidActionPositionList as well… at the end of the method, we’re asking if there is a path from the current position to the test position. We’re also testing the length of the path (FCost). The good news that we can do this with just the end position, using the methods I added in the first post of this thread.

                if (!Pathfinding.Instance.HasPath(testGridPosition))
                {
                    continue;
                }

                int pathfindingDistanceMultiplier = 10;
                if (Pathfinding.Instance.GetPathLength(testGridPosition) > maxMoveDistance * pathfindingDistanceMultiplier)
                {
                    // Path length is too long
                    continue;
                }

Privacy & Terms