Download

Creating an NavModifier path from an AI MoveTo

High Level Description:

  • An AI gets path to target/location. Once path is finalized, we get all the NavPolys along path within width (think of NavModifierVolumes oriented along path extending from point to point). We adjust the cost of each poly to reflect its distance from the end. Done correctly, we’d achieve a gradient displaying cost along the path (where highest cost is where the AI is currently and the lowest is at the destination).

Why?

  • An AI gets a path. Path has cost gradient. When other AI get a path, they can now account for each other’s path.

What I know (or think I do):

  • Thanks to Rama, how to get all nav polys in tiles (by index)

  • Having overridden RecastNavMesh - Solution2, I use RecastNavMesh::FindPath within custom class FindPath to get the path, which I can use to get all points along path, as well as cost of path

  • I believe a path cost is determined by virtual ENavigationQueryResult::Type CalcPathCost, which uses FNavMeshPath::GetCostFromNode and GetCostFromIndex functions that utilize TArray PathCorridor and TArray PathCorridorCost.

  • As a sort of prototype, instead of using any avoidance, I put a box collision on my characters with a high cost NavArea, which roughly gets them avoiding each other (due to using Move To Target, they seem very jittery from recalculating paths, slowing RotationSpeed in the movement component helps a bit)

  • In the custom RecastNavMesh, setting the actor tick interval to > 0 stops them from recalculating paths every frame.

What I don’t know:

  • Cost of paths is affected by NavAreas, which can be overridden. Is cost stored? Or is cost only determined by the A* algorithm, taking into account what NavArea the poly is in?

  • I believe by overriding FRecastQueryFilter I can create custom costs for paths. Could I create a float on NavPolys that I can then set to be added to cost, which reflects the cost gradient mentioned above?

  • How often are paths rebuilt? In the source code, it’s mentioned that on a move, if the target moves a certain distance path is rebuilt (there is a float used for this, don’t remember where). On a move to location, is the path only found once? The reason I ask is to figure out a way to reset the NavPolys in a path that have either been passed over, or if a new path has been found.

  • It seems they recalculate for every RecastNavMesh actor tick, depending on certain criteria

[LIST]

  • If the MoveTo is a MoveToActor, and that actor is moving, then FindPath will be called again. If it’s just a MoveToLocation, it seems to only call once

How exactly does cell size correlate to NavPolys? I understand that cells make up a tile, but are NavPolys arbitrarily sized?
Using FPathFindingResult, can I get the tile in which a pathpoint resides? That way I can get the index of the tile and get all it’s NavPolys.
[/LIST]
Please correct me on anything I’ve gotten wrong. I will update as I read more of the source.

So I’ve discovered FindPath() is called again for any moving AI if the navmesh is dynamically modified, regardless of which tile is modified.

What I’d like to be able to do then is create an interval for calling FindPath, which will clean any previous path. Perhaps only allow it to be called when a new AI calls FindPath, though only once more otherwise it’d be an endless loop.

The other problem is that while I can get access to the AI controller, it does require a cast. And I can’t create any variables on a custom recastnavmesh since FindPath is static.

Hopefully Mr. Mieszko hears my plea for help
So, currently what I do is in FindPath, I get all path points and add them to a TMap, using their CustomLinkID as the key and a NavModifier custom class (which is essentially just a NavModifierVolume) as the value.
I have a NavModifier spawning in between each current + next pathpoint successfully, using the CustomLinkID of the current pathpoint as the key to the TMap.
[SPOILER]




void AAnvilGameModeBase::SpawnNavPointModifiers(const TArray<FNavPathPoint>& locations)
{
    for (int i = 0; i < locations.Num(); i++)
    {
        FVector location = locations*.Location;
        FVector nextLocation;

        //Check next location in array so long as it is within array
        if ((i + 1) != locations.Num())
        {
            //Get the next location on path
            nextLocation = locations[i + 1].Location;

            //Get the center of the straight line distance between the current and next path points
            FVector middlePoint = (location * 0.5f) + (nextLocation * 0.5f);

            FActorSpawnParameters SpawnInfo;

            SpawnInfo.Owner = this;

            ANavModifier_Path* navModifier = GetWorld()->SpawnActor<ANavModifier_Path>(ANavModifier_Path::StaticClass(), middlePoint, FRotator(0, 0, 0), SpawnInfo);

            if (navModifier)
            {
                navModifier->Initialize(location, nextLocation);

                //Set key to first location, since middlepoint isn't stored in Path->GetPathPoints
                TPair<uint32, AActor*> pair;
                pair.Key = locations*.CustomLinkId;
                pair.Value = navModifier;

                navPointModifiers.Add(pair);
            }
        }
    }
}


[/SPOILER]

However, when I go to remove previous path points (a move stores pathpoints of resulting path in FPathFindingQuery& Query), and I use the pathpoint.CustomLinkID to check if the TMap contains it, only the first pathpoint is said to be in the TMap, but every other pathpoint can’t be found.

[SPOILER]



void AAnvilGameModeBase::RemoveAndDestroyNavModifiers(const TArray<FNavPathPoint> &oldLocations)
{
    UE_LOG(LogTemp, Warning, TEXT("Attempting to remove and destroy %d nav modifiers. AnvilGameModeBase::RemoveAndDestroyNavModifiers()"), oldLocations.Num());

    for (FNavPathPoint location : oldLocations)
    {
        if (navPointModifiers.Contains(location.CustomLinkId))
        {
            UE_LOG(LogTemp, Warning, TEXT("Destryoing %s. AnvilGameModeBase::RemoveAndDestroyNavModifiers()"), *navPointModifiers[location.CustomLinkId]->GetName());

            //Destroy the nav modifier
            navPointModifiers[location.CustomLinkId]->Destroy();

            navPointModifiers.Remove(location.CustomLinkId);
        }
    }
}


[/SPOILER]

I was planning to compare the memory addresses, but I’m unable to figure out how to get their address.

This is the code that executes both of those functions, from RecastNavMesh custom class

[SPOILER]




FPathFindingResult ARecastNavMesh_Battle::FindPath(const FNavAgentProperties& AgentProperties,const FPathFindingQuery& Query)
{
    FPathFindingResult Result;

    //If there is already a path the AI is traveling, then continue on that path
    if (Query.PathInstanceToFill.Get())
    {
        int num = Query.PathInstanceToFill->GetPathPoints().Num();
        UE_LOG(LogTemp, Warning, TEXT("Path instance to fill, number points: %d. RecastNavMesh_Battle::FindPath"), num);

        Result.Path = Query.PathInstanceToFill;
        Result.Result = ENavigationQueryResult::Success;
    }
    else
    {
        UE_LOG(LogTemp, Warning, TEXT("No previous path. RecastNavMesh_Battle::FindPath"));
    }

    //If AI are allowed to search for new paths
//    Originally, I would allow AI to get one path for each MoveTo (canFindPath is static). This would also allow each AI to update their path when a new AI calls MoveTo. However, this resulted in AI finding a path and then never moving.
//    if (canFindPath)
//    {
        //Get the gamemode, who will spawn and keep track of navmodifiers
        AAnvilGameModeBase* gameMode = Cast<AAnvilGameModeBase>(Query.Owner->GetWorld()->GetAuthGameMode());

        //If we had spawned a previous path
        if (Result.Path.Get() && Result.Path->GetPathPoints().Num() > 0)
        {
            //Need to remove and destroy the previous NavModifiers from the world
            //Done prior to retrieving a new path
            if (gameMode)
            {
                gameMode->RemoveAndDestroyNavModifiers(Result.Path->GetPathPoints());
            }
        }

        //Use Epic's A* algorithm to get a path
        Result = ARecastNavMesh::FindPath(AgentProperties, Query);

        if (gameMode)
        {
            gameMode->SpawnNavPointModifiers(Result.Path->GetPathPoints());
        }
        else
        {
            UE_LOG(LogTemp, Warning, TEXT("No GameMode. RecastNavMesh_Battle::FindPath"));
        }

        canFindPath = false;
//    }

    return Result;
}



[/SPOILER]

Here is an image of it in execution. Circled in red is the log of only the first navpoint being found in array, while the first 3 navpoints should be found.

So I went back to using FVector as the key instead of the uint32, and while it didn’t work previously (I must have had poor logic), it is now working as intended.

One peculiar behavior I noticed is that once my actors reach their target, FindPath() is still called even though I called StopMovement() once they reach the target. They aren’t attempting to move, only the path is being updated.

Another peculiarity is that when one actor kills the other (who destroys themselves), FindPath() is still attempting to call on the destroyed actor.

Moving on from the above post;

I overrode AIController::MoveTo as well as AIController::FindPathForMoveRequest (so I could utilize FindPathForMoveRequest mainly, I don’t change anything in MoveTo)

With FindPathForMoveRequest, I find a path like regular. Using the path points, I figure out the length of the path, then I find the middlepoint along the path. I ignore every path point before the middlepoint then I move the location of the first path point after the middlepoint to the middlepoint. I then remove the last two path points of the path.

The idea is that I will find a middle point of the path and move the target AI and targeting AI to that middle point, thereby not needing MoveToActor, as well as utilizing the pathmodifier system I created above to respect other AI paths.

The problem:

Even with the updated path and goal location, the AI who found the path still moves towards the original location and not the middlepoint. I checked PathResult.Path->GetGoalLocation() and it is the updated location. Still digging into it, but any devs with intimate knowledge of the nav system that can help?

Here are my overloaded functions. You can see that after finding the path, MoveTo calls RequestMove(MoveRequest, Path) (which I know is successful as I checked the validity)

AAIController_Base::MoveToTarget
[SPOILER]




FPathFollowingRequestResult AAIController_Base::MoveToTarget(const FAIMoveRequest & MoveRequest, FNavPathSharedPtr * OutPath)
{

    // Only overriden to provide pathing logic specific to custom moving to target
    // is not the override of MoveTo, therefore not the entry point of all moves
    // rather than build a path directly to target, the series of functions used here get a path from caller to target, then find the middle point, which they will path to

    SCOPE_CYCLE_COUNTER(STAT_MoveToTarget);
//    UE_VLOG(this, LogAIControllerBase, Log, TEXT("MoveTo: %s"), *MoveRequest.ToString());

    FPathFollowingRequestResult ResultData;
    ResultData.Code = EPathFollowingRequestResult::Failed;

    if (MoveRequest.IsValid() == false)
    {
//        UE_VLOG(this, LogAINavigation, Error, TEXT("MoveTo request failed due MoveRequest not being valid. Most probably desireg Goal Actor not longer exists"), *MoveRequest.ToString());
        return ResultData;
    }

    if (GetPathFollowingComponent() == nullptr)
    {
//        UE_VLOG(this, LogAINavigation, Error, TEXT("MoveTo request failed due missing PathFollowingComponent"));
        return ResultData;
    }

    ensure(MoveRequest.GetNavigationFilter() || !DefaultNavigationFilterClass);

    bool bCanRequestMove = true;
    bool bAlreadyAtGoal = false;

    //this will never be a move to actor request

    if (MoveRequest.GetGoalLocation().ContainsNaN() || FAISystem::IsValidLocation(MoveRequest.GetGoalLocation()) == false)
    {
//            UE_VLOG(this, LogAINavigation, Error, TEXT("AAIController::MoveTo: Destination is not valid! Goal(%s)"), TEXT_AI_LOCATION(MoveRequest.GetGoalLocation()));
        bCanRequestMove = false;
    }

    // fail if projection to navigation is required but it failed
    if (bCanRequestMove && MoveRequest.IsProjectingGoal())
    {
        UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
        const FNavAgentProperties& AgentProps = GetNavAgentPropertiesRef();
        FNavLocation ProjectedLocation;

        if (NavSys && !NavSys->ProjectPointToNavigation(MoveRequest.GetGoalLocation(), ProjectedLocation, INVALID_NAVEXTENT, &AgentProps))
        {
//                UE_VLOG_LOCATION(this, LogAINavigation, Error, MoveRequest.GetGoalLocation(), 30.f, FColor::Red, TEXT("AAIController::MoveTo failed to project destination location to navmesh"));
            bCanRequestMove = false;
        }

        MoveRequest.UpdateGoalLocation(ProjectedLocation.Location);
    }

    bAlreadyAtGoal = bCanRequestMove && GetPathFollowingComponent()->HasReached(MoveRequest);


    if (bAlreadyAtGoal)
    {
//        UE_VLOG(this, LogAINavigation, Log, TEXT("MoveTo: already at goal!"));
        ResultData.MoveId = GetPathFollowingComponent()->RequestMoveWithImmediateFinish(EPathFollowingResult::Success);
        ResultData.Code = EPathFollowingRequestResult::AlreadyAtGoal;
    }
    else if (bCanRequestMove)
    {
        FPathFindingQuery PFQuery;

        const bool bValidQuery = BuildPathfindingQuery(MoveRequest, PFQuery);
        if (bValidQuery)
        {
            FNavPathSharedPtr Path;
            FindPathForMoveRequestToTarget(MoveRequest, PFQuery, Path);

            const FAIRequestID RequestID = Path.IsValid() ? RequestMove(MoveRequest, Path) : FAIRequestID::InvalidRequest;
            UE_LOG(LogTemp, Log, TEXT("Path length is %d. AIController_Base::MoveToTarget()"), Path->GetPathPoints().Num());
            if (RequestID.IsValid())
            {
                bAllowStrafe = MoveRequest.CanStrafe();
                ResultData.MoveId = RequestID;
                ResultData.Code = EPathFollowingRequestResult::RequestSuccessful;

                if (OutPath)
                {
                    *OutPath = Path;
                }
            }
        }
    }

    if (ResultData.Code == EPathFollowingRequestResult::Failed)
    {
        ResultData.MoveId = GetPathFollowingComponent()->RequestMoveWithImmediateFinish(EPathFollowingResult::Invalid);
    }

    return ResultData;
}


[/SPOILER]

AAIController_Base::FindPathForMoveRequestToTarget
[SPOILER]




void AAIController_Base::FindPathForMoveRequestToTarget(const FAIMoveRequest & MoveRequest, FPathFindingQuery & Query, FNavPathSharedPtr & OutPath) const
{
    SCOPE_CYCLE_COUNTER(STAT_MoveToTarget);

    UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
    if (NavSys)
    {
        FPathFindingResult PathResult = NavSys->FindPathSync(Query);
        if (PathResult.Result != ENavigationQueryResult::Error)
        {
            if (PathResult.IsSuccessful() && PathResult.Path.IsValid())
            {

                PathResult.Path->EnableRecalculationOnInvalidation(true);

                /*
                    Get total length of path
                        get half length

                    pathLength
                    add distance from first navpoint to second navpoint
                        if less than half length
                            add to pathLength
                            continue
                        else
                            distanceLeft = halfLength - pathLength

                            add distanceLeft to previous navpoint location
                            set location of next navpoint at that location
                            destroy all other points

                */

                float pathLength = 0.0f;

                //Get the total length of the resulting path
                for (int i = 0; i < PathResult.Path->GetPathPoints().Num(); i++)
                {
                    FVector location = PathResult.Path->GetPathPoints()*.Location;
                    FVector nextLocation;

                    //Get distance to next location in array so long as it is within array
                    if ((i + 1) != PathResult.Path->GetPathPoints().Num())
                    {
                        //Get the next location on path
                        nextLocation = PathResult.Path->GetPathPoints()[i + 1].Location;

                        //increase the total length of the path
                        pathLength += FMath::Abs(FVector::Distance(location, nextLocation));
                    }
                }
                UE_LOG(LogAIControllerBase, Log, TEXT("PathLength is %f, with %d path points. AAIController_Base::FindPathforMoveRequestToTarget()"), pathLength, PathResult.Path->GetPathPoints().Num());

                //The distance along path we have calculated so far
                float distance = 0.0f;
                int i = 0;

                //Now to go from point to point along path until we reach the middle of the path
                for (i; i < PathResult.Path->GetPathPoints().Num(); i++)
                {
//                    UE_LOG(LogAIControllerBase, Log, TEXT("Checking Points. AAIController_Base::FindPathforMoveRequestToTarget()"));
                    FVector location = PathResult.Path->GetPathPoints()*.Location;
                    FVector nextLocation;

                    //Get distance to next location in array so long as it is within array
                    if ((i + 1) != PathResult.Path->GetPathPoints().Num())
                    {
                        //Get the next location on path
                        nextLocation = PathResult.Path->GetPathPoints()[i + 1].Location;

                        //increase the distance checked along path
                        float nextPointDistance = FMath::Abs(FVector::Distance(location, nextLocation));
                        distance += nextPointDistance;

//                        UE_LOG(LogAIControllerBase, Log, TEXT("Distance from %d to %d is %f, total distance covered is %f. AAIController_Base::FindPathforMoveRequestToTarget()"), i, i + 1, nextPointDistance, distance);

                        //if from the current point to the next point is past the middle point of the path
                        if (distance >= (pathLength / 2))
                        {
                            //How much does the distance go past the half length of the path?
                            float distancePastMiddle = distance - (pathLength / 2);

                            //Using the difference above, find out how much will be traveled from current point to next point
                            float percentageOfDistance = FMath::Abs(distancePastMiddle / FVector::Distance(location, nextLocation));

                            /*
                              Finding a point along a line a certain distance away from another point!
                              https://math.stackexchange.com/questions/175896/finding-a-point-along-a-line-a-certain-distance-away-from-another-point/175906

                              solving for FVector( a, b) 
                              currLocation is FVector(c,d)
                              NextLocation is FVector(e,f)

                              p = percentage

                              a = (1-p)c + pe
                              b = (1-p)d + pf
                            */

                            FVector point;
                            point.X = ((1 - percentageOfDistance) * location.X) + (percentageOfDistance * nextLocation.X);
                            point.Y = ((1 - percentageOfDistance) * location.Y) + (percentageOfDistance * nextLocation.Y);
                            point.Z = 0;

                            //Set the location of the next point to the middle point of the total path
                            PathResult.Path->GetPathPoints()[i + 1].Location = point;

                            //Set battlepoint of AI for manager to pass on to target
                            AI->BattlePoint = point;

                            UE_LOG(LogAIControllerBase, Log, TEXT("Current Location: %s; Next Location: %s; Percentage of distance: %f; Middle Point: %s, last index in path is %d. AAIController_Base::FindPathforMoveRequestToTarget()"), *location.ToString(), *nextLocation.ToString(), percentageOfDistance, *point.ToString(), (i + 1));

                            break;
                        }
                    }
                }


                //Now remove all other points in path
                int num = PathResult.Path->GetPathPoints().Num();

                //Remove pathpoints from last index in array down to the last index used + 1
                for (int d = num - 1; d > i + 1; d--)
                {
                    PathResult.Path->GetPathPoints().RemoveAt(d);
//                    UE_LOG(LogAIControllerBase, Log, TEXT("Removing at %d, last index is %d. AAIController_Base::FindPathforMoveRequestToTarget()"), d, num - 1);
                }

//                OutPath = FNavigationPath(*PathResult.Path.Get());

                OutPath = PathResult.Path;
                UE_LOG(LogAIControllerBase, Log, TEXT("OutPath length is %d, location of goal: %s. AAIController_Base::FindPathforMoveRequestToTarget()"), OutPath.Get() ? OutPath.Get()->GetPathPoints().Num() : 0, *PathResult.Path->GetGoalLocation().ToString());
            }
        }
        else
        {
/*            UE_VLOG(this, LogAINavigation, Error, TEXT("Trying to find path to %s resulted in Error")
                , MoveRequest.IsMoveToActorRequest() ? *GetNameSafe(MoveRequest.GetGoalActor()) : *MoveRequest.GetGoalLocation().ToString());
            UE_VLOG_SEGMENT(this, LogAINavigation, Error, GetPawn() ? GetPawn()->GetActorLocation() : FAISystem::InvalidLocation
                , MoveRequest.GetGoalLocation(), FColor::Red, TEXT("Failed move to %s"), *GetNameSafe(MoveRequest.GetGoalActor()));
*/        }
    }
}



[/SPOILER]

I found what’s happening.

The AI calls a move to the updated location (middlepoint of the path), but a PathEvent::UpdateDueToNavigationChanged occurs shortly afterwards and the AI reverts to their original goal.

Finally fixed the problem.

I was updating the query and moverequest, but the querydata of the OutPath wasn’t being updated.
By setting OutPath->SetQueryData to the updated query data the end goal is now the middle point I specify.