(2) The first step of my Nav-Mesh is checking for 'holes.' It does this by shooting raycasts to identify where the ground and air are. Then, it separates the holes.
(3) The second step is to check the edges with more detail by first identifying where the edge starts and adding a 'mouse' to follow the edge using raycasts, adding a point to a list every time it turns (4). I also remove points that form a 45-degree angle.
(5) Next, I perform line expansion by checking the points in between, getting the vector, rotating it, and adding it to the point.
(6,7) After that, I check if the lines intersect and remove any intersecting ones.
(8) Finally, I apply the Douglas-Peucker line simplification algorithm to all the points.
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.
Constrained-Delaunay Triangulation Gif
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.
The reason I made this was to more effectively store the data from my navmesh, so I’ll only be compacting integers and floats.
What I did for floats was use fixed-point with a scaling factor of 100.
I also wanted negative numbers to work, so I added 32,768 to the number. Then, I converted the result to a 16-bit binary number.
After that, I split the binary string into 8-bit segments and converted each 8-bit segment into a Base256 character.
From - 273 Characters
[(75.52, -327.68, -15.48), (-274.08, -327.68, -323.67), (-99.71, -327.68, 66.58), (41.76, -327.68, -124.55), (-202.54, -327.68, 146.19), (-162.37, -327.68, 268.98), (280.99, -327.68, -153.95), (-141.38, -327.68 -48.28), (296.48, -327.68, 248.75), (149.31, -327.68, 131.02)]
To - 60 Characters
þáAAÚŕUőAABòºNAAûCñ±AA°ºwŃAAĚb¡ôAAŊSŎĤAA¤ľ©ħAAÎkŔıAAłrě´AAĔu