Download

Obtaining Points from Path using FindPathForMoveRequest

Hi all,
I’m trying to implement a function in my custom AIController that takes in a FVector location and returns the array of FVectors generated using pathfinding on the navmesh.
Here is my code:

MyPointsFromPathFunction

FindPathForMoveRequest has 3 parameters:
const FAIMoveRequest& MoveRequest
FPathFindingQuery& Query
FNavPathSharedPtr& OutPath
I do not understand the parameters for FindPathForMoveRequest well enough and would like an explanation on the following:

  1. Do I need to specify a StartLocation? or is the location of the controlled pawn taken automatically?
  2. If I need to specify a StartLocation, do I do that in the parameter Query?
    Query.StartLocation = MyStartLocation;
    Or in the QueryData?
    QueryData.StartLocation = MyStartLocation;
    NavPath->SetQueryData(QueryData);
  3. Where do I specify the EndLocation?
    In the parameter Query?
    Query.EndLocation = locationMoveTo;
    Or in QueryData?
QueryData.EndLocation = locationMoveTo;
NavPath->SetQueryData(QueryData);

Or in the MoveRequest parameter??
MoveRequest.SetGoalLocation(locationMoveTo);

As you can see, I’m quite new to C++ programming in ue4. I did look up the source to try and figure all of this out myself, however, I was not able to find any verbose explanation on what each of these parameters is for and what information I should specify.

  1. Can you please explain what each parameter in FindPathFOrMoveRequest is for, and what the minimum information is that I need to specify for these structs to get the function to behave properly?

  2. My code throws an exception when I try to access the points in the for loop. This is most probably due to my misimpression of the parameters. How would I get this function to work?

Many thanks in advance!
Best.

Two years ago I experimented with their pathfinding and creating a custom path object. I don’t have time to reread and explain anything that may be unclear, and this code is also from I was first learning to program.

Ask any questions and I’ll try to clarify anything.

I do remember some things being essential to get a custom path to work, I believe it was:

		//To ensure path isn't seen as partial
		aggressorPath->SetIsPartial(false);

		//ensure path will be seen as valid by FNavigationPath::IsValid()
		aggressorPath->MarkReady(); //IsReady must be true to begin pathing
		aggressorPath->DoneUpdating(ENavPathUpdateType::GoalMoved); //IsUpToDate must be true to begin pathing

Where aggressorPath is a FNavPathSharedPtr. I think if you don’t do those MarkReady() and DoneUpdating() then the move request will be ignored. I don’t remember what effect IsPartial() has.

Make sure you use the Visual Log, as it shows every step in an AI’s movement and is amazing for clarifying things. It was essential for me to figure it out

ARecastNavMesh_Battle::ARecastNavMesh_Battle(const FObjectInitializer& ObjectInitializer)
	:ARecastNavMesh(ObjectInitializer)
{
	FindPathImplementation = FindPath;
}

FPathFindingResult ARecastNavMesh_Battle::FindPath(const FNavAgentProperties& AgentProperties,const FPathFindingQuery& Query)
{
/*
	Need a UNavigationPath which has pathpoints and cost function
		if we get all the points in the path
			get the tiles
			get the navpoly's within those tiles

			with the nav polys, get all nav poly's within point to point by width

			based on length of path and point to point
			adjust cost of nav polys based on distance to end of path
			


	//Rama's way of getting all navpolys
	//https://forums.unrealengine.com/development-discussion/c-gameplay-programming/34485-how-to-write-custom-ue4-ai-c-pathing-code-how-to-get-all-nav-polys-for-custom-code
	/
	TArray<FNavPoly> EachPolys;

	for (int32 v = 0; v < NavMesh->GetNavMeshTilesCount(); v++)
	{

		//CHECK IS VALID FIRST OR WILL CRASH!!!
	   //     256 entries but only few are valid!
	   // using continue in case the valid polys are not stored sequentially!
		if (!TileIsValid(NavMesh, v))
		{
			continue;
		}

		NavMesh->GetPolysInTile(v, EachPolys);
	}
	

		
	Look into how findpath works
	NavigationSystem::Tick() checks for pathfindingqueries
	if there are some, call TriggerAsyncQueries
		This creates a delegate for PerformAsyncQueries
		This calls FindPath()
*/

	//RecastNavMesh::DrawDebugPathCorridor

	FPathFindingResult Result;

	//If AI are allowed to search for new paths
	//Ensure the query owner has not been destroyed first
	//canFindPath was used for finding a single path, has been replace by setting RecastNavMesh_Battle::TickInterval to > 0
	if (Query.Owner.Get() /*&& canFindPath*/)
	{
		//Use Epic's A* algorithm to get a path
		Result = ARecastNavMesh::FindPath(AgentProperties, Query);

		//If there is already a path the AI is traveling, then continue on that path
		if (Query.PathInstanceToFill.Get() && Result.Path.Get())
		{
//			UE_LOG(LogTemp, Log, TEXT("Previous Path. RecastNavMesh_Battle::FindPath"));

			if (Query.PathInstanceToFill->GetCost() <= Result.Path->GetCost())
			{
				//Use the previous path if it has a lower cost
//				UE_LOG(LogTemp, Log, TEXT("Returning previous Path. RecastNavMesh_Battle::FindPath"));
				Result.Path = Query.PathInstanceToFill;
				Result.Result = ENavigationQueryResult::Success;

				//Since we already have a path no further execution is needed
				return Result;
			}
		}
	}
	else
	{
		UE_LOG(LogTemp, Warning, TEXT("Query owner is dead, need way to remove path points. RecastNavMesh_Battle::FindPath"));
	}

	return Result;
}


void AManager_Battle::CreateBattlePathQuery(FPathFindingQuery& Query, AAI_Base& start, FVector Goal)
{
	bool bResult = false;

	UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
	const ANavigationData* NavData = (NavSys == nullptr) ? nullptr : NavSys->GetNavDataForProps(start.GetNavAgentPropertiesRef());

	if (NavData)
	{
		FVector GoalLocation = Goal;

		FSharedConstNavQueryFilter NavFilter = UNavigationQueryFilter::GetQueryFilter(*NavData, this, start.filter);

		if (start.filter.Get())
		{
//			UE_LOG(LogTemp, Log, TEXT("NavQueryFilter is %s. Manager_Battle::CreateBattlePathQuery()"), *start.filter->GetName());
		}
		Query = FPathFindingQuery(*start.GetThisAIController(), *NavData, start.GetActorLocation(), GoalLocation, NavFilter);
		Query.SetAllowPartialPaths(false);

		if (start.GetThisAIController()->GetPathFollowingComponent())
		{
			start.GetThisAIController()->GetPathFollowingComponent()->OnPathfindingQuery(Query);
		}

		bResult = true;
	}
	else
	{
//		UE_VLOG(this, LogAINavigation, Warning, TEXT("Unable to find NavigationData instance while calling AAIController::BuildPathfindingQuery"));
	}
}

FPathFindingQuery AManager_Battle::CreatePathQueryForPath(ACharacter_Base& owner, FNavPathSharedPtr& inPath)
{
	bool bResult = false;

	UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
	const ANavigationData* NavData = (NavSys == nullptr) ? nullptr : NavSys->GetNavDataForProps(owner.GetNavAgentPropertiesRef());

	if (NavData)
	{
		FPathFindingQuery Query = FPathFindingQuery(owner, *NavData, inPath->GetStartLocation(), inPath->GetGoalLocation());
		Query.SetAllowPartialPaths(false);

		bResult = true;
		return Query;
	}
	else
	{
		UE_LOG(LogBattleManager, Error, TEXT("Unable to find NavigationData. Manager_Battle::CreatPathQueryForPath()"));
		//UE_VLOG(this, LogAINavigation, Warning, TEXT("Unable to find NavigationData instance while calling AAIController::BuildPathfindingQuery"));
	}

	return FPathFindingQuery(owner, *NavData, inPath->GetStartLocation(), inPath->GetGoalLocation());;
}

ANavModifier_BattleSpot* AManager_Battle::SplitPath(const FNavPathSharedPtr& initialPath, FNavPathSharedPtr& aggressorPath, FNavPathSharedPtr& targetPath)
{
	UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
	
	if (NavSys)
	{
		aggressorPath = MakeShareable(new FNavigationPath());
		aggressorPath->SetNavigationDataUsed(initialPath->GetNavigationDataUsed());
		aggressorPath->SetTimeStamp(GetWorld()->GetTimeSeconds());

		targetPath = MakeShareable(new FNavigationPath());
		targetPath->SetNavigationDataUsed(initialPath->GetNavigationDataUsed());
		targetPath->SetTimeStamp(GetWorld()->GetTimeSeconds());

		aggressorPath->EnableRecalculationOnInvalidation(false);
		targetPath->EnableRecalculationOnInvalidation(false);

		/*
			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

		*/

		//Retrieve the total length of the path
		float pathLength = initialPath->GetLength();

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

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

				//increase the total length of the path
				pathLength += FMath::Abs(FVector::Distance(location, nextLocation));
			}
		}*/
//		UE_LOG(LogBattleManager, Log, TEXT("PathLength is %f, cost is %f, with %d path points. AAIController_Base::FindPathforMoveRequestToTarget()"), pathLength, aggressorPath->GetCost(), aggressorPath->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 < initialPath->GetPathPoints().Num(); i++)
		{
//			UE_LOG(LogBattleManager, Log, TEXT("Checking Points. AAIController_Base::FindPathforMoveRequestToTarget()"));
			FVector location = initialPath->GetPathPoints()[i].Location;
			FVector nextLocation;

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

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

				aggressorPath->GetPathPoints().Add(initialPath->GetPathPoints()[i]);

//				UE_LOG(LogBattleManager, 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);
//					UE_LOG(LogBattleManager, Log, TEXT("distancePastMiddle is %f, distance so far is %f, half of pathlength is %f, last path point index %d. AAIController_Base::FindPathforMoveRequestToTarget()"), distancePastMiddle, distance, (pathLength/2), i);

					//Using the difference above, find out how much will be traveled from current point to next point
					float percentageOfDistance = FMath::Abs(distancePastMiddle / FVector::Dist(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
					*/
					middle.X = ((1 - percentageOfDistance) * location.X) + (percentageOfDistance * nextLocation.X);
					middle.Y = ((1 - percentageOfDistance) * location.Y) + (percentageOfDistance * nextLocation.Y);
					middle.Z = 0;

					//Add an extra point to represent the end of the path
					aggressorPath->GetPathPoints().Add(initialPath->GetPathPoints()[i + 1]);

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

//					UE_LOG(LogBattleManager, Log, TEXT("AIPath: Current Location: %s; Next Location: %s; Percentage of distance: %f; Middle Point: %s, last index in path is %d. Manager_Battle::SplitPath()"), *location.ToString(), *nextLocation.ToString(), percentageOfDistance, *middle.ToString(), (i + 1));

					break;
				}
			}
		}

		//Now to remove all other points in outpath
		//Need the total num as we will remove points from end of array during iteration
		int num = initialPath->GetPathPoints().Num();

		//Remove pathpoints from last index in array down to the last index used + 1 (which is the new end of aggressorPath)
		for (int d = num - 1; d > i + 1; d--)
		{
			//Target path will be end of aggressorPath down to middle, which will provide target with a predetermined path to middle point
			targetPath->GetPathPoints().Add(initialPath->GetPathPoints()[d]);

//			aggressorPath->GetPathPoints().RemoveAt(d);
//			UE_LOG(LogBattleManager, Log, TEXT("Removing at %d, last index is %d. AAIController_Base::FindPathforMoveRequestToTarget()"), d, num - 1);
		}


		//i is the middle path point, which is not touched by the for loop since it becomes the new endpoint
		//Only needed for target path since aggressorPath already has a properly set middlePoint
//		UE_LOG(LogTemp, Log, TEXT("Index is now %d, which should be end index of aggressorPath. Manager_Battle::SplitPath()"), i)
		FNavPathPoint point = aggressorPath->GetPathPoints()[i];
		point.Location = middle;
		targetPath->GetPathPoints().Add(point);

		//To ensure path isn't seen as partial
		aggressorPath->SetIsPartial(false);
		targetPath->SetIsPartial(false);

		//ensure path will be seen as valid by FNavigationPath::IsValid()
		aggressorPath->MarkReady(); //IsReady must be true to begin pathing
		aggressorPath->DoneUpdating(ENavPathUpdateType::GoalMoved); //IsUpToDate must be true to begin pathing
		targetPath->MarkReady(); 
		targetPath->DoneUpdating(ENavPathUpdateType::GoalMoved);
//		UE_LOG(LogBattleManager, Log, TEXT("TargetPath: Location of last index is %s while middle is %s. Manager_Battle::SplitPath()"), *targetPath->GetPathPoints().Last().Location.ToString(), *middle.ToString());
		ANavModifier_BattleSpot& spot = *SpawnBattleSpot(middle);

		if (spot.GetBoxBounds().IsValid)
		{
//			UE_LOG(LogBattleManager, Log, TEXT("Box is valid, building navigation. Manager_Battle::SplitPath()"));
			NavSys->AddDirtyArea(spot.GetBoxBounds(), 1);

			GetWorld()->Exec(GetWorld(), TEXT("RebuildNavigation"));

//			NavSys->Build();
			/*
			ANavigationData* NavData = NavSys->MainNavData;
			if (NavData)
			{
				NavData->RebuildDirtyAreas(NavSys->DirtyAreas);
			}
			*/
		}
		else
		{
//			UE_LOG(LogBattleManager, Log, TEXT("Box is not valid. Manager_Battle::SplitPath()"));
		}
		FPathFindingQuery aggressorQuery; 
		aggressorQuery.EndLocation = aggressorPath->GetQueryData().EndLocation;

//		aggressorPath->SetQueryData(CreatePathQueryForPath(aggressorPath));
//		targetPath->SetQueryData(CreatePathQueryForPath(targetPath));
		//QueryData.EndLocation has not been set at this point, so will read something crazy
//		UE_LOG(LogBattleManager, Log, TEXT("AIPath length is %d, location of goal: %s. Query end location: %s. Manager_Battle::SplitPath()"), aggressorPath.Get() ? aggressorPath.Get()->GetPathPoints().Num() : 0, *aggressorPath->GetGoalLocation().ToString(), *aggressorPath->GetQueryData().EndLocation.ToString());
//		UE_LOG(LogBattleManager, Log, TEXT("TargetPath length is %d, location of goal: %s. Query end location: %s. Manager_Battle::SplitPath()"), targetPath.Get() ? targetPath.Get()->GetPathPoints().Num() : 0, *targetPath->GetGoalLocation().ToString(), *targetPath->GetQueryData().EndLocation.ToString());
	
		return &spot; 
	}

	return nullptr;
}

@FurryOstich If I’m understanding you right, this is super easy actually. The function that seems to fit your use case best is UNavigationSystemV1::FindPathToLocationSynchronously. You pass in a start location, a target location, and some extra stuff and you’ll get an object of type UNavigationPath. That one has a property called PathPoints that contains the individual locations that make up your path.

If you need more information on how to use that function, just ask.

EDIT: I might have misunderstood what you’re actually asking for, but I’ll leave my reply up since it fits the task you describe in the beginning of your post.

Hi iSpam,

Thanks for your response and code snippet!
As of now, I have solved the initial problem of finding the points, using the following code:
PointsFromPath

However, I would like to improve this function s.t. the obtained points do not cut corners as much as they do now. I will make a new post for this problem and link it here.

Best.

Here is the link to the new post: