Auto Jump link navmesh questions

[Answers.Archive]

I’m looking to auto build jump links during navmesh generation. Ideally that will also run when the navmesh is build dynamically at runtime. I’ve been diving into the Detour Navmesh generation and here is where I’m at:

From my understanding, we generate an async task that calls GenerateTile, which calls GenerateCompressedLayers, which does the rasterization of the triangles that are fed in. If that succeeds, we do the rest of the algorithm until the regions are built, in GenerateNavigationData. After that, we start to handle offmeshlinks. Which seems to just translate the simple link object into recast offmesh link structures.

As each async task completes, we add it to the navmesh via AddGeneratedTiles. Here we have to link this finished tile to its neighbors. We also connect the offmesh links. First we base the link starts to the current tile that we are working on, then go through our neighbors and base the link end to the neighbor tile poly

So this seems fine, but I have questions:

• How does this handle links that go from tile to tile that are not neighbors? I didn’t see anything handling this case. And it sounds like I’m going to want smaller tile sizes if I have a lot of dynamic navmesh going on, which would make this worse.
• I’m guessing I want to do my generation before we start adding the links to the offmeshData structure in GenerateNavigationData. At this point, I’m going to have to do spatial queries and build my own FNavigationLinks. Doing this via physX seems like a no no with the Async tasks (I’m guessing). Or maybe there is a safe way to use physX here?
• Or should I just spin up other “GenerateJumpLink” tasks for the async task system? And add those offmesh links after. This would get around the use of physX in the recast code base. I’m assuming all the links are packed into an array and adding new elements might be a pain in the ■■■. If order doesn’t matter. I can put the new links at the end. I’m assuming I’d have to do a new alloc and a memcopy to extend that buffer. But this might be an easier option?

I’m assuming you guys would have a good intuition on how to go about this. I hope I gave enough information here about where my head is at.

Bonus Question What are segment links (FNavigationSegmentLink)?

[anonymous_user_6e7b421a]

Offmesh links to tiles other than direct neighbors are currently not supported. It’s on the list, but right now we don’t have time to work on it.

Running physx queries from async tasks should be possible. There’s a read lock on phys scene before accesing it which will slow down traces a bit, but rather won’t crash. Never tried it myself though.

As for the good place for offmesh link generation, it depends on whether you want to use intermediate recast data or not. Compact height field can provide you with preprocessed list of good places to jump from in cardinal directions, but requires reading internal data in FRecastTileGenerator::GenerateCompressedLayers (different coord space). On the other hand, hook at the end of FRecastTileGenerator::GatherGeometry allows working on game thread and safe access to uobjects if needed, but you’ll have to analyze geometry in tile bounds by yourself. Both places run before offmesh links are passed to Recast, so you’ll be able to add any new links with FRecastTileGenerator::AppendModifier call.

If physx refuses to work from async task you can scratch FRecastTileGenerator::GenerateCompressedLayers approach.

Segment links were suppose to create polys between two segments (like in: entire edge is a jump down), but they weren’t finished and got pushed back low in priority list. They are rather untested and have known issue when segment is crossing tile’s boundary. If your link generation will process geometry by tiles, they may or may not be useful - depends on how many other bugs hides there.