Find the point on navmesh closest to some FVector (not on navmesh)?

Development Programming & Scripting
1

I’m building a world where AI controlled characters navigate to various locations, usually another Actor, and I ran into the issue where the goal Actor’s location is occasionally not on the NavMesh. This is affecting my call to UNavigationSystem::SimpleMoveToActor() and UNavigationSystem::SimpleMoveToLocation().

How can I calculate a new FVector, one located on the navmesh which I can supply to SimpleMoveToLocation, so that my characters can move to the closest navigable point?

2

That looked promising but it doesn’t seem to “project” a point on to the NavMesh in the (x,y) plane. It seems to project a point in the sky onto the ground (z axis) just fine, but I need to be able to project a point completely out of bounds (but on the same plane) back into bounds. Here’s how I was using it:

FVector newGoalVector = UNavigationSystem::ProjectPointToNavigation(goalActor, goalActor->GetActorLocation());

Internally, it looks like this particular call was assigning an INVALID_NAVEXTENT value to Extent. No joy. Then I tried:

UNavigationComponent* PFindComp = nullptr;
UPathFollowingComponent* PFollowComp = nullptr;
AActor* goal = citizen ? container->TargetGoal : nullptr;   // set goal.  Never null
CitizenController->InitNavigationControl(PFindComp, PFollowComp);
FVector Point = goal->GetActorLocation();
FNavLocation ProjectedPoint(Point);
UNavigationSystem* NavSys = UNavigationSystem::GetCurrent(GEngine->GetWorldFromContextObject(goal));
NavSys->ProjectPointToNavigation(Point, ProjectedPoint, PFindComp->GetQueryExtent() , PFindComp->GetNavData(), PFindComp->GetStoredQueryFilter());

Same thing… Still doesn’t project the way I need it to. I can’t find a lot of documentation on Extent (or these functions or how to use them). Any further advice?

3

Were you able to resolve this? I’d like to be able to find the nearest point on a nav mesh from a point that is off the nav mesh - after determining that it is off the nav mesh.

thanks

4

It’s sad that docs are so bad on that topic and there is no proper answer. Anyway to figure it out I’ve looked at the source of GetRandomPointInNavigableRadius - and basically what I think would be the best approach is to get all NavPolys in are with GetPolysInBox method and then you can iterate on those Polys and find closest points.

1 Like
5

Can’t figure out how to use Project Point To Navigation either. Doesn’t do what I thought and no docs on it.

1 Like
6

I think Project Point To Navigation is just a simple node to basically do a trace to the navmesh and then offset the target point onto the navmesh if it’s not there already. Its used for minor adjustments and for detecting if the target location is or is not on the navmesh.

So if your AI is somehow moved off the Navmesh (let’s say thrown) then you could get the actor location of your AI, ProjectPointToNavigation, then from the Return value, plug it into a branch and from False you can run some extra code to get the nearest navigable location and make whatever adjustments necessary to get your character over there (like teleport them or Lerp them onto it). For example, you can use the GetRandomPointInNavigableRadius with a high radius value to grab a point that IS on the NavMesh and then lerp the actor there.

The issue is that RandomPointInNavigableRadius won’t return the nearest point, just one at random, so if you need the nearest point, you either have to set your radius to be small and hope that your character isn’t too far off, or do a bunch of checks, store them in an array and then figure out which one is closest to their current location with by getting the Vector of the point and the vector of your character and the subtracting the two points to see what the new length is. Basically, it’s a lot of extra work and there doesn’t seem to be an out-of-the-box node to get the nearest nav point.

7

Project Point to Navigation works fine.

				UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
				const FNavAgentProperties& AgentProps = Controller->GetNavAgentPropertiesRef();
				if (NavSys != nullptr)
				{
					FNavLocation ProjectedLocation;
					NavSys->ProjectPointToNavigation(Event.Location, ProjectedLocation, FVector(500.0f, 500.0f, 300.0f), &AgentProps);
					NearestMovableLocation = ProjectedLocation.Location;
				}

Note that the larger the radius you give it, the more impactful this call will be on CPU.

It’s a good idea to build your levels so that you don’t need to use this with a huge radius. 500x500x300 I would think should be more th an enough for most anything.

1 Like
8

I thought Project Point to Navigation was for ensuring that a target location is in fact on the navmesh. As far as I know, that’s not going to help in the situation where your AI is outside of the navmesh and you need to find the nearest location to move them back over there.
If it does do this, I’ll laugh because I just spent a good hour or so designing my own way to do exactly this and it seems pretty efficient too :slight_smile:

2 Likes
9

I’m not sure what else it could possibly do.

You give it a point anywhere in 3d space, and a 3d extent, and it asks Recast for the nearest poly to that point that is within that extent.

It does look like it doesn’t narrow it down to the nearest possible point, only the nearest poly, but that shouldn’t be a distinction that matters much to most, I would expect, as usually the polys are pretty small. I may also be wrong about that, because I’m not very adept at reading Recast code.

10

Great solution!

11

Looking at GetRandomReachablePointInRadius as an example, this should be the best way to do it I think:

FVector AAI_Controller_Human::GetClosestLocationOnNavMesh(const FVector Point)
{
	if (AGame::Instance() == nullptr)
		return FVector::Zero();

	if (ANavigation::Instance()->RecastMesh == nullptr)
		return FVector::Zero();
	
	//UNavigationSystemV1* Nav = UNavigationSystemV1::GetCurrent(GetWorld());

	const UE::Math::TVector4<double> a = UE::Math::TVector4<double>(Point.X - 1000, Point.Y - 1000, Point.Z - 1000, 0);
	const UE::Math::TVector4<double> b = UE::Math::TVector4<double>(Point.X + 1000, Point.Y + 1000, Point.Z + 1000, 0);
	const FBox Box = FBox(a, b);

	TArray<FNavPoly> Polies;
	ANavigation::Instance()->RecastMesh->GetPolysInBox(Box, Polies);

	
	float ClosestLength	= std::numeric_limits<double>::max();
	FVector ClosestPoint = FVector::Zero();
	
	for (int i = 0; i < Polies.Num(); i++)
	{
		FVector PointOnPoly;
		ANavigation::Instance()->RecastMesh->GetClosestPointOnPoly(Polies[i].Ref, Point, PointOnPoly);
		
		const float Length = (PointOnPoly - Point).SquaredLength();
		if (Length < ClosestLength)
		{
			ClosestLength	= Length;
			ClosestPoint	= PointOnPoly;
		}
	}

	return ClosestPoint;
}
2 Likes
13

@avol What ANavigation? Is this some custom type you have locally? I can’t find it anywhere in the docs or source code.

14

Yes, this is was a temp class. I rebuilt it to be bit more usable since then:

//NavigationQuery.h
#pragma once

class ARecastNavMesh;

class FNavigationQuery
{
public:
static bool GetClosestLocationOnNavMesh(const UObject* Context, const FVector& Point, FVector& ClosestLocation, const FVector& Extents = FVector(2000, 2000, 2000));
static ARecastNavMesh* GetRecastNavMesh(UWorld* World);
};

//NavigationQuery.cpp
#include "NavigationQuery.h"

#include "NavigationSystem.h"
#include "NavMesh/RecastNavMesh.h"

/**
*
* @param Context - UObject of world where recast mesh is
* @param Point
* @param ClosestLocation
* @param Extents
* @return
*/
bool FNavigationQuery::GetClosestLocationOnNavMesh(const UObject* Context, const FVector& Point, FVector& ClosestLocation, const FVector& Extents)
{
UWorld* World = GEngine->GetWorldFromContextObject(Context, EGetWorldErrorMode::ReturnNull);

#if UE_EDITOR
if (World == nullptr)
{
//Debug::Print("World Context is null while getting closest location on nav mesh!");
ClosestLocation = Point;
return false;
}
#endif

const ARecastNavMesh* NavMesh = GetRecastNavMesh(World);

#if UE_EDITOR
if (NavMesh == nullptr)
{
//Debug::Print("NavMesh is null!");
ClosestLocation = Point;
return false;
}
#endif

const FBox Box = FBox::BuildAABB(Point, Extents);
TArray<FNavPoly> Polies;
NavMesh->GetPolysInBox(Box, Polies);

double ClosestLength = std::numeric_limits<double>::max();
NavNodeRef ClosestPolyRef = INVALID_NAVNODEREF;

for (int i = 0; i < Polies.Num(); i++)
{
const double LengthToPoly = (Polies[i].Center - Point).SquaredLength();
if (LengthToPoly < ClosestLength)
{
// find edges
TArray<FNavigationPortalEdge> Edges;
NavMesh->GetPolyNeighbors(Polies[i].Ref, Edges);

bool HasConnectingNeighbour = false;
for (int c = 0; c < Edges.Num(); c++)
{
if (Edges[c].ToRef != INVALID_NAVNODEREF)
{
HasConnectingNeighbour = true;
break;
}
}

if (HasConnectingNeighbour)
{
ClosestPolyRef = Polies[i].Ref;
ClosestLength = LengthToPoly;
}
}
}

/*NavNodeRef NodeRef = INVALID_NAVNODEREF;
for (int i = 0; i < 10; i++)
{
// TODO: use this for priority, so that actor doesn't get stuck on top of buildings or areas that aren't connect to anything.
//ANavigation::Instance()->RecastMesh->GetPolyNeighbors()

NodeRef = ANavigation::Instance()->RecastMesh->FindNearestPoly(Point, FVector(500 + i * 500, 500 + i * 500, 500 + i * 500));
if (NodeRef != INVALID_NAVNODEREF)
break;

TArray<FNavigationPortalEdge> Edges;
ANavigation::Instance()->RecastMesh->GetPolyNeighbors(NodeRef, Edges);
}
*/

if (ClosestPolyRef == INVALID_NAVNODEREF)
{
//Debug::Print("Unable to find location on navmesh for point: ", Point, Context);
ClosestLocation = Point;
return false;
}

NavMesh->GetClosestPointOnPoly(ClosestPolyRef, Point, ClosestLocation);

return true;
}

/**
*
* @param World
* @return
*/
ARecastNavMesh* FNavigationQuery::GetRecastNavMesh(UWorld* World)
{
UNavigationSystemV1* NavSystem = UNavigationSystemV1::GetNavigationSystem(World);
ARecastNavMesh* RecastMesh = Cast<ARecastNavMesh>(NavSystem->GetDefaultNavDataInstance(FNavigationSystem::ECreateIfEmpty::DontCreate));
return RecastMesh;
}

1 Like
15

Thanks!