I am looking at implementing the Theta* algorithm in a 2D NavMesh. I have A* working, and I need to add a line of sight check to turn it into Theta*, this seems relatively easy in a uniform grid but a bit trickier in a NavMesh. There is excellent documentation on the funnel algorithm here, however this seems better suited to A* post smoothing.

Is there an method that would be better suited to Theta* line of sight checks in a Navmesh, or would I just need to use a modified version of the funnel algorithm?

  • \$\begingroup\$ aigamedev.com/open/tutorial/theta-star-any-angle-paths Link to Theta* \$\endgroup\$ Mar 14 '19 at 11:21
  • \$\begingroup\$ It's not clear to me how you can use the funnel algorithm to compute LineOfSight(s1,s2). Conceptually you want to follow the line from s1 to s2, determining which edges get crossed. I'm assuming all your polygons are convex, so the line intersects the boundary of each polygon at most twice. If you enter a polygon at one of those points, you can just find the other point and proceed to the next polygon. \$\endgroup\$
    – stewbasic
    Mar 15 '19 at 4:30
  • \$\begingroup\$ Apologies for the lack of specificity, I am using triangles as polygons. I suppose it would be more accurate to say that the concept of the funnel algorithm could be applied to work with Theta* . If you have a line going from Point A to Point B and want to check if Point A can go straight to point C, create a funnel for the area in the Path A-B-C, create portals between A and C, and check that the line AC goes through all portals \$\endgroup\$ Mar 15 '19 at 11:52

Conceptually you want to follow the line from s1 to 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 t1, t2 containing s1 and s2. Then the following Python pseudocode determines whether there is a line of sight:

def LineOfSight(s1,t1,s2,t2):
  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
  return True

This can probably be improved; it computes the same dot product multiple times, and probably mishandles the case where the line from s1 to s2 coincides with an edge in the NavMesh.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.