Conceptually you want to follow the line from
s2, determining which edges get crossed. The details depend on your representation of the NavMesh, but let's suppose it consists of triangles and allows the following operations:
# Returns the three vertices of the given triangle in CCW order
# Returns the three triangles adjacent to this one.
# Ordered so that GetAdjacentTriangles(t)[i] shares entries i and i+1 of GetVertices(t).
# An entry may be None if the edge is on the boundary of the navmesh.
Suppose we already know the triangles
s2. Then the following
Python pseudocode determines whether there is a line of sight:
d = s2 - s1 # Direction from s1 to s2
n = (-d.y, d.x) # Normal to line s1-s2.
ns = Dot(n, s1)
while 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 cross the edge between vertices i and i+1.
t1 = navmesh.GetAdjacentTriangles(t1)[i]
if t1 is None: return False # We stepped off the NavMesh
This can probably be improved; it computes the same dot product multiple times, and probably mishandles the case where the line from
s2 coincides with an edge in the NavMesh.