Hi,
I want to modify the costs of the pathfinding algorithm of UE4. I’ve been looking at the source code and the costs are calculated in the DetourNavMeshQuery class. However, UE 4 doesn’t allow me to create a sublcass of DetourNavMeshQuery from File → Create new C++ class menu. I don’t know why.
My question is, Why it doesn’t let me create a subclass of DetourNavMeshQuery? And, Is there any other way to do it? Maybe modifying the original class instead of creating a subclass?
Thanks!
First issue, DetourNavMeshQuery isn’t a class, it’s just the header file that contains many classes for Detour queries. I assume though, that the class you want to subclass is dtQueryFilter - which handles path costs for Detour. The reason why it doesn’t show up in the editor, is that none of the Recast/Detour library classes are UObject classes (except for the classes that Epic Provides for UE4).
Solution #3 shows you how to subclass dtQueryFilter, but it’s probably not your best solution - unless you’re invested into implementing your own Recast/Detour solution for UE4. However, the first two solutions might be of use to you.
UE4 uses Navigation Areas to modify the cost of a path. In this case, you can subclass UNavArea and provide a DefaultCost and FixedAreaEnteringCost. For example (you can also subclass a blueprint from NavArea as well):
UCLASS()
class MYPROJECT_API UNavArea_Example : public UNavArea_Default
{
GENERATED_BODY()
public:
UNavArea_Example(const FObjectInitializer& ObjectInitializer);
};
UNavArea_Example::UNavArea_Example(const FObjectInitializer& ObjectInitializer)
: Super(ObjectInitializer)
{
DefaultCost = 2.f;
FixedAreaEnteringCost = 10.f;
}
After this, you can then place a Nav Modifier Volume in the level where you desire and set the Area Class.
Add the Navmesh module as a public dependency in your MyProject.build.cs - this will link in any of the Recast/Detour libraries to your project. Subclass ARecastNavMesh in C++ and declare the constructor. Within DefaultEngine.ini, add a section (as shown below), to tell the engine to use our Navmesh Implementation. Create a second class below that, which subclasses FRecastQueryFilter (you can use INavigationQueryFilterInterface, but if you’re extending from RecastNavmesh, there’s a lot of assumptions in the existing code that will mean a crash, i.e. casting, etc). In this second class, you can override any virtual functions to allow changes in the cost of a path. Next, declare a variable of our second class type, and define the AMyRecastNavMesh constructor. We will then set the filter implementation for the DefaultQueryFilter shared pointer in our constructor. You can see this in the following few classes:
using UnrealBuildTool;
public class MyProject : ModuleRules
{
public MyProject(TargetInfo Target)
{
PublicDependencyModuleNames.AddRange(
new string[] {
"Core",
"CoreUObject",
"Engine",
"InputCore",
"Navmesh"
}
);
PrivateDependencyModuleNames.AddRange(new string[] { });
}
}
[/Script/Engine.NavigationSystem]
+SupportedAgents=(Name="CustomNavmesh",NavigationDataClassName=/Script/MyProject.MyRecastNavMesh)
#pragma once
#include "AI/Navigation/PImplRecastNavMesh.h"
#include "AI/Navigation/RecastNavMesh.h"
#include "MyRecastNavMesh.generated.h"
class MYPROJECT_API FNavFilter_Example : public FRecastQueryFilter
{
// Override any functions from INavigationQueryFilterInterface/FRecastQueryFilter here
};
UCLASS()
class MYPROJECT_API AMyRecastNavMesh : public ARecastNavMesh
{
GENERATED_BODY()
public:
AMyRecastNavMesh(const FObjectInitializer& ObjectInitializer);
FNavFilter_Example DefaultNavFilter;
};
#include "MyProject.h"
#include "MyRecastNavMesh.h"
AMyRecastNavMesh::AMyRecastNavMesh(const FObjectInitializer& ObjectInitializer)
: Super(ObjectInitializer)
{
if (DefaultQueryFilter.IsValid())
{
DefaultQueryFilter->SetFilterImplementation(dynamic_cast<const INavigationQueryFilterInterface*>(&DefaultNavFilter));
}
}
This will mean that every path finding query by default will use this solution - unless a QueryFilter has been chosen on PathFind. If you want to define a query filter, you can take a look at URecastFilter_UseDefaultArea. For example, the Move To node in Behavior Trees allow you to specify a move filter, if none is specified it will use the default (the one we’ve defined above).
If you’re looking to make your own solution, you’re going to have to put on some pretty high boots. The default NavMesh path finding costs utilise the FRecastQueryFilter class (as mentioned above), which implements INavigationQueryFilterInterface and subclasses dtQueryFilter. As mentioned before, if you’re extending from ARecastNavmesh, your filtering will have to extend from FRecastQueryFilter - doing a search of the entire solution for this class will show you why (C style casts galore on INavigationQueryFilterInterface objects to get as a dtQueryFilter).
If you’re going to subclass dtQueryFilter, you will have to link the Navmesh module (as shown for our MyProject.build.cs above) to be able to subclass it and make sure to have that class implement INavigationQueryFilterInterface. To create the class, you can just make a new Header file and CPP file, then regenerate the project files.
Unfortuantely, you would then have to throw out ARecastNavmesh, and start implementing your own subclass of ANavigationData in the same fashion that ARecastNavmesh does - hence why this is the hardest option.
Hopefully these solutions are at least insightful or will be of some help! 
Hey, Great answer! Solution #1 really fit my needs. My goal is to create a sort of influence map. I will fill the scene with a grid of small Nav Modifier Volumes and I will update them on runtime. However, I don’t know if a lot of Nav Modifier Volumes can be an important downgrade in efficiency. Do you know it?
For this reason I am checking Solution #2. But, which virtual functions can I override to change pathfinding costs? I only see functions to add costs to Nav Areas (like SetAreaCost(uint8 AreaType, float Cost) or SetFixedAreaEnteringCost(uint8 AreaType, float Cost)).
Is this nearly the same of what we are doing in Solution #1, isn’t it?
Thank you!
Sorry about the late reply! The Nav Modifier volumes should essentially ‘bake’ the specified Area Class (via Area IDs) into the polys. However, I also expect that the volume will force extra polys to be made to clearly distinguish areas with different area classes (may need clarification on this, but it seems like a sane assumption). This would definitely have an effect on performance as there are more polys to search through, but I envision it wouldn’t be too bad - you can profile it by using the stat Navigation command in console and compare the baseline with the added volumes.
Yes, they’re similar solutions, just that Solution #2 allows you to write your own algorithm on path building. SetAreaCost is for the duration of the area and SetFixedAreaEnteringCost is for the initial cost of entering the area… imagine if those two are added, you have your total cost of traversing that area. If you’re wanting to modify path costs dynamically, you will have to write your own FindPath algorithm that queries the Detour system (like how you’ve started in your other question).
In my opinion, third approach is the best one. I’ve successfully implemented it in less than a day. Thanks
Awesome, great work man! Glad to help! 
Hey, I am trying to achieve the same thing, but I can’t get it to work and what I am doing feels wrong ^^
When I make my own ARecastNavmesh, I need to make so many new classes just to use the custom ARecastNavmesh. I don’t really want to change the engine code and right now my code is just a mess to work with… Did you change the engine to get it to work or did you use some special casting technique I am not aware off?
Could you please explain a bit how you got it to work? ^^
Thanks in advance,
Elias
No, I didn’t change the engine code. I have just overridden some classes (yes, there are many…) and of course I had to use some castings. Here is a gist with my navmesh code:
file
file
Take a look and tell me if you have any doubt. Most of the methods are equal to the unreal source code except a few like getVirtualCost.
I got it to work with your code and help!
I was searching to far I think, thank you very much!
Hey ,
thanks for sharing the source but it seems not to work.
The constructor of AMyRecastNavMesh gets called by UClass::CreateDefaultObject(). But the dtQueryFilter_Example::getVirtualCost() function gets never called when searching a path.
I’m using Unreal 4.12
Hi ,
I am sorry but I haven’t worked on this for almost two years so I am not able to help you. You have probably already try it but I suggest you to look the source code and debug step by step the construction and execution of the NavMesh and Pathfinding methods.
My apologies and good luck!
Hi ,
We have working our own version of dtQueryFilter, but we noticed that when setting the SetFilterImplementation in our ARecastNavMesh, the nav modifiers like NavArea_Obstacle (or any other custom implementation) are ignored, seems like the cost is always bypassed to be Default one. Still those marked as NavArea_Null work.
We only care about overriding the getVirtualCost, the rest of dtQueryFilter methods haven’t been modified.
Any recommendations where to debug or what other method could be missing in the implementation?
Have you previously tested this case before?
Thank you.
Not quite so hard, it turns out. I can’t share much code, but I will give a quick overview:
FMyRecastQueryFilter::FMyRecastQueryFilter(bool bIsVirtual) : FRecastQueryFilter(true)
{}
Filter.SetFilterType<FMyRecastQueryFilter>();
Super::InitializeFilter(NavData, Querier, Filter);
NOTE: getVirtualCost and passVirtualFilter will be called a LOT. Do not do heavy operations!
they have written wrapper over wrapper with inheritance , poly morphism, public, private, etc that at the end simply calls functions of dtQueryFilter .
but i managed to add my dirt on top of them
struct FMyRecastQueryFilter : public FRecastQueryFilter
{
FMyRecastQueryFilter() {}
{
this->SetIsVirtual(true);
}
virtual bool passVirtualFilter(const dtPolyRef ref, const dtMeshTile* tile, const dtPoly* poly) const override
{
//using default impl
return passInlineFilter(ref, tile, poly);
}
//dtQueryFilter.getVirtualCost
virtual dtReal getVirtualCost(const dtReal* pa, const dtReal* pb,
const dtPolyRef prevRef, const dtMeshTile* prevTile, const dtPoly* prevPoly,
const dtPolyRef curRef, const dtMeshTile* curTile, const dtPoly* curPoly,
const dtPolyRef nextRef, const dtMeshTile* nextTile, const dtPoly* nextPoly) const override
{
const FVector& PointA = *reinterpret_cast<const FVector*>(pa); // sick C programmer rejected struct :D
const FVector& PointB = *reinterpret_cast<const FVector*>(pb);
//using default impl
return getInlineCost(pa, pb,
prevRef, prevTile, prevPoly,
curRef, curTile, curPoly,
nextRef, nextTile, nextPoly);
}
};
FSharedConstNavQueryFilter QueryFilter = UNavigationQueryFilter::GetQueryFilter(*NavData, Querier, FilterClass);
TSharedRef<FNavigationQueryFilter> NewNavFillter = MakeShareable(new FNavigationQueryFilter); //lets make our own waste
NewNavFillter->SetFilterType<FMyRecastQueryFilter>();//allocates FMyRecastQueryFilter
float AreaCosts[RECAST_MAX_AREAS];
float FixedCosts[RECAST_MAX_AREAS];
QueryFilter->GetImplementation()->GetAllAreaCosts(AreaCosts, FixedCosts, RECAST_MAX_AREAS);
NewNavFillter->GetImplementation()->SetAllAreaCosts(AreaCosts, RECAST_MAX_AREAS); //copy the data back to new one
//copy other properties too ...
@UPO33 Thank you for this short tutorial, great work! I tried to implement it in my code and here are two results:
FVector start = FVector(-pa[0], -pa[2], pa[1]);
FVector end = FVector(-pb[0], -pb[2], pb[1]);
It works for me. Do you have any similiar problems with coordinates?
@PazDim
search in source code, you need to use Unreal2RecastPoint, Recast2UnrVector
Is there any way how to access to Owner controller from filter?