Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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"?

enter image description here

share|improve this question
up vote 4 down vote accepted

You are looking for a funnel algorithm.

Here you are a simple one

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.

enter image description here

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.

enter image description here

share|improve this answer

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).

enter image description here

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
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).

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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