Improve slow down behaviors when AI are searching paths

[danilko]

As a player, I want the game to be smooth even when multiple units with AI are searching for paths to enable smooth game play experiences.

Currently, if there are more than 10+ units with AI, there will be periodically slow down to the game. The main root causes are for that few frame, each frame is stuck with all units' calculations.

[danilko]

One solution toward the problem is spreading the load of AI's AStar requests to more frames to reduce these very busy frame.

The mechanism will be implemented through queue and timer.

On PathFinding

1. The request of AStar will be pushed into queue (unit, start, end)
2. Timer will periodically scan (0.01s) the queue and process 1 request at a time. Once the AStar calculation is completed, push back the result back to the unit
3. This will ensure the AStar requests

On Unit AI

1. Define a path request state (NONE, WAIT, READY)
2. If current state is none, there is no pending astar request, request it and set state to WAIT
3. If current state is wait, then skip this update to wait for next update
4. If current state is ready, the request is completed, proceed to perform the unit move according to result path points

Only request points either:

1. State changes result target point changes (from PATROL to ADVANCE)
2. Travel to at least the first point (otherwise may result in same point already return and unit just stuck in traveling to first point and waste compute)

When state changes:

1. Clear the current path
2. Change path request state to none to ready for new path request

[danilko]

Update the logic to now able to do multiple logic per check

In PathFinding.cs

   [Export]
    private float UpdatePathRequestTime = 0.01f;

...
    // Test count, 3 seem to be more stable with 40 AI
    private int _processedPathRequestsPerCheck = 3;

Then the timer will trigger the queue base on above UpdatePathRequestTime

    public void AddPathRequest(Agent agent, Vector2 source, Vector2 target)
    {
        _cleanUpPathRequestList();
        // Remove any previous request from agent
        _pathRequestList.RemoveAll(pathRequest => pathRequest.Agent.GetUnitID() == agent.GetUnitID());

        PathRequest newPathRequest = new PathRequest(agent, source, target);

        _pathRequestList.Add(newPathRequest);
    }

    public void ClearRequest(String unitID)
    {
        _cleanUpPathRequestList();
        // Remove all agent request
        _pathRequestList.RemoveAll(pathRequest => pathRequest.Agent.GetUnitID() == unitID);
    }

    private void _cleanUpPathRequestList()
    {
        // Clean up invalid agents
        _pathRequestList.RemoveAll(pathRequest => pathRequest.Agent == null || !IsInstanceValid(pathRequest.Agent));
    }

    // Check queue periodically and process fixed request at a time to not slow down whole game
    private void _checkPathRequestQueue()
    {
        _cleanUpPathRequestList();

        // Processed through fixed path request count
        // This allow large amount of AI requests to be processed without "slow" down AI movement
        for (int index = 0; index < _processedPathRequestsPerCheck; index++)
        {
            if (_pathRequestList.Count > 0)
            {
                PathRequest pathRequest = _pathRequestList[0];

                _pathRequestList.RemoveAt(0);

                if (pathRequest.Agent != null && IsInstanceValid(pathRequest.Agent))
                {
                    List<Vector2> pathPoints = _getPath(pathRequest.Source, pathRequest.Target);
                    ((AIAgent)pathRequest.Agent).GetAI().SetPathResult(pathPoints);
                }
            }
            else
            {
                // No need to loop through as there is no more request
                break;
            }
        }

        // Start timer again afterward
        _updatePathRequestTimer.Start();
    }

[danilko]

Update the logic now to a time base slot: Allow computation of new path requests as long as total commutation times of all requests do not exceed the maximum per slot request

The timer will now auto kick in instead of waiting for execution to complete, so update should now be more exact at every 0.05s

In PathFinding.cs

   [Export]
    private float UpdatePathRequestTime = 0.05f;

...
    // Maximum timeframe per execution, it need to be less then the timer's slot (which is 0.05, so 50 milliseconds now above), and assume a last execution, so set at 30 to give 20 ms spare for the last execution
    private int _maximumProcessMilliseconds = 30;

Then the timer will trigger the queue base on above UpdatePathRequestTime

    public void AddPathRequest(Agent agent, Vector2 source, Vector2 target)
    {
        _cleanUpPathRequestList();
        // Remove any previous request from agent
        _pathRequestList.RemoveAll(pathRequest => pathRequest.Agent.GetUnitID() == agent.GetUnitID());

        PathRequest newPathRequest = new PathRequest(agent, source, target);

        _pathRequestList.Add(newPathRequest);
    }

    public void ClearRequest(String unitID)
    {
        _cleanUpPathRequestList();
        // Remove all agent request
        _pathRequestList.RemoveAll(pathRequest => pathRequest.Agent.GetUnitID() == unitID);
    }

    private void _cleanUpPathRequestList()
    {
        // Clean up invalid agents
        _pathRequestList.RemoveAll(pathRequest => pathRequest.Agent == null || !IsInstanceValid(pathRequest.Agent));
    }

    // Check queue periodically and process fixed request at a time to not slow down whole game
    private void _checkPathRequestQueue()
    {
        _cleanUpPathRequestList();

        // Processed through fixed path request count
        // This allow large amount of AI requests to be processed without "slow" down AI movement
        for (int index = 0; index < _processedPathRequestsPerCheck; index++)
        {
            if (_pathRequestList.Count > 0)
            {
                PathRequest pathRequest = _pathRequestList[0];

                _pathRequestList.RemoveAt(0);

                if (pathRequest.Agent != null && IsInstanceValid(pathRequest.Agent))
                {
                    List<Vector2> pathPoints = _getPath(pathRequest.Source, pathRequest.Target);
                    ((AIAgent)pathRequest.Agent).GetAI().SetPathResult(pathPoints);
                }
            }
            else
            {
                // No need to loop through as there is no more request
                break;
            }
        }

        // Start timer again afterward
        _updatePathRequestTimer.Start();
    }

Once done, following is the update for ADVANCE (moving to a particular target)

Instead of "refresh" new path on every point, will continue to use the original find path

            case State.ENGAGE:

                if (_targetAgent != null && IsInstanceValid(_targetAgent))
                {
                    // Default all state will change to weapon 0 for long range
                    if (_agent.GetCurrentWeaponIndex(Weapon.WeaponOrder.Left) != 0)
                    {
                        _agent.ChangeWeapon(0, Weapon.WeaponOrder.Left);
                    }

                    _agent.RotateToward(_targetAgent.GlobalPosition, delta);

                    // Calculate rotation
                    float angelToTargetAgent = _agent.GlobalPosition.DirectionTo(_targetAgent.GlobalPosition).Angle();

                    // Only start fire when agent is closely faced to its target agent (around Pi / 4)
                    if (Mathf.Abs(_agent.GlobalRotation - angelToTargetAgent) < 0.8f)
                    {
                        _agent.RightWeaponAction = (int)NetworkSnapshotManager.PlayerInput.InputAction.TRIGGER;
                        _agent.LeftWeaponAction = (int)NetworkSnapshotManager.PlayerInput.InputAction.TRIGGER;
                    }

                    // Chanse engaged agent closer if possible
                    if (_agent.GlobalPosition.DistanceTo(_targetAgent.GlobalPosition) > 250.0f)
                    {
                        if (_agent.GetCurrentWeaponIndex(Weapon.WeaponOrder.Left) != 0)
                        {
                            _agent.ChangeWeapon(0, Weapon.WeaponOrder.Left);
                        }

                        // If wait for Path
                        if (_pathRequestState == PathRequestState.NONE)
                        {
                            // Add a new request
                            _pathFinding.AddPathRequest(_agent, GlobalPosition, _targetAgent.GlobalPosition);
                            // Change state to request
                            _pathRequestState = PathRequestState.REQUEST;
                            break;
                        }

                        // Only should continue to process if request state is ready
                        // all other state will just contine to wait
                        if (_pathRequestState != PathRequestState.READY)
                        {
                            break;
                        }

                        if (_pathPoints.Count > 1)
                        {
                            Vector2 nextPoint = (Vector2)_pathPoints[1];
                            _agent.MoveToward(_agent.GlobalPosition.DirectionTo(nextPoint), delta);
                            _setPathLine(_pathPoints);

                            if (_agent.HasReachedPosition(nextPoint))
                            {
                                // Search for next path
                                // _resetPath();
                                _pathPoints.RemoveAt(1);
                            }
                        }
                        else
                        {
                            SetState(State.PATROL);
                            _pathLine.ClearPoints();
                        }

                    }
                    else
                    {
                        // Default all state will change to weapon 0
                        if (_agent.GetCurrentWeaponIndex(Weapon.WeaponOrder.Left) != 1)
                        {
                            _agent.ChangeWeapon(1, Weapon.WeaponOrder.Left);
                        }

                        // Random position in current position to avoid being hit
                        if (!_engagePositionSet)
                        {
                            _engagePositionOrign = _agent.GlobalPosition;
                            _engagePositionSet = true;
                        }

                        Vector2 randomPosition = new Vector2(_engagePositionOrign.x + _random.RandfRange(20.0f, -20.0f), _engagePositionOrign.y + _random.RandfRange(20.0f, -20.0f));
                        _agent.MoveToward(_agent.GlobalPosition.DirectionTo(randomPosition), delta);

                    }
                }

                break;

            case State.ADVANCE:

                if (_agent.GetCurrentWeaponIndex(Weapon.WeaponOrder.Left) != 0)
                {
                    _agent.ChangeWeapon(0, Weapon.WeaponOrder.Left);
                }

                // If wait for Path
                if (_pathRequestState == PathRequestState.NONE)
                {
                    // Add a new request
                    _pathFinding.AddPathRequest(_agent, GlobalPosition, _nextBasePosition);
                    // Change state to request
                    _pathRequestState = PathRequestState.REQUEST;
                    break;
                }

                // Only should continue to process if request state is ready
                // all other state will just contine to wait
                if (_pathRequestState != PathRequestState.READY)
                {
                    break;
                }

                if (_pathPoints.Count > 1)
                {
                    Vector2 nextPoint = (Vector2)_pathPoints[1];
                    _agent.RotateToward(nextPoint, delta);
                    _agent.MoveToward(_agent.GlobalPosition.DirectionTo(nextPoint), delta);
                    _setPathLine(_pathPoints);

                    if (_agent.HasReachedPosition(nextPoint))
                    {
                        // Search for next path
                        _resetPath();
                    }
                }
                else
                {
                    SetState(State.PATROL);
                    _pathLine.ClearPoints();
                }
                break;

[danilko]

Current performance tweak is able to stabilize around 15 - 15 (20 - 20 will be start to slow down)

[danilko]

To further improve performance, will experiment with Jump Point Search (JPS): https://harablog.wordpress.com/2011/09/07/jump-point-search/

[danilko]

But as right now, with 15 vs 15 will not crash, will consider the issue close and open a new one for future optimization