Support for Dynamic Gaps and Ledges?

General
#1

I’m considering buying A*PP to use instead of Unity’s navmesh, but I want to find out first if the Pro version supports my use case:

My game is like Fallout 4, Rust, and Fortnite, in that it’s a First Person game in which the player can place architectural components like floors and walls to create buildings and villages.

My game has NPCs that need to pathfind through these settlements which are built at runtime by the player.

I’m using Unity’s experimental LocalNavMeshBuilder (https://github.com/Unity-Technologies/NavMeshComponents/tree/master/Assets/Examples/Scripts) to generate my navmeshes in realtime. It’s not adequate in a few ways.

Here are the problems I’m hoping A*PP can solve:

  1. I have some static geometry, and some dynamic. Unity’s system doesn’t allow me to prebake a navmesh, then combine it later with a dynamic navmesh at runtime. That’s not a total show stopper, since I can treat the whole environment as dynamic, but it’s less efficient than I’d like, and means it’ll be harder to create system where my NPCS can navigate the larger environment, instead of just within the settlement areas.

  2. When prebaking a navmesh, Unity allows me to create OffMeshLinks so that, for example, gaps can be jumped across and ledges can be dropped down from. Unity’s dynamic navmesh generation doesn’t support those being generated automatically. This is the main show stopper. I need a way to dynamically generate a navmesh based on geometry added at runtime, and have it be smart enough to automatically account for gaps and ledges, in addition to making the geometry sensibly walkable for NPCs.

Can A*PP do that?

#2

Hi

Unfortunately this package is on the same level as Unity’s system here for both 1 and 2.
Unity’s off-mesh links are a bit more developed than the ones in this package though.

As for why (1) is not done. This would require saving several orders of magnitude more data about the navmesh and I don’t think it would lead to that significant performance improvements. At best it would be 2x faster, but it’s likely lower.
This package can recalculate tiles in recast graphs in a separate thread however which does help a bit.

#3

Thanks for letting me know Aron. That’s unfortunate – from a customer perspective, I would’ve bought the pro version right away if it solved #2, just so you have data for your roadmap.

I’ll consider whether the other benefits of the package are worth it given that I’ll have to do this part manually.

Given that you know everything about the code and I know nothing, how much work would you expect the implementation of this feature to be?

#4

To be clearer about my question:

I haven’t really thought about how I’d actually generate the links, but I’m guessing it would require me to trace the edges of the navmesh, raycast from intervals along those edges downward in some kind of arc that accounts for clearance/height, detect when that raycast/arc intersected a navmash polygon below, find the closest edge of that mesh in the direction of the raycast source, and instantiate the links between the 2 ends.

Does the A*PP API provide or at least allow access to those objects such that it’s even possible to run an algorithm like that?

#5

Hi

Yes you can access all the graph data to do these kinds of operations. To create a link you could simply create a new GameObject with a NodeLink2 component (sorry about the naming of them, as I mentioned before Unity off-mesh links are slightly more developed at the moment).

See for example: https://arongranberg.com/astar/documentation/dev_4_1_6_17dee0ac/class_pathfinding_1_1_graph_utilities.php#a318d1c40455132455eb91f5fa21cb46b
and https://arongranberg.com/astar/docs/accessing-data.php