I spent a few weeks playing around with this in the past for a game I never finished, huge waste of time.
Generation:
- Assuming you’re not doing this dynamically and pre-baked the NavMeshes as I did you can either generate the NavMesh stored as an octree (generate voxel data, useful if you’re doing true 3D pathfinding e.g. caves, an NPC that swims and so forth. I tried this as well but it didn’t give me good fidelity) or through raycasting.
- However, in my case, and by the looks of your image, neither of us need true 3D raycasting. All we want is to be able to pathfind around a set of 2D surfaces - this is what we do on a daily basis as humans
- Steps for raycasting:
- With the bounds of your map, flood fill the map with raycasts downwards towards the GameObjs at some n interval step - this will return you a set of points. Each of these points can be used to create a grid, given you a set of squares - here you can also define conditions to the raycast e.g. if I touch lava (as in the image below) do not draw a point
- Now you essentially have a bunch of rectilinear polygons, so you can decompose these to get larger rectangles and reduce our shape count
- Now you have many less shapes to deal with, you can decompose these shapes into polygons (merge the rectangles that all have the slopes to get convex shapes)
- Now we have a set of polygons that are separated by height + slope - once we have this we just need to triangulate them to get a set of meshes we can navigate through
Pathfinding:
- I used the A* algo and the SSFA algorithm to string pull the resulting paths
- However, you do have a set of convex polygons (i.e. your navmeshes) so you need to account for edges that are joined with other navmeshes so that the NPC can traverse between these sets, allowing you to move above/below levels, as well as allowing you to go underneath other sections
- These edges also allow you to define conditional events e.g. when traversing from one mesh->this specific mesh at this specific edge->do ‘JUMP’
You’ll end up with something like this (shaded green/blue wedges are the resultant navmesh):
Manual placement:
- In regard to manually placing them, you could just let the user place a bunch of nodes around the map, get the winding order of these points, and triangulate the points to get a nav mesh - obviously you would need to implement a method of triangulation that could handle complex, non-convex shapes with holes.