Conceptually you need to observe the road from s1 to s2, figuring out which edges get crossed. The main points rely in your illustration of the NavMesh, however let’s suppose it consists of triangles and permits the next operations:
# Returns the three vertices of the given triangle in CCW order
GetVertices(t)
# Returns the three triangles adjoining to this one.
# Ordered in order that GetAdjacentTriangles(t)[i] shares entries i and that i+1 of GetVertices(t).
# An entry could also be None if the sting is on the boundary of the navmesh.
GetAdjacentTriangles(t)
Suppose we already know the triangles t1, t2 containing s1 and s2. Then the next Python pseudocode determines whether or not there’s a line of sight:
def LineOfSight(s1,t1,s2,t2):
d = s2 - s1 # Route from s1 to s2
n = (-d.y, d.x) # Regular to line s1-s2.
ns = Dot(n, s1)
whereas t1 != t2:
dp = [Dot(n, v) for v in navmesh.GetVertices(t1)]
for i in xrange(3):
if dp[i] < 0 and dp[(i+1)%3] >= 0: break
# We should always cross the sting between vertices i and that i+1.
t1 = navmesh.GetAdjacentTriangles(t1)[i]
if t1 is None: return False # We stepped off the NavMesh
return True
This could in all probability be improved; it computes the identical dot product a number of instances, and doubtless mishandles the case the place the road from s1 to s2 coincides with an edge within the NavMesh.
