# “Line of sight” path across navigation mesh

I want to calculate the line of sight in a navigation mesh.

Consider the image below, the yellow line is the result of only A* and the red line is the result of a line of sight" algorithm that uses the yellow line as input. Now the unit can move directly without “zig-zagging”.

What is an algorithm to calculate that "line of sight"?

You are looking for a funnel algorithm.

Here you are a simple one

http://digestingduck.blogspot.com.es/2010/03/simple-stupid-funnel-algorithm.html

Basically, the algorithm identify edges as portals, and build a funnel that is tested against the vertex of the edges to check if they are inside funnel or not.

In step A the funnel is built with the start position and the portal crossed by yellow line.

In step B the next portal is checked, the upper vertex is inside the funnel, so the funnel upper line now pass though it. But the bottom vertex is out of the funnel because red line in under green line, so bottom line will not pass though it, it will continue passing through the bottom vertex of previous portal.

As you can check the funnel will be smaller, and smaller, until step F, where the funnel is not possible to be build, because red line makes a bad funnel, so the upper vertex is choosed as new start point and a new funnel would be build if the end point is not in that mesh.

Realize that this kind of algorithm lets a simple solution to the model size problem too, because you can consider that the portals are smaller by the 2xradius of your model.

There's a simple technique that can be used with generated paths using this line of sight idea. Basically, you want to walk the path, and at each node, "look back" two the node before the last to see if it's visible. If the node before last is visible, you can remove the last node (since you have line of sight between your current node and the node before last, the last node, being an intermediate node, is not required).

A Gamasutra article has the following pseudo code example:

checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next


This algorithm does as you want, where the Walkable function is essentially a line-of-sight function, but slightly improved to also include situations where the path is visible, but not walkable (i.e. pits, traps, restricted zones).

• I understand what you are saying, but I still don't know how to calculate the line of sight. Could you describe what would be in the Walkable function using a triangle navigation mesh? – Yannick Lange Mar 8 '14 at 18:21
• This answer is about grid based pathing, and is useless in a navigation mesh scenario – Blau Mar 8 '14 at 23:57