koobas.hobune.stream
Making my own navmesh
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?
Do you really mean a Nav$$anonymous$$esh, which is generated by dividing the empty space using polygons? Or do you want your way points to be navigable points on a network of points?
I'm not entirely sure what a Navmesh actually is, my understanding of it was just a collection of points generated from a mesh. I'm looking to create paths without manually setting up node graphs.
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
This is a good approach. Will the raycasting be fast enough to do at runtime or will that require a separate thread?
Well I do it at level startup and then I do different things for dynamic obstacle avoidance - but presu$$anonymous$$g that you have the initial setup then yes, it should be fine.
Link to archived Unity Gems Article site: https://web.archive.org/web/20140223101216/http://unitygems.com/astar-1-journeys-start-single-step/
