NavMesh Circuits

I use Sloan's Triangulation Algorithm to create the start of my NavMesh, then I create constrained edges by checking the intersecting lines and flipping the faces. Afterward, I locate the holes and remove the super triangle.

My A-star algorithm is fairly straightforward. The green point represents the start, and the red point represents the goal.

The algorithm begins by identifying the triangles that contain these points. It then retrieves the edges connected to the starting triangle and calculates the costs, where G represents the actual cost of the path from the start, and H is the estimated distance to the goal. The triangle with the lowest total cost (G + H) is selected, and this process repeats until the triangle containing the goal is reached.

In the image, the green triangles are the ones the algorithm has checked, while the red triangles are those it still needs to explore.

SSFA works by having two lines that follow portals or edges. It sets the point closer if it makes the funnel narrower. If the lines intersect, a new point is added, and the algorithm continues until it reaches the end. The algorithm does not account for height directly, so a point is added at every intersection of the endpoints. The height of these points is then calculated and added to the path position array. 

In the first image, you can see a normal A* algorithm with a small character width.

In the second image, I added a cost to triangles 9 and 18, where the cost to move through them is higher.

In the third image, the character's width is too large, so it navigates around obstacles. I achieved this by adding a parameter to the A* algorithm that checks the triangles the character is attempting to move through. If the edges of the triangle are not wide enough for the character, it will avoid that path.

For the SSFA, I first reduced the length of all the edges. This was done by calculating the direction vector between the two endpoints of each edge/portal, normalizing it, multiplying it by half the character's width, and adjusting the endpoints accordingly. For one of the endpoints, the direction was reversed to ensure proper alignment.