Filtering of unreachable spans

[Hussein Khalil]

Hello,

I've been delving into NavMesh generation in Unreal Engine 5.2, which led me to discover Recast & Detour. I explored version 1.6.0's implementation and shared my findings.

I'd appreciate your insights on a specific topic regarding the filtering of unreachable spans.

Following the generation of the Heightfield, various filters like rcFilterLowHangingWalkableObstacles(...), rcFilterLedgeSpans(...), and rcFilterWalkableLowHeightSpans(...) are applied to identify walkable spans. However, these filters understandably do not encompass all scenarios where spans should be marked as non-walkable, as the conditions can be game-specific.

To optimize memory usage and simplify the static representation of our NavMesh in our game, we are investigating the possibility of filtering out spans in unreachable locations, such as a flat walkable roof without any stairs or ladders leading to it.

In the Recast demo, walkable spans are generated in raised spots that are technically unreachable.

At present, I haven't come up with an elegant solution within Recast to address this issue. It seems like this is something that needs to be handled at a higher level, directly within Unreal Engine, post-generation with Recast (or during generation, if it's possible to extend the generation logic with our own).

Have you encountered this problem before? If so, I would greatly appreciate any suggestions or insights you can provide, such as the use of seed points or alternative approaches.

Thank you for your time.

Best regards,
Hussein

[Gabriel Garcia]

Seed points is the play, usually the player start. Just walk the whole mesh with floodfill and remove any polys you couldn't reach.

[Hussein Khalil]

Thanks for the reply.

I assume this is run post-generation with Recast, essentially cleaning the data is produced ?

Looking at NavMeshPruneTool.cpp, there's a floodNavmesh(...) function. Haven't looked into it, but I assume I'd have to do something similar.

[Gabriel Garcia]

Ye, what you can do is, generate once, run the reachability check, re-generate but now don't include verts from polygons that were tagged to be removed, in RecastMesh.cpp::rcBuildPolyMesh you can just filter out the verts from polygons you don't want in

[Hussein Khalil]

That makes sense - so essentially, we keep in cache the contour set that was produced from the first generation, then call a modified version of rcBuildPolyMesh by passing that cached contour set, as well as a new data structure which holds the verts we want to exclude ?

My only concern is modifying a function within the lib (rcBuildPolyMesh), as it means handling possible conflicts when we upgrade to a new version of UE. Another concern is having to maintain those seed points, though I assume that was never a real issue based on your experience ?

Thanks again !

[Mikko Mononen]

Hi!

Flood filling polys is the way. I've seen different heuristics, like spawn points, player starts, smart objects, etc. Here's one good reference: https://www.gdcvault.com/play/1022274/Sunset-City-Express-Improving-the

If you have dynamic navmesh, it is not possible to prune because small islands can potentially connect important patches of data. But for static mesh it works.

I have built a custom version of dtCreateNavMeshData() for a couple of projects, which takes an existing tile as input, a list of valid polygons indices, and spits out new tile.

It's not a fun thing to write, but not very complex either. I think rcBuildPolyMesh() is too early in the process for pruning.

--mikko

--

---
You received this message because you are subscribed to the Google Groups "recastnavigation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to recastnavigati...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/recastnavigation/a8b901d9-f941-4e03-b752-db36f4f10253n%40googlegroups.com.

[Hussein Khalil]

Thank you Mikko. I've taken a quick look at the slides you shared, but I wish there was a recording of the presentation.

In your case, I assume you also run the same generation twice ? Meaning, the first time to get a list of all polygons from Recast from which you execute your custom "flood fill", which returns the list of valid polygons you pass to your custom implementation of dtCreateNavMeshData().

I'll have to dig deeper into the later stages of generation, namely polygonization, as to get a better grasp as to why rcBuildPolyMesh() might be too early.

My biggest worry is data maintenance, i.e.: management of "seed points" as the environment changes, and not being able to easily present to the users what's causing various polygons to be pruned as they regenerate the NavMesh (i.e.: missing "seed point" or misplacement)

[Gabriel Garcia]

Mikko mentioned rcBuildPolyMesh is too early correctly, but in my proposed approach you have to generate the navmesh twice, then in the second generation rcBuildPolyMesh would have the necessary information to filter out the verts.

[Gabriel Garcia]

About maintenance, in my experience it's not a big issue, player starts will always be in reasonable places and if the environment changes to a point that the player start is in a bad place, well, players will spawn in a bad place lol, so it's unlikely to happen and you would have bigger problems then

[Gabriel Garcia]

Ah, and yes, it would require a fair amount of engine code modification, so updates aren't as trivial, but recast rarely updates, specially on UE, so, I personally don't see an issue

[Mikko Mononen]

The pruning process I mentioned first created tiles as usual, did the flood fill, and stored the visited polygons per tile. Then it unpacked the tile, removed unnecessary polys and unused verts, and then build the tile back. It is not complicated, but it's not fun either. Removing the polygons is relatively simple, and then pruning the vertex list and remapping the indices and dealing with the detail mesh is the annoying thing.

--mikko

To view this discussion on the web visit https://groups.google.com/d/msgid/recastnavigation/463c085a-09f1-4d0d-bcda-69b5022e76bfn%40googlegroups.com.

[Bill Bierman]

I have done it Mikko's way in the past and had good results as well.  And yeah, it's a bit tedious writing the code to deconstruct the mesh tile and make the appropriate changes, but it works.  Incidentally, you might want to do an empirical study on how much space you stand to free up by doing this.  I ended up abandoning it because the savings was negligible, and it didn't account for reachability due to falling/jumping.

To view this discussion on the web visit https://groups.google.com/d/msgid/recastnavigation/CAPyD2naXv5RC32LmGZtNB2-bBNX-7VYzqw_oO9-tDe62MvNMPA%40mail.gmail.com.