Making my own navmesh

[luckruns0ut]

Hi, I was in the middle of making an a* algorithm for a project the other day and ran into the problem that I couldn’t find a way to place nodes or check if they were walkable.

I’ve already got the algorithm done so it is able to path find, however I need to somehow create a navmesh made up of nodes, and it has to work for all GameObjects, not just terrain. How should I go about doing this?

[whydoidoit]

So to make a network of points the steps I take are these:

For each point:

• Determine ground level by firing a ray downwards from the point until it hits an object in a layer I have determined is walkable
• CheckCapsule the ground aligned point to make sure it is walkable given overhead obstructions or blockage by some scenery object.
• Raycast (or sphere cast) all other points within a predefined radius at a known height above the floor (to avoid floor angle changes blocking the cast), if the raycast hits nothing then add the point to a list of connected points.
• Destroy any points that have no connections

Note that I also allow for predefined connections if necessary - each of my nav points has a bool to say whether it should raycast for connections. This allows you to configure special areas where it’s just easier to set them up.

The other way is to make a grid based nav mesh (which truly isn’t actually a nav mesh either unless you combine the cells). I describe this technique in this Unity Gems article