I had a challenge last week from my partner for this game project. Allow an NPC to come up with a quick way to navigate to a particular place, even if the environment around him is dynamic.
Some high-budget games use static node path meshes, which must be a final step in production for each map. A combination of theses meshes in different formats have been used in different games, and some use smoothing algorithms to make the web of node seem more natural. I wanted a different approach that didn't require a web of objects hand placed into the world.
I came up with a rotational path collection.
On a pivot, a box would rotate several degrees and create a collection of distances from the target. After the closest one is found, it adds this entity to a PathCollection, then moves the pivot to this new closer spot.
The cycle repeats itself until the radius is close enough to the target.
I used a collection of Entities to avoid storing a minimum radius, and calculated terrain slope to manage where NPCs can actually travel. Changing the rotating radius and amount of degrees for each iteration can be used to create a low-density path compared to my example.
The best part about this approach is you can store these paths in memory, removing the data as necessary.