UE: NPC navigation through destructible geometry

The Problem

Our game Minermancers involves a handful of silly wizards going mining together. They dig through rock to get to minerals, and that has its own challenges for navmesh updates, but until recently the standard UE navmesh facilities worked fine.

However, a tricky problem I had recently is: what if I want NPCs to dig through rock to get to where they need to go, if there isn’t a good open path already? The walls have to be solid for collision, but the NPCs have to know that some content can be navigated through as a last resort.

Our levels are arbitrary caves which change as they’re excavated, so placing explicit dig points (e.g. through Navigation Links) wasn’t the answer. Nav Modifier Components also weren’t of any use, because they can only mark otherwise open areas as higher cost than normal, they can’t override solid geometry to be navigable in certain circumstances. What we needed was solid geometry that NPCs would bounce off in physics terms, but which could decide to try to excavate and navigate through if it was the only viable option.

I couldn’t find any articles about this, the best I could find was something suggesting you turn off collision entirely and then put a nav modifier over the top to make NPCs not want to go through it. But that’s crap, what if your NPC gets knocked into that wall? They’d just go straight through. No, we needed something better than that.

The Solution

It turns out, it wasn’t actually that hard; it’s just not documented anywhere (pikachu shocked face).

INavRelevantInterface

At first I thought I’d have to do something more intrusive with the navmesh, but a bit of digging through the source code of how UE talks to Recast, the library which generates the navmesh, revealed there are a bunch of hooks you can override.

In particular, the INavRelevantInterface interface is key, particularly these two functions:

    /** If true then DoCustomNavigableGeometryExport will be called to collect navigable geometry of this component. */
	ENGINE_API virtual EHasCustomNavigableGeometry::Type HasCustomNavigableGeometry() const override;

	/** Collects custom navigable geometry of component.
	 *	@return true if regular navigable geometry exporting should be run as well
	 */
	ENGINE_API virtual bool DoCustomNavigableGeometryExport(FNavigableGeometryExport& GeomExport) const override;

UPrimitiveComponent implements these, and my map geometry is a subclass of that, so all I had to do was override them to change how my geometry was reported to Recast.

So first, I make sure that HasCustomNavigableGeometry returns EHasCustomNavigableGeometry::Yes, which means that DoCustomNavigableGeometryExport will be called get to decide whether the default colliders will be considered blocking to navigation or not. Helpfully, UPrimitiveComponent simply returns the value of its bHasCustomNavigableGeometry variable, so I just need to set that in my constructor and not override HasCustomNavigableGeometry.

    // This makes the navmesh build call my DoCustomNavigableGeometryExport function to make all the decisions
    bHasCustomNavigableGeometry = EHasCustomNavigableGeometry::Yes;

Next, I need an actual implementation of DoCustomNavigableGeometryExport. What I want is for the default collision to not be used as normal blocking geometry. Instead, while I still want actual physics collision to be blocking, for navigation purposes I want it to be considered as just a nav modifier instead. So as a last resort, NPCs will try to go through it. they won’t be able to unless they dig, of course, but they need to try to trigger that behaviour.

bool UMinerMapProcMeshComponent::DoCustomNavigableGeometryExport(
	FNavigableGeometryExport& GeomExport) const
{
    // Don't use typical colliders to generate nav mesh because we want nav to be possible through
    // this geometry, just diggable

    // The code below would generate usual collision areas, but we don't want that (that's blocked fully)
    //     GeomExport.ExportRigidBodySetup(*ProcMeshBodySetup, GetComponentTransform());

    // Instead, we add modifier areas only (these have been built elsewhere)
    GeomExport.AddNavModifiers(NavModifiers);

    // This tells the caller NOT to do its normal blocking collision navmesh setup
    return false;
}

This is really simple - we’re just telling the caller not to do the default behaviour, and instead just to add some nav modifiers. NavModifiers is a member variable, here it is in the header:

// Nav modifiers for areas
FCompositeNavModifier NavModifiers;

Setting this up is in different code simply because I rebuild my meshes & their collision in threaded code to avoid stalling the game. But, because I’ve already built collision (a series of convex hulls), I can just add that collision to the modifiers like this:

NavModifiers.CreateAreaModifiers(this, DiggableAreaClass);

Where DiggableAreaClass is just a UNavAreaBase instance specifying the cost of traversing this area. This works because my class is a UPrimitiveComponent and the default behaviour for CreateAreaModifiers is to go through the colliders (UBodySetup) and add them in turn.

The Result

This isn’t much code, why does it work? Well, it’s just that I’m using the colliders to build nav modifiers instead of exclusion areas like the default navmesh build does, while still having the colliders as solid for movement in the game. The result in navmesh debug mode is this:

The brown areas extend under all the diggable geometry, meaning that although collision won’t let NPCs through, in the event that there isn’t a cheaper navigation path, NPCs will try to move through those. The navmesh still excludes non-walkable areas, and impenetrable rock.

Actually making the NPCs dig is a bit out of scope since it starts getting deep into our specific game code, but the general principle is:

1. Once an NPC starts moving, if they have the “dig” ability, start a periodic timer to check navigation blockages
2. If an NPC stops making progress towards their goal, do some traces ahead for diggable geometry
3. If we find diggables in our way, dig them!
4. Repeat until we stop moving

Hey presto, NPCs that mine through diggable geometry!