AI Path Finding

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.