Navigation Mesh

Adding Constraints

This next step proved to be the most difficult step for me during this project, which I talk about in more detail below. There are many ways you could handle this step all with their own challenges, but I decided to follow the more straightforward approach of completing a series of line intersection tests. I achieved this by breaking down each obstacle into edges and each triangle into edges, then checking the two sets of edges against each other to see if an overlap occurs. This check is completed by doing a series of cross product checks. For triangle edge T1 to T2 and for obstacle edge O1 to O2, I check:

A. (O2-O1) Cross (T1- O1)

B. (O2-O1) Cross (T2 - O1)

C. (T2-T1) Cross (O1 - T2)

D. (T2-T1) Cross (O2 - T2)

If there is an overlap, we add the triangle points to a list. Once I have checked all triangles, I then determine which side of the constraint edge each point falls on and create two corresponding lists that contain the respective points. Then all these points are triangulated using the already created Delaunay triangulation function and add them to our triangle stack.

Turning it into a Navigation Mesh

My next hurdle was to figure out how this mesh can be used for navigation by our agents. In previous projects, I used node graphs as a way to determine the navigable areas for the agent and realised that this was something I can also use here. I constructed the node graph using the generated triangles, where the center point of each triangle will become a node in the graph. From here, I simply connected each node to the adjacent triangles of each edge, resulting in a graph structure that the agent can then move around using the node connections. 

Another notable challenge was correctly identifying which lines were truly overlapping a constraint edge. Originally when completing the cross product checks (mentioned above) I wasn't including any results equal to 0, meaning any lines passing through the vertex of a constraint edge weren't being detected as an overlap.

I found out quickly that changing the conditional check from  “A x B < 0” to “A x B <= 0” wasn’t enough to solve this issue, as some lines connected to the edge of a constraint would classify as an overlap despite that not being the case. So I added in a simple check to see if the line was connected to either end of the constraint, if so then move on to the next line. 

But after some stress testing, I was still having incorrect overlaps being detected. I found that line segments that fall on the same axis of the constraint edge were also being detected as an overlap. To address this, one final check was completed to see if the two points of the line fell on opposite sides of the constraint line. This was done in the form of two cross products; One from the first point of the constraint edge to each point of the overlapping line, and one from the second point of the constraint edge to each point of the overlapping line. If both return 0, then the line is collinear with the constraint edge and should not be considered an overlap. 

Moving Obstacles

Moving obstacles is another feature I’d like to implement. When researching navigation meshes before starting this process, I read an article(2) which showcased how the functionality of updating a mesh to allow for moving obstacles would work, and this was something that had stuck with me throughout this project. Isolating and retriangulating the area which the obstacle affects seems straightforward at first, until you experience the number of edge cases it introduces. For my first attempt at this project, I did begin the process of having a dynamically updating mesh, but quickly scrapped that until I was able to solidify the base constraint solving first with hopes to return to the idea of moving obstacles. 

Half Edge Mesh

This data structure could have solved a number of issues I had throughout this project, but was only something I was introduced to at the later stages of the project. This would help to easily navigate the triangles when searching for neighbours and adjacent triangles, which notably was something I found challenging. Introducing this data structure can assist with optimisation, though usually meshes are baked once. More so when looking to implement moving obstacles, this will significantly improve performance when having to retriangulate the areas during runtime.