path discovering – Line of Sight Verify Theta* Algorithm

Conceptually you wish to comply with the road from s1 to s2, figuring out which edges get crossed. The small print 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 # Path 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 must 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 may in all probability be improved; it computes the identical dot product a number of occasions, and doubtless mishandles the case the place the road from s1 to s2 coincides with an edge within the NavMesh.