This is currently in progress as a replacement for the current SpAI system

The Idea of remaking the current node graph system to a nav system is to reduce pathing time over long distances. Because the system allows movement in many directions the total path calculation time can increase drastically over long distances.

Delaunay triangulation

The main idea with this triangulation is that no other point would lie within the triangle circumcircle.

Using mesh data I did ray casts between the triangle points and created shared points on collision. Each point would be stored inside the meshes. This allowed me to single out a set of points to triangulate against. Per point array I constructed random triangles. With each triangle I created their circumcircle and checked if any of the other points where inside this circle. If the point was within the circle the triangle could not exist.

One problem that occurred with this algorithm was quadruples, this happens when 4 set of points would always return false when checking.

To know which set makes a quadruple I checked the angle between the nodes and if the angles are 90* then it was a quadruple. I stored a reference to these nodes in a list to prevent duplication when dividing the quad into triangles.

Connecting triangles

For navigation along the triangles I need to connect each triangle to a neighbor triangle, I incorporate the idea I had before with connecting triangles. I make an array of the lines. Each line will be used twice, both times by a different triangle.

Each time if I wanted to create an existing line I could set the neighbor triangle reference using the information stored in the already existing line

Now I have my mesh connected and it’s ready to be used in path finding, to find which triangle the Actor inside I do a ray trace downwards to find the mesh. Now I can single out a set of triangles that belong to that mesh only and check for ray/line – triangle intersection to find the right tringle the player is at.

Pathing

With the Triangles combined and knowing who is at which triangle I could apply navigation. To find the path I would use the midpoint of the triangles and project each point onto the line to the next neighbor to find the shortest path. See the black lines in fig finding a path from red to green.

After I got the triangle path I use the actor (brown) position to get the closest point to the neighbor line and walk this way to my destination.

This would be the minimum idea of having a path. To extend on this I could do the following:

• The AI has a bound and I will subtract this from the lines creating new shorter lines (light brown) this way the AI does not clip into objects and it allows a smooth avoidance
• Use an offset angle towards the target line to create some path differentiation. (blue lines)

This would make the AI utilize the walkable area (dark brown) some more

Height fields

With the use of a height field I can make the AI walk on the right surfaces, adding the feature where the AI would not be able to pass under an object via the floor surface but it could when going sideways. As seen in the figure below the AI would have enough room using the red surface but it does on the green, this would set the path along the surface and would allow the AI to still move beneath the object that way.